2.2.3.2. Линейные функции

Определение. Арифметические функции в алгебре логики это сложение по модулю два и умножение (конъюнкция).

Определение. Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: , причем на каждом наборе все аij (j = 1, …, k) различны, aj Î {0, 1}.

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

Многочлен Жегалкина можно получить различными способами. Остановимся на рассмотрении построения многочлена Жегалкина с помощью треугольника Паскаля. Рассмотрим алгоритм на примере.

Пример 46.

Построить многочлен Жегалкина для функции f=10011110.

Решение.

Алгоритм построения многочлена Жегалкина:

Шаг 1. Строим таблицу (табл. 57). Первый столбец содержит возможные слагаемые полинома Жегалкина. Нулевому набору всегда соответствует слагаемое 1. Остальным наборам соответствует слагаемое, представляющее собой конъюнкцию переменных, которые на данном наборе принимают значение 1. Следующие n столбцов – всевозможные наборы из 0 и 1, соответствующие переменным. Далее столбец значений функции f. Функция g является вспомогательной, поэтому изначально этот столбец не заполнен.

Таблица 57

Шаг 2. Построение треугольника Паскаля.

Таблица 58

Шаг 3. Построение полинома Жегалкина. В полином войдут только те слагаемые, которым соответствует единица во вспомогательной функции g.

Для данной функции многочлен Жегалкина имеет вид:

f = 1 + x3 + x2 + x1 x3 + x1 x2 + x1 x2 x3.

Определение. Функция f(x1, x2, …, xn) называется линейной, если многочлен Жегалкина для нее имеет следующий линейный относительно переменных вид:

f(x1, x2, …, xn) = a1x1 + … + anxn + an+1, где каждое ai равно 0 или 1.

Булева функция из рассмотренного выше примера не является линейной.

Теорема. Класс L = {f | f = a0+a1x1+…+anxn, aiÎ{0, 1}} линейных функций замкнут относительно суперпозиций.