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

Полином Жегалкина - полином(многочлен) над Z ₂, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики. Полином Жегалкина представляет собой сумму по модулю два (операция Исключающее ИЛИ) произведений неинвертированных переменных, а также (если необходимо) константы 1

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

Для получения полинома Жегалкина следует выполнить следующие действия:

1.Получить ДНФ функции

2.Все ИЛИ заменить на Исключающее ИЛИ

3.Во всех термах заменить элементы с отрицанием на конструкцию: («элемент» «исключающее ИЛИ» 1)

4.Раскрыть скобки по правилам алгебры Жегалкина и привести попарно одинаковые термы

Имеется 2-й способ нахождения полинома Жегалкина для функций, заданных в виде ДНФ. Этот способ основан на том, что х+1 =. Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило де Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как х+ х = 0), а нечетное число одинаковых слагаемых равно одному такому слагаемому.