[Список тем]

Совершенные нормальные формы алгебры логики

Порядок приведения формул логики к СДНФ и СКНФ

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

Преобразование выполним в два этапа. Вначале построим ДНФ, а затем преобразуем ее в СДНФ.

1. Преобразуем формулу так, чтобы в ней были только операции v,&,, причем знак отрицания может стоять только при переменных.
2. Преобразуем формулу так, чтобы все конъюнкции выполнялись раньше, чем дизъюнкции.
3. Если в ДНФ имеется несколько одинаковых элементарных конъюнкций, то мы оставляем только одну.
4. Делаем элементарные конъюнкции правильными:
   а) если в элементарную конъюнкцию входит некоторая переменная вместе с ее отрицанием, то мы удаляем эту конъюнкцию из ДНФ;
   б) если некоторая переменная входит в элементарную конъюнкцию несколько раз, причем, или во всех случаях со знаком отрицания,или во всехслучаях без знака отрицания, то мы оставляем только одно вхождение.
5. Если в некоторую конъюнкцию не входит переменная Y, то нужно рассмотреть равносильное выражение с (YvY) и вновь применить преобразование (2).
   Если недостающих переменных несколько, то нужно добавить несколько конъюнктивных членов вида (YvY) (осн.равн. 13)
6. Если в процессе преобразований (5) появятся одинаковые конъюнкции необходимо повторно выполнить преобразование (3) Во всех преобразованиях необходимо пользоваться коммутативностью и ассоциативностью конъюнкции и дизъюнкции ( осн.равн. 2-5).

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

Преобразование выполним в два этапа. Вначале построим КНФ, а затем преобразуем ее в СКНФ.

1. Преобразуем формулу так, чтобы в ней были только операции v,&,, причем знак отрицания может стоять только при переменных.
2. Преобразуем жормулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.
3. Если в ДНФ имеется несколько одинаковых элементарных дизъюнкций, то мы оставляем только одну.
4. Делаем элементарные дизъюнкции правильными:
   а) если в элементарную дизъюнкцию входит некоторая переменная вместе с ее отрицанием, то мы удаляем эту конъюнкцию из КНФ;
   б) если некоторая переменная входит в элементарную дизъюнкцию несколько раз, причем, или во всех случаях со знаком отрицания, или во всехслучаях без знака отрицания, то мы оставляем только одно вхождение.
5. Если в некоторую дизъюнкцию не входит переменная Y, то нужно рассмотреть равносильное выражение с (Y&Y) и вновь применить преобразование (2).
   Если недостающих переменных несколько, то нужно добавить несколько дизъюнктивных членов вида (Y&Y) (осн.равн. 16)
6. Если в процессе преобразований (5) появятся одинаковые дизъюнкции необходимо повторно выполнить преобразование (3)
   Во всех преобразованиях необходимо пользоваться коммутативностью и ассоциативностью конъюнкции и дизъюнкции ( осн.равн. 2-5).

Пример:

Для функции (a b) (a&c) последовательно выполним пункты алгоритма:

Вычисления	Выполняемые действия	Применяемые законы логики
( a b) (a&c)=	Избавляемся от импликации	x y = x y
=(a b) (a&c)=	Избавляемся от равнозначности	x y = (x y) & (y x)
=(a b a&c) &(a&c a b)=	Избавляемся от импликаций	x y = xy
=((ab) a&c)&( (a& c)ab)=	Вносим отрицание в скобки	(xy)=x&y
=(a&b) a& c)&((a& c)ab)=	Вносим отрицание в скобки	(x&y) = xy
=(a&b a&c)&(ac ab)=	Избавляемся от правых скобок	(a a)=1;  x&1=x
=a & b a&c  - начальная форма соответствует здесь ДНФ. Она используется для получения СДНФ и СКНФ	Добавляем в ДНФ в каждую элементарную конъюнкцию все недостающие аргументы функции со всеми возможными сочетаниями знаков	x = x&y x&y
=(a&b&c) (a&b&c) (a&b&c) (a&b&c) получена СДНФ
a&b a& c=(a&ba) &(a&b c)=	К начальной форме дважды применим дистрибутивный закон	x (y & z)=(xy) &(xz)
= (aa)&(ab)&(a c)&(b c)=	избавляемся от умножения на 1	xx = 1; x&1= x
= (ab)&(ac)&(b c) - КНФ	Добавляем в КНФ в каждую элементарную дизъюнкцию все недостающие аргументы функции со всеми возможными сочетаниями знаков	x=(xy)&(x y)
(a b c) & (abc) & (abc) & (a bc) & (a b c) & (abc)=	2й и 5й, 4й и 6й сомножители - совпадают. Оставляем по одному.	x&x = x
= (a b c) & (abc) & (abc) & (ab c) получена СКНФ

[Список тем]