Элементы математической логики. Фролов И.С. - 35 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

5. Теорема о функциональной полноте
Теорема 4. Для того чтобы система логических функций Σ была
функционально полной, необходимо и достаточно, чтобы она целиком
не содержалась ни в одном из пяти замкнутых классов T
0
, T
1
, S, M и
L.
Иными словами, критерием функциональной полноты системы
функций является наличие в ней:
1) функции, не сохраняющей 0;
2) функции, не сохраняющей 1;
3) несамодвойственной функции;
4) немонотонной функции;
5) нелинейной функции.
Доказательство основывается на следующих трех леммах.
Лемма 1. Если f — несамодвойственная функция, то из нее
путем подстановки функций x и x можно получить константу.
Так как f /∈ S, то найдется набор (α
1
, . . . , α
n
) такой, что
f(α
1
, . . . , α
n
) = f(α
1
, . . . , α
n
). Подставим в f на место i-го аргумента
функцию f
i
(x) = x
α
i
(1 6 i 6 n): F (x) = f(x
α
1
, . . . , x
α
n
). Эта функ-
ция — константа, так как
F (0) = f(0
α
1
, . . . , 0
α
n
) = f(α
1
, . . . , α
n
) =
= f(α
1
, . . . , α
n
) = f(1
α
1
, . . . , 1
α
n
) = F (1).
Лемма 2. Если f — немонотонная функция, то из нее путем под-
становки констант 0 и 1 и тождественной функции x можно получить
функцию x.
Пусть f /∈ M. Тогда найдутся наборы (α
1
, . . . , α
n
) < (β
1
, . . . , β
n
)
1
такие, что f(α
1
, . . . , α
n
) = 1 > f(β
1
, . . . , β
n
) = 0. Построим цепочку
наборов
(α
1
, . . . , α
n
) = (α
0
1
, . . . , α
0
n
) < (α
1
1
, . . . , α
1
n
) < . . .
. . . < (α
k
1
, . . . , α
k
n
) = (β
1
, . . . , β
n
),
в которой каждая пара соседних наборов различается только в одной
компоненте. Очевидно, найдется такая пара соседних наборов, для ко-
торых f(α
i
1
, . . . , α
i
n
) = 1, f(α
i+1
1
, . . . , α
i+1
n
) = 0, причем отличие заклю-
чено лишь в компоненте j:
1
Это означает, что α
1
6 β
1
, . . . , α
n
6 β
n
, и хотя бы в одном случае неравенство
строгое.
34

Страницы