14b přirozená dedukce

  1. Kdo je autorem přirozené dedukce a co měl proti Hilbertovské dedukci?:)
    • Gerhard Gentzen- Hilbertovská dedukce neodpovídá přirozenému usuzování
    • Gentzenem navržená přirozená dedukce je založena na množství jednoduchých pravidel
    • důkazová síla tedy neleží v axiomech, ale v pravidlech
  2. Popiš vlastnosti systému přirozené dedukce
    • introdukční pravidla zavádějí spojku, jež se nevyskytuje v předpokladech pravidla; u eliminačních pravidel se naopak tato spojka vyskytuje mezi jejich předpoklady, nikoli v jejich závěrech (např. MP je eliminací →)
    • pravidla vystihují sémantickou definici (= tabulka) té či oné spojky
    • obecně platí, že každou tautologii tvaru A → B (→ může být `skryta' v ↔) lze převést na pravidlo tvaru A/B (např. De Morganovy zákony se dají takto předělat)
    • správná odvození (důkazy) formule B z předpokladů A1, A2, ... jsou odvozenými pravidly tvaru A1, A2, .../B

    Image Upload 1
  3. Modus ponens (MP)
    • A → B
    • A
    • ----------
    • B

    MP vystihuje, že platí-li u implikace antecedent A, platí i konsekvent B
  4. Modus tollens (MT)
    • A → B
    • ¬B
    • ---------
    • ¬A

    • MT vystihuje, že neplatí-li u implikace konsekvent B, neplatí ani antecedent A
    • MT vystihuje, že → je tranzitivní
  5. Pravidlo Hypotetický sylogismus (HA)
    • A → B
    • B → C
    • --------
    • A → C
  6. Pravidlo Reductio ad absurdum (RAA)
    • A → B
    • A → ¬B
    • ---------
    • ¬A
  7. Pravidlo simplifikace (Simp či ∧-E)
    • A ∧ B
    • ----------
    • A

    • nebo
    • A ∧ B
    • --------
    • B

    ∧-E je eliminace
  8. Pravidlo přidání (Add či ∨-I)
    • A
    • ------------
    • A ∨ B

    • nebo
    • B
    • ------------
    • A ∨ B

    introdukce (zavedení)
  9. Pravidlo zavedení konjunkce (∧-I)
    • A
    • B
    • -------
    • A ∧ B

    • nebo
    • B
    • A
    • ------------
    • A ∧ B
  10. Pravidlo Disjunktivní sylogismus (DS či ∨-E)
    • A ∨ B
    • ¬A
    • --------
    • B

    • nebo
    • A ∨ B
    • ¬B
    • ----------
    • A
  11. Image Upload 2
    Image Upload 3
  12. Dokažte, že z formulí A → (B → C), D → (C → E), A a D lze odvodit B → E.
    Image Upload 4
  13. Dokažte, že z formulí A a ¬A lze odvodit B, tedy Pravidlo Dunse
    Scota.
    Image Upload 5
  14. Dokažte, že z formulí A → B, C → D, A a ¬D lze odvodit (A ∧ ¬D) ∧ (B ∧ ¬C).
    Image Upload 6
  15. Dokažte, že z formulí A → B, ¬B ∧ C, D ∧ E a (¬A ∧ D) → F lze odvodit F ∧ C.
    Image Upload 7
  16. Dokažte, že z formulí A → (B → C), C ∨ A a ¬C lze odvodit ¬B.
    Image Upload 8
  17. Dokažte, že z formulí A → B, (B ∨ C) → (D ∧ E) a A lze odvodit D.
    Image Upload 9
  18. Dokažte, že z formulí A → B, B → C, C → D a ¬D lze odvodit (A → C) ∧ (¬B ∧ ¬C).
    Image Upload 10
  19. Dokažte, že z formulí A → B a ¬B lze odvodit ¬A, tedy Modus tollens. Důkaz sporem.
    Image Upload 11
  20. Dokažte, že z formulí A → (B → C), D → (C → E), A ∨ F, ¬F a D lze odvodit (B → C) ∧ (B → E).
    Image Upload 12
  21. Dokažte, že z formulí A → B a A → ¬B lze odvodit ¬A, tedy Pravidlo Reductio ad absurdum. Důkaz sporem.
    Image Upload 13
  22. Dokažte, že z formulí A → ¬(B ∧ C) a A ∧ C lze odvodit ¬B.
    Image Upload 14
  23. Dokažte, že z formulí (B → C) → A a ¬(D ∨ A) lze odvodit B.
    Image Upload 15
  24. Dokažte, že z formulí (A ∧ B) ∨ C a ¬A ∧ ¬D lze odvodit C.
    Image Upload 16
  25. Dokažte, že z formulí ¬A → B a A → (C ∨ D) lze odvodit ¬C → (¬D → B).
    Image Upload 17
  26. Dokažte, že z formulí (A → ¬B) ∧ ¬C a B → (¬A → C) lze odvodit B → A
    Image Upload 18
  27. Dokažte, že z formulí A → B, C → (D ∧ E), ¬C → ¬B a D → (E → A) lze odvodit A ↔ C.
    Image Upload 19
  28. Dokažte, že z formulí A → B, C → D a ¬B ∨ ¬D lze odvodit ¬A ∨ ¬C, tedy Pravidlo Destruktivní dilema. Důkaz sporem.
    Image Upload 20
Author
iren
ID
354254
Card Set
14b přirozená dedukce
Description
VÝROKOVÁ LOGIKA
Updated