Система булевых функций называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из .
Например, следующие системы , , являются полными.
Множество булевых функций называется замкнутым классом, если любая суперпозиция функций из снова принадлежит .
Всякая система булевых функций порождает некоторый замкнутый класс. Этот класс состоит из всех булевых функций, которые можно получить суперпозициями из . Такой класс называется замыканием и обозначается . Для замкнутого класса следует, что . Очевидно, что если - полная система, то .
Рассмотрим следующие классы булевых функций.
- класс булевых функций, сохраняющих константу 0, т.е. функций , для которых .
- класс булевых функций, сохраняющих константу 1, т.е. функций , для которых .
Булева функция называется двойственной к функции , если .
Булева функция называется самодвойственной, если она совпадает с двойственной, т.е. .
– класс всех самодвойственных функций.
Булевы функции вида , где , равны нулю или единице, называются линейными.
|
|
– класс всех линейных булевых функций.
Для того, чтобы определить, является ли данная булева функция линейной или нет, ее надо представить в виде полинома Жегалкина.
Два набора и называются сравнимыми, если , .
Запись означает, что набор предшествует набору .
Булева функция называется монотонной, если для любых наборов и таких, что , имеет место неравенство .
– класс монотонных функций.
Теорема (о функциональной полноте) Для того, чтобы система булевых функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти классов , , , , .
В тех задачах, где требуется выяснить, является ли данная система булевых функций полной, мы будем составлять таблицы, которые называются таблицами Поста.
В клетках данной таблицы мы будем писать плюс или минус, в зависимости от того, входит функция, стоящая в данной строке в класс, стоящий в данном столбце, или не входит. Используя теорему о полноте, мы получаем, что для полноты данной системы булевых функций необходимо и достаточно, чтобы в каждом столбце стоял хотя бы один минус.
Пример 1 Выяснить, является ли функция линейной.
Найдем полином Жегалкина для данной функции.
,
Следовательно, данная функция линейна.
Пример 2 Какие из указанных функций являются монотонными:
а) б)
а) Упростим формулу . Эта функция равна нулю на наборах (0,0,0), (0,1,0), (1,0,0). Все оставшиеся наборы, исключая (0,0,1) содержат не менее двух единиц, а значит, они могут быть только больше. Набор (0,0,1) (0,0,0), а с остальными двумя он несравним. Значит, рассматриваемая функция монотонна.
|
|
б) Функция немонотонна, т.к. (0,0) (1,0), но
.
Пример 3 Является ли функция самодвойственной?
Найдем двойственную функцию к данной
Следовательно, данная функция самодвойственная.
Пример 4 Выяснить, являются ли данные системы булевых функций полными
а) ; б) ; в)
а) . Ясно, что , . Так как , то . Найдем полином Жегалкина для . Следовательно, . Так как (0,0) (1,1), но , то . Таблица Поста для системы имеет вид.
– | – | – | – | – |
Итак, - полная система.
б)
+ | – | – | + | + | |
– | + | – | + | + | |
+ | + | – | – | + | |
+ | + | + | + | – |
Функция самодвойственная, так как
Функция немонотонная, так как (0,0,1) (0,1,1), но 1=0+0+1>0+1+1=0.
Система - полная система.
в)
– | – | + | + | – | |
+ | + | + | – | – |
Функция самодвойственная, так как
Итак, система целиком принадлежит классу . Следовательно, по теореме о полноте не является полной системой.