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

UptoLike

ВУЗ: 

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

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

Рубрика: 

2.2. Metody dokazatel~stva tavtologi$i i sekvenci$i
Tavtologii i sekvencii mono dokazat~ tabliqnym metodom,
no praktiqeski to mono osuwestvit~ togda, kogda qislo le-
mentarnyh vyskazyvani$i neveliko. Rassmotrim pravila, pozvo-
lwie provodit~ dokazatel~stva, ne pribega k tablicam.
Teorema 2.3 (Svo$istva znaka |
=
).
Pust~
Γ =
A
1
,
. . .
, A
n
— spisok
formul,
B
1
, . . .
, B
k
, C — formuly.
1
. A
1
, . . .
, A
n
|
= A
i
pri i
= 1
,
. . . , n (lementarnye sledstvi
).
2
.
Esli Γ |
=
C , to
Γ, B
1
, . . . , B
k
|=
C (
dobavlenie dopuweni$i).
3. Esli Γ
|
=
B
i
pri
i = 1,
. . . , k
i
B
1
,
. . .
, B
k
|=
C
, to
Γ |= C
(
dokazatel~stvo s pomow~ lemm)
.
Dokazatel~stvo rekomenduets qitatel kak upranenie.
Opredelenie 2.3 (Ravnosil~nost~ spiskov dopuweni$i). Spisok
dopuweni$i
Γ
1
nazyvaets ravnosil~nym spisku dopuweni$i
Γ
2
,
esli dl lbo$i formuly B
sekvenci Γ
1
|
=
B
dokazana togda i
tol~ko togda, kogda dokazana sekvenci
Γ
2
|
= B.
Po opredeleni 2.3 spiski dopuweni$i
Γ
1
, Γ
2
ravnosil~ny,
esli oni vydelt odinakovye stroki.
Sleduwee utverdenie oqevidno.
Teorema 2.4 (Ravnosil~nost~ spiska dopuweni$i dopuweni).
Vski$i spisok dopuweni$i Γ ravnosilen dopuweni
V
Γ
.
Esli
V
Γ = 1, to iz Γ sledut tol~ko tavtologii. V qas-
tnosti,
V
Γ
= 1 pri pustom spiske
Γ
i potomu tavtologi
A oboznaqat simvolom |
= A
. Esli
V
Γ = 0
, to spisok Γ
nazyvaets protivoreqivym i oboznaqaets simvolom Γ |
=
.
Sledstvie (Pravila preobrazovani spiskov dopuweni$i).
Pust~
Γ, Γ
1
, Γ
2
— spiski formul,
A, B, C — formuly i
pust~
Γ
|
=
C
. Sleduwie spiski dopuweni$i ravnosil~ny:
1)
Γ
1
, A, B, Γ
2
i
Γ
1
, B, A, Γ
2
(pravilo perestanovki)
,
2)
Γ
1
, A, A, Γ
2
i Γ
1
, A, Γ
2
(
pravilo sokraweni
)
,
3)
Γ
1
, A, B, Γ
2
i Γ
1
, A
∧
B, Γ
2
(pravila obedineni i raswepleni),
4) Γ
i Γ, C
(
pravilo popolneni).
Teorema 2.5 (O protivoreqivyh spiskah dopuweni$i).
Spisok Γ
protivoreqiv togda i tol~ko togda, kogda suwestvuet formula
A taka, qto Γ
|
= A i
Γ
|= A.
D o k a z a t e l ~ s t v o . Esli Γ
|= , to po opredeleni 2.2 iz
Γ sleduet lboe vyskazyvanie, v qastnosti,
Γ |=
A i
Γ |
= A
.
Obratno, esli Γ
|= A
i Γ |=
A
, to spisok
Γ
po pravilu popol-
neni ravnosilen protivoreqivomu spisku
Γ, A,
A.
J
17

Страницы