Другой важный случай когда n=m. При этом все переменные в правой части (1) получают фиксированные значения и функции в конъюнкции правой части становятся равными 0 или 1, что дает:

, (3)

где дизъюнкция берется по всем наборам (b₁…b_n), на которых f=1. При f=0 множество конъюнкций в правой части пусто. Такое разложение называется совершенной дизъюнктивной нормальной формой. СДНФ функции f содержит ровно столько конъюнкций, сколько единиц получается в таблице истинности f. Каждому единичному набору (b₁,…, b_n) соответствует конъюнкция всех переменных, в которой x_i взято с отрицанием, если b_i=0 b ,и без отрицания, если, b_i=1. Таким образом существует взаимно однозначное соответствие между таблицей истинности функции f и ее СДНФ, и ,следовательно, СДНФ для всякой логической функции единственна. Единственная функция не имеющая СДНФ – это константа 0.

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

Теорема 2. Всякая логическая функция может быть представлена в виде булевой формулы.

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

3.1.3 Алгоритм преобразования формулы в СДНФ

Равенство (3) дает возможность находить СДНФ для функции по ее таблице истинности

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

Таб. 4.

Х₁	Х₂	Х₃	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Данная функция имеет следующую СДНФ:

. Однако, если функция задана формулой, то строить СДНФ по таблице не рационально, тогда применяют следующий алгоритм: построение СДНФ состоит из двух этапов, каждых из которых состоит их трех шагов. На первом этапе строят ДНФ, а на втором этапе из ДНФ строят СДНФ.

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

· импликация

· эквивалентность

· перенос отрицания: из свойств:

можно произвести следующие преобразования:

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

Например:

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

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

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

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

5 шаг. Делаем все элементарные конъюнкции полными. Если в некоторую конъюнкцию

не входит переменная y , то необходимо рассмотреть равносильное выражение

и вновь применить шаг 2. Если недостающих переменных несколько, то нужно добавить несколько конъюнктивных членов вида

6 шаг. После применения 5-го шага могут вновь появится одинаковые конъюнкции. Поэтому на шестом шаге применяют шаг 3.

Задание №5.

Найти СДНФ для следующей формулы:

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

Используя свойство

, получим

используя свойство

,получим

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

Используя свойство дистрибутивности получим

3. шаг. Все конъюнкции получились правильными, делаем их полными

4. шаг. Одинаковых конъюнкций нет, следовательно оставляем их все.

получили совершенную дизъюнктивную нормальную форму.

(в конце примера опущен знак конъюнкции)

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

Формула вида

, называется элементарной дизъюнкцией.

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

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

Правильная элементарная дизъюнкция, называется полной относительно переменных х₁…х_n_,если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).

Совершенной конъюнктивной нормальной формой относительно переменных х₁…х_n, называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильны и полны относительно переменных х₁…х_n.

Теорема 3: всякую функцию f можно представить в СКНФ

, (4)

где символ

означает, что конъюнкция берется по тем наборам, которые находятся под ним.

3.2.1 Алгоритм преобразования формулы в СКНФ

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

Находить СКНФ для функции также можно по ее таблице истинности, но дизъюнкции берутся по тем наборам, где функция =0. С отрицанием берется та переменная, значение которой =1.

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

Таб. 5

Х	Y	Z	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Данная функция имеет следующую СКНФ:

Однако, если функция задана формулой, то строить СКНФ по таблице не рационально, тогда применяют следующий алгоритм: построение СКНФ состоит из двух этапов, каждых из которых состоит их трех шагов. На первом этапе строят КНФ, а на втором этапе из КНФ строят СКНФ.