3.4 Полнота системы булевых функций
Система булевых функций {f1 (x11,...,x1p1),...,fs (xs1,...,xsps),...} называется полной, если для любой булевой функции f (x1,...,xn) можно построить равную её функцию, представляющую собой результат суперпозиции функций {f1,...,fs,...} и x1,...,xn .
Примерыполных систем булевых функций.
x
1x2,
x1 ٧x2,x1.
Полнота следует из того, что для каждой
функции можно построить совершенные
ДНФ и КНФ.x1x2,x1. Полнота следует из п.1 и равенства х1 ٧х2 = х1х2 .
x
1
٧x2
, x1.
Полнота следует из п.1 и равенства х1х2
=х1
٧х2
.х1х2, х1 х2, 1. Полна, так какх1 = х1 1, а система x1x2,x1 является полной (п.2).
Теорема 3. Любую булеву функцию f (x1,...,xn) можно представить в виде полинома
f (x1,x2,...,xn) = a0 a1x1 a2x2 ...a2n-1x1…xn,
гдеai {0,1}, i = 0, 1,...,2n-1.
Доказательство. Система функций х1х2, х1 х2, 1, 0 полна. Пользуясьправилами
A A = 0, A ∙ A = A, A0 = A,
A ∙ 0 = 0, A ∙ 1 = A, A ∙ B = B ∙ A,
A B = BA, (AB) ∙ C = A ∙ CB ∙ C,
к
оторые
легко проверить, получим представление
функции в виде полинома по модулю 2.
Легко показать, что представление функции в виде полинома по модулю два является единственным.
Как обнаружить полноту или неполноту булевых функций? Для решения этого вопроса познакомимся с пятью классами булевых функций.
Класс функций, сохраняющих ноль
Функция f (x1,...,xn) называется сохраняющей ноль, если она на наборе из нулей принимает значение 0, т.е. f (0,...,0) = 0.
Так, функции x1x2 , x1 ٧x2, х, 0 – сохраняют ноль, функции x1 х2,х, 1 – не сохраняют.
Лемма 1.Из функций, сохраняющих ноль, суперпозицией можно получить только функции, сохраняющие ноль.
Доказательство.Поскольку функции, равные переменным, сохраняют ноль, достаточно показать, что функция
Φ (х1,...,хn) = f (f1 (x1,...,xn),..., fm (x1,...,xn))
сохраняет ноль, если функции f, f1,...,fm сохраняют ноль. Последнее следует из
f
(f1 (0,...,0),...
fm (0,...,0))
= f (0,...,0) = 0.
Следствие.Полная система булевых функций должна содержать хотя бы одну функцию, не сохраняющую ноль.
Класс функций, сохраняющих единицу
Функция f (x1,...,xn) называется сохраняющей единицу, если она на наборе из единиц принимает значение 1, то есть f (1,..,1) = 1.
Так, функции x1x2 , x1 ٧x2, х, 1 – сохраняют единицу, функции
x1 х2,х, 0 – не сохраняют.
Лемма 2.Из функций, сохраняющих единицу, суперпозицией можно получить только функции, сохраняющие единицу.
Доказательствоочевидно.
Следствие.Полная система булевых функций должна содержать хотя бы одну функцию, не сохраняющую единицу.
Класс самодвойственных функций
Функция f (x1, ... ,xn) называется самодвойственной, если
f (x1, ... ,xn) =f (x1,…,xn). Например, x ,x – самодвойственные функции, x1x2, x1 ٧x2 - несамодвойственные.
Лемма 3.Из самодвойственных функций путём суперпозиции можно получить только самодвойственные функции.
Доказательство. Пусть f (y1, ... ,ym), f1 (x1, ... ,xn),...,fm (x1, ... ,xn) самодвойственные функции. Надо показать, что
Φ (x1,...,xn) = f (f1 (x1,...,xn),..., fm (x1,...,xn)) самодвойственная.
Из цепочки равенств
Φ (x1,…,xn) =f (f1 (x1,…,xn),…,fm (x1,…,xn)) =
f
(f1
(x1,…,xn),…,fm
(x1,…,xn))
= f (f1(x1,…,xn),…,fm
(x1,…,xn))
= 
= Φ (x1,...,xn) следует, что Φ (x1,...,xn) – самодвойственна.
Следствие. Полная система функций должна содержать хотя бы одну несамодвойственную функцию.
Лемма 4. Из несамодвойственной функции подстановкой x иx можно получить константу.
Доказательство. Функция f (x1, ... ,xn) несамодвойственная, поэтому найдется набор = (1,...,n) такой, что f (1,..., n) = f (1,...,n). По набору = (1,...,n) определяются вспомогательные функции
i (x) (i = 1,2...,n),
x,еслиi= 0,
i(x) =
x, еслиi= 1.
Функция i (x) обладает свойством i(0) = i, i(1) = i .
Рассмотрим функцию
(x) = f (1(x),
... , n(x)).
Она получена из функции f (x1,
... ,xn)
подстановкой x иx.
Функция
(x) – константа, так как 
(0) = f (1(0),...,n(0))
= f (1,...,n)
= f (1,...,n)
=
= f (1(1),..., n(1)) = (1).