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

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

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

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

Теорема:

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

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

[math]\triangleright[/math]

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и класс К не мог быть полным. Докажем достаточность этого утверждения. Рассмотрим функцию, несохраняющую 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 - полная система функций, что и требовалось доказать.

[math]\triangleleft[/math]

Источники

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