Алгебра жегалкина
Определение. Полиномом Жегалкина для n логических переменных называется полином, являющийся суммой константы и различных одночленов, в которые все пере-
менные входят не выше, чем в первой степени:
a 
x
x
… x
, ( 1 d k d n
)
причем в каждом наборе ( i
, , i
) все i
различны, а суммирование по
mod 2 ведется по некоторому множеству таких не совпадающих
наборов.
Например, 1 x x x
, x x x
x xx - некоторые полиномы Жегалкина для
двух и трех переменных соответственно.