Теоремы Поста с доказательством.

Набор булевых функций $K$ является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов $S,M,L,T_0,T_1$ , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

Доказательство:

$\triangleright$

Необходимость.

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора $K$ входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор $K$ не мог бы быть полным.

Достаточность.

Докажем, что если набор $K$ не содержится полностью ни в одном из данных классов, то он является полным.

Рассмотрим функцию, не сохраняющую ноль — (то есть функцию, для которой ). Тогда может принимать два значения:
1. $f_0(1) = 1$ , тогда $f_0(x, x, x, \ldots, x) = 1$ .
2. $f_0(1) = 0$ , тогда $f_0(x, x, x, \dots, x) = \neg x$ .
Рассмотрим функцию, не сохраняющую один — (то есть функцию, для которой ). Тогда может принимать два значения:
1. $f_1(0) = 0$ , тогда $f_1(x, x, x, \ldots, x) = 0$ .
2. $f_1(0) = 1$ , тогда $f_1(x, x, x, \ldots, x) = \lnot x$ .

Таким образом, возможны четыре варианта:

Мы получили функцию $\neg$ .

Используем несамодвойственную функцию $f_s$ . По определению, найдется такой вектор $x_0$ , что $f_s(x_0) = f_s(\lnot x_0)$ . Где $x_0 = (x_{01}, x_{02}, \ldots, x_{0k})$ .

Рассмотрим $f_s(x^{x_{01}}, x^{x_{02}}, \ldots, x^{x_{0k}})$ , где либо $x^{x_{0i}} = x$ , при $x_{0i} = 1$ . Либо $x^{x_{0i}} = \lnot x$ , при $x_{0i} = 0$ . Нетрудно заметить, что $f_s(0) = f_s(1) \Rightarrow f_s = \operatorname {const}$ . Таким образом мы получили одну из констант.

Мы получили $\neg$ и $0 \Rightarrow$ имеем константу, равную $1$ , поскольку $\lnot 0 = 1$ .
Мы получили $\neg$ и $1 \Rightarrow$ имеем константу, равную $0$ , поскольку $\lnot 1 = 0$ .
Мы получили $1$ и $0$ .

Рассмотрим немонотонную функцию $f_m$ . Существуют такие $x_1, x_2, \ldots, x_n$ , что $f_m(x_1, x_2, \ldots, x_{i-1}, 0 , x_{i+1}, \ldots, x_n) = 1$ , $f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0$ , зафиксируем все $x_1, x_2, \ldots, x_n$ , тогда $f_m(x_1, x_2, \ldots, x_{i-1}, x, x_{i+1}, \ldots, x_n)= \lnot x$ .

В итоге имеем три функции: $\neg$ , $0$ , $1$ .

Используем нелинейную функцию $f_l$ . Среди нелинейных членов $f_l$ (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем $x_1$ и $x_2$ . Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде $g_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1]$ , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).

Рассмотрим несколько вариантов:

Присутствует член $\oplus ~1$ . Возьмем отрицание от $g_l$ и член $\oplus ~1$ исчезнет.
Присутствуют три члена, без $\oplus ~1$ : $g_l= x_1 \land x_2 \oplus x_1 \oplus x_2$ . Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции $\vee$ .
Присутствуют два члена, без $\oplus ~1$ . Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции $g_l$ будет состоять только из одного члена. Если это так, то не составляет труда выразить $\wedge$ через $\neg$ и $g_l$ . Например, если функция $g_l(x_1, x_2, ..., x_n)$ принимает истинное значение, когда аргументы c номерами $i_1, i_2, ..., i_m$ ложны, а все остальные истины, то функцию $\wedge$ можно выразить как $g_l([\lnot]x_1, [\lnot]x_2, ..., [\lnot]x_n)$ , где $\lnot$ ставится перед аргументами с номерами $i_1, i_2, ..., i_m$ .
Присутствует один член. Выразим $\wedge$ через $\neg$ и $g_l$ аналогично пункту 3.

В итоге получим функцию $\neg$ , а также либо функцию $\wedge$ , либо функцию $\vee$ . Поскольку функцию $\wedge$ можно выразить через $\vee$ и $\neg$ , а функцию $\vee$ через $\wedge$ и $\neg$ , то мы получили базис $\wedge$ , $\vee$ , $\neg$ . Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде $x \land \lnot x$ .

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

$\triangleleft$

Примеры

Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов $T_0$ , $T_1$ , $S$ , $M$ , $L$ .

В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера или стрелку Пирса.

Широко известны такие полные системы булевых функций:

$\left\{\land,\lor,\neg\right\}$ (конъюнкция, дизъюнкция, отрицание);
$\left\{\land,\oplus,1\right\}$ (конъюнкция, сложение по модулю два, константа один).