назад

2.6 Критерий полноты системы булевых функций

Рассмотренные 5 классов функций используются при решении вопроса о функциональной полноте.

Критерий полноты системы булевых функций (теорема Поста) - система ∑ полна в том и только в том случае, если для каждого из классов T0,T1,S,L,M в системе существует функция, не принадлежащая этому классу; иначе говоря, система ∑ полна, если выполнены 5 условий:

1) в системе ∑ есть f1 T0 ,
2) в системе ∑ есть f2 T1 ,
3) в системе ∑ есть f3 S ,
4) в системе ∑ есть f4 L ,
5) в системе ∑ есть f5 М .

Функции f1-f5 - не обязательно различные.

Предварительно рассмотрим 3 утверждения, которые демонстрируют, как суперпозициями функций системы, удовлетворяющей условию теоремы Поста, выразить функции известных полных систем.

Лемма 1. Суперпозициями несамодвойственной функции f(Xl,X2,...,Xn) и функции ┐Х можно получить функцию-константу. Если f S , то существует набор 12,...,σn) такой, что

f(σ12,...,σn) = f(┐σ1,┐σ2,...,┐σn)         (*)

Построим суперпозицию φ(Х) = f(Xσ1,Xσ2,...,Xσn) , где вместо каждого переменного функции f подставляется либо X , либо ┐X . Тогда φ(0) = f(0σ1,0σ2,...,0σn)= [поскольку 0σ = ┐σ] = f(┐σ1,┐σ2,...,┐σn) = [ввиду (*] = f(σ12,...,σn)= [поскольку 1σ=σ] = f(1σ1,1σ2,1σn)=φ(1) . Таким образом φ(0) = φ(1) , а это означает, что φ(Х) - константа.

Следствие. Из функции - ┐X и константы можно получить другую константу.

Лемма 2. Суперпозициями немонотонной функцию ┐X. f(X1,X2,...,Xn) и функций-констант 0 и 1 можно получить функцию Если f М, то существуют наборы = (α12,...,αn) и = (β12,...,βn) такие, что <, (т.е. αii для i = l,2,...,n) и f() > f(), т.е. f()=1, f()=0. Пусть = (γ12,...,γn) -набор, где каждое γi - либо переменная X , либо константа и определяется следующим образом

Отметим, что если X = О , то = ; если X = 1 , то = . Пусть Ψ(X) = f(γ12,...,γn) . Тогда Ψ(0) = f(┐α) = l; Ψ(1) = f(┐β) = 0, т.е. Ψ(X)=┐X.

Лемма 3. Суперпозициями нелинейной функции f(Xl,X2,...,Xn) , функции ┐Х и функций-констант 0 и 1 можно получить конъюнкцию XY.

Построим для функции f многочлен Жегалкина. В силу нелинейности f среди слагаемых найдется содержащее не менее 2 множителей. Пусть это переменные Х1 и Х2 . Тогда все слагаемые разбиваются на 4 группы: содержащие обе переменные Х1 и Х2 , только одну из них Х1 или Х2 и не содержащие ни одной. Объединяя слагаемые и вынося за скобки соответствующие множители в каждой из трех первых групп, получим:

f(X1,X2,X3,...,Xn)=X1∙X2g1(X3,...,Xn)X1∙g2(X3,...,Xn)X2g3(X3,...,Xn)g4(X3,...,Xn).

Функции g1-g4 зависят от переменных Х3,...,Хn , причем g1 не равна тождественно 0, - иначе не было бы ни одного слагаемого с произведением Х1∙Х2. Подставим в функцию f вместо переменных Х3,...,Хn тот набор констант σ3,...,σn , для которого g1(X3,...,Xn} = 1 ; при этом функции g2,g3,g4 обращаются в некоторые константы; обозначим их соответственно α,β,γ. Получим функцию двух переменных

φ(X1,X2)=f(X1,X23,...,σn)=X1∙X2α X1 βX2 γ

Теперь произведем еще одну подстановку: в функцию φ(X1,X2) подставим функцию (Х1 β ) вместо Х1 и (Х2 α) вместо Х2. В зависимости от значений α и β каждая из этих функций представляет собой либо Xi , либо ┐Хi , так что фактически мы подставляем либо переменную, либо ее отрицание. Получаем функцию ψ(Х1, Х2) , равную (Х1 β)(Х2 α) α(Х1 β) β(Х2 α) γ= [после раскрытия скобок] = Х1 ∙ Х2 βХ2 αХ1 α β αХ1 αβ βX2 αβ γ = [после сокращений] = Х1 ∙ Х2 αβ γ , т.е. сумму по модулю 2 конъюнкции и константы (αβ γ). Если последняя равна 0, то построение закончено; в противном случае, т.е. если ψ(Х12) = Х1∙X2 1, то нужно подставиты ψ(X1,X2) в функцию ┐X : ┐(X1∙X2 1)=X1∙X2

Теперь доказательство теоремы Поста уже достаточно просто. Необходимость следует из сделанного выше замечания: если все функции системы принадлежат какому-нибудь из 5 классов (обозначим его Q), то в силу замкнутости класса Q все суперпозиции функций системы также принадлежат ему; в то же время в Р2 есть функции, которые не принадлежат Q , что означает неполноту системы.

Достаточность выводится из лемм 1 -3. Пусть в системе есть функции f1 T0, f2 T1, f3 S, f4 L, f5 M (некоторые из них могут совпадать). Суперпозиция h1(X) = f1(X,X,...,X) - функция одной переменной, имеющая столбец значений (1,α)T ; аналогично, h2(X) = f2(X,X,...,X) - функция со столбцом значений (β,0)T . Возможны два случая.

  1. α = 0 или β = 1. Тогда h1(X) или h2(X) - функция ┐Х . По лемме 1 , из функций f3 S и ┐X можно получить константы 0 и 1 .
  2. в противном случае α = 1 и β = 0 . Тогда h1(Х) 1 , h2(X) 0 .

По лемме 2, из функций f5 М и констант можно получить функцию ┐M

Как видим, в обоих случаях из функций системы могут быть построены обе константы и отрицание.

По лемме 3, из функций f4 L , отрицания ┐X и констант 0 и 1 можно получить конъюнкцию XY . В свою очередь, конъюнкция и отрицание образуют полную систему, чем и завершается доказательство теоремы Поста.

Для проверки конкретной системы на полноту можно заполнить для функций системы так называемую таблицу Поста: (таблица 1), в которой исследуется система {X Y, X Y} ("+" означает принадлежность функции данному предполному классу).


Таблица 1
  T0 T1 S L M
X Y + - - + -
X Y + + - - +
1 - + - + +

Таблица2
  T0 T1 L
X Y + - +
X Y + + -
1 - + +

Принадлежность трех данных функций классам T0 и T1 проверяется по их таблицам очень просто. Также несложно проверить принадлежность их классу М (заметим, что если f T1 и не равна 0 тождественно, то она не монотонна). Очевидно также, что (X Y) ≥ L, свойство (X Y) S следует из соотношения

(X Y)*= ┐(┐X ┐Y)=(X 1) (Y 1) 1=X Y 1 X Y

Функция (X Y) не самодвойственна, поскольку двойственная ей, как мы знаем, другая функция - конъюнкция. Далее, (X Y) нелинейна, так как ее многочлен Жегалкина XY X Y содержит произведение X ∙ Y . Легко проверяется также заполнение последней строки таблицы 1 - для функции-константы 1. Наконец, согласно теореме Поста, для полноты системы в каждом столбце таблицы Поста должен быть хотя бы один минус.

В таблице 3 для каждого из пяти рассмотренных выше классов T0,T1,S,L,M знаками "+" и "-" показана принадлежность ему ряда известных функций: всех 4 функций одной переменной, 6 функций двух переменных и 2 функций трех переменных. В отличие от предыдущей таблицы функции здесь представлены столбцами. Заметим, что в каждой строке таблицы имеется знак"-"; другими словами, для каждого из пяти классов есть не принадлежащая ему функция и, следовательно, ни один из них не совпадает с множеством всех логических функций Р2, а каждый является частью Р2.

Таблица 3
  0 1 X -X X Y X Y X Y X Y X Y X | Y X Y Z m3(X,Y,Z)
T0 + - + - + + - - + - + +
T1 - + + - + + + + - - + +
S - - + + - - - - - - + +
L + + + + - - - + + - + -
M + + + - + + - - - - - +

Из таблицы 3 можно заключить, что система состоящая из одной функции - штриха Шеффера X | Y - полна.

Система функций G называется независимой, если никакая функция f этой системы не выражается через остальные, т.е. f не принадлежит замыканию системы G\{f}. Независимая система функций G называется базисом замкнутого класса К, если всякая функция F ≥ К есть суперпозиция функций из G . Можно определить понятие базиса и так: базис замкнутого класса К - система функций, замыкание которой равно К, причем любое подмножество К (кроме самого К ) уже не обладает этим свойством.

Примеры

1) Система {┐, } -независимая.

