Дрозд Ю. Основи математичної логіки (на укр. языке)
Подождите немного. Документ загружается.
0 = 1
P(M) M
A ∨B A ∧B
A B
n
B
n
∨ ∧
A ≡ B A, B
A |= B B |= A L
≡ [A]
A L ∨ ∧
[A] ∨ [B] = [A ∨ B] [A] ∧ [B] = [A ∧ B].
L
1
0 L
A
1
, A
2
, . . . , A
n
A
1
×
A
2
×. . . ×A
n
(a
1
, a
2
, . . . , a
n
) ∨ (b
1
, b
2
, . . . , b
n
) = (a
1
∨ b
1
, a
2
∨ b
2
, . . . , a
n
∨ b
n
),
(a
1
, a
2
, . . . , a
n
) ∧ (b
1
, b
2
, . . . , b
n
) = (a
1
∧ b
1
, a
2
∧ b
2
, . . . , a
n
∧ b
n
).
A
1
, A
2
, . . . , A
n
A
i
A
A
n
A A
◦
A a ∨ b
a ∧ b A A
◦
∨ ∧
B
n
' P(M)
M n
M = {1, 2, . . . , n }
(a
1
, a
2
, . . . , a
n
) a
i
∈ B M(a) = {k | a
k
= 1 }
B
n
n
2
n
A
A a 6 b
a ∨ b = b
a 6 b a ∧ b = a
6 A
0 1
a 6 b ¬b 6 ¬a
a ∈ A a 6= 0 x < a
x = 0
a
¬a 6= 1 ¬a < x x = 1 c
c 6= 1 c < x x = 1 ¬c
a 66 x a ∧ x = 0 x 66 ¬a x ∨ ¬a = 1
b a 6= b a∧¬b = a
x 6 ¬x x = 0
x 6= 0 a a 6 x
A E = {a
1
, a
2
, . . . , a
n
}
a
1
∨ (¬a
1
∧ ¬a
2
∧ . . . ∧ ¬a
n
) = a
1
¬a
1
∧ ¬a
2
∧ . . . ∧ ¬a
n
= 0
a
1
∨ a
2
∨ ··· ∨ a
n
= 1
x ∈ A
E(x) = {a ∈ E | a 6 x }.
x =
W
a∈E(x)
a
x
E(x)
E(x) ∨ E(y) = E(x ∨ y) E(x) ∧ E(y) = E(x ∧ y).
x → E(x) A
P(E) E
B
n
B
n
n B
n
L
E
A A ∧ E < A
L
n
L
[A] A A
k
=
A||. . . | k | k < n L
n
' B
n
L =
S
∞
n=1
L
n
B
B × B × . . .
(a
1
, a
2
, . . . , a
n
, . . . ) a
i
0
L
n
[B
0
∧ B
1
∧ . . . B
n−1
] B
k
A
k
¬A
k
A A
⊕ x ⊕ y = (x ∨ y) ∧ (¬x ∨ ¬y)
⊕
0 x ¬x
x∧(y ⊕z) = x∧y ⊕x∧z ⊕
∧ A
x ∧ x = x
A x
2
= x x
xy+yx = 0 x y = 1 x+x =
0 x = −x xy = yx
x ∧ y = xy, x ∨ y = x + y + xy
A
¬x = 1 + x
2
•
•
•
A, B |= C
P
M
0, 1
1
∀xP (x) ∃xP (x)
∀ ∃
A
v
n
, p
m
n
, f
m
n
, ¬, ⇒, ∨, ∧, ∀, ∃, (, ) ,
m, n ∈ N = {0, 1, 2, 3, . . . }
v
n
p
m
n
f
m
n
m p
m
n
f
m
n
f
m
n
f
m
n
m
0 f
0
n
0
p
0
n
A
t
1
, t
2
, . . . , t
m
F m
F t
1
t
2
. . . t
m
F t
1
t
2
. . . t
m
F (t
1
, t
2
, . . . , t
m
)
A P t
1
t
2
. . . t
m
P m
t
1
, t
2
, . . . , t
m
m = 0
P
P (t
1
, t
2
, . . . , t
m
) P t
1
t
2
. . . t
m
A
A, B ¬A, (A ∨ B), (A ∧ B), (A ⇒ B)
A x ∀xA ∃xA
f
2
4
v
3
v
0
, f
3
6
f
1
1
v
7
v
5
f
1
1
v
5
, f
1
2
f
2
3
v
3
f
0
1
p
2
1
v
0
v
5
, p
3
2
v
1
f
2
2
v
1
f
0
3
f
2
2
v
5
v
2
, p
2
2
f
2
2
v
1
v
1
f
2
2
v
0
f
1
3
v
2
v
n
, p
m
n
f
m
n
v||. . . |, p||. . . | ∗ ∗···∗ f||. . . | ∗ ∗···∗ n
| m ∗
Qx ∀ ∃
A
A = QxB x B
A
B
A ¬B, B ∨ C, B ∧ C B ⇒ C Q
B C Qx A
B C
x A
Qx
Q
x A
x
A
A ∀x
1
∀x
2
. . . ∀x
n
A
x
1
, x
2
, . . . , x
n
A
v
k
v
m
k < m
(∀v
3
¬p
3
2
(v
4
, v
1
, v
3
)) ⇒ ∃v
1
(p
2
2
(v
1
, v
5
) ∧ p
1
5
(f
2
3
(v
4
, v
1
)))
v
1
, v
4
, v
5
v
3
∀
v
1
∃v
1
(p
2
2
(v
1
, v
5
) ∧ p
1
5
(v
4
))
∃
∀v
1
∀v
4
∀v
5
((∀v
3
¬p
3
2
(v
4
, v
1
, v
3
)) ⇒ ∃v
1
(p
2
2
(v
1
, v
5
) ∧ p
1
5
(f
2
3
(v
4
, v
1
)))).
∃v
2
¬∀v
3
(p
1
1
(v
2
) ∨ p
2
3
(v
3
, f
2
2
(v
2
, v
2
)) ⇒ ∃v
1
(p
2
3
(v
2
, v
1
) ∧ p
1
3
(v
3
)))
I
M = M(I)
I
m P
I(P ) : M
m
→ B
m = 0 I(P ) ∈ B
m F
I(F ) : M
n
→ M
m = 0 I(F ) ∈ M
I φ : X → M
X
φ x φ
x
ψ ψ(y) = φ(y)
y 6= x
φ(t) t φ
t = v
n
φ(t) = φ(v
n
)
t = F t
1
t
2
. . . t
m
F m φ(t) =
I(F )(φ(t
1
), φ(t
2
), . . . , φ(t
m
))
val(I, φ, A) A φ I
A = P t
1
t
2
. . . t
m
val(I, φ, A) = I(P )(φ(t
1
), φ(t
2
), . . . , φ(t
m
));
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, φ, ∀xA) = min {val(I, ψ, A) | ψ ∈ φ
x
}
val(I, φ, ∃xA) = max {val(I, ψ, A) | ψ ∈ φ
x
}
0 < 1
val(I, φ, ∀xA) = 1 val(I, ψ, A) = 1
ψ φ
x val(I, φ, ∃xA) = 1 val(I, φ, A) = 1
f : M
n
→ B
n n M
I(P ) I P n
n M
f
M = {a ∈ N
n
| f(a) = 1 }
x
A ψ φ ψ ∈ φ
x
val(I, φ, A) =
val(I, ψ, A) A φ
A A val(I, φ, A)
φ val(I, A)
A
A x
A = QxB Q
ψ
x
= φ
x
A ¬B, B ⇒ C, B ∨C, B ∧C
QyB Q y 6= x
x B C
ψ φ
A
A
I val(I, φ, A) = 1
φ
M
M
|=
I
A |=
M
A |= A
R
E
1
, E
2
, . . . , E
n
A
1
, A
2
, . . . , A
n
R
E
1
,E
2
,...,E
n
A
1
,A
2
,...,A
n
R
E
i
A
i
R
E
1
,E
2
,...,E
n
A
1
,A
2
,...,A
n
R R
E
1
,E
2
,...,E
n
A
1
,A
2
,...,A
n
R
E
1
,E
2
,...,E
n
A
1
,A
2
,...,A
n
R
A, B, C
A x t
y
1
, y
2
, . . . , y
m
t
t x A
x A
Qy
i
(i = 1, 2, . . . , m) A
x
t
A t
x t x A
∀xA ⇒ A
x
t
,
A
x
t
⇒ ∃xA.
A, B x
A
∀x(A ⇒ B) ⇒ (A ⇒ ∀xB),
∀x(B ⇒ A) ⇒ (∃xB ⇒ A).
val(I, φ, A
x
t
) = 1 val(I, φ, ∃xA) = 0
val(I, φ, A
x
t
) = 1 ψ
ψ(y) =
(
φ(y) y 6= x,
φ(t) y = x.
ψ ∈ φ
x
val(I, ψ, A) = val(I, φ, A
x
t
) = 1
val(I, φ, ∃xA) = 1
val(I, φ, ∀x(A ⇒ B)) = 1
val(I, ψ, A ⇒ B) = 1 ψ ∈ φ
x
val(I, φ, A ⇒ ∀xB) = 1
val(I, φ, A) = 1 val(I, φ, ∀xB) = 0
ψ ∈ φ
x
val(I, ψ, A) =
val(I, φ, A) = 1 val(I, ψ, A ⇒ B) = 1 val(I, ψ, B) = 1
val(I, φ, ∀xB) = 1
x x
A
x
x
= A
∀xA ⇒ A ∀ ⇒ ∃xA
Qx Q A y
B A x y
val(I, φ, A) = val(I, φ, B)
I φ
A I
M
∀xA x A
I M
A ⇒ ∀xA
T
T T
T
A T
T
T I |=
I
A
A ∈ T M
I T M M
I
T
I
T I(P ) I(F )
T
I T
T
T