Спирина, М.С. Дискретная математика

Связь между дизъюнкцией и суммой по модулю два (строгой дизъюнкцией) х, v х2= = х, ® х2 ® XiX2 показана на рис. 4.14. Конъюнкцию Х|Х2 можно выразить через сумму по модулю два и дизъюнкцию по формуле Х]Х2= X! 0 х2 ® (Х| v х2), что следу­ ет из таблицы истинности (табл. 4.34). Формула в последнем столбце истинна при любых значениях х, и х2 , т.е. является тавтологией. Теперь представим отрицание суммы по модулю два в виде, аналогичном Х| 0 х2 = Xix2 v Х]Х2: х, Фх2 = = X, 0 Х 2 = Х,Х2 V X, • Х2 = Х,Х2 V х ,х2. Получено разложение в СДНФ и самой функции и ее отрицания. Как видно из таблиц истинности, для двух переменных М2 реализует неравнозначность, т.е . исключающее ши. Можно^по- пытаться сконструировать функцию для трех переменных х,х2х3v v х,х2х3 v Х]Х2х3 или Х\ х2х3 v XjX2x3 v XjX2x3, аналогичную Xi 0 х2 0 0 х3 и А(хи х2, х3), принимающую значение 0 только при совпа­ дении всех аргументов. Проверим гипотезу о том, что и для трех переменных опера­ ции дадут одинаковый результат. Для этого сравним таблицы истинности трех этих операций (табл. 4.35). Как видно из таблицы, несовпадение последних трех столбцов говорит о том, что гипотеза не подтвердилась: для трех перемен­ ных результаты операций различны. Это является прямым след­ ствием того, что мы рассматриваем двузначную логику: невоз­ можно сделать так, чтобы все три булевы переменные принимали разные значения. Логический элемент, соответствующий операции М2, показан на рис. 4.15, а. Треугольником обозначен инвертор НЕ. Т а б л и ц а 4.34 Связь между конъюнкцией и суммой по модулю два Х \ X I XI V х2 X) © х2 X, ФХ2 © (Xl V х2) х,х2 XiX2 = X) ФХ2 Ф (Х| V х2) 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 Х(©х 2 Рис. 4.14. Связь между дизъюнкцией Х[ v х2и суммой по модулю два х, ® х2 189