Совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ)

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

Элементарная конъюнкция — конъюнкция конечного множества логических переменных и их инверсий.

Элементарная дизъюнкция — дизъюнкция конечного множества логических переменных и их инверсий.

Число аргументов, образующих элементарную дизъюнкцию или конъюнкцию, называется ее рангом.

Дизъюнктивная нормальная форма (ДНФ) содержит элементарные конъюнкции, связанные между собой операцией дизъюнкции.

Конъюнктивная нормальная форма (КНФ) содержит элементарные дизъюнкции, связанные между собой операцией конъюнкции.

Одну и ту же логическую функцию можно представить разными ДНФ и КНФ.

Пример 2. Нетрудно убедиться (построив таблицы истинности для каждой из логических формул или проведя преобразования на основании логических законов), что приведенные ниже формулы определяют одну и ту же логическую функцию F(X, Y, Z):

1) Ú Ú ;

2) Ú Ú .

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

Совершенная дизъюнктивная нормальная форма (СДНФ) отвечает следующим требованиям:

1) в ней нет двух одинаковых элементарных конъюнкций;

2) ни одна элементарная конъюнкция не содержит двух одинаковых переменных;

3) ни одна элементарная конъюнкция не содержит переменную вместе с ее инверсией;

4) все конъюнкции имеют один и тот же ранг.

Аналогичным требованиям подчиняется и совершенная конъюнктивная нормальная форма (СКНФ).

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

Ú Ú Ú Ú Ú .

СДНФ и СКНФ можно получить по табличному представлению логической функции.

5.5.1. Алгоритм образования СДНФ по таблице истинности