Получить СКНФ и СДНФ логического
выражения:
Вариант | Логическое выражение | Вариант | Логическое выражение | |
1 | (a b) (a&c) | 9 | (a b&c) (a&c) | |
2 | (a b) (a&c) | 10 | (a b&c) (a&c) | |
3 | (a b) (a&c) | 11 | a&b (a&c) | |
4 | (a b) (a&c) | 12 | a&b (a&c) | |
5 | (a b) (a&c) | 13 | a&b (a&c) | |
6 | (a b&c) (a&c) | 14 | ab (ac) | |
7 | (a b&c) (a&c) | 15 | ab (ac) | |
8 | (a b&c) (a&c) | 16 | ab (ac) |
Пример.
Для функции (a b) (a&c) последовательно выполним пункты алгоритма:
Вычисления | Выполняемые действия | Применяемые законы логики |
(a b) (a&c)= | Избавляемся от импликации | x y = xy |
=(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)&(acab)= | Избавляемся от правых скобок | (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&bc)= | К начальной форме дважды применим дистрибутивный закон | x (y & z)=(xy) &(xz) |
= (aa)&(ab)&(ac)&(b c)= | избавляемся от умножения на 1 | xx = 1; x&1= x |
= (ab)&(ac)&(b c) - КНФ | Добавляем в КНФ в каждую элементарную дизъюнкцию все недостающие аргументы функции со всеми возможными сочетаниями знаков | x=(xy)&(xy) |
(a b c) & (abc) & (abc) & (abc) & (a b c) & (abc)= | 2й и 5й, 4й и 6й сомножители - совпадают. Оставляем по одному. | x&x = x |
= (a b c) & (abc) & (abc) & (abc) получена СКНФ |