Глава 1

H'i. Полученная формула H' реализует функцию h и является формулой в базисе G. Теорема доказана.

Из доказанной теоремы и законов двойственности немедленно следует полнота систем {&, }и{ , }.

Пример 1.6.1. Покажем, что система {x y, x } является полной.

Так как x y = x y, то x y = x y, т.е. дизъюнкция двух переменных реализуется формулой в базисе из импликации и отрицания. Ранее было отмечено, что дизъюнкция и отрицание образуют полную систему.

Следовательно, в силу предыдущей теоремы система {x y, x } является полной.

Теорема 1.6.2. Для того чтобы система функций F была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из пяти замкнутых классов T0, T1, S, M и L.

Доказательство. Необходимость. Пусть система функций F

полна в P2. Предположим, что F целиком содержится в замкнутом классе R{T0, T1, S, M, L }. Тогда из свойств операции замыкания, включения F R и равенства [F] = P2 следует, что P2 = [F] = R. Поэтому, R = P2. С другой стороны каждый из классов T0, T1, S, M, L отличен от P2, т.е. R P2. Противоречие. Необходимость доказана.

Достаточность. Так как система функций F не содержится целиком ни в одном из пяти замкнутых классов перечисленных в условии теоремы, то в этой системе найдутся пять (не обязательно различных)

Следовательно, после отождествления переменных у функций fT0 и fT1

получаем либо (i) отрицание, либо (ii) две тождественные константы 0 и 1. Последовательно рассмотрим эти возможности.

(i) Так как fS не является самодвойственной, то найдутся такие противоположные наборы 1,..., k и 1,..., k , что

fS ( 1,..., k ) fS ( 1,..., k ) .

т.е. функция 1 является константой. Вторая константа получается из 1 и отрицания.

(ii) Так как fM не является монотонной, то найдутся такие соседние

Рассмотрим функцию 2 x fM g1 x ,..., gk x . Легко видеть, что

2 0 fM ( 1,..., k ) f4 ( 1,..., k ) 2 1 ,

т.е. 2 - отрицание.

Таким образом, из функций fT0 , fT1 , fS и fM получены константы и

отрицание.

Теперь, рассмотрим нелинейную функцию fL. В многочлене Жегалкина этой функции найдется слагаемое, содержащее не менее двух переменных. Без ограничения общности будем полагать, что это x1 и x2. Группируя слагаемые, содержащие x1, x2 и x1x2, преобразуем многочлен Жегалкина функции fL к виду

f1 x1,..., xk x1x2 f0 x3,..., xk x1 f1 x3,..., xk x2 f2 x2,..., xkf3 x2,..., xk

x1, x2 fM x1, x2, 3,..., k x1x2 1x1 2x2 3 ,

где i fi 3,..., k - константы. Положим

3 x1, x2 x1 2, x2 1 1 2 3 .

Легко видеть, что

3 x1, x2 x1 2, x2 1 1 2 3

x1 2 x2 1 1 x1 2 2 x2 1 3 1 2 3 x1x2

Таким образом, 3 x1, x2 x1x2 . Теперь утверждение теоремы следует из теоремы 1.6.1 и полноты системы функций {&, }.

Пример 1.6.2. Снова, как и в примере 1.6.1, докажем полноту

системы {x y, x }. Сделаем это при помощи теоремы 1.6.2. Легко видеть, что отрицание не сохраняет нуль, не сохраняет единицу и не является монотонной функцией. Многочлен Жегалкина импликации равен xy x 1. Следовательно, импликация не принадлежит классу линейных функций. Наконец заметим, что вес импликации равен трем, и поэтому, она не является самодвойственной функцией. Таким образом, система {x

y, x } не содержится целиком ни в одном пяти замкнутых классов T0, T1, S, M и L и в силу теоремы 1.6.2 является полной.

Пример 1.6.3. Используя теорему 1.6.2, исследуем полноту системы {x y, xy}. Так как 1 1 = 1 и 1 1 = 1, то очевидно, что импликация и конъюнкция сохраняют единицу. Следовательно, система {x y, xy} содержится в классе T1 и в силу теоремы 1.6.2. не является полной.

Пусть F - замкнутый класс в P2. Система булевых функций {f1,… , fi, …} называется базисом в F, если ее замыкание совпадает с F, а любая ее собственая подсистема не является полной в F. Рассмотренная в примере

1.6.2 система функций { x y, x } является базисом в P2. Эта система полна в P2, ее первая функция сохраняет единицу, а вторая является линейной и самодвойственной. Другая полная в P2 система функций {&,

} базисом не является, так как две ее собственные подсистемы {&, } и { , } полны в P2.

Булева функция f называется шефферовой, если [f] = P2. Очевидно, что каждая шефферова функция является базисом в P2.

Пример 1.6.4. Найдем все шефферовы функции в P2(2). Допустим, что f - шефферова, и f = (f1, f2, f3, f4) - вектор ее значений. Так как f T0 и fT1, то f1 = 1 и f4 = 0. Отсюда немедленно следует, что f M. Теперь посмотрим, какие значения могут принимать вторая и третья компоненты вектора f. Если f2 f3, то либо f = (1100), либо f = (1010). В обоих случаях f будет линейной самодвойственной функцией. Если f2 = f3, то либо f = (1000), либо f = (1110). Непосредственной проверкой легко убедиться, что каждый из этих векторов задает нелинейную и несамодвойственную функцию. Таким образом, в P2(2) содержится ровно две шефферовы функции: стрелка Пирса и штрих Шеффера.

Задачи

1.6.1.Выяснить, является ли множество A базисом в B:

a)A = {xy z}, B = T1;

b)A = {xy z}, B = T0;

c)A = {x y, x y}, B = L;

d)A = {x1 x2 … xk , 1}, k - константа, B = L;

1.6.2.Выяснить, при каких n функция f является шефферовой:

a)f(x1, …, xn) = 1 x1x2 … xixi+1 … xn - 1xn xnx1;

b)f(x1, …, xn) = 1 x1x2 … xixi+1 … xn - 1xn;

c)f(x1, …, xn) = 1 1 i j n xi x j ;

d)f(x1, …, xn) = 1 (x1 | x2 ) … (xi | xi+1) … (xn – 1 | xn) (xn | x1);

e)f(x1, …, xn) = 1 (x1 | x2) … (xi | xi+1) … (xn – 1 | xn);

f)f(x1, …, xn) = 1 (x1 x2 ) … (xi xi+1) … (xn – 1 xn)

1.6.3.Доказать, что если f монотонна и существенно зависит не

менее чем от двух переменных, то система {0, f } полна в P2.

1.6.4. Набор из Bn назовем нижней единицей монотонной функции f, если f() = 1 и f() = 0 для каждого . Пусть монотонная функция f

имеет ровно две нижние единицы. Доказать, что f - шефферова.

1.6.5. Найти число шефферовых функций в:

а) Р2(3); b) P2(4); c) P2(5); d)P2(n).