Дрозд Ю. Основи математичної логіки (на укр. языке)
Подождите немного. Документ загружается.
A B
A B A ⇒ B
0 0 1
0 1 1
1 0 0
1 1 1
A B
A B
2 × 2 = 4
2 × 2 = 4
A B
A B
A B A ⇔ B
A ⇔ B
A B
A B A ⇔ B
0 0 1
0 1 0
1 0 0
1 1 1
A B
A B
¬
A ¬A
0 1
1 0
((A ∨ B) ⇒ ((¬B) ∧ (C ⇔ A))) ⇒ ((¬C) ∨ B).
(A ∨ B ⇒ ¬B ∧ (C ⇔ A)) ⇒ ¬C ∨ B.
A
0
A, |, (, ), ¬, ∨, ∧, ⇒ .
A
W W |
W ¬W
W V (W ⇒ V ), (W ∨
V ), (W ∧ V )
A
0
A||. . . | |
W
W ¬x x
A ( W
¬ W
0
W
0
W
( ) W
0
W
W
∗
= a
1
a
2
. . . a
m
W
∗
= A||. . . |aW
1
a ∈ {∨, ∧, ⇒} W
W
1
a
1
6= ( W a
1
= (
s(k) 1 6 k < m − 1
s(1) = 1,
s(k + 1) =
s(k) + 1, a
k+1
= (,
s(k) − 1, a
k+1
=),
s(k)
s(k) 6= 0 1 < k < m−1 W
k s(k) = 0
W
1
= a
1
a
2
. . . a
k
a
k+1
∈ {∨, ∧, ⇒}
W
2
= a
k+2
. . . a
m
W
A||. . . | n |
A
n
A
0
A
(A
2
⇒ A
3
∨ (A
0
⇒ ¬A
2
)) ∧ ¬(A
1
∨ ¬A
0
⇒ ¬A
2
)
((A|| ⇒ (A||| ∨ (A ⇒ ¬A||))) ∧ ¬((A| ∨ ¬A) ⇒ ¬A||)).
E
A, B
I :
E → B = {0, 1 }
I A
A I val(I, A)
A val(I, A) = I(A)
A = ¬B
val(I, A) =
(
0, val(I, B) = 1,
1, val(I, B) = 0.
A = (B ∨ C)
val(I, A) =
(
0, val(I, B) = val(I, C) = 0,
1, .
A = (B ∧ C)
val(I, A) =
(
1, val(I, B) = val(I, C) = 1,
0, .
A = (B ⇒ C)
val(I, A) =
(
0, val(I, B) = 1, val(I, C) = 0,
1, .
val(I, A) I A
M A
M M |= A
val(I, A) = 1 I val(I, B) = 1
B ∈ M
M M
A |= A
1
M
I val(I, A) = 1 A ∈ M
M |= B B
A, B, C
A ⇒ (B ⇒ A),
(A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C),
A ⇒ (A ∨ B),
B ⇒ (A ∨ B),
(A ⇒ C) ⇒ ((B ⇒ C) ⇒ (A ∨ B ⇒ C)),
A ∧ B ⇒ A,
A ∧ B ⇒ B,
(A ⇒ B) ⇒ ((A ⇒ C) ⇒ (A ⇒ B ∧ C)),
(A ⇒ B) ⇒ ((A ⇒ ¬B) ⇒ ¬A),
¬¬A ⇒ A.
M |= A ⇒ B M |= A M |= B
M |= A N |= B B ∈ M N |= A
A |= A ∨ ¬A
M
A M |= A M |= ¬A
I val(I, C)
= 1 C ∈ N val(I, A) = 1 val(I, A ⇒ B) = 1
val(I, B) = 1
M M |= A
A
I
M ∪ {A }
val(I, B) = 1 B ∈ M val(I, A) = 1
A, B, C
A ⇒ B, A
B
,
A, B
A
1
, A
2
, . . . , A
n
A M A = A
n
i = 1, 2, . . . , n
A
i
A
i
∈ M
j < i k < i A
j
= A
k
⇒ A
i
A
i
A
j
A
k
A
M M ` A ` A A
A
M ` A M |= A
M |=
A M ` 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 = B
B = A ⇒ A
B = A ⇒ A C = A
` A∧B ⇒ B∧A A
A ∧ B ⇒ A, A ∧ B ⇒ B,
(A ∧ B ⇒ B) ⇒ ((A ∧ B ⇒ A) ⇒ (A ∧ B ⇒ B ∧ A)),
(A ∧ B ⇒ A) ⇒ (A ∧ B ⇒ B ∧ A), A ∧ B ⇒ B ∧ A.
M
A M ` A M ` ¬A
M ` B B A
M ¬A M
A ⇒ (¬B ⇒ A), ¬B ⇒ A, ¬A ⇒ (¬B ⇒ ¬A), ¬B ⇒ ¬A,
(¬B ⇒ A) ⇒ ((¬B ⇒ ¬A) ⇒ ¬¬B), (¬B ⇒ ¬A) ⇒ ¬¬B,
¬¬B, ¬¬B ⇒ B, B.
B M
M ` A ⇒ B M ` B ⇒ C M ` A ⇒ C
A ⇒ B B ⇒
C
(B ⇒ C) ⇒ (A ⇒ (B ⇒ C)), A ⇒ (B ⇒ C),
(A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)),
(A ⇒ B) ⇒ (A ⇒ C), A ⇒ C.
A ⇒ C M
A, B
` A ∨ B ⇒ B ∨ A.
A, B, C
` (A ⇒ (B ⇒ C)) ⇒ (B ⇒ (A ⇒ C)).
A
` (¬A ⇒ A) ⇒ A.
` ¬A ⇒ ¬A
M ` A N ` B B ∈ M
N ` A
M
M A
¬A
N M
A ¬A N M
N ` A N ` ¬A N
M ∪ {A } ` B M `
A ⇒ B
B M∪{A }
A ⇒ B M B
1
, B
2
, . . . , B
n
B M {A }
B
n
= B B
i
A ⇒ B
i
B
i
B
i
M
B
i
, B
i
⇒ (A ⇒ B
i
), A ⇒ B
i
.
B
i
= A A ⇒ A
B
i
B
j
B
k
j < i, k < i, B
j
= B
k
⇒ B
i
(A ⇒ B
j
) ⇒ ((A ⇒ B
k
) ⇒ (A ⇒ B
i
)),
(A ⇒ B
k
) ⇒ (A ⇒ B
i
), A ⇒ B
i
.
B
j
= B
k
⇒ B
i
A ⇒ B
j
B
j
A ⇒ B
k
B
k
A ⇒ B
B
n
M
M ∪ {A
1
, A
2
, . . . , A
m
} ` B
M ` A
1
⇒ (A
2
⇒ (. . . ⇒ (A
m
⇒ B) . . . )).
` 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 ⇒ B) ⇒ (¬B ⇒ ¬A)
A ⇒ B, ¬B ` ¬A
¬B ⇒ (A ⇒ ¬B), ¬B, A ⇒ ¬B,
(A ⇒ B) ⇒ ((A ⇒ ¬B) ⇒ ¬A), A ⇒ B,
(A ⇒ ¬B) ⇒ ¬A, ¬A.
A, ¬A
A, ¬A ` B B
` ¬A ⇒ (A ⇒ B)
A, A ⇒ B ` B A ⇒ ((A ⇒ B) ⇒ B)
(¬A ⇒ ¬B) ⇒ (B ⇒ A),
¬A ⇒ (¬B ⇒ ¬(A ∨ B)),
(A ⇒ B) ⇒ ((¬A ⇒ B) ⇒ B)),
A ⇒ (B ⇒ A ∧ B).