Дрозд Ю. Основи математичної логіки (на укр. языке)
Подождите немного. Документ загружается.
I : E →
B A
A
I
=
(
A, val(I, A) = 1,
¬A val(I, A) = 0.
E
I
=
E
I
| E ∈ E
E
I
` A
I
A
A
A A
I
∈ E
I
E
I
` A
I
A
B ⇒ C,
B ∧ C,
B ∨ C,
¬B,
B C
E
I
` B
I
E
I
` C
I
val(I, B) val(I, C)
A = B ⇒ C val(I, B) = 0 val(I, A) = 1 E
I
` ¬B
` ¬B ⇒ (B ⇒ C)
E
I
` A
val(I, C) = 1 val(I, A) = 1 E
I
` C ` C ⇒
(B ⇒ C) E
I
` A
val(I, B) = 1 val(I, C) = 0 val(I, A) = 0
E
I
` B E
I
` ¬C
B ⇒ ((B ⇒ C) ⇒ C), (B ⇒ C) ⇒ C,
((B ⇒ C) ⇒ C) ⇒ (¬C ⇒ ¬(B ⇒ C)) ,
¬C ⇒ ¬(B ⇒ C), ¬(B ⇒ C)
A
I
= ¬A E
I
A = B ∧ C val(I, B) = 0 val(I, A) = 0 E
I
` ¬B
(B ∧ C) ⇒ B, ((B ∧ C) ⇒ B) ⇒ (¬B ⇒ ¬(B ∧ C)) ,
¬B ⇒ ¬(B ∧ C), ¬(B ∧ C),
A
I
= ¬A E
I
val(I, C) = 0
val(I, B) = val(I, C) = 1 val(I, A) = 1 E
I
` B
E
I
` C
B ⇒ (C ⇒ B ∧ C) , C ⇒ B ∧ C, B ∧ C,
A E
I
M
A M ` A M ` ¬A
A M
M ∪ {¬A }
M
A M ∪ {¬A }
M ∪ {¬A } ` A M ` ¬A ⇒ A
` (¬A ⇒ A) ⇒ A M ` A
M
A
1
, A
2
, . . . , A
n
, . . . M
i
(i ∈ N)
M
1
= M,
M
i+1
=
(
M
i
, M
i
` A
i
,
M
i
∪ {¬A
i
},
M
i
(i ∈ N)
M
∞
=
S
∞
i=1
M
i
A
i
M
i
` A
i
M
∞
` A
i
¬A
i
∈ M
i+1
⊆ M
∞
M
∞
` ¬A
i
M
∞
M 6` A M ∪ {¬A }
N
I
I(E) =
(
1, N ` E,
0, N ` ¬E,
E val(I, B) = 1
B ∈ N E
I
` B
I
N ` E
I
E I N `
B
I
N B ∈ N
B
I
= B val(I, B) = 1 val(I, B) = 1
B ∈ M val(I, ¬A) = 1 val(I, A) = 0 M 6|= A
M
M M |= A M ` A
A
M
M
A
A E
1
, E
2
, . . . , E
n
E
m
= {E
1
, E
2
, . . . , E
m
} (m 6 n) E
0
= ∅
I : E
m
→ B A E
I
m
m = n
A E
I
0
m+1
E
I
1
m+1
I
0
(E
i
) = I
1
(E
i
) = I(E
i
) i 6 m,
I
0
(E
m+1
) = 0,
I
1
(E
m+1
) = 1.
E
m+1
⇒ A ¬E
m+1
⇒ A E
I
m
` (E
m+1
⇒ A) ⇒ ((¬E
m+1
⇒ A) ⇒ A)
A E
I
m
m = 0 A
¬A ⇒ (A ⇒ B).
I
A
M M `
I
A
A
e
A
¬¬A M
f
M =
n
e
A | A ∈ M
o
M `
I
A M ` A
M ` A
f
M `
I
e
A
M ` ¬A
f
M `
I
¬A
¬¬A ⇒ A
I
` A ` ¬¬A
A ⇒ A
I
M `
I
A M `
I
¬A M `
I
B
B
`
I
A ⇒ ¬¬A `
I
(A ⇒ B) ⇒ (¬B ⇒ ¬A)
`
I
¬¬¬A ⇒ ¬A
A M
e
A
f
M
A, B
¬¬A, ¬¬(A ⇒ B) `
I
¬¬B
`
I
¬¬(¬¬A ⇒ A)
¬¬A, ¬B `
I
¬(A ⇒ B)
(A ⇒ ¬B) ⇒ ((A ⇒ B) ⇒ ¬A), ¬B ⇒ (A ⇒ ¬B), ¬B,
A ⇒ ¬B, (A ⇒ B) ⇒ ¬A, ¬¬A ⇒ ((A ⇒ B) ⇒ ¬¬A),
¬¬A, (A ⇒ B) ⇒ ¬¬A,
((A ⇒ B) ⇒ ¬A) ⇒ (((A ⇒ B) ⇒ ¬¬A) ⇒ ¬(A ⇒ B)),
((A ⇒ B) ⇒ ¬¬A) ⇒ ¬(A ⇒ B), ¬(A ⇒ B).
¬¬A `
I
¬B ⇒ ¬(A ⇒ B)
`
I
(¬B ⇒ ¬(A ⇒ B)) ⇒ (¬¬(A ⇒ B) ⇒ ¬¬B)
B ⇒ (A ⇒ B) `
I
¬(A ⇒ B) ⇒ ¬B
`
I
¬(¬¬A ⇒ A) ⇒ ¬A
¬A ⇒ (¬¬A ⇒ A), ¬(¬¬A ⇒ A) ⇒ ¬¬A, ¬(¬¬A ⇒ A) ⇒ ¬A,
(¬(¬¬A ⇒ A) ⇒ ¬A) ⇒ ((¬(¬¬A ⇒ A) ⇒ ¬¬A) ⇒ ¬¬(¬¬A ⇒ A)),
¬¬(¬¬A ⇒ A)
A M
e
A
f
M
¬¬(¬¬A ⇒ A)
B ∈ M
e
B = ¬¬B ∈
f
M
A
i
A
j
A
k
= A
j
⇒ A
i
j, k < i
e
A
i
= ¬¬A
i
e
A
j
= ¬¬A
j
e
A
k
= ¬¬(A
j
⇒ A
i
)
X U(X)
{A A ⊆ X
{A = X \A A
◦
A
U ⊆ A
I : E → U(X)
I
• A val(I, A) = I(A)
•
val(I, ¬A) =
{ val(I, A)
◦
;
val(I, A ∨ B) = val(I, A) ∪ val(I, B);
val(I, A ∧ B) = val(I, A) ∩ val(I, B);
val(I, A ⇒ B) =
{ val(I, A) ∪ val(I, B)
◦
.
A I val(I, A) = X
M |=
I
A
M A
M `
I
A M |=
I
A
¬¬A ⇒ A, A ∨ ¬A, (A ⇒ B) ⇒ ((¬A ⇒ B) ⇒ B),
A, B
X
X
T
1
T
1
M |=
I
A M `
I
A
X
[0, 1]
f : B
n
→ B B =
{0, 1 }
∨, ∧, ¬, ⇒
F
F
F
f : B
n
→ B
a = (a
1
, a
2
, . . . , a
n
) a
i
∈ B T
a
= y
1
∧ y
2
∧
. . . y
n
y
i
=
(
x
i
a
i
= 1,
¬x
i
a
i
= 0.
f (x
1
, x
2
, . . . , x
n
) =
_
f(a)=1
T
a
.
f
f
f (x
1
, x
2
, . . . , x
n
) =
V
T
0
a
T
0
a
¬, ∨ ∧ {¬, ∨, ∧}
¬(x ∨ y) = ¬x ∧ ¬y
{¬, ∨} {¬, ∧}
x ⊕ y = ¬(x ⇔ y)
x ⊕ y = y ⊕ x,
(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z),
x ∧ (y ⊕ z) = x ∧ y ⊕ x ∧ z.
x
i
1
∧ x
i
2
∧ . . . ∧ x
i
m
i
1
< i
2
< ··· < i
m
m = 0 1
2
n + 1
f (x
1
, x
2
, . . . , x
n+1
) n f
0
=
f(x
1
, x
2
, . . . , x
n
, 0) f
1
= f(x
1
, x
2
, . . . , x
n
, 1)
f = x
n+1
∧ f
1
⊕ (1 ⊕ x
n+1
) ∧ f
0
n
{0, 1, ⊕, ∧}
1 ⊕ 1 = 0 {1, ⊕, ∧}
f : B
n
→ B
• f(0, 0, . . . , 0) = 0
F
0
• f(1, 1, . . . , 1) = 1
F
1
• f (a
1
, a
2
, . . . , a
n
) 6 f (b
1
, b
2
, . . . , b
n
)
a
i
6 b
i
i 0 < 1
F
2
• f (¬a
1
, ¬a
2
, . . . , ¬a
n
) = ¬f (a
1
, a
2
, . . . , a
n
)
a
1
, a
2
, . . . , a
n
F
3
•
f (x
1
, x
2
, . . . , x
n
) = c ⊕ (
L
m
k=1
x
i
k
)
i
1
< i
2
< ··· < i
k
c ∈ B
F
4
F
i
(i = 0, 1, 2, 3, 4) F
i
F ⊆ F
i
F
ˆ
f(x) = f(x, x, . . . , x)
• f
ˆ
f(x) = ¬x
ˆ
f(x) = 1
• f
ˆ
f(x) = ¬x
ˆ
f(x) = 0
f
a
1
, a
2
, . . . , a
n
b
1
, b
2
, . . . , b
n
f (a
1
, a
2
, . . . , a
n
) = 0, f (b
1
, b
2
, . . . , b
n
) = 1 a
i
= b
i
i i = k
a
k
= 1, b
k
= 0
F
F
f
a
1
, a
2
, . . . , a
n
f (a
1
, a
2
, . . . , a
n
) = f(¬a
1
, ¬a
2
, . . . , ¬a
n
)
y
i
= x a
i
= 1 y
i
= ¬x a
i
= 0
f (y
1
, y
2
, . . . , y
n
)
F 6⊆ F
i
i ∈ {0, 1, 2, 3 } F
f (x
1
, x
2
, . . . , x
n
)
x
i
1
∧x
i
2
∧. . . ∧ x
i
m
f
m > 1
g(x, y) = f (y
1
, y
2
, . . . , y
n
) y
i
1
= x, y
i
2
= ··· = y
i
m
=
y, y
j
= 0 j /∈ {i
1
, i
2
, . . . , i
m
} g(x, y) = c
0
⊕
c
1
∧ x ⊕ c
2
∧ y ⊕ x ∧ y c
k
∈ B
g ¬g x∧y, x∨
y, x ∧ ¬y, ¬x ∧ y
F F 6⊆
F
i
i ∈ {0, 1, 2, 3, 4 }
f(x, y)
f(x, y) = ¬(x ∨y) x|y f (x, y) = ¬(x ∧y)
x↓y
f n
f
F
F
0
⊆ F
4
F
F
0
⊆ F
3
F 4
F
0
⊂ F
A
∨ ∧
x ∨ x = x,
x ∧ x = x,
∗
x ∨ y = y ∨ x,
x ∧ y = y ∧ x,
∗
x ∨ (y ∨ z) = (x ∨ y) ∨ z,
x ∧ (y ∧ z) = (x ∧ y) ∧ z,
∗
0 x ∨ 0 = x x,
1 x ∧ 1 = x x,
∗
x ∨ (x ∧ y) = x,
x ∧ (x ∨ y) = x,
∗
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z),
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z),
∗
x ¬x x ∨ ¬x = 1
x ∧ ¬x = 0.
x ∧ 0 = 0 x ∨ 1 = 1
∗
0 1 ¬x
¬(¬x) = x
¬(x ∧ y) = ¬x ∨ ¬y ¬(x ∨ y) = ¬x ∧ ¬y
¬x x
B = {0, 1 }
0 6= 1