Обозначим через T0 класс всех булевых функций f(x1,x2,...,xn), сохраняющих константу 0, то есть функций, для которых выполнено равенство f(0,0,...,0)=0. Очевидно, что функции 0, x, x1& x2, x1Ú x2, x1Å x2 принадлежат классу T0, а функции 1, , x1® x2 в него не входят.
Поскольку таблица для функций f(x1,x2,...,xn) из класса T0 в первой строке содержит фиксированное значение 0, то в T0 попадает ровно половина всех булевых функций: .
Покажем, что T0 - замкнутый класс. Так как он содержит тождественную функцию, то для обоснования его замкнутости достаточно показать, что функция Ф=f(f1,...,fm) принадлежит классу T0, если только f, f1,..., fm принадлежат этому классу.
Обозначим через T1 класс всех булевых функций f(x1,x2,...,xn), сохраняющих константу 1; для них выполнено равенство f(1,1,...,1)=1. Этому классу принадлежат функции 1, x, x1& x2, x1Ú x2, x1® x2 и не принадлежат функции 1, , x1Åx2.
Покажем, что класс T1 состоит из функций, двойственных функциям из класса T0 (говорят, что класс T1 двойственен классу T0).
Пусть f(x1,x2,...,xn) принадлежит T1, т.е. выполняется равенство f(1,1,...,1)=1. Тогда, воспользовавшись определением двойственной функции, получим: f*(0,0,...,0)= ( , ,..., )= (1,1,...,1)=0. Это значит, что f*(x1,x2,...,xn) принадлежит классу T0.
Из взаимной двойственности классов T0 и T1 следует, что T1 также является замкнутым классом, и что он содержит столько же булевых функций, что и класс T0.
Класс самодвойственных функций
Класс S включает в себя все самодвойственные функции, то есть такие функции, для которых выполняется равенство: f(x1,x2,...,xn)=f*(x1,x2,...,xn). Очевидно, что функции x и самодвойственные (см. табл. 1.7). Менее тривиальным примером самодвойственной функции является функция h(x1,x2,x3)=x1x2 Ú x1x3 Ú x2x3. Составив двойственную к h функцию h* и преобразовав h*, легко убедиться, что это так. Для самодвойственной функции имеет место тождество:
f(x1,...,xn); (*)
иначе говоря, на наборах (a1,...,an) и , которые называются противоположными, самодвойственная функция принимает противоположные значения.
Навесим отрицания на (*) слева и справа:
`f(x1,...,xn); (**)
Отсюда следует, что самодвойственная функция полностью определяется своими значениями на первой половине строк, которых для n переменных будет 0.5×2n. Поэтому число самодвойственных функций, зависящих от переменных x1,...,xn, равно .
Докажем, что класс S замкнут. Поскольку он содержит тождественную функцию, достаточно показать, что функция Ф=f(f1,...,fm) является самодвойственной, если функции f, f1,..., fm самодвойственны. Последнее устанавливается непосредственно:
Ф*(x1,...,xn) =`Ф =`f (f1 ,...,fm ) = по (**)
=`f (`f1(x1,...,xn),...,`fm(x1,...,xn)) = `f (`f1,...,`fm) = по (*)
= f(f1,...,fm) =Ф(x1,...,xn).
Так как функции x и самодвойственные, а функции 0 и 1 самодвойственными не являются, то несамодвойственная функция одного переменного - это просто константа.
Лемма 1.1 (о несамодвойственной функции)
Если функция f(x1,...,xn) не принадлежит классу S, то из нее путем подстановки функций x и можно получить несамодвойственную функцию одного переменного, то есть константу.
Так как f(x1,...,xn) Ï S, то найдется хотя бы один набор (a1,...,an), такой, что выполняется равенство f =f (a1,...,an). Используя этот набор, составим функцию одной переменной y(x)=f . Вычислим значение этой функции в нуле:
y(0) = f( ) = f( ) = f(a1,...,an) = f( ) = y(1).
Так как y(0)= y(1), то y(x) - это константа.
Пример. Пусть f(x1,x2) = x1 | x2 . Тогда (a1,a2)=(0,1); y(x)=x0|x1=`x | x = 1.
Класс монотонных функций
Для двух наборов =(a1,...,an) и =(b1,..., bn), выполнено отношение предшествования , если a1£b1, ..., an£bn и хотя бы в одной координате i выполнено условие ai< bi.
Пример. (0, 1, 0, 1) (1, 1, 0, 1), а наборы (0, 1) и (1, 0) не сравнимы.
Функция f(x1,...,xn) называется монотонной, если для любых двух наборов и таких, что , имеет место неравенство: f( )£f( ). Например, функции 0, 1, x, x1&x2, x1Ú x2 монотонные, а функции , x1® x2, x1Åx2 монотонными не являются.
Обозначим через M множество всех монотонных функций. Покажем, что класс М замкнут. Поскольку тождественная функция принадлежит множеству M, то достаточно показать, что функция Ф=f(f1,...,fm) является монотонной, если функции f, f1,..., fm монотонны.
Пусть и - два набора длины n значений переменных x1,...,xn, причем . Так как функции f1,..., fm монотонны, то выполняются соотношения fi( )£fi( ) при 1 £ i £ m, , поэтому набор (f1( ),..., fm( )) предшествует набору (f1( ),..., fm( )) или они совпадают. В обоих случаях в силу монотонности функции f справедливо неравенство:
f (f1( ),..., fm( )) £ f (f1( ),..., fm( )),
откуда следует, что Ф ( ) £ Ф ( ), т.е. Ф - функция монотонная.
Наборы и называются соседними по i-й координате, если
Если функция f(x1,...,xn) не принадлежит классу M, то из нее путем подстановки констант 0 и 1 и функции x можно получить функцию .
Так как f(x1,...,xn) - немонотонная функция, то найдутся такие два набора и , что и при этом f( )>f( ). Если наборы и не являются соседними, то отличается от в t>1координатах. Так как предшествует , то такое различие означает, что эти t координат в наборе имеют значение 0, а в наборе - значение 1. Поставим между наборами и (t-1) промежуточных наборов так, чтобы выполнялось отношение предшествования . Наборы, стоящие в этой цепочке рядом, являются соседними. (Например, если =(0, 0, 0), а =(1, 1, 1), то получится цепочка (0, 0, 0) (0, 0, 1) (0, 1, 1) (1, 1, 1)).
Так как f( )>f( ), то, по крайней мере, на одной из этих пар соседних наборов - обозначим их через и ( ) - окажется, что f( )>f( ). Для определенности будем считать, что данные наборы имеют соседство по i-й координате и, следовательно,
Итак, j(0) > j(1). Это возможно только в том случае, когда j(0)=1, j(1)=0, т.е. j(х) = .
Пример. Пусть f(x1,x2) = x1 x2 . Тогда =(0,0), =(0,1); y(x) = 0 x =`x.
Класс L линейных функций содержит функции 0, 1, x, , x1Åx2 и не содержит функций x1&x2 и x1Ú x2. Выше было показано, что этот класс также замкнут.
Лемма 1.3 (о нелинейной функции).
Если функция f(x1,...,xn) не принадлежит классу L, то из нее путем подстановки констант 0 и 1 и функций x и , а также, быть может, путем навешивания отрицания над f можно получить функцию x1&x2.
Составим полином Жегалкина для функции f(x1,...,xn).
Так как f(x1,...,xn) - нелинейная функция, в полиноме Жегалкина найдется слагаемое, содержащее не менее двух множителей. Без ограничения общности можно считать, что среди этих множителей присутствуют x1 и x2. Тогда соответствующий полином можно представить в виде:
x1x2g12(x3,...,xn) Å x1g1(x3,...,xn) Å x2g2(x3,...,xn) Å g0(x3,...,xn),
причем в силу единственности полинома g12(x3,...,xn)¹0. Значит, найдется хотя бы один набор (a3,...,an) такой, что g12(a3,...,an)=1.
Введем обозначения a= g1(a3,...,an), b= g2(a3,...,an), c= g0(a3,...,an)
и составим вспомогательную функцию 2 переменных: f(x1,x2)=f(x1,x2,a3,...,an)= x1x2 Å ax1 Å bx2 Å c.
Рассмотрим функцию
Y(x1,x2)= f(x1Åb, x2Åa) Å ab Å c.
Преобразуем ее с учетом определения функции f(x1,x2):
Y(x1,x2)= f(x1Åb, x2Åa) Å ab Å c=(x1Åb)(x2Åa) Å a(x1Åb) Å b(x2Åa) Å c Å ab Å c=
= = x1x2.
Таким образом, с помощью нелинейной функции удалось построить конъюнкцию Y(x1,x2)= x1&x2.
Пример. Пусть f(x1, x 2, x3) = x1 x 2 x3 Å x1 x3 Å x 2 = x 2Ú x1 x3.
Тогда f(x1,x2) = x1 x 2 Å x1 Å x 2. Y(x1,x2) = x1x2.
Таблица 1.10
f
T0
T1
S
M
L
+
-
-
+
+
-
+
-
+
+
x
+
+
+
+
+
-
-
+
-
+
x1&x2
+
+
-
+
-
x1Ú x2
+
+
-
+
-
Таблица 1.10 не содержит двух одинаковых столбцов. Это хорошо иллюстрирует тот факт, что замкнутые классы T0, T1, S, M и L попарно различны (знак “+” здесь показывает, что функция содержится в классе, а “-” обозначает обратную ситуацию).
, x1® x2 в него не входят.
.
( 
, 
f(x1,...,xn); (*)
, которые называются противоположными, самодвойственная функция принимает противоположные значения.
`f(x1,...,xn); (**)
.
=`f (f1 
самодвойственные, а функции 0 и 1 самодвойственными не являются, то несамодвойственная функция одного переменного - это просто константа.
=f (a1,...,an). Используя этот набор, составим функцию одной переменной y(x)=f 
. Вычислим значение этой функции в нуле:
) = f( 
) = f(a1,...,an) = f( 
) = y(1).
=(a1,...,an) и 
=(b1,..., bn), выполнено отношение предшествования 
. Так как функции f1,..., fm монотонны, то выполняются соотношения fi( 
, ai+1,... an).
и 
, что 
- значение 1. Поставим между наборами 
и 
так, чтобы выполнялось отношение предшествования 
. Наборы, стоящие в этой цепочке рядом, являются соседними. (Например, если 
= x1x2.