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

Знаете ли вы, что каждая булева функция на самом деле является многочленом?

Чтобы в этом убедиться, вспомним, что одну и ту же б. ф. можно (хоть и не всегда) представлять разными способами — это зависит от того, какие логические символы-связки между переменными x?, ..., x? вы решите использовать. Самым распространенным набором является конъюнкция (?, •, & или просто отсутствие знака), дизъюнкция (V), отрицание (¬), а также константы 1 и 0 (конечно, некоторые вещи отсюда можно выразить через остальные). Этими символами можно задать любую функцию. Мы же ограничимся конъюнкцией, константами и исключающим "или" (?), т. е. сложением по модулю 2. Ими тоже можно задать любую функцию: легко видеть, что ¬x = x ? 1, а x V y = x ? y ? xy. Соответствующая запись булевой функции называется «полиномом Жегалкина» или алгебраической нормальной формой. По сути, этот полином есть сумма (по модулю 2) мономов (конъюнкций).

Что насчет единственности?

Оказывается, каждой б. ф. от n переменных соответствует единственный полином Жегалкина:

1) Полином состоит из нескольких мономов. Всего их 2? разных штук (каждая из n переменных либо входит в моном, либо не входит в него), и каждый из них либо входит в полином, либо нет. Получаем, что существует ровно 2^2? разных полиномов Жегалкина.

2) Самих булевых функций от n переменных тоже 2^2? штук: в таблице истинности каждому из 2? наборов (x?,..., x?) соответствует значение 0 или 1.

3) Понятное дело, что один и тот же полином не может соответствовать двум разным функциям (и у каждой функции есть полином), поэтому (с учетом того, что число функций совпадает с числом полиномов) получаем биекцию.

Таким образом, все элементы из P?? (так обозначают множество всех б. ф. от n переменных) можно отождествить с многочленами(!) от n переменных над Z?, где и сами переменные принадлежат Z? (вспомните арифметику остатков). Ура!

Кстати, определение полинома Жегалкина можно формализовать (рис. 2):

f = сумма всех конъюнкций, каждую из которых нужно умножить на коэффициент (0 или 1), отвечающий за то, присутствует ли данная конъюнкция (моном) в полиноме или нет. Эти коэффициенты можно задать некоторой булевой функцией. Таким образом, построение полинома Жегалкина сводится к нахождению функции коэффициентов, а для нее (ее значений) есть формула. Но пользоваться ею неприятно: если известна таблица истинности функции, то, считая каждый коэффициент по отдельности, для нахождения полинома потребуется порядка 3? операций сложения, что довольно много.

Можно ли уменьшить сложность?

Да! Приведем алгоритм «быстрого преобразования Мёбиуса» (рис. 3):

1) Выписываем таблицу истинности рассматриваемой функции (напротив каждого набора переменных указываем значение функции на нем);

2) Выписываем новый столбец из нулей и единиц, равный предыдущему столбцу, но если последний бит набора равен 1, то прибавляем (по модулю 2) к соответствующему значению значение функции на таком же наборе, но с нулевым последним битом;

3) Последовательно проделываем то же самое для следующих битов наборов;

4) В полином войдут все те и только те конъюнкции, напротив наборов которых в последнем столбце стоит 1. Замечание: если для набора (0, ..., 0) получена единица, то у полинома будет ненулевой свободный коэффициент.

Попробуйте выяснить сами, почему это работает.

Отмечу, что всего было проделано n шагов и для каждого потребовалось 2^{n-1} сложений (для любого i только у половины наборов на i-м месте стоит 1), поэтому сложность преобразования Мёбиуса равна n*2^{n-1}, что значительно лучше по сравнению с предыдущим результатом.

Для чего всё это нужно?

Полином Жегалкина — это очень удобная форма представления функции. По ней можно сразу понять, от скольких переменных функция существенно зависит (см. упражнение ниже). Кроме того, в разных науках мы так или иначе работаем с функциями, которые полезно приближать или описывать с помощью многочленов. В этом случае мы переходим на язык алгебры, которая вооружена кучей инструментов для работы с многочленами над всякими полями/кольцами. Как было указано выше, все булевы функции — это просто многочлены над Z?, работать с которыми одно удовольствие. По одному лишь виду полинома можно говорить о его линейности или нелинейности, что важно, например, в шифровании или проверке на полноту.

В следующий раз, возможно, обсудим другую запись б. ф. — так называемый «?-полином». А пока вот пара упражнений:

1) По таблице истинности найдите полином Жегалкина для стрелки Пирса;

2) Докажите (можно устно), что б. ф. существенно зависит от переменной x_i тогда и только тогда, когда x_i присутствует в полиноме Жегалкина б. ф.

На сегодня всё.

Источник: vk.com

Комментарии: