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

Критерий Поста

Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.

Формулировка и доказательство критерия

Теорема:

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

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

[math]\triangleright[/math]

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным. Докажем достаточность этого утверждения. Рассмотрим функцию, несохраняющую 0 — [math]f_0[/math]. [math]f_0(0) = 1[/math]. [math]f_0(1)[/math] может принимать два значения: а) [math]f_0(1) = 1[/math], тогда [math]f_0(x, x, x, \ldots, x) = 1[/math]. б) [math]f_0(1) = 0[/math], тогда [math]f_0(x, x, x, \dots, x) = \neg x[/math]. Рассмотрим функцию, несохраняющую 1 — [math]f_1[/math]. [math]f_1(1) = 0[/math]. [math]f_1(0)[/math] может принимать два значения: а) [math]f_1(0) = 0[/math], тогда [math]f_1(x, x, x, \ldots, x) = 0[/math]. б) [math]f_1(0) = 1[/math], тогда [math]f_1(x, x, x, \ldots, x) = \lnot x[/math]. Возможны 4 варианта: 1) Мы получили функцию НЕ. Используем несамодвойственную функцию [math]f_s[/math]. По определению найдется такой вектор [math]x_0[/math], что [math]f_s(x_0) = f_s(\lnot x_0)[/math]. [math]x_0 = (x_{01}, x_{02}, ..., x_{0k})[/math]. Возьмем [math]f_s(x^{x_{01}}, x^{x_{02}}, \ldots, x^{x_{0k}})[/math], где [math]x^{x_{0i}} = x[/math], при [math]x_{0i} = 1[/math] и [math]x^{x_{0i}} = \lnot x[/math], при [math]x_{0i} = 0 [/math]. Нетрудно заметить, что [math]f_s(0) = f_s(1) \Rightarrow f_s = \operatorname {const}[/math]. Таким образом мы получили одну из констант. 2)Мы получили НЕ и [math]0[/math]. [math]\lnot 0 = 1[/math]. 3)Мы получили НЕ и [math]1[/math]. [math]\lnot 1 = 0[/math]. 4)Мы получили [math]1[/math] и [math]0[/math]. Рассмотрим немонотонную функцию [math]f_m[/math]. Существуют такие [math]x_1, x_2, \ldots, x_n[/math], что [math]f_m(x_1, x_2, \ldots, x_{i-1}, 0 , x_{i+1}, \ldots, x_n) = 1[/math], [math]f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0[/math], зафиксируем все [math]x_1, x_2, \ldots, x_n[/math], тогда [math]f_m(x_1, x_2, \ldots, x_{i-1}, x, x_{i+1}, \ldots, x_n)= \lnot x[/math]. В итоге имеем три функции: НЕ, [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 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1][/math], где в квадратных скобках указаны члены, которые могут и не присутствовать. Рассмотрим несколько вариантов: Присутствует член [math]~1[/math]. Возьмем отрицание от [math]f_l[/math] и член [math]~1[/math] уберется. Присутствуют 3 члена, без [math]~1[/math]: [math]f_l[/math] = [math]x_1 \land x_2 \oplus x_1 \oplus x_2[/math]. Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции ИЛИ. Присутствуют 2 члена, без [math]~1[/math]. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить И, через НЕ и [math]f_l[/math]. Присутствует 1 член. Выразим И, через НЕ и [math]f_l[/math]. В итоге получаем функцию НЕ, а также либо функцию И, либо функцию ИЛИ, но НЕ образует базис и с той и с другой функциями. Из того, что через функции F можно выразить базис, следует, что F — полная система функций, что и требовалось доказать.

[math]\triangleleft[/math]

Источники

• Википедия — свободная энциклопедия
• Образовательный сайт MiniSoft
• Post's lattice