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

Полные системы функций

Определение:

Если любая булева функция, являющаяся суперпозицией функций некоторого множества, принадлежит этому множеству, то такое множество называют замкнутым (англ. closed set).

Определение:

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

Определение:

Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций.

Определение:

Полная система функций называется безызбыточной (англ. irredundant functions), если она перестает быть полной при исключении из неё любого элемента.

Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:

• функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math],
• самодвойственныые функции [math]S[/math],
• монотонные функции [math]M[/math],
• линейные функции [math]L[/math].

Замкнутые классы булевых функций

Класс функций сохраняющих ноль [math]T_0[/math].

Определение:

Говорят, что функция сохраняет ноль, если [math]f(0, 0, \dots, 0) = 0[/math].

Класс функций сохраняющих единицу [math]T_1[/math].

Определение:

Говорят, что функция сохраняет единицу, если [math]f(1, 1, \dots, 1) = 1[/math].

Класс самодвойственных функций [math]S[/math].

Определение:

Говорят, что функция самодвойственна (англ. self-dual), если [math]f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}[/math]. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.

Класс монотонных функций [math]M[/math].

Определение:

Говорят, что функция монотонна (англ. monotonic function) , если [math]\forall i (a_i \leqslant b_i) \Rightarrow f(a_1,\dots,a_n)\leqslant f(b_1,\dots,b_n)[/math].

Класс линейных функций [math]L[/math].

Определение:

Говорят, что функция линейна (англ. linear function), если существуют такие [math]a_0, a_1, a_2, \dots, a_n[/math], где [math]a_i \in \{0, 1\}, \forall i=\overline{1,n}[/math], что для любых [math]x_1, x_2, \dots, x_n[/math] имеет место равенство: [math]f(x_1, x_2, \dots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\dots\oplus a_n\cdot x_n[/math].

Количество линейных функций от [math]n[/math] переменных равно [math]~2^{n+1}[/math].

Функция является линейной тогда, и только тогда, когда в ее полиноме Жегалкина присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью преобразования Мебиуса.

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

Теорема:

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

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

[math]\triangleright[/math]

Необходимость. Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора [math]K[/math] входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор [math]K[/math] не мог бы быть полным. Достаточность. Докажем, что если набор [math]K[/math] не содержится полностью ни в одном из данных классов, то он является полным. Рассмотрим функцию, не сохраняющую ноль — [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]. Рассмотрим функцию, не сохраняющую один — [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]. Таким образом, возможны четыре варианта: Мы получили функцию [math] \neg [/math]. Используем несамодвойственную функцию [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}, \ldots, 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]. Таким образом мы получили одну из констант. Мы получили [math] \neg [/math] и [math]0 \Rightarrow[/math] имеем константу, равную [math]1[/math], поскольку [math]\lnot 0 = 1[/math]. Мы получили [math] \neg [/math] и [math]1 \Rightarrow[/math] имеем константу, равную [math]0[/math], поскольку [math]\lnot 1 = 0[/math]. Мы получили [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] \neg [/math], [math]0[/math], [math]1[/math]. Используем нелинейную функцию [math]f_l[/math]. Среди нелинейных членов [math]f_l[/math] (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем [math]x_1[/math] и [math]x_2[/math]. Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде [math]g_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1][/math], где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов). Рассмотрим несколько вариантов: Присутствует член [math]\oplus ~1[/math]. Возьмем отрицание от [math]g_l[/math] и член [math]\oplus ~1[/math] исчезнет. Присутствуют три члена, без [math]\oplus ~1[/math]: [math]g_l= x_1 \land x_2 \oplus x_1 \oplus x_2[/math]. Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции [math] \vee [/math]. Присутствуют два члена, без [math]\oplus ~1[/math]. Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции [math]g_l[/math] будет состоять только из одного члена. Если это так, то не составляет труда выразить [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math]. Например, если функция [math]g_l(x_1, x_2, ..., x_n)[/math] принимает истинное значение, когда аргументы c номерами [math]i_1, i_2, ..., i_m[/math] ложны, а все остальные истины, то функцию [math] \wedge [/math] можно выразить как [math]g_l([\lnot]x_1, [\lnot]x_2, ..., [\lnot]x_n)[/math], где [math]\lnot[/math] ставится перед аргументами с номерами [math]i_1, i_2, ..., i_m[/math]. Присутствует один член. Выразим [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math] аналогично пункту 3. В итоге получим функцию[math] \neg [/math], а также либо функцию [math] \wedge [/math], либо функцию [math] \vee [/math]. Поскольку функцию [math] \wedge [/math] можно выразить через [math] \vee [/math] и [math] \neg [/math], а функцию [math] \vee [/math] через [math] \wedge [/math] и [math] \neg [/math], то мы получили базис [math] \wedge [/math], [math] \vee [/math], [math] \neg [/math]. Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде [math]x \land \lnot x[/math]. Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K — полная система функций, что и требовалось доказать.

[math]\triangleleft[/math]

Примеры

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

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

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

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

Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.

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

Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему [math]\left\{\oplus,1\right\}[/math] можно назвать базисом класса линейных функций.

Источники информации

• Википедия — Критерий Поста
• Википедия — Замкнутые классы булевых функций
• Образовательный сайт MiniSoft
• Post's lattice
• Лекции по дискретной математике