Тема 9.2. Алгебра Жегалкина и линейные функции

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

В алгебре Жегалкина выполняются следующие соотношения:

;

;

;

.

Кроме того, выполняются соотношения, ранее сформулированные булевой алгебры, относящиеся к конъюнкции и константам. Отрицание и дизъюнкция выражаются так:

;

;

.

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

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

Пример 9.2: Составить полиномы Жегалкина для данных функций:

а) ,

б) .

Заметим, что если в полученных полиномах Жегалкина произвести обратную замену функций, то получим упрощённые формулы булевой алгебры.

Теорема: Для всякой логической функции существует полином Жегалкина и притом единственный.

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

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

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

Если функция задана таблично, то для построения реализующего её многочлена Жегалкина можно применить метод неопределённых коэффициентов. Сопоставим -ому набору значений переменных в таблице положительную конъюнкцию переменных, равных 1 в этом наборе. Тогда для получения нужного многочлена Жегалкина достаточно определить все коэффициенты , в выражении

Подставляя в это равенство значения переменных из набора , , мы получим линейных уравнений относительно неизвестных коэффициентов . Решив эту систему, получим требуемый многочлен Жегалкина. Эта система треугольная и легко решается «сверху – вниз»: каждое определяется по значениям из уравнения, соответствующего набору .

Пример 9.3: Рассмотрим в качестве примера функцию , заданную следующей таблицей.

	1.

Многочлен Жегалкина для неё (как и для любой функции от 3-х переменных) представляется в виде:

(Для сокращения записи в формуле опущены конъюнкции).

В этом представлении в индексах у коэффициентов перечислены переменные, входящие в соответствующие конъюнкции.

Последовательно подставляя значения переменных и функции из таблицы, получаем:

Следовательно, функция представляется многочленом Жегалкина:

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

Все функции от одной переменной линейны. Также линейными являются функции эквивалентность и исключающее или.

Дата добавления: 2015-10-28