ВУЗ:
Составители:
Рубрика:
40
Теорема
(о функциональной полноте). Для того, чтобы система
функций F={f
1
,…,f
n
} была полной, необходимо и достаточно,
чтобы она не содержалась целиком ни в одном из пяти замкнутых
классов T
0
,T
1
,S,M и L.
Доказательство
. Необходимость. Пусть F - полна, т.е. [F]=P
2
.
Предположим, что F содержится в одном из замкнутых классов,
который обозначим через F
′
, т.е. F
⊆
F
′
. Но тогда
P
2
=[F]
⊆
[F]
′
=F
′
- противоречие.
Достаточность. Пусть F не содержится ни в одном из пяти
замкнутых классов. Тогда из F можно выделить подсистему,
содержащую 5 функций f
i
, f
j
, f
k
, f
m
, f
l
, которые не содержатся
соответственно в классах T
0
,T
1
,S,M,L. Пусть эта подсистема будет
F
′
={f
i
,f
j
,f
k
,f
l
,f
m
}.
Можно считать, что все эти функции зависят от одинакового
числа переменных.
1.
Построим при помощи функций f
i
, f
j
и f
k
константы 0 и 1.
Рассмотрим f
i
∉
T
0
. Если f
i
(1,…,1)=1, то
ϕ
(x)=f
i
(x,…,x) есть
константа 1, т.к.
ϕ
(0)=f
i
(0,…,0)=1, в силу того, что f
i
∉
T
0
и
ϕ
(1)=f
i
(1,…,1)=1. Константу 0 получаем из f
j
: f
j
(1,…,1)=0.
Если f
i
(1,…,1)=0, то
ϕ
(x)=f
i
(x,…,x) есть x , т.к.
ϕ
(0)=f
i
(0,…,0)=1,
ϕ
(1)=f
i
(1,…,1)=0. Возьмем f
k
(f
k
∉
S). Из леммы о
несамодвойственной функции мы можем получить константу 0
или 1, а т.к. у нас есть функция
x , то мы можем получить и
вторую константу.
2.
Имея константу 0 и 1 и функцию f
m
(f
m
∉
M), мы по лемме о
немонотонности функции можем получить функцию
x
.
3.
Имея константы 0 и 1, функцию
x
и функцию f
l
(f
l
∉
L) мы
по лемме о нелинейной функции можем получить функцию x&y.
Таким образом, мы при помощи формул над F
′
(а значит и над
F) получили функции
x и x
1
&x
2
, что доказывает достаточность.
Страницы
- « первая
- ‹ предыдущая
- …
- 38
- 39
- 40
- 41
- 42
- …
- следующая ›
- последняя »
