17b Prirozena dedukce II

  1. Dokažte ∀x(A(x) → B(x)), ∃x(A(x) ∧ C(x)) I- ∃x(C(x) ∧ B(x)):
    • 1. ∀x(A(x) → B(x)) ...předpoklad
    • 2. ∃x(A(x) ∧ C(x)) ...předpoklad
    • 3. A(a) ∧ C(a) ...∃E (2)
    • 4. A(a) → B(a) ...UI (1) (naším t je a)
    • 5. A(a) ...Simp (3)
    • 6. B(a) ...MP (4,5)
    • 7. C(a) ...Simp (3)
    • 8. C(a) ∧ B(a) ...I∧ (7,6)
    • 9. ∃x(C(x) ∧ B(x)) ...∃I (8)
  2. Dokažte ∀x((A(x) ∨ B(x)) → ¬C(x)), ∃xA(x) I- ∃x¬C(x):
    • 1. ∀x((A(x) ∨ B(x)) → ¬C(x)) p°edpoklad
    • 2. ∃xA(x) p°edpoklad
    • 3. A(a) ...∃E (2)
    • 4. (A(a) ∨ B(a)) → ¬C(a) ...UI (1)
    • 5. A(a) ∨ B(a) ...Add (3)
    • 6. ¬C(a) ...MP (4,5)
    • 7. ∃x¬C(x) ...∃I (6)
  3. Dokažte ∀x((A(x) → B(x)), ∃x(C(x) ∧ A(x)) I- ∃x(C(x) ∧ B(x)):
    • 1. ∀x((A(x) → B(x)) ...předpoklad
    • 2. ∃x(C(x) ∧ A(x)) ...předpoklad
    • 3. C(a) ∧ A(a) ...∃E (2)
    • 4. (A(a) → B(a) ...UI (1) (naším t je a)
    • 5. A(a) ...Simp (3)
    • 6. C(a) ...Simp (3)
    • 7. B(a) ...MP (5,4)
    • 8. C(a) ∧ B(a) ...∧I (6,7)
    • 9. ∃x(C(x) ∧ B(x)) ...∃I (8)
  4. Dokažte ∀x((C(x) → ¬Z(x)), ∃x(S(x) ∧ Z(x)) I- ∃x(S(x) ∧ ¬C(x)):
    • 1. ∀x((C(x) → ¬Z(x)) ...předpoklad
    • 2. ∃x(S(x) ∧ Z(x)) ...předpoklad
    • 3. S(a) ∧ Z(a) ...∃E (2)
    • 4. C(a) → ¬Z(a) ...UI (1)
    • 5. Z(a) ...Simp (3)
    • 6. ¬C(a) ...MT (4,5)
    • 7. S(a) ...Simp (3)
    • 8. S(a) ∧ ¬C(a) ...∧I (6,7)
    • 9. ∃x(S(x) ∧ ¬C(x)) ...∃I (8)
  5. Dokažte ∃x A(x)→∀x (B(x)→C(x)), A(a)∧B(a) ٟI- C(a):
    Image Upload 1
  6. Dokažte ∀x (A(x)→B(x)), ∃x (A(x)∧C(x)) ٟI- ∃ x (C(x)∧B(x)):
    Image Upload 2
  7. Dokažte ∀x∀y (P(x,y)→¬P(y,x)), ∀x∀y (P(y,x)↔¬(Q(x,y)∨R(y,x))), ∀x∀y (P(x,y)→¬R(y,x)), P(a,b) ٟI- Q(b,a):
    Image Upload 3
  8. Dokažte ∀x (A(x)→B(x))→∀x (C(x)→A(x)), ∀x ¬A(x) ٟI- ∀ x ¬C(x):
    Image Upload 4
  9. Dokažte ∃x A(x)→B(y) ٟI- ∀ x (A(x)→B(y)) (podmiňovaný důkaz, CP):
    Image Upload 5
  10. Dokažte ∀x (P(x)→Q(x)) ٟI- (∃x P(x)→∃x Q(x)): (CP)
    Image Upload 6
  11. Dokažte ∀x(A(x) → B(x)) I- ∀x(A(x) → (B(x) ∨ C(x))): (CP)
    Image Upload 7
  12. Dokažte I- ¬∀xA(x) ↔ ∃x¬A(x), tj. De Morganův zákon (důkaz formule tvaru ↔ spočívá v důkazu obou směrů ↔, tj. v důkazu → a ←):
    • Image Upload 8
    • Image Upload 9

    • Podle věty o dedukci odpovídají tomuto teorému následující odvozená dedukční pravidla, jež budeme značit DM:
    • Image Upload 10

    Důkaz ¬∃x A(x)↔∀x ¬A(x) je prakticky izomorfní, proto jsou příslušná dvě odpovídající pravidla níže značena rovněž DM
  13. Dokažte ¬∃x¬(P(x) → Q(x)), ¬∃xQ(x) I- ¬∀xP(x) (Pravidlo záměny kvantifikátorů, DM, je dokázáno výše):
    Image Upload 11
  14. Dokažte ¬∃x(P(x) ∧ ¬Q(x)), ¬∀x(¬R(x) ∨ Q(x)) I- ∃x¬P(x)
    (Pravidlo záměny kvantifikátorů, DM, je dokázáno ob jeden příklad výše):
    Image Upload 12
  15. Dokažte ∀x∀y(P(x, y) → ¬P(y, x)), ∀x∀y(P(y, x) ↔
    ¬(Q(x, y) ∨ R(y, x))), ∀x∀y(P(x, y) → ¬R(y, x)), P(a, b) I- Q(b, a):
    Image Upload 13
  16. Dokažte ∀x (A(x)→B(x))→∀x (C(x)→A(x)), ∀x ¬A(x) ٟI- ∀x ¬C(x):
    Image Upload 14
  17. Dokažte ∀x(P(x) → (x≠a)) I- ¬P(a):
    Image Upload 15
  18. Dokažte I- (t1 = t2) ↔ (t2 = t1), tj. zákon komutativity =:
    Image Upload 16
  19. Dokažte ∀x(∃y(x=y) → F(x)),(b=a) I- F(a):
    Image Upload 17
  20. Dokažte P(b), ¬∀x((x=b) → P(x)) I- ¬P(b):
    Image Upload 18
  21. Dokažte I- (t1 = t2) → ((t2 = t3) → (t1 = t3)), tj. zákon tranzitivity identity:
    Image Upload 19

    E= (1,2; na základě 1 dosazujeme do (x=t3))
  22. Dokažte
    F(a) ∧ ∀x(F(x) → (x = a)),(a 6= b), G(b) I- ∃x(G(x) ∧ ¬F(x)):
    Image Upload 20
Author
iren
ID
355235
Card Set
17b Prirozena dedukce II
Description
predikatova logika
Updated