Логические основы построения цифровых автоматов. Определение функционально полной системы функций алгебры логики. Примеры полных систем. Полином Жегалкина. Его построение по таблице истинности и по СДНФ. Теорема Жегалкина.

Определение. Система функций {f₁, f₂, ..., f_s, ...}ÌP₂ называется полной в Р₂, если любая функция f(x₁, ..., x_n) Î P₂ может быть записана в виде формулы через функции этой системы.

Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина.

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

f(x₁, ..., x_n) Î P₂, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как {x₁&x₂, x₁Å(Круг с плюсом)x₂, 0, 1} полна в Р₂. В силу свойства x & (yÅz) =xy Å xz можно раскрыть все скобки, привести подобные члены, и 

С помощью эквивалентных преобразований СДНФ

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

x1	x2	x3	x4	f(x1,x2,x3,x4)
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	1
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	1
1	1	0	1	0
1	1	1	0	1
1	1	1	1	0