Важнейшие замкнутые классы булевых функций. Теорема Поста о полноте

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

Замыкание любой полной системы функций содержит все булевы функции. Для неполной системы функций это уже не так. В п. 3.4 было показано, что отрицание не входит в замыкание класса K={∧,∨}.

Рассмотрим важнейшие замкнутые классы булевых функций.

Класс P₀. Класс P₀ – это класс всех функций, сохраняющих 0, то есть таких функций f(x₁,x₂,…,x_n), для которых f(0,0,…,0)=0. В этот класс входят тождественная функция, конъюнкция, дизъюнкция, сложение по модулю 2; не входят тождественная единица, отрицание, импликация. Таблица для функции из класса P₀ в первой строке содержит 0, остальные значения могут быть какими угодно.

Класс P₁. Класс P₁ – это класс всех функций, сохраняющих 1, то есть таких функций f(x₁,x₂,…,x_n), для которых f(1,1,…,1)=1. В этот класс (так же, как и в P₀) входят тождественная функция, конъюнкция, дизъюнкция, сложение по модулю 2; импликация также входит в P₁; тождественный ноль, отрицание в класс P₁ не попадают.

Класс S. Класс S– это класс всех самодвойственных функций, то есть таких функций f, которые совпадают со своей двойственной функцией, f^*=f. Простейшие примеры самодвойственных функций – x и x’. Функция xy∨xz∨yz также самодвойственная:

(xy∨xz∨yz)^* = (x∨y)(x∨z)(y∨z) = (x∨xy∨xz∨yz)(y∨z) =

= xy∨xz∨yz∨xyz = xy∨xz∨yz.

Конъюнкция и дизъюнкция не самодвойственны.

В таблице самодвойственной функции значение в последней строке противоположно значению в первой строке, значение в предпоследней – значению во второй, и т.д.

Класс L. Класс L– это класс всех линейных функций, то есть функций, представимых в виде

f(x₁,x₂,…,x_n) = α₁x₁⊕α₂x₂⊕…⊕α_nx_n,

где α₁, α₂, …, α_n∈{0,1} – константы. Функции x, x’=1⊕x, x⊕y линейные; конъюнкция, дизъюнкция – нет.

Класс M. Класс M– это класс монотонных функций. Функция f(x₁,x₂,…,x_n) называется монотонной, если f(α₁,α₂,…,α_n)≤f(β₁,β₂,…,β_n) при (α₁,α₂,…,α_n)≤(β₁,β₂,…,β_n). Конъюнкция, дизъюнкция монотонны; отрицание, импликация, сложение по модулю 2 – нет.

Теперь мы можем сформулировать один из важнейших результатов теории булевых функций – теорему Поста о полноте.

Теорема.Класс функций Kполон тогда и только тогда, когда он не содержится целиком ни в одном из перечисленных выше пяти классов P₀, P₁, S, L, M.􀀀

Не приводя доказательства теоремы, поясним ее смысл. Как было показано, ни один из перечисленных пяти замкнутых классов не является полным (имеются не входящие в него булевы функции). Поэтому не может быть полным ни один класс функций, целиком содержащийся в одном из них. Имеются булевы функции, не входящие ни в один из классов P₀, P₁, S, L, M. Любая такая функция в соответствии с теоремой составляет полную систему функций, то есть через эту функцию может быть выражена любая булева функция. Среди функций от двух переменных такими функциями являются стрелка Пирса и штрих Шеффера.

С помощью теоремы Поста можно установить полноту системы функций, не выписывая непосредственно выражения для булевых функций.

Пример.Покажем, что система функций {→,} является полной. Составим таблицу, в которой символ 1 означает, что функция входит в соответствующий класс, а символ 0 – что не входит:

P₀ P₁ S L M

-------------------------------

→ 0 1 0 0 0

0 0 1 1 0

В каждом столбце таблицы имеется 0, значит, нет ни одного класса из пяти, который содержал бы обе функции. Следовательно, система функций {→,} полна.􀀀