Полнота системы булевых функций

Для начала дадим основные определения.

Определение. Говорят, что булева функция сохраняет 0, если f (0,0,…,0)=0.

Определение. Говорят, что булева функция сохраняет 1, если .

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

Функцию, двойственную к функции , обозначают , т.е. .

Определение. Говорят, что булева функция самодвойственная, если .

Определение. Если для любого  (), то говорят, что вектор предшествует вектору  и пишут .

Например, ; .

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

Определение. Говорят, что булева функция линейна, если в ее каноническом полиноме Жегалкина коэффициенты при всех слагаемых, содержащих произведения переменных, равны 0.

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

ПРИМЕР. Является ли система булевых функций  полной?

Чтобы убедиться в функциональной полноте, составим таблицу, столбцы которой соответствуют классам , , , ,. , строки – функциям , а в клетках проставляется «+» или «–» в зависимости от того, принадлежит ли функция соответствующему классу или не принадлежит.

0	+	–	–	+	+
1	–	+	–	+	+
	–	–	+	–	+

Как видно из таблицы, для каждой пары классов найдется функция, принадлежащая одному классу из пары и не принадлежащая другому

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

1. B – полна;

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

ПРИМЕРЫ.

1.  – дизъюнктивный базис Буля.

2. – конъюнктивный базис Буля.

3.  – базис Шеффера.

4.  – базис Пирса.

5. – базис Жегалкина.