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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Sootnoxenie 3 vypolnets v odnolementnyh mnoestvah.
Predpoloim, qto ono vypolnets v k
-lementnyh mnoes-
tvah. Pust~ M — k + 1-lementnoe mnoestvo s lementami
m
1
,
. . . , m
k
, m
k+1
. Dokazatel~stvo po metodu matematiqesko$i in-
dukcii svodits k dokazatel~stvu sekvencii
P ∨ Q
→
R
|
= (P
∧
a)
∨ (Q∧
b
)
→
R∧(a
∨ b)
,
(1)
gde P
=
V
k
i
=1
A(
m
i
)
, Q =
V
k
i=1
B
(
m
i
)
, R
=
V
k
i
=1
(
A
(
m
i
)
∨ B
(m
i
)),
a
=
A
(
m
k+1
), b = B
(m
k
+1
)
. Dokaem (1) tabliqnym sposobom
P
∨
Q →
R |= (P ∧a
) ∨ (Q ∧
b) →
R ∧ (a ∨ b)
0 0 0 1 0 0 0 a
0 0 0
b 1
0 0 0 1 1 0 0 a 0 0 0 b 1
0 1 1 0 0
0 1 1 1 1 0 0 a b
1 b b 1 1
a ∨
b a ∨
b
1 1 0 0 0
1 1 0 1 1 1 a a a 0 0 b 1 1 a ∨
b a ∨
b
1 1 1 0 0
1 1 1 1 1 1 a a a
∨ b 1 b b
1 1
a
∨
b a ∨ b
Dl dokazatel~stva sootnoxeni$i 18, 19 zametim, qto
|
=
A
(
x
)
→
B(
x)
kvivalentno
A
(x) |
=
B(x
)
, otkuda sledut tav-
tologii |= (∀x)A
(
x)
→
(
∀
x
)
B
(x
),
|
= (
∃x)A
(
x) →
(
∃x)
B(x)
. J
Teorema 3.2 (Osnovnye svo$istva kvantorov). Pust~
x
— proiz-
vol~na peremenna,
A(x
) — proizvol~ny$i predikat, soderawi$i
x svobodno. Esli peremenna
t
svobodna dl
x
v
A(
x)
, to:
1)
|
= (∀x)A(x
)
→ A
(
t
) ; 2)
|
= A
(
t
) → (∃x)A
(
x)
.
D o k a z a t e l ~ s t v o . 1) Vozmony dva vzaimoisklqawih
sluqa:
A(
x
)
— libo tavtologi, libo oproverimy$i pre-
dikat. V pervom sluqae A(
t
) = 1, vo vtorom
(∀x)
A
(
x
) = 0 i
potomu v oboih sluqah utverdenie 1) vypolnets.
2) Vozmony dva vzaimoisklqawih sluqa: A
(x)
— li-
bo protivoreqie, libo vypolnimy$i predikat. V pervom sluqae
A
(t) = 0
, vo vtorom
(
∃
x)
A
(
x
) = 1 i potomu v oboih sluqah
utverdenie 2) vypolnets.
J
Teorema 3.3 (Pravila obobweni i konkretizacii).
Pust~
x
—
proizvol~na peremenna, A
(
x
) — proizvol~ny$i predikat, soder-
awi$i
x svobodno, a
D
ne soderit
x
svobodno. Togda:
1)
esli |=
D
→ A(
x
), to |
= D → (
∀x
)
A
(x
) (obobwenie);
2) esli |
=
A(x) →
D
, to
|
= (
∃x)
A(
x
) →
D (
konkretizaci).
Dokazatel~stvo analogiqno dokazatel~stvu teoremy 3.2.
33

Страницы