[Список тем]


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


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

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

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

  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) получена СКНФ


[Список тем]