Совершенная дизъюнктивная нормальная форма

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

· для каждого набора значений переменных , на котором функция равна 1, выписываются конъюнкции всех переменных;

· над теми переменными, которые на этом наборе равны 0, ставятся отрицания;

· все такие конъюнкции соединяются знаками дизъюнкции.

Полученная таким образом формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции. Для каждой функции СДНФ единствена.

Пример: для логической функции, заданной в таблице 2.3, СДНФ имеет вид

.

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

Пример.Перевести в булев базис следующую логическую формулу .

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

Пример. В алгебре Жигалкина , ее сигнатура является функционально полной системой. Убедиться в этом, используя теоремы 1 и 2.

Решение. Из теоремы 1 следует, что набор булевых функций полон. Тогда, в соответствии с теоремой 2, для доказательства функциональной полноты набора достаточно доказать следующие равенства:

Используя обычный подход, построим таблицы истинности 2.5 и 2.6.

Таблица 2.5.

x			xÅ1

Таблица 2.6.

0 0 0 1 1 0 1 1

Из полученных таблиц истинности следует, что алгебра Жигалкина функционально полна.