2.5. Полнота и замкнутость
Мы видели, что каждая булева функция может быть выражена в виде формулы через элементарные функции ; x1Λx2; x1Vx2. Является ли этот набор случайным? Или есть и другие наборы функции, обладающие тем же свойством?
Определение. Система функций {f1, f2, …, fs, …} из P2 называется полной, если каждая булева функция может быть записана в виде формулы через функции этой системы.
Примеры полных систем.
1. Система P2 – полная система.
2. Система B={ ; x1Λx2; x1Vx2} – полная.
Теорема. Пусть даны две системы функций из P2
B={f1, …, fs, …} (I) и G={g1, …} (II),
относительно которых известно, что система I полна и каждая функция системы I выражается через функции системы II в виде формулы. Тогда система II будет полной.
Доказательство очевидно.
3. Система B={ ; x1Λx2} является полной.
Для доказательства этого используем теорему и тождество
x1Vx2=
4. Система B={ ; x1Vx2} является полной.
Это доказывается либо так же, как и в п.3, либо через принцип двойственности.
5. Система B={x1/x2} является полной.
Для доказательства в качестве системы I возьмем { ; x1Λx2}, а за систему II – систему {x1/x2}.
Легко видеть, что выполняются эквивалентности
=
x1/x2;
(x1/x2)/(
x1/x2)=
=
x1Λx2.
6. Система B={0; 1; x1Λx2; x1+x2} является полной.
Для доказательства за систему I возьмем { ; x1Λx2}, а за систему II – рассматриваемую систему В. Имеем равенства
х1+1= .
Конъюнкцию x1Λx2 будем обозначать для краткости и, по аналогии с обычным умножением, через x1x2.
Так как формула, построенная из полной системы 6 после раскрытия скобок и приведения подобных переходит в полином по модулю 2, получаем следующую теорему:
Теорема Жегалкина. Каждая функция из Р2 может быть выражена при помощи полинома по модулю 2 (полинома Жегалкина).
Посчитаем число полиномов Жегалкина от n переменных, число членов xi1…xis равно числу подмножеств (i1, …, is) из n чисел (1, …, n), т.е. равно 2n. Поскольку ai1…is равно либо 0, либо 1, то искомое число полиномов равно , т.е. числу всех булевых функций от тех же переменных следует, что каждая булева функция представляется полиномом Жегалкина единственным образом.
Пример 12. Выразить x1Vx2 в виде полинома Жегалкина.
Будем искать выражение для x1Vx2 в виде полинома с неопределенными коэффициентами.
x1Vx2= ax1x2+bx1+cx2+d
Таблица 9
-
x1
x2
(x1Vx2)
0
0
0
0
1
1
1
0
1
1
1
1
x1Vx2=
-x1x2+x1+x2
С понятием полноты тесно связано понятие замкнутости.
Определение: Пусть М – некоторое подмножество функций из Р2. Замыканием М называется множество всех функций, представимых в виде формул через функции множества М. Обозначается [M].
Нетрудно видеть, что замыкание инвариантно относительной операции введения и удаления фиктивных переменных.
Пример 13.
1) M=P2. Очевидно, что [M]=P2.
2) M={1, x1+x2}. Замыканием этого множества будет класс L всех линейных функций
f(x1, …, xn)= c0+ c1x1+…+ cnxn,
где ci=0; 1 (i=0, …, n); существенные переменные входят с коэффициентом 1, фиктивные – с коэффициентом 0.
Определение. Множество М называется замкнутым, если [M]=M.
Пример 14.
1) Множество M=P2 является замкнутым.
2) M={1, x1+x2} не замкнуто.
3) Множество M=L замкнуто, так как каждое линейное выражение, составленное из линейных выражений линейно.