Полные системы функций. Теорема Поста о полной системе функций

Формулировка теоремы

Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов [math]~S,M,L,T_0,T_1[/math], т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

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

---

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

---

Докажем достаточность этого утверждения.

Рассмотрим функцию, несохраняющую 0 - [math]f_0[/math]. [math]f_0[/math](0) = 1. [math]f_0[/math](1) может принимать два значения:

а) [math]f_0[/math](1) = 1, тогда [math]f_0[/math](x, x, x, ..., x) = [math]~1[/math].

б) [math]f_0[/math](1) = 0, тогда [math]f_0[/math](x, x, x, ..., x) = ¬x.

Возьмем функцию, несохраняющую 1 - [math]f_1[/math]. [math]f_1[/math](1) = 0. [math]f_1[/math](0) может принимать два значения:

а) [math]f_1[/math](0) = 0, тогда [math]f_1[/math](x, x, x, ..., x) = [math]~0[/math].

б) [math]f_1[/math](0) = 1, тогда [math]f_1[/math](x, x, x, ..., x) = ¬x.

Возможны 4 варианта:

1) Мы получили функцию НЕ. Используем несамодвойственную функцию [math]f_s[/math].

По определению найдется такой вектор [math]x_0[/math], что [math]f_s[/math]([math]x_0[/math]) = [math]f_s[/math](¬[math]x_0[/math]). [math]x_0[/math] = ([math]x_{01}, x_{02}, ..., x_{0k}[/math]).

Возьмем [math]f_s[/math]([math]x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}[/math]), где [math]x^{x_{0i}}[/math] = x, при [math]x_{0i}[/math] = 1 и [math]x^{x_{0i}}[/math] = ¬x, при [math]x_{0i}[/math] = 0.

Нетрудно заметить, что [math]f_s[/math](0) = [math]f_s[/math](1) => [math]f_s[/math] = const. Таким образом мы получили одну из констант.

2)Мы получили НЕ и [math]~0[/math]. ¬[math]~0[/math] = [math]~1[/math].

3)Мы получили НЕ и [math]~1[/math]. ¬[math]~1[/math] = [math]~0[/math].

4)Мы получили [math]~1[/math] и [math]~0[/math].

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

В итоге мы имеем три функции: НЕ, [math]~0[/math], [math]~1[/math].

Используем нелинейную функцию [math]f_l[/math]. Среди нелинейных членов [math]f_l[/math], выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем [math]x_1[/math] и [math]x_2[/math], а все элементы, не входящие в данный член, сделаем равными 0. Тогда [math]f_l[/math] = [math]x_1[/math]^[math]x_2[/math] ⊕ [[math]x_1[/math]] ⊕ [[math]x_2[/math]] ⊕ [[math]~1[/math]], где в квадратных скобках указаны члены, которые могут и не присутствовать.

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

1) Присутствует член [math]~1[/math]. Возьмем отрицание от [math]f_l[/math] и член [math]~1[/math] уберется.

2) Присутствуют 3 члена, без [math]~1[/math]: [math]f_l[/math] = [math]x_1[/math]^[math]x_2[/math] ⊕ [math]x_1[/math] ⊕ [math]x_2[/math]. Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции ИЛИ.

3) Присутствуют 2 члена, без [math]~1[/math]. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить И, через НЕ и [math]f_l[/math].

4) Присутствует 1 член. Выразим И, через НЕ и [math]f_l[/math].

Получается, что у нас есть функция НЕ, а также либо функция И, либо функция ИЛИ, но НЕ образует базис и с той и с другой функциями. Из того, что через функции F можно выразить базис, следует, что F - полная система функций, что и требовалось доказать.