Теорема поста о функциональной полноте
|
T0 |
T1 |
S |
L |
M |
|
|
f |
+ |
- |
- |
- |
- |
Пример 49.
Доказать полноту системы {+, Ъ, 1}.
Решение.
Введем обозначения: f1 = x1 + x2, f2 = x1 Ъ x2, f3 = 1. Построим единую таблицу для функций (табл. 60).
Таблица 60
|
Слагаемые |
№ |
х1 |
х2 |
f1 = х1+х2 |
D Паскаля |
f2 =х1Ъх2 |
D Паскаля |
f3 =1 |
D Паскаля |
|
1 |
0 |
0 |
0 |
0 |
0 1 1 0 |
0 |
0 1 1 1 |
1 |
1 1 1 1 |
|
х2 |
1 |
0 |
1 |
1 |
1 0 1 |
1 |
1 0 0 |
1 |
0 0 0 |
|
х1 |
2 |
1 |
0 |
1 |
1 1 |
1 |
1 0 |
1 |
0 0 |
|
х1х2 |
3 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Полином Жегалкина:
|
f |
T0 |
T1 |
L |
M |
S |
|
f1 |
+ |
- |
+ |
- |
- |
|
f2 |
+ |
+ |
- |
+ |
- |
|
f3 |
- |
+ |
+ |
+ |
- |
Поскольку для каждого из пяти функционально замкнутых классов нашлась функция, не принадлежащая этому классу (в каждом столбце имеется хотя бы один минус), то система булевых функций {+, Ъ, 1} является полной.
предыдущаяследующая