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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Opredelenie 3.4 (Tavtologii v isqislenii predikatov). Predi-
kat
A nazyvaets todestvenno istinnym v koneqnom pred-
metnom mnoestve M , esli tablica istinnosti togo predi-
kata soderit tol~ko
1
. Predikat
A
nazyvaets tavtologie$i
(simvoliqeski
|
= A
)
, esli on vlets todestvenno istinnym
v lbom koneqnom predmetnom mnoestve.
Pri koneqno$i predmetno$i oblasti formuly isqisleni pre-
dikatov otliqats ot formul isqisleni vyskazyvani$i tol~ko
tem, qto v nih prisutstvut diznkcii i konnkcii vi-
da
W
n
i
=1
a
i
,
V
n
i
=1
a
i
, v kotorye perehodt formuly, soderawie
kvantory suwestvovani i obwnosti. Pri dokazatel~stve tav-
tologi$i, soderawih takie diznkcii i konnkcii s pro-
izvol~nymi natural~nymi n, mono vospol~zovat~s principom
matematiqesko$i indukcii.
Teorema 3.1 (Nekotorye tavtologii isqisleni predikatov).
Pri proizvol~nyh predikatah A
(x)
, B(x)
, soderawih svobodnye
vhodeni x; C(x, y)
, soderawem svobodnye vhodeni x
i y;
P
, ne soderawem svobodno
x, vypolnts sootnoxeni:
1) |= (∀x)(A(
x)
∧B(
x)) ∼
(∀
x)
A(
x
)
∧
(∀
x
)B
(x) ,
2) |= (∃x)(
A(x
) ∨ B(x))
∼ (∃
x)A(x)
∨ (∃
x)B(x)
,
3)
|= (
∀x
)A
(x
)
∨
(
∀x
)
B(
x) → (
∀
x
)(
A(x)
∨ B(
x
)) ,
4)
|= (∃x)(
A
(
x
)
∧B(
x))
→
(∃
x)
A(x
)
∧(∃x)
B
(
x
)
,
5)
|= (
∀x)A
(
x) ∼
(
∃x)
A
(x) ,
6) |
=
(∃
x
)
A
(x
) ∼
(
∀
x)A(
x
)
,
7) |
= (
∀x
)P
∼ P ,
8)
|= (
∃x
)
P ∼ P ,
9) |= (
∀
x)(
P
∨
A
(
x
))
∼ P
∨ (
∀
x
)A(x
)
,
10) |
= (∃
x
)(P
∧
A
(x))
∼ P
∧
(
∃x)A
(x
)
,
11) |= (P → (
∀
x)
A
(
x
))
∼
(
∀x
)(P
→
A
(x)) ,
12) |= ((
∀x)
A(
x)
→ P
)
∼
(
∃x
)(
A(
x) → P
)
,
13) |= (
∀x)A
(x
)
∨
(∀
x)B
(
x
) ∼
(
∀
x)(
∀
y)(A(
x
)
∨ B(
y
))
,
14)
|= (
∃x
)
A(
x)
∧(∃
x
)B(x)
∼
(
∃
x
)(∃y
)(A
(
x)
∧B
(y))
,
15)
|
= (
∀
x
)(
∀y
)C
(
x, y
) ∼ (∀
y
)(∀x
)
C(x, y
) ,
16) |
= (
∃x
)(
∃
y
)
C(
x, y
)
∼ (∃y)(∃x
)
C(
x, y
)
,
17) |
= (∃y)(
∀
x
)
C(x, y)
→ (∀
x
)(∃
y)
C
(x, y)
,
18) esli
|
= A(
x) → B
(x
)
,
to |
= (∀x
)
A
(x
)
→
(∀
x
)B(x
)
,
19)
esli |
=
A(x)
→
B(x
) , to |
= (
∃x
)A
(
x) → (
∃
x)B
(x) ,
20) esli |=
A
(x
) ∼
B
(x)
, to
|= (∀x)A
(x) ∼ (
∀x)
B(x) ,
21)
esli
|= A(x
)
∼
B
(
x) ,
to |
= (
∃x
)A
(x)
∼
(∃x)B
(
x
)
.
D o k a z a t e l ~ s t v o . Dokaem tol~ko sootnoxeni 3, 18, 19.
32

Страницы