-
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
-
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 ∨
-
Vyjmenuj Pravidla pro zavedení a eliminaci kvantikátorů
- ∀I (I∀)
- UI ...Univerzální instanciace (či ∀E)
- ∃I (I∃)
- E∃ ...Existenční generalizace (či EG)
-
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
-
O jaké pravidlo jde?
A ∧ B
------
A
Pravidlo simplifikace (Simp, ∧-E)
-
O jaké pravidlo jde?
A
------
A ∨ B
Pravidlo pidání (Add, ∨-I)
-
O jaké pravidlo jde?
A
B
-------
A ∧ B
Pravidlo zavedení konjunkce (∧-I)
-
O jaké pravidlo jde?
A ∨ B
¬A
---------
B
Pravidlo Disjunktivní sylogismus (DS, ∨-E)
-
O jaké pravidlo jde?
A → B
A
--------
B
- MP
- MP vystihuje, že platí-li u implikace antecedent A, platí i konsekvent B
-
O jaké pravidlo jde?
A → B
¬B
----------
¬A
- MT
- MT vystihuje, že neplatí-li u implikace konsekvent B, neplatí ani antecedent A
-
O jaké pravidlo jde?
A → B
B → C
---------
A → C
- HS
- HS vystihuje, že → je tranzitivní
-
O jaké pravidlo jde?
A → B
A → ¬B
----------
¬A
Pravidlo Reductio ad absurdum (RAA)
-
O jaké pravidlo jde?
¬¬A
--------
A
A
------
¬¬A
Pravidlo dvojité negace (¬¬)
-
O jaké pravidlo jde?
A
¬A
--------
B
Pravidlo Dunse Scota (PDS)
-
O jaké pravidlo jde?
Pravidlo De Morgana (DM-VL)
-
O jaké pravidlo jde?
Pravidlo De Morgana (DM-VL)
-
O jaké pravidlo jde?
Pravidlo převodu ∨ na →
-
O jaké pravidlo jde?
Pravidlo převodu → na ∨
-
df I∀
Podmínka: A(x) nebyla odvozena z nějakého předpokladu obsahujícího x jako volnou proměnnou.
-
df UI
Podmínka: term t musí být korektně substituovatelný za x, tj. A[t/x].
-
df I∃
Podmínka: term t musí být korektně substituovatelný za x, tj. A[t/x].
-
df E∃
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.
-
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).
-
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).
-
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.
-
df pravidla pro zavedení a eliminaci identity
-
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
Bez podmiňovaného důkazu je dokázání některých formulí nemožné nebo velmi obtížné.
-
Dokažte ∀x (A(x)→B(x)), A(a) ٟI- ∃x B(x):
-
Dokažte ∃x (A(x)∧B(x)) ٟI- ∀ x (A(x)∨¬C(x)):
-
Dokažte ∀x P(x) ٟI- ((P(a)∨P(b))∨Q(x)):
-
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)
-
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)
-
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)
-
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)
-
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)
-
Dokažte ∀x(M(x) → ¬P(x)), ∃x(S(x)∧M(x)) I- ∃x(S(x)∧ ¬P(x)),
tj. sylogismus modu festino:
-
Dokažte ∀x (M(x)→¬P(x)), ∀x (S(x)→M(x)) ٟI- ∀ x (S(x)→¬P(x)), tj. sylogismus modu celarent:
-
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)
-
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)
-
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)
-
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)
-
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)
-
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)
-
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)
|
|
