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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Прокомментируем таблицу. Функции f
0
и f
15
суть константы 0 и
1. Далее,
f
3
(x
1
, x
2
) = x
1
, f
5
(x
1
, x
2
) = x
2
, f
12
(x
1
, x
2
) = ¬x
1
, f
10
(x
1
, x
2
) = ¬x
2
.
Остальные функции существенно зависят от обеих переменных:
f
1
(x
1
, x
2
) — конъюнкция, обозначается : x
1
· x
2
, x
1
∧ x
2
, x
1
& x
2
;
f
7
(x
1
, x
2
) — дизъюнкция : x
1
+ x
2
, x
1
∨ x
2
;
f
6
(x
1
, x
2
) — разделительная дизъюнкция
1
: x
1
⊕ x
2
, x
1
4 x
2
;
f
9
(x
1
, x
2
) — эквиваленция : x
1
≡ x
2
, x
1
⇔ x
2
;
f
13
(x
1
, x
2
) — импликация : x
1
⊃ x
2
, x
1
⇒ x
2
;
f
11
(x
1
, x
2
) — обратная импликация («x
1
если x
2
») : x
1
⊂ x
2
, x
1
⇐ x
2
;
f
2
(x
1
, x
2
) — коимпликация («x
1
не влечет x
2
») : x
1
6⇒ x
2
;
f
4
(x
1
, x
2
) — обратная коимпликация : x
1
: x
2
;
f
8
(x
1
, x
2
) — стрелка Пирса («ни x
1
, ни x
2
») : x
1
↓ x
2
;
f
14
(x
1
, x
2
) — штрих Шеффера («не x
1
или не x
2
») : x
1
| x
2
.
Упражнение 1. Как выразить |x
1
⊕ x
2
|, |x
1
↓ x
2
|, |(x
1
| x
2
)| через |x
1
| и |x
2
| ?
3. Функции и формулы
Для каждой из функций, рассмотренных в предыдущем пункте
и существенно зависящих от всех своих переменных, мы ввели логиче-
скую связку. Рассматривая общий случай, предположим, что имеется
некоторое множество связок, или функций Σ = {f
1
, f
2
, . . . , f
m
, . . .}.
Определение. Формулой над Σ называется выражение, индук-
тивно конструируемое по следующим правилам
1
:
(1) константы 0, 1 и переменные x
1
, x
2
, . . . , x
n
, . . . — формулы над
Σ;
(2) если F
1
, F
2
, . . . , F
n
— формулы над Σ, а f
i
(x
1
, x
2
, . . . , x
n
) —
функция от n переменных из Σ, то F = f
i
(F
1
, F
2
, . . . , F
n
) — формула
над Σ.
В последнем случае F
1
, F
2
, . . . , F
n
являются подформулами фор-
мулы F ; кроме того, подформулы всех формул F
1
, F
2
, . . . , F
n
являют-
ся также подформулами формулы F . Функция f
i
называется внешней
операцией формулы F . Результат применения функции f(x
1
, x
2
, . . . , x
n
)
к функциям f
1
(x
1
, x
2
, . . . , x
k
), f
2
(x
1
, x
2
, . . . , x
k
),. . . , f
n
(x
1
, x
2
, . . . , x
k
) на-
зывается суперпозицией функций f и f
1
, f
2
, . . . , f
n
.
1
Другое название — циклическое сложение , или сложение по модулю 2; в про-
граммировании используется обозначение: x
1
xor x
2
.
1
Аналогично определению логической формулы в п.1.2.
16

Страницы