Основные понятия по теме. Система булевых функций называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из

Система булевых функций называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из .

Например, следующие системы , , являются полными.

Множество булевых функций называется замкнутым классом, если любая суперпозиция функций из снова принадлежит .

Всякая система булевых функций порождает некоторый замкнутый класс. Этот класс состоит из всех булевых функций, которые можно получить суперпозициями из . Такой класс называется замыканием и обозначается . Для замкнутого класса следует, что . Очевидно, что если - полная система, то .

Рассмотрим следующие классы булевых функций.

- класс булевых функций, сохраняющих константу 0, т.е. функций , для которых .

- класс булевых функций, сохраняющих константу 1, т.е. функций , для которых .

Булева функция называется двойственной к функции , если .

Булева функция называется самодвойственной, если она совпадает с двойственной, т.е. .

– класс всех самодвойственных функций.

Булевы функции вида , где , равны нулю или единице, называются линейными.

– класс всех линейных булевых функций.

Для того, чтобы определить, является ли данная булева функция линейной или нет, ее надо представить в виде полинома Жегалкина.

Два набора и называются сравнимыми, если , .

Запись означает, что набор предшествует набору .

Булева функция называется монотонной, если для любых наборов и таких, что , имеет место неравенство .

– класс монотонных функций.

Теорема (о функциональной полноте) Для того, чтобы система булевых функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти классов , , , , .

В тех задачах, где требуется выяснить, является ли данная система булевых функций полной, мы будем составлять таблицы, которые называются таблицами Поста.

В клетках данной таблицы мы будем писать плюс или минус, в зависимости от того, входит функция, стоящая в данной строке в класс, стоящий в данном столбце, или не входит. Используя теорему о полноте, мы получаем, что для полноты данной системы булевых функций необходимо и достаточно, чтобы в каждом столбце стоял хотя бы один минус.

Пример 1 Выяснить, является ли функция линейной.

Найдем полином Жегалкина для данной функции.

Следовательно, данная функция линейна.

Пример 2 Какие из указанных функций являются монотонными:

а) б)

а) Упростим формулу . Эта функция равна нулю на наборах (0,0,0), (0,1,0), (1,0,0). Все оставшиеся наборы, исключая (0,0,1) содержат не менее двух единиц, а значит, они могут быть только больше. Набор (0,0,1) (0,0,0), а с остальными двумя он несравним. Значит, рассматриваемая функция монотонна.