Дискретная математика

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

4) свойства констант

Жегалкина, используя тождества:

суммы по модулю 2 элементарных конъюнкций различного количества переменных без

Линейной

Примеры линейных функций от 3-х переменных:

Если
то

Если формула

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

1. Существование

2. Докажем единственность.

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

Полином состоит

Сколько может быть различных слагаемых?

Столько, сколькими способами можно составить подмножеств из множества переменных.

Множество переменных

{x1}  x1 ;

1; конъюнкция без переменных

{x1, x2}  x1x2;

{x1, x2, x3}  x1x2x3;…

{x1, x2, x3, …, xn}  x1x2x3…xn.

Полином от

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

{{x1}} 

0; полином без слагаемых

{{x1}, {x1, x2}}  x1  x1x2
полином с 2 слагаемыми ;

{{x1}, {x1, x2}, {x1, x2, x3}} 
x1  x1x2  x1x2x3
полином с 3 слагаемыми ; и так далее.

 
Значит, между