Теорема поста о функциональной полноте
Теорема Поста (признак полноты системы булевых функций). Для того чтобы система булевых функций {f1, …, fm} была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классов T0, T1, L, M, S нашлась хотя бы одна функция fi из системы, не принадлежащая этому классу.
Пример.
Выяснить к каким функционально замкнутым классам принадлежит булева функция f=01001110, используя теорему Поста.
Решение.
Строим таблицу значений и треугольник Паскаля (табл. 59):
Таблица 59
|
Слагаемые полинома Жегалкина |
x1 |
x2 |
x3 |
f |
g |
Треугольник Паскаля |
|
1 |
0 |
0 |
0 |
0 |
0 |
f = 0 1 0 0 1 1 1 0 |
|
x3 |
0 |
0 |
1 |
1 |
1 |
1 1 0 1 0 0 1 |
|
x2 |
0 |
1 |
0 |
0 |
0 |
0 1 1 1 0 1 |
|
x2x3 |
0 |
1 |
1 |
0 |
1 |
1 0 0 1 1 |
|
x1 |
1 |
0 |
0 |
1 |
1 |
1 0 1 0 |
|
x1 x3 |
1 |
0 |
1 |
1 |
1 |
1 1 1 |
|
x1 x2 |
1 |
1 |
0 |
1 |
0 |
0 0 |
|
x1 x2 x3 |
1 |
1 |
1 |
0 |
0 |
0 |
Полином Жегалкина имеет вид: f = x3 + x2x3 + x1 + x1 x3.
- f(0, 0, 0) = 0 Ю fОT0;
- f(1, 1, 1) = 1 Ю fПT1;
- f(0, 0, 0) = f(1, 1, 1), а наборы (0, 0, 0) и (1, 1, 1) являются противоположными, то f П S;
- так как в полиноме Жегалкина присутствуют слагаемые, представляющие собой конъюнкцию нескольких переменных, то f П L;
- сокращенная ДНФ функции имеет вид:
, так как она содержит
отрицания, то f П
M.
Сведем полученные данные:
предыдущаяследующая