17b Pritozena dedukce

  1. Metoda přirozené dedukce PL je zobecněním metody přirozené dedukce VL. Od této metody se liší pouze tím, že pracuje s obecnějším jazykem PL a v souvislosti s tím používá rozšířenou množinu výchozích dedukčních pravidel. Tato pravidla lze rozdělit do dvou hlavních skupin:
    • Pravidla přirozené dedukce z VL.
    • Pravidla pro zavedení a eliminaci kvantifikátorů.
    • Pravidla pro zavedení a eliminaci identity
  2. Vyjmenuj Pravidla přirozené dedukce z VL
    • Modus ponens (MP)
    • Modus tollens (MT)
    • Disjunktivní sylogismus (DS, ∨-E)
    • Pravidlo Dunse Scota (PDS)
    • Hypotetický sylogismus (HS)
    • Reductio ad absurdum (RAA)
    • Pravidlo simplifi kace (Simp, ∧-E)
    • Pravidlo přidání (Add, ∨-I)
    • Pravidlo dvojité negace (¬¬)
    • Pravidlo zavedení ∧ (∧-I)
    • Pravidlo De Morgana (DM-VL)
    • Pravidlo převodu ∨ na →
    • Pravidlo převodu → na ∨

    • Image Upload 1
    • Image Upload 2
    • Image Upload 3
    • Image Upload 4
  3. Vyjmenuj Pravidla pro zavedení a eliminaci kvantikátorů
    • ∀I (I∀)
    • UI ...Univerzální instanciace (či ∀E)
    • ∃I (I∃)
    • E∃ ...Existenční generalizace (či EG)

    Image Upload 5

    Image Upload 6
  4. Která pravidla používají ve své zkratce symbolů ∧ a ∨?
    • Pravidlo simplifikace (Simp, ∧-E)
    • Pravidlo přidání (Add, ∨-I)
    • Pravidlo zavedení konjunkce (∧-I)
    • Pravidlo Disjunktivní sylogismus (DS, ∨-E)

    ∧-I (apod.) je introdukce (zavedení) dané spojky, kdežto ∧-E (apod.) je eliminace
  5. O jaké pravidlo jde?
    A ∧ B
    ------
    A
    Pravidlo simplifikace (Simp, ∧-E)
  6. O jaké pravidlo jde?
    A
    ------
    A ∨ B
    Pravidlo pidání (Add, ∨-I)
  7. O jaké pravidlo jde?
    A
    B
    -------
    A ∧ B
    Pravidlo zavedení konjunkce (∧-I)
  8. O jaké pravidlo jde?
    A ∨ B
    ¬A
    ---------
    B
    Pravidlo Disjunktivní sylogismus (DS, ∨-E)
  9. O jaké pravidlo jde?
    A → B
    A
    --------
    B
    • MP
    • MP vystihuje, že platí-li u implikace antecedent A, platí i konsekvent B
  10. O jaké pravidlo jde?
    A → B
    ¬B
    ----------
    ¬A
    • MT
    • MT vystihuje, že neplatí-li u implikace konsekvent B, neplatí ani antecedent A
  11. O jaké pravidlo jde?
    A → B
    B → C
    ---------
    A → C
    • HS
    • HS vystihuje, že → je tranzitivní
  12. O jaké pravidlo jde?
    A → B
    A → ¬B
    ----------
    ¬A
    Pravidlo Reductio ad absurdum (RAA)
  13. O jaké pravidlo jde?
    ¬¬A
    --------
    A

    A
    ------
    ¬¬A
    Pravidlo dvojité negace (¬¬)
  14. O jaké pravidlo jde?

    ¬A
    --------
    B
    Pravidlo Dunse Scota (PDS)
  15. O jaké pravidlo jde?
    Image Upload 7
    Pravidlo De Morgana (DM-VL)
  16. O jaké pravidlo jde?
    Image Upload 8
    Pravidlo De Morgana (DM-VL)
  17. O jaké pravidlo jde?
    Image Upload 9
    Pravidlo převodu ∨ na →
  18. O jaké pravidlo jde?
    Image Upload 10
    Pravidlo převodu → na ∨
  19. df I∀
    • A(x)
    • --------
    • ∀x A(x)

    Podmínka: A(x) nebyla odvozena z nějakého předpokladu obsahujícího x jako volnou proměnnou.
  20. df UI
    • ∀x A(x)
    • -------
    • A[t/x]

    Podmínka: term t musí být korektně substituovatelný za x, tj. A[t/x].
  21. df I∃
    • A[t/x]
    • -------
    • ∃x A(x)

    Podmínka: term t musí být korektně substituovatelný za x, tj. A[t/x].
  22. df E∃
    • ∃x A(x)
    • ---------
    • A[t/x]

    Podmínka: při každé nové aplikaci E∃ v důkazu musíme namísto x zavést vždy novou (dosud nepoužitou) konstantu c.
  23. Vysvětli podmínku substituovatelnosti u pravidel I∃ a E∀
    • Kdyby naší formulí „A“ byla například otevřená formule R(a,x),
    • tak by volba t, jímž by bylo „x“ jakožto substituent za „a“, vedla po aplikaci I∃ k ∃x R(x,x), čímž by došlo k vázání původně volné proměnné „x“. Takže z předpokladu, že a je v relaci R k x, bychom došli k neoprávněnému závěru, že některé individuum je v relaci samo k sobě.
    • Správné je však odvodit, že nějaké individuum je vztaženo relací R k x. Proto musíme volit proměnnou odlišnou od „x“, například „y“, čímž dostaneme ∃y R(y,x). Podobně je tomu v případě E∀: například od ∃x R(x,y) chceme dojít k R(a,y), nikoli k R(y,y).
  24. Vysvětli podmínku substituovatelnosti u pravidla E∃
    • Předpoklad ∃x A(x) je pravdivý, pokud nějaké individuum je A. Uvažme, že by mezi dalšími předpoklady v důkazu byla třeba formule ∃x B(x). Jistě nemůžeme odvodit, že je to jedno a totéž individuum, jež je A i B. Oba předpoklady jsou pravdivé i tehdy, když jejich pravdivost takříkajíc způsobují jiná individua. Zde je ukázka správné aplikace daného pravidla:
    • 1. ∃x A(x) ...předpoklad
    • 2. ∃x B(x) ...předpoklad
    • 3. C(b) ...předpoklad
    • 4. A(c) ...E∃ (1); „c“ nikoli „b“ („b“ by bylo chybně)

    Povšimněme si ještě toho, že jako t je při E∃ volena konstanta, nikoli proměnná. Z  toho, že existuje nějaké A, protože třeba individuum b činí pravdivou formuli ∃x A(x), nemůžeme odvodit, že libovolné individuum y je A, tj. A(y).
  25. Vysvětli podmínku I∀, tj. A(x) / ∀x A(x).
    Podmínka tohoto pravidla zní, že formule A(x) nebyla odvozena z nějakého předpokladu obsahujícího x jako volnou proměnnou.
  26. df pravidla pro zavedení a eliminaci identity
    Image Upload 11
  27. V čem spočívá technika podmiňovaného důkazu (angl. „conditional proof “)?
    • Podstata dokazování tkví v tom, že v našem důkazu užijeme poddůkaz. Z první a předposlední formule daného poddůkazu sestavíme implikaci (označovanou CP), jež je již normální součástí hlavního důkazu. Zde je ukázka
    • Image Upload 12

    Bez podmiňovaného důkazu je dokázání některých formulí nemožné nebo velmi obtížné.
  28. Dokažte ∀x (A(x)→B(x)), A(a) ٟI- ∃x B(x):
    Image Upload 13
  29. Dokažte ∃x (A(x)∧B(x)) ٟI- ∀ x (A(x)∨¬C(x)):
    Image Upload 14
  30. Dokažte ∀x P(x) ٟI- ((P(a)∨P(b))∨Q(x)):
    Image Upload 15
  31. Dokažte ∀x∀y R(x,y) ٟI- ∀y∀x R(x,y):
    • 1. ∀x∀y R(x,y) ...předpoklad
    • 2. ∀y R(x,y) ...UI (1) (naším t je x)
    • 3. R(x,y) ...UI (2) (naším t je y)
    • 4. ∀x R(x,y) ...PG (3)
    • 5. ∀y∀x R(x,y) ...PG (4)
  32. Dokažte ∀x(A(x) ∧ B(x)) I- ∀xA(x) ∧ ∀xB(x):
    • 1. ∀x(A(x) ∧ B(x)) ...předpoklad
    • 2. A(x) ∧ B(x) ...UI (1) (naším t je x)
    • 3. A(x) ...Simp (2)
    • 4. B(x) ...Simp (2)
    • 5. ∀xA(x) ...∀I (3)
    • 6. ∀xB(x) ...∀I (4)
    • 7. ∀xA(x) ∧ ∀B(x) ...zavedení ∧ (5,6)
  33. Dokažte ∀x(P(x) → Q(x)), ∃xP(x) I- ∃xQ(x):
    • 1. ∃y∀x R(x,y) ...předpoklad
    • 2. ∀x R(x,a) ...E∃ (1)
    • 3. R(x,a) ...UI (2) (naším t je x)
    • 4. ∃y R(x,y) ...I∃ (3)
    • 5. ∀x∃y R(x,y) ...PG (4)
  34. Dokažte ∀x (A(x)→B(x)), ∀y (¬B(y)∨C(y)) ٟI- ∀ x (A(x)→C(x)):
    • 1. ∀x (A(x)→B(x)) ...předpoklad
    • 2. ∀y (¬B(y)∨C(y)) ...předpoklad
    • 3. A(x)→B(x) ...UI (1) (naším t je x)
    • 4. ¬B(x)∨C(x) ...UI (2) (naším t je x)
    • 5. B(x)→C(x) ...převod ∨ na → (4)
    • 6. A(x)→C(x) ...HS (3,5)
    • 7. ∀x (A(x)→C(x)) ...PG (6)
  35. Dokažte ∀x∃y (P(x)∧Q(y)) ٟI- ∃y∀x (P(x)∧Q(y)):
    • 1. ∀x∃y (P(x)∧Q(y)) ...předpoklad
    • 2. ∃y (P(x)∧Q(y)) ...UI (1) (naším t je x)
    • 3. P(x)∧Q(b) ...E∃ (2)
    • 4. ∀x (P(x)∧Q(b)) ...PG (3)
    • 5. ∃y∀x (P(x)∧Q(y)) ...I∃ (4)
  36. Dokažte ∀x(M(x) → ¬P(x)), ∃x(S(x)∧M(x)) I- ∃x(S(x)∧ ¬P(x)),
    tj. sylogismus modu festino:
    Image Upload 16
  37. Dokažte ∀x (M(x)→¬P(x)), ∀x (S(x)→M(x)) ٟI- ∀ x (S(x)→¬P(x)), tj. sylogismus modu celarent:
    Image Upload 17
  38. Dokažte ∀x ¬P(x) ٟI- ∃¬ x P(x) (důkaz sporem):
    • 1. ∀x ¬P(x) předpoklad
    • 2. ¬¬∃x P(x) ...předpoklad důkazu sporem
    • 3. ∃x P(x) ...¬¬ (2)
    • 4. P(a) ...E∃ (3)
    • 5. ¬P(a) ...UI (1)
    • 6. ¬∃x P(x) ...reductio (4,5)
  39. Dokažte ¬∃x ¬P(x) ٟI- ∀x P(x) (důkaz sporem):
    • 1. ¬∃x ¬P(x) ...předpoklad
    • 2. ¬P(x) ...předpoklad důkazu sporem
    • 3. ∃x ¬P(x) ...I∃ (2)
    • 4. P(x) ...reductio (1,3)
    • 5. ∀x P(x) ...PG (4)
  40. Dokažte ∃xA(x) → ∀x(B(x) → C(x)), A(a) ∧ B(a) I- C(a):
    • 1. ∃xA(x) → ∀x(B(x) → C(x)) ...předpoklad
    • 2. A(a) ∧ B(a) ...předpoklad
    • 3. A(a) ...Simp (2)
    • 4. ∃xA(x) ...∃I (3)
    • 5. ∀x(B(x) → C(x)) ...MP (1,4)
    • 6. B(a) → C(a) ...UI (5)
    • 7. B(a) ...Simp (2)
    • 8. C(a) ...MP (6,7)
  41. Dokažte ∀x(A(x) → B(x)) → ∀x(C(x) → A(x)), ∀x¬A(x) I- ∀x¬C(x):
    • 1. ∀x(A(x) → B(x)) → ∀x(C(x) → A(x)) ...předpoklad
    • 2. ∀x¬A(x) ...předpoklad
    • 3. ¬A(x) ...UI (2) (naším t je x)
    • 4. ¬A(x) ∨ B(x) ...Add (3)
    • 5. A(x) → B(x) ...převod ∨ na → (4)
    • 6. ∀x(A(x) → B(x)) ...∀I (5)
    • 7. ∀x(C(x) → A(x)) ...MP (1,6)
    • 8. C(x) → A(x) ...UI (7) (naším t je x)
    • 9. ¬C(x) ...MT (8,3)
    • 10. ∀x¬C(x) ...∀I (9)
  42. Dokažte ∀xP(x) I- P(a) ∨ P(b):
    • 1. ∀xP(x) ...předpoklad
    • 2. P(a) ...UI (1)
    • 3. P(a) ∨ P(b) ...Add (2)
  43. Dokažte ∀y∃xR(x, y) I- ∃x∀yR(x, y):
    • 1. ∀y∃xR(x, y) ...předpoklad
    • 2. ∃xR(x, y) ...UI (1) (naším t je y)
    • 3. R(a, y) ...∃E (2)
    • 4. ∀yR(a, y) ...∀I (3)
    • 5. ∃x∀yR(x, y) ...∃I (4)
  44. Dokažte ∀x∃y(P(x) ∧ Q(y)) I- ∃y∀x(P(x) ∧ Q(y)):
    • 1. ∀x∃y(P(x) ∧ Q(y)) ...předpoklad
    • 2. ∃y(P(x) ∧ Q(y)) ...UI (1) (naším t je x)
    • 3. P(x) ∧ Q(a) ...∃E (2)
    • 4. ∀x(P(x) ∧ Q(a)) ...∀I (3)
    • 5. ∃y∀x(P(x) ∧ Q(y)) ...∃I (4)
Author
iren
ID
355234
Card Set
17b Pritozena dedukce
Description
predikatova logika (274s)
Updated