Алгебра Жегалкина

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

1) коммутативность сложения по модулю 2

;

2) ассоциативность сложения по модулю 2

;

3) дистрибутивность конъюнкции по отношению к сложению по модулю 2

,

4)

а также все тождества, истинные для конъюнкции.

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

,

.

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

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

,

где, .