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

Та б лиц а 4.31 Карта Карно Х 3 Х 4 Х 3 Х 4 ХзХ 4 Х 3 Х 4 * 1 * 2 s * 1 * 2 у Х,Х 2 Х,Х 2 Составим карту Карно для функции четырех переменных (табл. 4.31). Объединим контурами полученные единицы. Опустим дополняющие друг друга переменные (х4v х4) и (х2v х2) с (х3 v х3). _ Получим упрощенную булеву функцию / ’(х,х2х3х4) = х,х4. При желании можно проверить аналитически. _ F (X\X2X-sXA) = (X,Х 2 ХзХ 4 VХ[Х 2 ХзХ4) V (XiX 2 X 3 X 4 V Х!Х 2 ХзХ4) = Х|Х 2 Х 4 V V Х|Х 2 Х 4 = XiX4. Из последних примеров особенно наглядно видно, что карты Карно дают более рациональный путь минимизации булевых функ­ ций. 4.7. Сумма по модулю два Решением всякой проблемы служит новая проблема. Народная мудрость Напомним, что суммой по модулю два (М2 или строгой дизъюн­ кцией) двух переменных X] и х2называется булева функция х, © х2, которая равна 1 тогда и только тогда, когда равна 1 только одна переменная. Приведем таблицу ее значений еще раз (табл. 4.32). Приведем свойства, которыми обладает сумма по модулю два. Она подчиняется законам: • переместительному X] 0 х2 = х2® х,; • сочетательному (х! Ф х2) Ф х3 = Xj © (х2Ф х3), поэтому скобки можно не писать; • распределительному конъюнкции относительно М2 х,(х2Ф х3) = = Х]Х2 Ф Х)Х3. 187