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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

1)
Γ ` A
∆ ` A
(где Γ ⊂ ∆); 2)
Γ `
∆ `
(где Γ ⊂ ∆);
3)
Γ ` A; Γ, A ` B
Γ ` B
; 4)
Γ, A, B, ∆ ` C
Γ, A ∧ B, ∆ ` C
;
5)
Γ ` A ∧ ¬A
Γ `
; 6)
Γ `
Γ ` A
;
7)
Γ, A `
Γ ` ¬A
; 8)
Γ ` A
Γ, ¬A `
; 9)
Γ ` ¬¬A
Γ ` A
;
10)
Γ, A ` B
Γ, ¬B ` ¬A
; 11)
Γ, ¬A ` ¬B
Γ, B ` A
.
/ Допустимость правила 1) следует из правила утончения; 2) — из
1), 5) и 6). Докажем правило 3):
Γ ` A
Γ, A ` B
Γ ` A ⇒ B
Γ ` B
.
Допустимость правила 4) следует из правила 3), правила удале-
ния ∧ и правила утончения. Докажем правила 5) и 6):
Γ ` A ∧ ¬A
Γ ` A
Γ ` A ∧ ¬A
Γ ` ¬A
Γ `
;
Γ `
Γ, ¬A `
Γ ` A
.
Чтобы доказать допустимость правила 7), покажем, что секвен-
ция A, ¬A ` доказуема; для этого применим правило 5) и пример 2:
A, ¬A ` A ∧ ¬A
A, ¬A `
.
Тогда, разумеется, и секвенция ¬A, ¬¬A ` доказуема. Используем это
в следующем дереве доказательства:
¬¬A, ¬A `
Γ, ¬¬A, ¬A `
Γ, ¬¬A ` A
Γ, A `
Γ, A ` A ∧ ¬A
Γ, ¬¬A, A ` A ∧ ¬A
Γ, ¬¬A ` A ⇒ A ∧ ¬A
Γ, ¬¬A ` A ∧ ¬A
Γ, ¬¬A `
Γ ` ¬A
.
Доказательства допустимости остальных правил не представляет
трудностей. .
Упражнение 1. Докажите допустимость правил 4), 8)–11).
54

Страницы