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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Лемма 1. Для любой формулы A имеет место секвенция
A ` ¬¬A.
A, ¬A ` A
A, ¬A ` ¬A
¾
A ` ¬¬A.
Лемма 2. Для любых формул A и B имеет место секвенция
A ⇒ B, ¬A ⇒ B ` B.
Пусть Γ = {A ⇒ B, ¬A ⇒ B}; тогда
Γ, ¬B, A ` B (MP)
Γ, ¬B, A ` ¬B
¾
Γ, ¬B ` ¬A (прив. к абсурду),
Γ, ¬B, ¬A ` B (MP)
Γ, ¬B, ¬A ` ¬B
¾
Γ, ¬B ` ¬¬A (прив. к абсурду).
Еще раз применяя правило приведения к абсурду, получим:
Γ ` ¬¬B ` B.
Лемма 3. Пусть A — формула; L
1
, . . . , L
k
— атомы, входящие в
A; I — интерпретация этих атомов. Пусть
L
0
i
=
½
L
i
при |L
i
| = 1,
¬L
i
при |L
i
| = 0,
и точно так же A
0
=
½
A при |A| = 1,
¬A при |A| = 0.
.
Тогда L
0
1
, . . . , L
0
k
` A
0
.
Поскольку формулировка этой леммы не простая, проиллюстрируем ее на
примере. Для формулы A = (¬L
1
⇒ L
2
) таблица значений имеет вид:
L
1
L
2
A
0 0 0
0 1 1
1 0 1
1 1 1
Каждая строка таблицы задает некоторую интерпретацию; первой строке со-
ответствует секвенция ¬L
1
, ¬L
2
` ¬(¬L
1
⇒ L
2
), второй строке — секвенция
¬L
1
, L
2
` (¬L
1
⇒ L
2
) и т.д.
Доказательство проведем индукцией по числу связок n, входящих
в состав формулы A.
Пусть n = 0. Тогда A состоит из одного атома: A = L
1
, и доказа-
тельство леммы сводится к проверке секвенции L
1
` L
1
при |L
1
| = 1 и
¬L
1
` ¬L
1
при |L
1
| = 0.
Пусть утверждение леммы верно для любой формулы с числом
связок m < n. Внешней связкой формулы A может являться либо ¬,
либо одна из бинарных связок.
47

Страницы