Определение. Положительной конъюнкцией называется элементарная конъюнкция, не содержащая инверсий переменных. Договоримся обозначать положительную конъюнкцию через K+.
Примеры. K1+=x1x2 x3, K2+= x4, K3+=1. •
Определение. Полиномом Жегалкина, или алгебраической нормальной формой (АНФ), булевой функции f(x1, …, xn) называется дизъюнкция с исключением различных положительных конъюнкций переменных из множества X={x1, …, xn}, то есть формула вида
Пример.
P=x1x3 x1x2 x4
x2
1 –
полином Жегалкина.
•
Определение. Длиной полинома Жегалкина назовем количество конъюнкций в полиноме, а его степенью – наибольший из рангов конъюнкций, входящих в полином.
Пример. Длина полинома Жегалкина из предыдущего примера равна 4, а степень – 3. •
Условимся считать константу 0 полиномом длины и степени 0.
Определение. Полином Жегалкина называется линейным, если его степень не превышает единицы.
Примеры. P1=1, P2=x y
1 – линейные полиномы.
•
Напомним основные равносильности для дизъюнкции с исключением (подраздел 4.3), необходимые для дальнейших рассуждений.
Свойства 0 и 1:
x 0 = x, x
1 = x .
Закон коммутативности:
x y = y
x.
Закон ассоциативности:
x (y
z) = (x
y)
z = x
y
z.
Закон дистрибутивности: x(y z) = xy
xz.
Добавим к ним еще две равносильности (первая очевидна, доказательство второй предоставляется читателю):
Если в последней равносильности переменные заменить конюнкциями, то получим:
Для ортогональных конъюнкций равносильность примет вид:
В частности, совершенная ДНФ булевой функции f(x1, …, xn) состоит из попарно ортогональных конъюнкций, значит
Теорема о существовании полинома Жегалкина. Любая булева функция представима полиномом Жегалкина.
Доказательство. Константа 0 – это полином Жегалкина по договоренности. Любая другая булева функция f(x1, …, xn) представима совершенной ДНФ (подраздел 7.3.), а значит, как только что было показано, и формулой вида:
Эта формула не является полиномом Жегалкина, если
содержит переменные с инверсиями. От инверсий можно избавиться,
используя равносильность x =x 1.
Раскрыв в полученной формуле скобки на основе закона дистрибутивности,
получим сумму
положительных конъюнкций, которая не является полиномом
Жегалкина, если в ней конъюнкции повторяются. Используя
равносильности x
x = 0 и x
0 = x, удалим пары
одинаковых конъюнкций. В результате получим полином Жегалкина.
•
Лемма о числе положительных конъюнкций. Число различных положительных конъюнкций переменных из множества X={x1 …, xn} равно 2n.
Доказательство. Каждая положительная конъюнкция состоит из подмножества переменных из X, то есть представляется булевым вектором длины n, и наоборот, каждый вектор длины n задает положительную конъюнкцию подмножества переменных X. Значит, число различных положительных конъюнкций равно числу векторов длины n, то есть равно 2n. •
Определение. Форму представления полинома Жегалкина
булевой функции f(x1, …, xn), где ci – булевы константы, назовем формой с коэффициентами.
Число 2n положительных конъюнкций Ki+ определяется леммой. Договоримся однозначно связывать с номером конъюнкции Ki+ ее вид по следующему правилу: число i представлять булевым вектором a1 … an, который, в свою очередь, задаст подмножество переменных, составляющих конъюнкцию Ki+.
Пример. При n=3 конъюнкция K5+=x1x3, так как число 5 представляется булевым вектором 101, который задает подмножество переменных {x1,x3} множества {x1, x2, x3}. •
Таким образом, полином Жегалкина булевой функции n аргументов однозначно определяется вектором своих коэффициентов π=c0 c1… c2n –1, и наоборот, любой булев вектор длины 2n однозначно определяет полином Жегалкина функции n аргументов.
Пример. Полином Жегалкина
представляется вектором коэффициентов π=10011101. •
Из последних рассуждений следует, что число различных полиномов Жегалкина булевых функций n аргументов равно числу различных булевых векторов длины 2n.
Теорема о единственности полинома Жегалкина. Каждая булева функция имеет единственный полином Жегалкина.
Доказательство. Как только что было замечено, число различных полиномов Жегалкина булевых функций n аргументов равно числу булевых векторов длины 2n, то есть равно 22n. Но количество различных булевых функций n аргументов тоже равно 22n (по теореме о числе булевых функций), и каждая булева функция представима полиномом Жегалкина (по теореме о существовании полинома), следовательно, на каждую булеву функцию приходится ровно по одному полиному Жегалкина. •
Таким образом, наряду с совершенной ДНФ, совершенной КНФ и сокращенной ДНФ, полином Жегалкина является еще одной канонической формой представления булевых функций.