[Список тем]

Математическая логика

Получить СКНФ и СДНФ логического выражения:

Вариант	Логическое выражение		Вариант	Логическое выражение
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) получена СКНФ

[Список тем]