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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

они содержат 1. Класс T
1
состоит из функций, двойственных функциям
из T
0
. Отсюда сразу можно сделать вывод о замкнутости класса T
1
.
L — класс всех линейных функций. Ему принадлежат константы
0, 1, тождественная функция x, функции x, x
1
⊕x
2
и не принадлежат
функции x
1
∧x
2
и x
1
∨x
2
. Класс L замкнут, так как является замыка-
нием системы функций {1, ⊕}.
S — класс всех самодвойственных функций, т.е. функций f ∈
Λ, удовлетворяющих условию f
∗
= f. Мы уже рассматривали такие
функции в п.3. Примерами самодвойственных функций могут служить
x, x, а также функция голосования.
Упражнение 5. Докажите, что функция голосования, определенная в п.1 § 2:
g(x
1
, x
2
, x
3
) = x
1
x
2
∨ x
1
x
3
∨ x
2
x
3
, является самодвойственной.
На противоположных наборах (α
1
, . . . , α
n
) и (α
1
, . . . , α
n
) са-
модвойственная функция принимает противоположные значения. От-
сюда следует, что самодвойственная функция полностью определяет-
ся первой половиной строк таблицы значений (или же, наоборот, вто-
рой). Поэтому число самодвойственных функций от n переменных рав-
но 2
2
n−1
=
√
2
2
n
. Замкнутость класса S следует из теоремы 3.
M — класс всех монотонных функций, т.е. функций f ∈ Λ, удо-
влетворяющих условию
α
1
6 β
1
, . . . , α
n
6 β
n
⇒ f(α
1
, . . . , α
n
) 6 f(β
1
, . . . , β
n
).
Монотонными функциями, очевидно, являются 0, 1, x, x
1
∧x
2
, x
1
∨x
2
и не являются x, x
1
⊕ x
2
.
Для доказательства замкнутости класса M покажем, что если f,
f
1
, . . . , f
m
∈ M, то F = f(f
1
, . . . , f
m
) ∈ M. Пусть α
i
6 β
i
(1 6 i 6 n).
Тогда f
i
(α
1
, . . . , α
n
) 6 f
i
(β
1
, . . . , β
n
) (1 6 i 6 n) и
F (α
1
, . . . , α
n
) = f(f
1
(α
1
, . . . , α
n
), . . . , f
m
(α
1
, . . . , α
n
)) 6
6 f(f
1
(β
1
, . . . , β
n
), . . . , f
m
(β
1
, . . . , β
n
)) = F (β
1
, . . . , β
n
).
Замкнутые классы T
0
, T
1
, S, M, L попарно различны, что видно
из следующей таблицы, в которой знак «+» означает принадлежность
функции, стоящей в первой колонке, указанному классу, а знак «−» —
противоположную ситуацию.
T
0
T
1
S M L
0 + − − + +
1 − + − + +
¬ − − + − +
33

Страницы