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

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

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

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

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

Пример 1. Х & Y & Z, Х &. Y & Z — элементарные конъюнкции третьего ранга. Х v Y, Х v Y — элементарные дизъюнкции второго ранга.

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

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

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

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

1) ÚÚ;

2) ÚÚ.

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

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

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

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

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

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

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

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

ÚÚÚÚÚ.

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

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

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

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

3. Соединить элементарные конъюнкции знаком дизъюнкции.

Дата добавления: 2014-01-06