Дискретная математика. Алгебра Жегалкина презентация

Алгебра Жегалкина
Алгеброй Жегалкина называется алгебра вида .
В алгебре Жегалкина действуют тождества:

Тождества алгебры Жегалкина
1) коммутативность сложения по модулю 2:
2) ассоциативность сложения по модулю 2:
3) дистрибутивность конъюнкции по отношению к сложению по модулю 2:
4) свойства констант

Формулы перехода
От любой булевой формулы можно перейти к формуле алгебры Жегалкина, используя тождества:

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

Линейная функция
Линейной функцией называется функция, полином Жегалкина которой имеет вид:
Примеры линейных функций от 3-х переменных:

Утверждение 1
Если
то

Утверждение 2
Если формула F – СДНФ, то при переходе к формуле алгебры Жегалкина достаточно заменить символы дизъюнкции ( )на символ сложения по модулю 2 ( ).

Пример 1

Пример 2 Дана СДНФ:

Теорема (о существовании и единственности полинома Жегалкина логической функции)
У каждой логической функции существует и единственен полином Жегалкина.

Доказательство:
1. Существование полинома уже доказано.
2. Докажем единственность.
Для этого установим взаимно однозначное соответствие между полиномами и логическими функциями от n переменных.

Доказательство:
Полином состоит из слагаемых – конъюнкций переменных без отрицаний.
Сколько может быть различных слагаемых?
Столько, сколькими способами можно составить подмножеств из множества переменных.

Множество переменных имеет вид: U={x1, x2, x3, …, xn}.
{x1} ⇔ x1 ;
∅⇔1; конъюнкция без переменных
{x1, x2} ⇔ x1x2;
{x1, x2, x3} ⇔ x1x2x3;…
{x1, x2, x3, …, xn} ⇔ x1x2x3…xn.

Доказательство:
Полином от полинома отли-чается составом слагаемых.
Значит, сколько подмножеств множества слагаемых можно образовать, столько и будет полиномов.

{{x1}} ⇔ x1
полином с одним слагаемым ;
∅⇔0; полином без слагаемых
{{x1}, {x1, x2}} ⇔ x1 ⊕ x1x2
полином с 2 слагаемыми ;
{{x1}, {x1, x2}, {x1, x2, x3}} ⇔
x1 ⊕ x1x2 ⊕ x1x2x3
полином с 3 слагаемыми ; и так далее.