Теорема о функциональной полноте была сформулирована в 1921 г. американским ученым Эмилем Постом и доказана советским ученым Яблонским С.В.
Система S булевых функций fi является полной тогда и только тогда, когда выполняются 5 условий: существует функция fi Î S, не сохраняющая константу нуль: fi Ï K0; функция fi Î S, не сохраняющая константу 1: fi Ï K1; нелинейная функция, не самодвойственная и немонотонная функция в системе 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
— конъюнкция
— левая коимпликация (читается “неправда, что если X1 то X2», префикс ко – от латинского conversus — обратный
— правая коимпликация
— сложение по модулю 2 (неравнозначность)
— дизъюнкция
— стрелка Пирса, функция Вебба
— эквивалентность
— отрицание X2
— правая импликация («если X1 то X2»)
— отрицание X1 («если X1 то X2»)
— левая импликация
— штрих Шеффера
Для порождения всех базисов в P2 построим двумерную таблицу, каждой строке которой взаимно однозначно составим 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 |
|||
Из таблицы видно, что каждое, указанное ниже, покрытие порождает базис Bi.
П1 = {g} Û B1 – базис Вебба;
П2 = {p} Û B2 – базис Шеффера;
П3 = {a, n} Û B3 = {Þ, 0} – импликативный базис;
П4 = {b, m} Û B4 = {& Ø} – конъюнктивный базис Буля;
П5 = {m, e} Û B5 = {Ú Ø} – дизъюнктивный базис Буля;
П6 = {r, b, d} Û B6 = {Å, &, 1} – базис Жегалкина;
П7 = {m, n} Û B7 = {Þ , Ø} – базис Фреге.
Всего 17 базисов.
Наиболее часто приходится использовать базис Шеффера.