Алгебра высказываний. Многочлены Жегалкина. (Лекция 4)

и единицы, называется многочленом (полиномом) Жегалкина.

Определение 1

Приведения булевой функции к многочлену Жегалкина (способ 1)
1)Приводим функцию к ДНФ.
2)Избавляемся от всех дизъюнкций с помощью законов Моргана.
3)Избавляемся от всех отрицаний.
4)Раскрываем все скобки.
5)Упрощаем полученное выражение.

дизъюнкцию на сложение по модулю 2
3)Избавляемся от всех отрицаний.
4)Раскрываем все скобки.
5)Упрощаем полученное выражение.

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