Приведение к СДНФ. Алгоритм приведения.

Приведение к СКНФ. Алгоритм приведения.

1. привести формулу с помощью равносильных преобразований к КНФ.
2. удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);
3. из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного;
4. из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить все, кроме одного;
5. если в какой-нибудь дизъюнкции не содержится переменной x_i из числа переменных, входящих в исходную формулу, добавить к этой дизъюнкции член и применить закон дистрибутивности дизъюнкции относительно конъюнкции;
6. если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.

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

Пример 28.

Привести следующие формулы к СКНФ с помощью равносильных преобразований:

1. ;

2. .

Решение.

1.

2.

2-й способ – табличный.

Составляем таблицу истинности для данной функции.

Строим таблицу значений формулы. Рассматриваем только те строки, в которых значение формулы равно единице. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Причем, аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 – без отрицания. Наконец, образуем дизъюнкцию всех полученных конъюнкций.

Пример 29.

Построить СДНФ для данных формул логики высказываний.

1. .

2.

Решение.

1. .

Строим таблицу истинности (табл. 13) для формулы F:

Таблица 13

№	x	y	z

Рассматриваем только 4, 5 и 7 наборы, так как только на этих наборах формула принимает значение равное единице.

СДНФ имеет вид:

2. 2.

Строим таблицу истинности (табл. 14) для формулы F:

Таблица 14

СДНФ (1): № 3:

F = x y.