Критерии полноты Поста-Яблонского

Теорема о функциональной полноте была сформулирована в 1921 г. американским ученым Эмилем Постом и доказана советским ученым Яблонским С.В.

Система S булевых функций f_i является полной тогда и только тог­да, когда выполняются 5 условий: существует функция f_i  S, не сохра­няющая константу нуль: f_i  K₀; функция f_i  S, не сохраняющая констан­ту 1: f_i  K₁; нелинейная функция, не самодвойственная и немонотонная функция в системе S. Построим все булевы функции от двух переменных (табл.).

переменные		булевы функции
X1	X2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Индекс i функциональной переменной равен десятичному эквиваленту этой функции, читаемому сверху вниз.

- константа 0

- конъюнкция

- левая коимпликация (читается “неправда, что если X₁ то X₂», префикс ко – от латинского conversus - обратный

- правая коимпликация

- сложение по модулю 2 (неравнозначность)

- дизъюнкция

- стрелка Пирса, функция Вебба

- эквивалентность

- отрицание X₂

- правая импликация («если X₁ то X₂»)

- отрицание X₁ («если X₁ то X₂»)

- левая импликация

- штрих Шеффера

Для порождения всех базисов в P₂ построим двумерную таблицу, каж­дой строке которой взаимно однозначно составим 11 функций, столбцу - класс, и в клетке (i, j) ставим 1, если 1 -функция не принадлежит j классу.

идентификатор строки	номер функции fi	классы
		K0	K1	Kл	Kс	Kм
a	0		1		1
b	1			1		1
c	2		1	1	1	1
d	6		1		1	1
e	7			1	1
g	8	1	1	1	1	1
k	9	1			1	1
m	12	1	1			1
n	13	1		1	1	1
p	14	1	1	1	1	1
r	15	1			1

Из таблицы видно, что каждое, указанное ниже, покрытие порождает базис B_i.

П₁ = {g}  B₁ – базис Вебба;

П₂ = {p}  B₂ – базис Шеффера;

П₃ = {a, n}  B₃ = {, 0} – импликативный базис;

П₄ = {b, m}  B₄ = {& } – конъюнктивный базис Буля;

П₅ = {m, e}  B₅ = { } – дизъюнктивный базис Буля;

П₆ = {r, b, d}  B₆ = {, &, 1} – базис Жегалкина;

П₇ = {m, n}  B₇ = { , } – базис Фреге.

Всего 17 базисов.

Наиболее часто приходится использовать базис Шеффера.