1_Algebra_logiki

Полиномы

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

Теорема

Любую булеву функцию можно представить полиномом Жегалкина единственным образом.

Доказательство

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

Åñëè f(x1; : : : ; xn) = 0 ) задающий ее полином константа 0. Пусть f(x1; : : : ; xn) 6= 0

) для каждой булевой функции f(x1; : : : ; xn) найдется задающий ее полином.

Полиномы

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

Доказательство

Полиномы

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

Доказательство

2. Единственность.

Каждая переменная может входить или не входить в произведение.

Полиномы

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

Доказательство

2. Единственность.

Каждая переменная может входить или не входить в произведение.

соответствует константа 1

Полиномы

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

Доказательство

2. Единственность.

Полиномы

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

Доказательство

2. Единственность.

Всего всевозможныех произведения булевых переменных (x1 xn) 2n

Полиномы

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

Доказательство

2. Единственность.

Всего всевозможныех произведения булевых переменных (x1 xn) 2n

Каджому полиному соответствует подмножество из произведений

)

Полиномы

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

Доказательство

2. Единственность.

Всего всевозможныех произведения булевых переменных (x1 xn) 2n

Каджому полиному соответствует подмножество из произведений

)

Всевозможных полиномов 22n

Полиномы

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

Доказательство

2. Единственность.

Всего всевозможныех произведения булевых переменных (x1 xn) 2n

Каджому полиному соответствует подмножество из произведений

)

Полиномы

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

Доказательство

2. Единственность.

Всего всевозможныех произведения булевых переменных (x1 xn) 2n

Каджому полиному соответствует подмножество из произведений

)