Рассмотренные 5 классов функций используются при решении вопроса о функциональной полноте.
Критерий полноты системы булевых функций (теорема Поста) - система ∑ полна в том и только в том случае, если для каждого из классов T0,T1,S,L,M в системе существует функция, не принадлежащая этому классу; иначе говоря, система ∑ полна, если выполнены 5 условий:
1) в системе ∑ есть f1Функции f1-f5 - не обязательно различные.
Предварительно рассмотрим 3 утверждения, которые демонстрируют, как суперпозициями функций системы, удовлетворяющей условию теоремы Поста, выразить функции известных полных систем.
Лемма 1. Суперпозициями несамодвойственной функции
f(Xl,X2,...,Xn) и функции ┐Х можно получить функцию-константу. Если f S , то существует набор
(σ1,σ2,...,σn) такой, что
f(σ1,σ2,...,σ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(σ1,σ2,...,σn)= [поскольку 1σ=σ] = f(1σ1,1σ2,1σn)=φ(1) . Таким образом φ(0) = φ(1) , а это означает, что φ(Х) - константа.
Следствие. Из функции - ┐X и константы можно получить другую константу.
Лемма 2. Суперпозициями немонотонной функцию ┐X.
f(X1,X2,...,Xn) и функций-констант 0 и 1 можно получить функцию
Если f М, то существуют наборы
= (α1,α2,...,αn) и
= (β1,β2,...,βn) такие, что
<
, (т.е. αi<βi для i = l,2,...,n) и
f(
) > f(
), т.е. f(
)=1, f(
)=0. Пусть
= (γ1,γ2,...,γn) -набор,
где каждое γi - либо переменная X , либо константа и определяется следующим образом
Отметим, что если X = О , то =
; если X = 1 , то
=
. Пусть Ψ(X) = f(γ1,γ2,...,γ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,X2,σ3,...,σn)=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, то построение закончено; в противном случае, т.е. если
ψ(Х1,Х2) = Х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 . Возможны два случая.
По лемме 2, из функций f5 М и констант можно получить функцию ┐M
Как видим, в обоих случаях из функций системы могут быть построены обе константы и отрицание.
По лемме 3, из функций f4 L , отрицания ┐X и констант 0 и 1
можно получить конъюнкцию X
Y . В свою очередь, конъюнкция и отрицание образуют полную систему, чем и завершается доказательство теоремы Поста.
Для проверки конкретной системы на полноту можно заполнить для функций системы так называемую таблицу Поста: (таблица 1), в которой
исследуется система {X Y, X
Y} ("+" означает принадлежность функции данному предполному классу).
T0 | T1 | S | L | M | |
X ![]() |
+ | - | - | + | - |
X ![]() |
+ | + | - | - | + |
1 | - | + | - | + | + |
T0 | T1 | L | |
X ![]() |
+ | - | + |
X ![]() |
+ | + | - |
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.
0 | 1 | X | -X | X ![]() |
X ![]() |
X ![]() |
X ![]() |
X ![]() |
X | Y | X ![]() ![]() |
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 | объясняет название предполных классов: если к какому-нибудь из них, допустим 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, то для ее полноты достаточно, чтобы в ней содержались немонотонная функция и нелинейная функция. |
![]() |
Практические задания |
![]() |
Tест для самоконтроля |