Представление булевых функций полиномом Жегалкина

Рассмотрим полную систему функций . Формула, построенная из функций этой системы, после раскрытия скобок и алгебраических преобразований переходит в полином по mod 2, который в честь русского логика конца XIX века И.И. Жегалкина называют полиномом Жегалкина. Возможность такого преобразования следует из следующих тождеств:

; (1)

; (2)

; (3)

; (4)

. (5)

Действительно, из тождеств (1) – (5) следует, что формулы, содержащие операции & и , можно преобразовывать по обычным алгебраическим законам: переставлять слагаемые и множители, раскрывать скобки, выносить общий множитель за скобки.

Пример 1. Представим функцию над множеством связок :

. (6)

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

где коэффициенты полинома либо равны 1, либо 0 в зависимости от наличия или отсутствия соответствующего члена.

Приведенное выше рассуждение доказывает справедливость следующей теоремы, принадлежащей И.И. Жегалкину.

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

Подсчитаем число полиномов Жегалкина от переменных , то есть число выражений вида

.

Число членов равно количеству подмножеств множества , то есть . Поскольку коэффициент равен 0 или 1, то искомое число полиномов равно , то есть числу всех булевых функций от тех же переменных. Отсюда, как следствие, получаем единственность представления функций полиномом Жегалкина.

Пример 2. Представить функцию в виде полинома Жегалкина.

Будем искать выражение для данной функции в виде полинома с неопределенными коэффициентами:

.

При имеем ,

при имеем ,

при имеем ,

при имеем , то есть .

Отсюда .

Пример 2. Представить полиномом Жегалкина функцию, заданную таблицей истинности:

0 0 0
0 0 1

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

I. Представим заданную функцию совершенной д.н.ф.:

. (6)

Из формулы следует, что для булевых функций и , одновременно не обращающихся в 1 (), выполняется равенство . Такие функции называются ортогональными. Из последнего равенства следует, что логическая сумма для ортогональных слагаемых не изменяется, если операцию заменить на . Далее выполним следующий шаг, воспользовавшись этим результатом.

II. Заменим в выражении (6) все знаки на :

.

III. Заменим все отрицания по формуле , раскроем скобки и приведем подобные члены:

Из приведенных примеров следует, что существует целый ряд полных систем. Таким образом, для задания булевых функций можно использовать различные языки формул. Какой именно из языков является более удобным, зависит от характера рассматриваемой задачи.