Совершенные нормальные формы

3.1.1 Совершенная дизъюнктивная нормальная форма

Введем обозначения:

; А^А=1; Х^А=1, если Х=А, Х^А=0, если Х А.

Формула Х^А_1……Х^А_n, где А= - какой-либо двоичный набор, а среди переменных Хi могут быть совпадающие называется элементарной конъюнкцией.

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

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

Например: 1) (значок конъюнкции в данном случае опущен).

1),4) – правильные элементарные конъюнкции;

2)– переменная х входит один раз сама и второй раз под знаком отрицания;

3) – переменная y входит трижды: один раз сама и два раза под знаком отрицания.

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

Например: из перечисленных в предыдущем примере конъюнкций полной является только 4) относительно переменных x,y,z,t; а относительно переменных x,y,z полной является только 1).

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

3.1.2 Разложение по переменным

Теорема 1. Всякая логическая функция может быть представлена в СДНФ:

, (1)

где m , а дизъюнкция берется по всем 2^m наборам значений переменных х₁,…х_m. Функция f разложена по первым n-переменным. Данное равенство называется разложением по переменным. х₁,…х_m. Например при n=4, m=2 разложение имеет вид:

теорема доказывается подстановкой в обе части равенства (1) произвольного набора (b₁,…,b_m, b_m₊₁,…,b_n) всех n-переменных.

При m = 1 из (1) получаем разложение функции по одной переменной:

(2)

Очевидно, что аналогичное разложение справедливо для любой из n- переменных.

Другой важный случай когда 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

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

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

· импликация

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

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

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

Например:

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

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

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

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

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