Определение. Совершенной дизъюнктивной формулой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой:

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

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

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

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

,

где дизъюнкция берется по всем наборам с=(с₁, с₂, …, с_n) из 0 и 1, для которых F(c)=1.

Теорема (о СДНФ). Для всякой не равной тождественному нулю формулы логики высказываний F(x₁, x₂, …, x_n)  существует такая формула F₁, зависящая от того же списка переменных и находящаяся в СДНФ относительно этого списка, что F₁ выражает собой формулу F. Формула F₁ определена однозначно с точностью до перестановки дизъюнктивных членов.

Определение. Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:

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

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

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

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

,

где конъюнкция берется по всем наборам с=(с₁, с₂, …, с_n) из 0 и 1, для которых F(c)=0.

Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x₁, x₂, …, x_n)  существует такая формула F₁, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F₁ выражает собой формулу F. Формула F₁ определена однозначно с точностью до перестановки конъюнктивных членов.

Опишем два способа приведения к совершенным нормальным формам.

1-й способ – аналитический.

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

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

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

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

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

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

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

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

Пример 27.

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

1) ;

2) ;

3) .

Решение.

1) .

2)

3)

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

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

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

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

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

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

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

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

Пример 28.

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

1) ;

2) .

Решение.

1) 

2)

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

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

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

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

Пример 29.

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

1) .

2)

Решение.

1) .

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

Таблица 2.11 Таблица истинности для формулы из примера 29

N/н	x	y	z
0	0	0	0	1	1	0
1	0	0	1	1	1	0
2	0	1	0	0	0	0
3	0	1	1	0	1	0
4	1	0	0	1	1	1
5	1	0	1	1	1	1
6	1	1	0	0	0	0
7	1	1	1	0	1	1

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

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

2)

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

Таблица 2.12 Таблица истинности для формулы из примера 29

N/н	x	y	x® y	F=(x® y) xy
0	0	0	1	0
1	0	1	1	0
2	1	0	0	0
3	1	1	1	1

СДНФ (1): № 3:  F = x y.

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

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

Пример 30.

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

1) .

2)

Решение.

1) Строим таблицу значений, используя предыдущий пример (табл. 2.13).

Таблица 2.13 Таблица истинности для формулы из примера 30

N/н	x	y	z
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	0
4	1	0	0	1
5	1	0	1	1
6	1	1	0	0
7	1	1	1	1

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

СКНФ (0): № 0, 1, 2, 3, 6:

2) Строим таблицу значений, используя предыдущий пример (табл. 2.14).

Таблица 2.14 Таблица истинности для формулы из примера 30

N/н	x	y	F=(x® y) xy
0	0	0	0
1	0	1	0
2	1	0	0
3	1	1	1

СКНФ (0): № 0, 1, 2: