ПОЛИНОМЫ ЖЕГАЛКИНА

Рассмотрим систему функций B = {x₁ x₂, x + 1}, где x₁ x₂ - это двоичное умножение.

Данная система является полной, поскольку x₁ x₂ совпадает с конъюнкцией x₁ & x₂, а x + 1 - это .

Пусть U - произвольная формула над B. Преобразуем ее по следующим правилам:

1) раскроем скобки в U; используя дистрибутивность сложения и умножения, получим сумму различных произведений переменных и констант 1;

2) в каждом произведении удалим все кратные вхождения одной и той же переменной (на основании тождества xx º x);

3) в каждом произведении переменных переставим переменные в порядке возрастания индексов (здесь применяется следующее тождество x_I & x_j º x_j & x_i);

4) удалим из полученной суммы все пары одинаковых слагаемых, используя тождество x + x º 0;

5) если в результате выполнения преобразований 1) – 4) получается пустая запись, то запишем результат в виде: 0.

Полученная в результате формула W, рассматриваемая с точностью до порядка записи слагаемых, носит название полинома Жегалкина.

Поскольку все преобразования, применявшиеся к исходной формуле U в процессе получения полинома W, являются эквивалентными преобразованиями, то полином W эквивалентен U.

Следовательно, всякая б.ф. представляется некоторым полиномом Жегалкина.

Пример. Рассмотрим функцию f = . Она имеет следующее табличное задание:

Общий вид полинома Жегалкина для функции двух переменных можно записать так: a x₁ x₂ + b x₁ +g x₂ + d, где a, b, g, d - неопределенные коэффициенты из E₂, значения которых для функции f необходимо уточнить.

В полином Жегалкина общего вида с неопределенными коэффициентами последовательно подставим все различные двоичные наборы значений переменных x₁ и x₂, и приравняем полученные выражения значениям функции на соответствующих наборах. При этом на каждом шаге удается уточнить значение одного из коэффициентов полинома.

Для нулевого набора значений переменных имеем:

f(0,0) =0, т.е. d = 0;

Для следующего набора(0, 1):

f(0, 1) =1, т.е. g = 1.

Аналогично, f(1, 0) = 1, т.е. b = 1.

Наконец, f(1, 1) = 1 и a = 1.

Следовательно, f(x₁, x₂) = x₁ x₂ + x₁ + x₂.

Упражнение

1. Определить количество слагаемых в полиноме Жегалкина общего вида для n переменных x₁, . . . , x_n.

2. Привести пример записи общего вида полинома Жегалкина от n переменных x₁, . . . , x_n.

ТЕОРЕМА 4.6

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

Доказательство

Покажем, что существует ровно различных полиномов Жегалкина, которые можно составить, используя символы переменных x₁, . . . , x_n.

1. С помощью символов переменных x₁, . . . , x_n можно составить разных произведений, в которых переменные располагаются слева направо в порядке возрастания индексов. К таким произведениям относится и пустое произведение, которое не содержит переменных и соответствует свободному члену полиномов Жегалкина.

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

При этом пустое подмножество множества всех таких произведений соответствует полиному, равному0.

Поэтому существует ровно различных полиномов, которые можно составить для переменных x₁, . . . , x_n.

Следовательно, число полиномов и число булевых функций для этих переменных совпадают. А так как каждая функция представляется некоторым полиномом, то такое представление единственно.

Справедливость данного заключения может быть проверена рассуждениями от противного с использованием комбинаторного правила птичьих гнезд.

Доказательство окончено.

Замечание. Если произвольный полином содержит вхождение некоторой переменной x_i, то такая переменная является существенной переменной для функции, представляемой этим полиномом.

Действительно, если полином Жегалкина W представляет f и содержит вхождение несущественной переменной x_i, то существует функция g, равная f и не имеющая x_i в качестве своей переменной. Тогда полином Жегалкина V, представляющий функцию g, не содержит вхождений переменной x_i.

Следовательно, f представляется двумя разными полиномами W и V, что невозможно в силу доказанной теоремы. Поэтому x_i является существенной переменной функции f.

Дата добавления: 2014-11-15; просмотров: 504; Нарушение авторских прав

Мы поможем в написании ваших работ!