Билет 19.

СПНФ, построение и свойства. Полином Жегалкина.

Полиномиальная форма

Используют запись в полиномиальной форме, вместо дизъюнкции используют .

При записи в форме СДНФ для каждого набора j из T1 равен 1 будет только 1 минтерм, вместо дизъюнкции можно , т.е.

f(x1,x2,…,xn)= = все инверсии можно заменить Это СПНФ.

x y = x y (x & y)

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

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:

1. Хотя бы одна функция, не сохраняющая 0.

2. Хотя бы одна функция, не сохраняющая 1.

3. Хотя бы одна нелинейная функция.

4. Хотя бы одна немонотонная функция.

5. Хотя бы одна несамодвойственная функция.

Этому требованию отвечает система функций . На её основе и строятся полиномы Жегалкина.

Ф=а a1x1 ..anxn a12x1x2 … a1nx1xn, где а=(0,1)

Дата добавления: 2015-07-26