2014-02-02
4203
Теорема Поста о полноте
Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T 0, T 1, L, S, M.
Следствие. Всякий замкнутый класс функций из Р 2, не совпадающий с Р 2 содержится, по крайней мере, в одном из замкнутых классов T 0, T 1, L, S, M.
1. Покажем, что система функций { f 1 = x 1 x 2, f 2 =0, f 3 =1, f 4 = x 1Å x 2Å x 3} полна в Р 2. Составим таблицу, которая называется критериальной:
2.
| Т 0 | Т 1 | L | M | S | |
| x 1 x 2 | + | + | - | + | - |
| + | - | + | + | - | |
| - | + | + | + | - | |
| x 1Å x 2Å x 3 | + | + | + | - | + |
| x 1 x 2 x 3 | x 1Å x 2Å x 3 |
| 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
Из таблицы видно, что какой бы класс мы ни взяли, всегда есть функция из данной системы, которая в этот класс не входит. Можно сформулировать следующее правило: для того чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце критериальной таблицы был хотя бы один «минус».
Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, { f 2, f 3, f 4}Î L, { f 1, f 3, f 4}Î T 1, { f 1, f 2, f 4}Î T 0, { f 1, f 2, f 3}Î M.
2 Мы знаем, что система { x 1| x 2} – полна в Р 2. Составим для нее критериальная таблица? x 1| x 2=
= x 1 x 2Å1.
| Т 0 | Т 1 | L | M | S | |
| x 1| x 2 | - | - | - | - | - |
3. Составим критериальную таблицу для другой полной системы функций из Р2: из Р2: {0, 1, x 1 x 2, x 1Å x 2}.
| Т 0 | Т 1 | L | M | S | |
| + | - | + | + | - | |
| - | + | + | + | - | |
| x 1 x 2 | + | + | - | + | - |
| x 1Å x 2 | + | - | + | - | - |
Согласно критериальной таблице, полной является и система {0, 1, x 1 x 2, x 1Å x 2}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где а 
равны 0, если члены х 
х 
... х 
, в полиноме отсутствуют.
4. Выясним, полна ли система 
. Составим критериальную таблицу, очевидно 
. Чтобы показать, что 
, достаточно найти одну функцию 
и 
. Возьмем 
, удовлетворяющую требуемым условиям. Если f 
S \ T 0, то f (0,..., 0) = 1, f (1,..., 1)=0, следовательно, f 
M, f T 1. Рассмотрим функцию h = x 1 x 2
x 2 x 3 x 1 x 3=1, набор ее значений (11101000), h S \ T 0, но h L. Следовательно, критериальная таблица имеет вид:
| Т 0 | Т 1 | L | M | S | |
L  T 1 | - | + | + | - | - |
| S \ T 0 | - | - | - | + | - |
и А – полная система функций.
Определение. Система функций { f 1,..., fs,...} называется базисом в Р 2,если она полна в Р 2, но любая ее подсистема не будет полной. Например, система функций { x 1& x 2, 0, 1, x 1 x 2 x 3} – базис.
