Пример 3.19. Какие из ниже перечисленных формул являются, а какие не являются скнф:

1) ;2) _;3) ;

4) ;5) .

Решение.

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

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

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

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

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

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

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

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

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

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

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

Решение.

а) Во второй дизъюнкции не хватает переменной , поэтому добавим , а в третьей дизъюнкции не хватает и , поэтому добавляем и применяем дистрибутивные закон :

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

1) различны все члены дизъюнкции;

2) различны все члены каждой конъюнкции;

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

4) каждая конъюнкция содержит все переменные, входящие в формулу,

Пример 3.17.Какие из ниже перечисленных формул являются, а какие не являются сднф:

1) ;2) _;3) ;

4) ;5) .

Решение.

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

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

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

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

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

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

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

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

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

Любая булева формула, которая не является тождественно ложной (кроме 0), имеет единственную СДНФ.

Пример 3.18. Преобразовать данную функцию в СДНФ: а) б)

Решение.

а)Раскроем скобки и увидим, что в первой конъюнкции не хватает , добавив к этой конъюнкции член и применив дистрибутивные закон получим СДНФ:

б) в первой конъюнкции не хватает переменной , , добавив к этой конъюнкции члены , ,а к третьей член и применив дистрибутивные закон получим:

Замечание: СДНФ, СКНФ определяется для каждой функции однозначно. Единственная функция не имеющая СКНФ  константа 1. Единственная функция не имеющая СДНФ  константа 0.