2)Система {┐, , } не является независимой, поскольку, как мы знаем, можно выразить через и ┐ или, наоборот, - через и ┐.

3) Система {, ,1} - независима, в чем можно убедиться, построив для нее фрагмент таблицы Поста (таблица 2). Действительно, для каждой из трех функций в этой таблице имеется класс, которому она не принадлежит, но принадлежат две остальные и, следовательно, все их суперпозиции.
В примерах 1-3 представлены полные системы функций. Теперь рассмотрим пример независимой системы для замкнутого класса, не совпадающего с Р2.

Система {0,} не полная, так как обе функции линейны, и представляет базис класса L . Действительно, ┐Х = X О , ┐0 = 1, X Y = ┐(X Y) = (X Y) 0 , а каждая линейная функция выражается через (X Y) и ┐Х . Независимость функций системы также легко проверить (O T0, 0 T1, ≥ T0, ≥ Т1).

Некоторые следствия теоремы Поста.
Следствие 1Всякий замкнутый класс Q Р2 содержится целикомхотя бы в одном из 5 предполных классов T0,T1,S,L,M : иначе онпредставлял бы полную систему и, в силу замкнутости, равнялся бы P2 .
Следствие 2 объясняет название предполных классов: если к какому-нибудь из них, допустим S , (для других классов рассмотрение аналогичное) добавить любую не принадлежащую ему функцию h, то замыкание системы S U {h} совпадает с Р2. Действительно, система S U {h} шире, чем S и, в то же время, не может входить в какой-либо из остальных 4 классов, так как тогда в нем содержался бы целиком класс S , что противоречит замечанию в конце предыдущего параграфа.Иначе говоря, между предполным классом и Р2 не может существовать промежуточный замкнутый класс. Отсюда
Следствие 3 В Р2 существуют лишь 5 предполных классов, т.е. обладающих свойством, сформулированным в следствии 2. Это рассмотренные нами T0,T1,S,L,M .
Следствие 4 Из лемм 1-3 и доказательства теоремы можно заключить, что если в системе функций присутствуют константы 0 и 1, то для ее полноты достаточно, чтобы в ней содержались немонотонная функция и нелинейная функция.

 

Вопросы для самоконтроля

  1. Сформулируйте критерий полноты системы булевых функций Лемму 1, Лемму 2, Лемму 3.
  2. Докажите эти теоремы.

Практические задания

Tест для самоконтроля