Логика. Множества. Вероятность. Лексаченко В.А. - 19 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

Teoremy 2.3 — 2.6 pozvolt dokazyvat~ tavtologii i sek-
vencii, ne ispol~zu tablic istinnosti.
Primer 2.3 (Dokazatel~stvo s pomow~ teorem 2.3 — 2.6).
Dokaem
|
= (A →
B) ∼ (
B
→
A
)
.
1) A
→
B , B , A |
=
B — svo$istvo 1,
2)
A →
B , B , A |= B — svo$istvo 2, udalenie →,
3) A → B , B |
=
A — vvedenie , 1, 2,
4)
A →
B
|=
B
→
A
— vvedenie
→, 3,
5)
|
= (A
→ B) →
(
B
→
A
) — vvedenie
→
, 4,
6) B
→
A , A , B
|=
A
— svo$istvo 1,
7)
B
→
A , A , B
|
= A
— svo$istvo 2, udalenie
→,
8)
B
→
A , A
|
= B
— vvedenie
, 6, 7,
9)
B → A , A |
= B
— svo$istvo 3, udalenie , 8,
10) B → A |= A
→ B
— vvedenie →, 9,
11) |= (B → A) →
(A
→ B)
— vvedenie
→, 10,
12) |
= (A →
B
)
∼ (B → A)
— svo$istvo 3, vvedenie ∼, 5, 11.
Razsneni v pravo$i qasti strok nazyvats analizom do-
kazatel~stva. V nih ukazyvats svo$istva znaka
|=
, pravila
vvedeni ili udaleni logiqeskogo znaka, ispol~zuemye v stro-
ke, i nomera strok, na kotorye pri tom sleduet soslat~s.
Privedennoe dokazatel~stvo nazyvaets line$inym. Bolee infor-
mativnym sposobom zapisi togo dokazatel~stva vlets zapis~
ego v vide dereva:
B → A, A, B |= A, B → A, A, B |= A
.
A
→
B, B, A
|
= B, A
→
B, B, A
|
= B
.
B
→
A, A
|
= B
.
A
→ B,
B
|=
A
.
→
B
→
A, A
|=
B
.
→
A
→
B |= B → A
.→
B → A |
=
A → B
.→
|= (A → B
)
→
(
B → A)
|
= (B → A)
→
(A
→
B
)
.
∼
|
= (
A →
B) ∼
(B
→
A
)
Iz rassmotreni dereva dokazatel~stva vidno, qto ego nin
qast~ do sekvenci$i A →
B,
B
|
= A
i
B
→
A, A
|
= B
odnoznaqno
opredelets pravilami vvedeni i udaleni logiqeskih zna-
kov, a dokazatel~stvo tih sekvenci$i trebuet nekotoro$i izob-
retatel~nosti v primenenii pravila vvedeni otricani. Dl
oblegqeni ponimani dokazatel~stva tavtologii mono snaqala
dokazat~ vspomogatel~nu sekvenci A
→ B,
B
|=
A
(lemmu 1)
19

Страницы