Совершенные нормальные формы формул алгебры высказываний

Элементарная конъюнкция (дизъюнкция) называется правильной, если в её составе нет одинаковых переменных.

Дизъюнкт (конъюнкт) является полным, относительно некоторого набора переменных, если в его составе представлены все переменные этого набора.

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

Теорема 1. Любая формула f, не являющаяся тождественной ложью, обладает единственной СДНФ.

Теорема 2. Любая формула f, не являющаяся тавтологией, обладает единственной СКНФ.

Алгоритм перехода от таблицы истинности формулы к её записи в виде СДНФ(СКНФ):

1) выбрать в таблице такие наборы исходных переменных, на которых истинностное значение формулы равно 1 (0);

2) записать элементарные конъюнкции (дизъюнкции) для выбранных наборов переменных; при этом необходимо руководствоваться следующим правилом: если значение входной переменной в наборе – единичное, то она записывается в прямой форме (форме отрицания), если же значение переменной – нулевое, то – в форме отрицания (прямой форме);

3) полученные конъюнкты (дизъюнкты) объединить между собой знаками дизъюнкции (конъюнкции).

Алгоритм получения СДНФ и СКНФ с помощью равносильных переходов

1) привести формулу с помощью равносильных преобразований к ДНФ;

2) удалить члены дизъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);

3) из одинаковых членов дизъюнкции (если такие окажутся) удалить все, кроме одного;

4) из одинаковых членов каждой конъюнкции (если такие окажутся) удалить все, кроме одного;

5) если в какой-нибудь конъюнкции не содержится переменной из числа переменных, входящих в исходную формулу, добавить к этой конъюнкции член – закон расщепления;

6) если в полученной дизъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.

7) Полученная формула и является СДНФ данной формулы.

СКНФ получается аналогично. Закон расщепления имеет вид:

Примеры выполнения типовых заданий.

Применяя равносильные преобразования, найти СДНФ и СКНФ для данной формулы. Проверить результат с помощью таблицы истинности.

1. Получим ДНФ:

– ДНФ.

2. Добавим в каждый неполный конъюнкт переменную и ее отрицание, пока все конъюнкты не станут полными:

3. Уберем одинаковые члены все, кроме одного:

 – СДНФ.

4. Получим КНФ:

 – КНФ

5. Получим СКНФ:

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

x

y

z

f

СДНФ

СКНФ

Задания для совместного решения.

Применяя равносильные преобразования, найти СДНФ и СКНФ для данной формулы. Проверить результат с помощью таблицы истинности.

1.

2.

3.

4.

5.

Ответ:

	СДНФ	СКНФ
1
2
3
4
5

Индивидуальные контрольные задания.

Применяя равносильные преобразования, найти СДНФ и СКНФ для данной формулы. Проверить результат с помощью таблицы истинности.

Практическая работа №5. Представление булевой функции в виде минимальной ДНФ