Классы Поста. Полные системы булевых функций. Теорема Поста. Базисы

Система булевых функций F={f₁,…,f_n} называется полной, если любая булева функция представима в виде терма сигнатуры (f₁,…,f_n}, т.е в виде суперпозиции функций из F.

Классы Поста:

1) P₀={f|f(0,…,0)=0} - класс булевых функций, сохраняющих ноль

2) P₁={f|f(1,…,1)=1} – класс булевых функций, сохраняющих 1

3) S={f|f⁺=f} – класс самодвойственных функций

4) M – класс монотонных функций. Булева функция f(x₁,…,x_n) называется монотонной, если для любых наборов нулей и единиц (α₁,…,α_n) и (β₁,…,β_n) из условий α_i≤β_i следует f(α₁,…,α_n)≤f(β₁,…,β_n)

5) Класс I – это класс линейных функций. Булева функций f(x₁,…,x_n) называется линейной, если в булевом кольце функция f представима в виде .

Каждый класс Поста замкнут относительно операций замены переменных и суперпозиции.

Теорема Поста: Система F булевых функций тогда и только тогда является полной, когда для каждого из классов P₀, P₁, S, M, L в системе F найдется функция, не принадлежащая этому классу..

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

Доказательство: Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f – функция из F, не принадлежащая классу P₀. Тогда f(0,…,0)=1 и f(1,…,1)=1, но тогда f не принадлежит классу самодвойственных функций, а это противоречит предположения.