Упражнения

1. Докажите, что если б.ф. f является суперпозицией б.ф. g ₁, …, g _s, то f^* является суперпозицией той же структуры функций g ₁^*, …, g_s ^*.

2. Докажите, что ( Û у)^* = Å у, ( ÷ у)^* = ¯ у, ( Þ у)^* =

h^* = h, где h (, y, z) = y Å z Å yz.

3.10. Полином Жегалкина

Если в ЭК нет отрицаний переменных, то она называется монотонной элементарной конъюнкцией (Мон. ЭК). Например, 1, , y, y – все монотонные ЭК от переменных , y; или 1, х, y, z, y, z, yz, yz – все Мон. ЭК от переменных , y, z. Сумма по модулю 2 различных монотонных элементарных конъюнкций называется полиномом Жегалкина.

ТЕОРЕМА. Любую булеву функцию можно представить в виде полинома Жегалкина, причем, единственным образом с точностью до коммутативности & и Å.

Доказательство. Представим б.ф. в виде СДНФ или СКНФ. С помощью тождеств заменим все значки Ú и Ø, т.е. б.ф. представим в виде суперпозиции &, Å, 0, 1 – в виде полинома Жегалкина. Так как число всех различных полиномов Жегалкина от равно , т.е. числу всех различных n -местных б.ф., то любую б.ф. представить в виде полинома Жегалкина можно лишь единственным способом. ■

Пример. Представьте в виде полинома Жегалкина f = Þ` y.

¨ f =` x Ú` y =` x Å` y Å` x ` y = x Å 1Å y Å 1Å (x Å 1)(y Å 1) = xy Å 1.

Пример. Найдите полином Жегалкина для функции f = (11111000).

Решение. Применим метод неопределенных коэффициентов.

Если , то получим систему уравнений

= 1 = 1

Å = 1 = 0

Å = 1 = 0

Å = 1 = 0

Å Å Å = 1 = 0

Å Å Å = 0 = 1

Å Å Å = 0 = 1

Å Å Å Å Å Å Å = 0 = 1

Отсюда f = K ₀ Å K ₄ Å K ₅ Å K ₇ = 1 Å _{1 2} Å _{2 3} Å _{1 2 3}.