СНВ в логике предикатов
1. ├ "х(Q(y) É R(x,y)) É (Q(y) É "xR(x,y))
1. "х (Q(y) É R(x,y)) – доп.
2. Q(y) – доп.
3. (Q(y) É R(x,y)) - "и: 1
4. R(x,y) - Éи: 2, 3
5. "xR(x,y)) - "в: 4, х – абсолютно ограничена, х ограничивает у
6. (Q(y) É "xR(x,y)) - Éв: 5
7. "х(Q(y) É R(x,y)) É (Q(y) É " xR(x,y)) - Éв: 6
2. ├ ∃x(P(x) É "yP(y))
1. P(x) – доп.
2. "yP(y) - "в: 1, х – абсолютно ограничена
3. (P(x) É "yP(y)) - Éв: 2
4. ∃x(P(x) É "yP(y)) - ∃в: 3
3. ├ "x"уR(x,y) É "y"xR(x,y)
1. "x"уR(x,y) – доп.
2. "уR(x,y) - "и: 1
3. R(x,y) - "и: 2
4. "xR(x,y) - "в: 3, х - абсолютно ограничена, х ограничивает у
5. "y"xR(x,y) – у – абсолютно ограничена
6. "x"уR(x,y) É "y"xR(x,y) - Éв: 5
4. ├ "xP(x) ≡ Ø∃xØP(x)
├ ("xP(x) É Ø∃xØP(x)) & (Ø∃xØP(x) É"xP(x))
1. "xP(x) – доп.
2. ∃xØP(x) – доп.
3. ØP(x) - ∃и: 2, х – абсолютно ограничена
4. P(x) - "и: 1
5. Ø∃xØP(x) - Øв: 3,4
6. ("xP(x) ÉØ∃xØP(x)) - Éв: 5
7. Ø∃xØP(x) – доп.
8. ØP(x) – доп.
9. ∃xØP(x) - ∃в: 8
10. ØØP(x) - Øв: 7,9
11. P(x) - Øи: 10
12. "xP(x) - "в: 11, х – абсолютно ограничена
13. (Ø∃xØP(x) É"xP(x)) - Éв: 12
14. ("xP(x) É Ø∃xØP(x)) & (Ø∃xØP(x) É"xP(x)) - &в: 6,13
5. ├ ∃x(P(x) Ú Q(x)) ≡ (∃xP(x) Ú ∃xQ(x))
5.1. ├ ∃x(P(x) Ú Q(x)) É (∃xP(x) Ú ∃xQ(x))
1. ∃x(P(x) Ú Q(x)) – доп.
2. Ø (∃xP(x) Ú ∃xQ(x)) – доп.
3. Ø P(x) – доп.
4. (P(x) Ú Q(x)) - ∃и: 1, х – абсолютно ограничена
5. Q(x) - Úи: 3, 4
6. ∃xQ(x) - ∃в: 5
7. (∃xP(x) Ú ∃xQ(x)) - Úв: 6
8. ØØ P(x) - Øв: 2, 7
9. P(x) - Øи: 8
10. ∃хP(x) - ∃в: 9
11. (∃xP(x) Ú ∃xQ(x)) - Úв: 10
12. ØØ (∃xP(x) Ú ∃xQ(x)) - Øв: 2, 11
13. (∃xP(x) Ú ∃xQ(x)) - Øи: 12
14. ∃x(P(x) Ú Q(x)) É (∃xP(x) Ú ∃xQ(x)) - Éв: 13
5.2. ├ (∃xP(x) Ú ∃xQ(x)) É ∃x(P(x) Ú Q(x))
1. (∃xP(x) Ú ∃xQ(x)) – доп.
2. Ø ∃x(P(x) Ú Q(x)) – доп.
3. Ø∃xP(x) – доп.
4. ∃xQ(x) - Úи: 1, 3
5. Q(x) - ∃и: 4, х – абсолютно ограничена
6. (P(x) Ú Q(x)) - Úв: 5
7. ∃x(P(x) Ú Q(x)) - ∃в: 6
8. ØØ∃xP(x) - Øв: 2, 7
9. ∃xP(x) - Øи: 8
10. P(y) - ∃и: 9, у – абсолютно ограничена
11. (P(y) Ú Q(y)) - Úв: 10
12. ∃x(P(x) Ú Q(x)) - ∃в: 11
13. ØØ∃x(P(x) Ú Q(x)) - Øв: 2,12
14. ∃x(P(x) Ú Q(x)) - Øи: 13
15. ∃x(P(x) Ú Q(x)) É (∃xP(x) Ú ∃xQ(x)) - Éв: 14
Доказать, что если неверно, будто кто-то умнее всех, то каждый не умнее кого-нибудь.
├ Ø∃x"yR(x,y) É "x∃yØR(x,y)
1. Ø∃x"yR(x,y) – доп.
2. R(x,y) – доп.
3. "yR(x,y) - "в: 2, у – абсолютно ограничена, х – ограничена
4. ∃x"yR(x,y) - ∃в: 3
5. ØR(x,y) - Øв: 1, 4
6. ∃yØR(x,y) - ∃в: 6
7. "x∃yØR(x,y) - "в: 6, х – абсолютно ограничена
8. Ø∃x"yR(x,y) É "x∃yØR(x,y) - Éв: 7
Все философы знакомы с натуральным исчислением предикатов. Некоторые математики – философы. Следовательно, некоторые математики знакомы с натуральным исчислением предикатов.
"x(P(x) É Q (x)), ∃x(S(x) & P(x)) ├ ∃x(S(x) & Q(x))
СНВ:
1. "x(P(x) É Q (x)) – пос.
2. ∃x(S(x) & P(x)) – пос.
4. (P(x) É Q (x)) - "и: 1
5. (S(x) & P(x)) - ∃и: 2, х – абсолютно ограничена
6. P(x) - &и: 5
7. S(x) - &и: 5
8. Q(x) - Éи: 4, 6
9. (S(x)&Q(x)) - &в: 7, 8
10. ∃x(S(x)&Q(x)) - ∃в: 9
F": = F": S, F"xA(x) |= S, FA(w), где w — новая переменная (не входящая в S и "xA(x))
T$: = S, T$xA(x) |= S, TA(w), где w — новая переменная/константа.
T": = S, T"xA(x) |= S, TA(α) (или S, T"xA(x) |= S, T"xA(x), TA(t)
F$: = S, F$xA(x) |= S, FA(α) (или S, F$xA(x) |= S, F$xA(x), FA(t)
где α (A(α)) — временная метапеременная, A(t) — результат правильной подстановки терма/переменной t в формулу A(x) вместо всех вхождений переменной x)
"x(P(x) É Q (x)), ∃x(S(x) & P(x)) ├ ∃x(S(x) & Q(x))
МАТ:
1.T["x(P(x) É Q (x))], T[∃x(S(x) & P(x))], F[∃x(S(x) & Q(x))]
2. T[P(α) É Q(α)], T[∃x(S(x) & P(x))], F[∃x(S(x) & Q(x))] - T": 1
3. T[P(α) É Q(α)], T[∃x(S(x) & P(x))], F[S(α) & Q(α)] - F∃: 2
4. T[P(α) É Q(α)], T[S(w) & P (w)], F[S(α) & Q(α)] - T∃: 3
5. T[P(α) É Q(α)], T[S(w)], T[P(w)], F[S(α) & Q(α)] – T&: 4
6. F[P(w)], T[S(w)], T[P(w)], F[S(α) & Q(α)] T[Q(α)], T [S(w)], T[P(w)], F[S(α) & Q(α)] - TÉ: 5
T[Q(α)], T [S(w)], T[P(w)], F[S(w)] T[Q(t)], T [S(w)], T[P(w)], F[Q(t)] – F&:6
Ни одна кошка не умеет летать. Все тигры - кошки. Следовательно, ни один тигр не умеет летать.
"x(M(x) É ØP(x)), "x(S(x) É M(x)) ├ "x(S(x) É ØP(x))
СНВ:
1. "x(M(x) É ØP(x)) – пос.
2. "x(S(x) É M(x)) – пос.
3. S(x) – доп.
4. (M(x) É ØP(x)) - "и: 1
5. (S(x) É M(x)) - "и: 2
6. M(x) - Éи: 3, 5
7. ØP(x) - Éи: 4, 6
8.(S(x) É ØP(x)) - Éв: 8
9. "x(S(x) É ØP(x)) - "в: 9, х – абсолютно ограничена
МАТ:
1. T["x(M(x) É ØP(x))], T["x(S(x) É M(x))], F["x(S(x) É ØP(x))]
2. T[M(α) É ØP(α)], T["x(S(x) É M(x))], F["x(S(x) É ØP(x))] - T": 1
3. T[M(α) É ØP(α)], T[S(α) É M(α)], F["x(S(x) É ØP(x))] - T": 2
4. T[M(α) É ØP(α)], T[S(α) É M(α)], F[(S(w) É ØP(w)] - F": 3
5. T[M(α) É ØP(α)], T[S(α) É M(α)], T[S(w)], F[ØP(w)] - FÉ: 4
6. F[M(α)], T[S(α) É M(α)], T[S(w)], F[ØP(w)] T[ØP(w)], T[S(α) É M(α)], T[S(w)], F[ØP(w)] - TÉ: 5
7. F[M(α)], F[S(w)], T[S(w)], F[ØP(w)] F[M(t)], T[M(t)], T[S(w)], F[ØP(w)] - TÉ: 6
Теория родственных отношений
Аксиомы:
1) Ни один человек не является родителем самого себя: "x ØP(x,x)
2) Каждый человек имеет единственного отца: "y$x!F(x,y), или
"y$x!(P(x,y) & M(х)), т.е. "y$x(P(x,y) & M(х) & "z(P(z,y) & M(z) É z=x))
3) Каждый человек имеет единственную мать: "y$x!Mt(x,y), или
"y$x(P(x,y) & ØM(х)), т.е. "y$x(P (x,y) & ØM(х)) & "z(P (z,y) & ØM(z) É z=x))
Доказать, что если х есть бабушка у по материнской линии, то х не есть мать у.
"x"y($z((P(x, z) & ØM(x)) & (P(z,y) & ØM(z))) É Ø (P(x,y) & Ø M(x)))
1. $z((P(x, z) & ØM(x)) & (P(z,y) & ØM(z))) – доп.
2. (P(x,y) & ØM(x)) – доп.
3. "y$x(P (x,y) & ØM(х)) & "z((P(z,y) & ØM(z)) É (z=x)) - аксиома
4. ((P(x, z) & ØM(x)) & (P(z,y) & ØM(z)) - $и: 1, z – а. о., х, у – о.
5. (P(x, z) & ØM(x)) - &и: 4 (х – мама z)
6. (P(z,y) & ØM(z)) - &и: 4 (z- мама y)
7. $x(P(x,y) & ØM(х)) & "z((P (z,y) & ØM(z)) É (z=x)) - "и: 3
8. (P(x,y) & ØM(x)) & "z((P(z,y) & ØM(z)) É (z=x)) - $и: 7, x – a.о., y – о.
9. "z((P (z,y) & ØM(z)) É (z=x)) - &: 8
10. ((P(z,y) & ØM(z)) É (z=x)) - "и: 9
11. (z=x) – Éи: 6, 10
12. "xØP(x,x) – аксиома
13. Ø (z=x) – из 5, 12
14. Ø(P(x,y) & Ø M(x)) - Øв: 11, 13
15. $z((P(x, z) & ØM(x)) & (P(z,y) & ØM(z))) É Ø (P(x,y) & Ø M(x))) - Éв: 14
16. "y($z((P(x, z) & ØM(x)) & (P(z,y) & ØM(z))) É Ø (P(x,y) & Ø M(x))) - "в: 15
17. "x"y($z((P(x, z) & ØM(x)) & (P(z,y) & ØM(z))) É Ø (P(x,y) & Ø M(x))) - "в: 16