Примеры использования теоремы Поста.

1. Покажем, что система функций {f1 =x1x2, f2 =0, f3 =1, f4 = x1Åx2Åx3} полна в Р2. Составим таблицу, которая называется критериальной :

  Т0 Т1 L M S
x1x2 + + - + -
+ - + + -
- + + + -
x1Åx2Åx3 + + + - +

 

 

x1 x2 x3 x1Åx2Åx3
0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

 

Из таблицы видно, что какой бы класс мы ни взяли, всегда есть функция из данной системы , которая в этот класс не входит. Можно сформулировать следующее правило: для того чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце критериальной таблицы был хотя бы один «минус».

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f2, f3, f4L, {f1, f3, f4T1, {f1, f2, f4T0, {f1, f2, f3M.

2. Мы знаем, что система {x1|x2} – полна в Р2. Какова для нее критериальная таблица? x1|x2== x1x2Å1.

  Т0 Т1 L M S
x1|x2 - - - - -

3. Составим критериальную таблицу для другой полной системы функций из Р2: {0, 1, x1x2, x1Åx2}.

  Т0 Т1 L M S
+ - + + -
- + + + -
x1x2 + + - + -
x1Åx2 + - + - -

Согласно критериальной таблице, полной является и система {1, x1x2, x1Åx2}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где аравны 0, если члены хх...х, в полиноме отсутствуют.

4. Выясним, полна ли система . Составим критериальную таблицу, очевидно . Чтобы показать, что , достаточно найти одну функцию и . Возьмем , удовлетворяющую требуемым условиям. Если f S\T0, то f(0, ..., 0) = 1, f(1, ..., 1)=0, следовательно, fM, fT1. Рассмотрим функцию h = x1x2x2x3x1x3=1, набор ее значений (11101000), hS\T0, но hL. Следовательно, критериальная таблица имеет вид:

  Т0 Т1 L M S
LT1 - + + - -
S\T0 - - - + -

и А – полная система функций.

Система функций {f1, ..., fs, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система функций {x1&x2, 0, 1, x1x2x3} – базис.