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

этого и происходит смена значения суммы по модулю два на про­ тивоположное при изменении значения одного из аргументов. По этой же причине сумма по модулю два не поддается мини­ мизации через операции отрицания, дизъюнкции и конъюнкции, так как ее единичные значения не образуют ни общих ребер, ни общих граней. На практике если булева функция имеет много еди­ ниц и сложно минимизируется, то не исключено, что она имеет вид М2 или близкий к нему. Приведенные соотношения позволяют выражать одни булевы функции через другие. ? Какое минимальное число булевых функций позволяет выразить все остальное множество булевых функций в виде композиции заданных? 4.8. Полином Жегалкина. Функционально замкнутые классы Верность теорий проверяется не опытом, а временем. Н. Векшин Как было отмечено ранее, в СДНФ булевой функции / только одна из элементарных конъюнкций равна 1. Это дает основание представить любую булеву функцию с помощью операции сложе­ ния по модулю два. 4.8.1. Канонический полином Жегалкина Заменив в СДНФ х, на 1 ® х, = х, и используя распределитель­ ный закон для конъюнкции относительно сложения по модулю два, имеем (1 © х,)(1 ® ху) = 1 ф х,- © ху © х,х; . Тогда, учитывая, что / © / = 0 , а / Ф 0 = / , булеву функцию / можно представить в виде f ( x xX 2 ...X„) = / о Ф / ,Х ] Ф / 2Х2 ф . . . ® /„Х „ Ф / 12Х,Х2 Ф . . . ф f 2...nX\X2...Xn, п р и ч е м € в = {0, 1}. Такое представление булевой функции называется канониче­ ским полиномом Жегалкина. Например, представим в виде полинома Жегалкина булеву функцию, заданную таблично (табл. 4.36). Найдем ее^ЗДНФ и преобразуем: / ( Х ) Х 2Х3) = Х[Х2Х3 V Х ,Х 2Х3 V Х |Х 2Х3 V х , х 2х 3 = (1 ф х , ) х 2(1 Ф х 3) ф Ф X ^ l Ф Х 2)(1 ф Х3) Ф Х [(1 Ф х 2) х 3 Ф Х |Х2Х3 = ( х 2 ф Х[Х 2)(1 Ф х 3) Ф Ф ( х , Ф Х,Х2) ( 1 ф Х3) ф ( х , ф Х |Х2)Х3 ф Х1Х2Х3 = Х2 © Х|Х2 ф Х2Х3 Ф Х,Х2Х3 ф Ф X, Ф Х]Х2 Ф Х |Х3 ф Х]Х2Х3 ф Х |Х3 ф Х ,Х2Х3 = Х[ Ф Х2 ф Х2Х3 Ф Х]Х2Х3 = = 0 Ф Х | © х 2 Ф 0 • Х |Х3 Ф 0 • XjX2 Ф х 2х 3 © Х |Х 2х 3. 192