Преобразование выполним в два этапа. Вначале построим ДНФ, а затем преобразуем ее в СДНФ.
Преобразование выполним в два этапа. Вначале построим КНФ, а затем преобразуем ее в СКНФ.
Пример:
Для функции (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) получена СКНФ |