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

Т а б л и ц а 4.32 Значения функции М2 Х\ *2 / ( * 1. Х2) = X, © х2 0 0 0 0 1 1 1 0 1 1 1 0 Операции с константами имеют вид: • хФ х = 0; • х ® () = х; • X® X= 1; • X ф 1 = X. Возможно^азложение в СДНФ: • Xj ф Х2 = Х,Х2 V Х^2- Для суммы по модулю два справедлива формула отрицания Х[ Ф Х2 = X, Ф Х2 = X) © х2. Проверим справедливость последней формулы с помощью таб­ лицы истинности (табл. 4.33). Совпадение пятого , шестого и восьмого столбцов п од ­ тверждает справедливость формулы. Докажем аналитически эту парадоксальную на первый взгляд равносильность. Для этого выведем формулы, связывающие сумму по модулю два с другими операциями. Операции отрицания и М2 связаны фор­ мулой X = X ф 1. ПОЭТОМУ Xj Ф Х2 = (Xj © Х2) © 1= X] © (х2 © 1) = = X] Ф х2. В силу симметрии исходной функции по своим аргумен­ там Х| Ф х2 = X, © х 2. Т а б л и ц а 4.33 Снятие отрицания с операции М2 _ _ _ *1 х2 XI *2 X ! ® Х2 Xi Ф х2 X! Ф Х2 Х| Фх2 0 0 1 1 1 1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 188