Система булевых функций F={f1,…,fn} называется полной, если любая булева функция представима в виде терма сигнатуры (f1,…,fn}, т.е в виде суперпозиции функций из F.
Классы Поста:
1) P0={f|f(0,…,0)=0} — класс булевых функций, сохраняющих ноль
2) P1={f|f(1,…,1)=1} – класс булевых функций, сохраняющих 1
3) S={f|f+=f} – класс самодвойственных функций
4) M – класс монотонных функций. Булева функция f(x1,…,xn) называется монотонной, если для любых наборов нулей и единиц (α1,…,αn) и (β1,…,βn) из условий αi≤βi следует f(α1,…,αn)≤f(β1,…,βn)
5) Класс I – это класс линейных функций. Булева функций f(x1,…,xn) называется линейной, если в булевом кольце 
функция f представима в виде 
.
Каждый класс Поста замкнут относительно операций замены переменных и суперпозиции.
Теорема Поста: Система F булевых функций тогда и только тогда является полной, когда для каждого из классов P0, P1, S, M, L в системе F найдется функция, не принадлежащая этому классу..
Теорема: Каждый базис содержит не более четырех булевых функций
|
|
|
Доказательство: Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f – функция из F, не принадлежащая классу P0. Тогда f(0,…,0)=1 и f(1,…,1)=1, но тогда f не принадлежит классу самодвойственных функций, а это противоречит предположения.
