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

Пусть дан набор из переменных . Надо найти число конъюнкций, не содержащих отрицание, полученных из этих переменных.

Всего их будет 2ⁿ.

Пример:

1) Пусть x ₁, x ₂, n = 2, тогда: 2) Пусть x ₁, x ₂, x ₃, n = 3, тогда:

конъюнкций всего

конъюнкций

Æ

Пусть – всевозможные конъюнкции, не содержащие отрицания и состоящие из переменных .

Определение. Выражение вида , называется
полиномом Жегалкина.