15.3. Класс линейных булевых функций

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

Определение. Положительной конъюнкцией называется элементарная конъюнкция, не содержащая инверсий переменных. Договоримся обозначать положительную конъюнкцию через K⁺.

Примеры. K₁⁺=x₁x₂ x₃, K₂⁺= x₄, K₃⁺=1. •

Определение. Полиномом Жегалкина, или алгебраической нормальной формой (АНФ), булевой функции f(x₁, …, x_n) называется дизъюнкция с исключением различных положительных конъюнкций переменных из множества X={x₁, …, x_n}, то есть формула вида

P= K₁⁺ … K_p⁺,

Пример. P=x₁x₃ x₁x₂ x₄ x₂ 1 – полином Жегалкина. •

Определение. Длиной полинома Жегалкина назовем количество конъюнкций в полиноме, а его степенью – наибольший из рангов конъюнкций, входящих в полином.

Пример. Длина полинома Жегалкина из предыдущего примера равна 4, а степень – 3. •

Условимся считать константу 0 полиномом длины и степени 0.

Определение. Полином Жегалкина называется линейным, если его степень не превышает единицы.

Примеры. P₁=1, P₂=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.

Добавим к ним еще две равносильности (первая очевидна, доказательство второй предоставляется читателю):

x x = 0,

x y = x y xy.

Если в последней равносильности переменные заменить конюнкциями, то получим:

K₁ K₂= K₁ K₂ K₁K₂.

Для ортогональных конъюнкций равносильность примет вид:

K₁ K₂= K₁ K₂.

В частности, совершенная ДНФ булевой функции f(x₁, …, x_n) состоит из попарно ортогональных конъюнкций, значит

Теорема о существовании полинома Жегалкина. Любая булева функция представима полиномом Жегалкина.

Доказательство. Константа 0 – это полином Жегалкина по договоренности. Любая другая булева функция f(x₁, …, x_n) представима совершенной ДНФ (подраздел 7.3.), а значит, как только что было показано, и формулой вида:

Эта формула не является полиномом Жегалкина, если содержит переменные с инверсиями. От инверсий можно избавиться, используя равносильность x =x 1. Раскрыв в полученной формуле скобки на основе закона дистрибутивности, получим сумму положительных конъюнкций, которая не является полиномом Жегалкина, если в ней конъюнкции повторяются. Используя равносильности x x = 0 и x 0 = x, удалим пары одинаковых конъюнкций. В результате получим полином Жегалкина. •

Лемма о числе положительных конъюнкций. Число различных положительных конъюнкций переменных из множества X={x₁ …, x_n} равно 2ⁿ.

Доказательство. Каждая положительная конъюнкция состоит из подмножества переменных из X, то есть представляется булевым вектором длины n, и наоборот, каждый вектор длины n задает положительную конъюнкцию подмножества переменных X. Значит, число различных положительных конъюнкций равно числу векторов длины n, то есть равно 2ⁿ. •

Определение. Форму представления полинома Жегалкина

P = c₀ K₀⁺ c₁K₁⁺ … c₂ⁿ –1 K₂ⁿ –1⁺

булевой функции f(x₁, …, x_n), где c_i – булевы константы, назовем формой с коэффициентами.

Число 2ⁿ положительных конъюнкций K_i⁺ определяется леммой. Договоримся однозначно связывать с номером конъюнкции K_i⁺ ее вид по следующему правилу: число i представлять булевым вектором a₁ … a_n, который, в свою очередь, задаст подмножество переменных, составляющих конъюнкцию K_i⁺.

Пример. При n=3 конъюнкция K₅⁺=x₁x₃, так как число 5 представляется булевым вектором 101, который задает подмножество переменных {x₁,x₃} множества {x₁, x₂, x₃}. •

Таким образом, полином Жегалкина булевой функции n аргументов однозначно определяется вектором своих коэффициентов π=c₀ c₁… c₂ⁿ –1, и наоборот, любой булев вектор длины 2ⁿ однозначно определяет полином Жегалкина функции n аргументов.

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

P=1 x xz yz xyz = K₀⁺ K₄⁺ K₅⁺ K₃⁺ K₇⁺ =

= 1 K₀⁺ 0 K₁⁺ 0 K₂⁺ 1 K₃⁺ 1 K₄⁺ 1 K₅⁺ 0 K₆⁺ 1 K₇⁺

представляется вектором коэффициентов π=10011101. •

Из последних рассуждений следует, что число различных полиномов Жегалкина булевых функций n аргументов равно числу различных булевых векторов длины 2ⁿ.

Теорема о единственности полинома Жегалкина. Каждая булева функция имеет единственный полином Жегалкина.

Доказательство. Как только что было замечено, число различных полиномов Жегалкина булевых функций n аргументов равно числу булевых векторов длины 2ⁿ, то есть равно 2²ⁿ. Но количество различных булевых функций n аргументов тоже равно 2²ⁿ (по теореме о числе булевых функций), и каждая булева функция представима полиномом Жегалкина (по теореме о существовании полинома), следовательно, на каждую булеву функцию приходится ровно по одному полиному Жегалкина. •

Таким образом, наряду с совершенной ДНФ, совершенной КНФ и сокращенной ДНФ, полином Жегалкина является еще одной канонической формой представления булевых функций.