# Zápočtová písemka - cvičení Malenko

<{ForumPost(poster="ufi", timestamp=2009-01-14 18:20:39)}>
[http://img26.picoodle.com/img/img26/3/1 ... 935301.png](http://img26.picoodle.com/img/img26/3/1/14/f_pisemkam_2935301.png)
<{/ForumPost}>

<{ForumPost(poster="Mikina", timestamp=2009-01-16 21:29:43)}>
Nekdo nemate reseni 1. priklad?  
To vubec nejde.  :oops:
<{/ForumPost}>

<{ForumPost(poster="hkvm", timestamp=2009-01-16 23:29:42)}>
Snad to nebude blbost ;-)  
  
Dokazuju tohle (přepsáno bez '&' dle definice '&'): **(A → B) → ((C → D) → (¬(A → ¬C) → ¬(B → ¬D)))**  
  
(1) **|- D → (¬¬B → ¬(D → ¬B))**  ; V6: A → (¬B → ¬(A → B))  
(2) **A → B, C → D, A, C |- D**  ; předpoklady navíc, MP z předpokladů  
(3) **A → B, C → D, A, C |- B**  ; MP z předpokladů  
(4) **A → B, C → D, A, C |- ¬¬B**  ; V4: B → ¬¬B, MP  
(5) **A → B, C → D, A, C |- ¬(D → ¬B)**  ; 2x MP z (1), (2), (4)  
(6) **A → B, C → D, A, C |- (B → ¬D) → (D → ¬B)**  ; tautologie kterou nebudu dokazovat: (A → ¬B) → (B → ¬A)  
(7) **A → B, C → D, A, C |- ¬(D → ¬B) → ¬(B → ¬D)**  ; V5: (A → B) → (¬B → ¬A), MP  
(8) **A → B, C → D, A, C |- ¬(B → ¬D)**  ; MP z (6), (7)  
(9) **A → B, C → D, A |- C → ¬(B → ¬D)**  ; VD  
(10) **A → B, C → D, A |- (C → ¬(B → ¬D)) → ((B → ¬D) → ¬C)**  ; zase ta tautologie z (6)  
(11) **A → B, C → D, A |- (B → ¬D) → ¬C**  ; MP z (9), (10)  
(12) **A → B, C → D, A, B → ¬D |- ¬C**  ; VD  
(13) **A → B, C → D, B → ¬D |- A → ¬C**  ; VD  
(14) **A → B, C → D |- (B → ¬D) → (A → ¬C)**  ; VD  
(15) **A → B, C → D |- ¬(A → ¬C) → ¬(B → ¬D)**  ; V5, MP  
(16) **A → B |- (C → D) → (¬(A → ¬C) → ¬(B → ¬D))**  ; VD  
(17) **|- (A → B) → ((C → D) → (¬(A → ¬C) → ¬(B → ¬D)))**  ; VD  
(18) **|- (A → B) → ((C → D) → ((A & C) → (B & D)))**  ; definice '&'  
  
Nebo i s větama o spojce '&':  
(1) **A → B, C → D , A & C |- B → (D → (B & D))**  ; tautologie + předpoklady navíc  
(2) **A → B, C → D , A & C |- C ** ; z A & C |- C  
(3) **A → B, C → D , A & C |- A**  ; z A & C |- A  
(4) **A → B, C → D , A & C |- B**  ; MP z (3) a předpokladu  
(5) **A → B, C → D , A & C |- D**  ; MP z (2) a předpokladu  
(6) **A → B, C → D , A & C |- B & D**  ; 2x MP z (1), (4), (5)  
(7) **A → B, C → D |- (A & C) → (B & D)**  ; VD  
(8) **A → B |- ((C → D) → ((A & C) → (B & D)))**  ; VD  
(9) **|- (A → B) → ((C → D) → ((A & C) → (B & D)))**  ; VD
<{/ForumPost}>

<{ForumPost(poster="Mikina", timestamp=2009-01-18 00:51:45)}>
Super ale v pripade  
(A->B)->\[(C->D)->((AvC)->(BvC))]  
jak to resis?
<{/ForumPost}>

<{ForumPost(poster="hkvm", timestamp=2009-01-18 13:12:26)}>
Asi jsi myslel tohle:  
**(A → B) → ((C → D) → ((A ∨ C) → (B ∨ D))**  
(v tom co jsi napsal byla poslední formule zase C)  
  
Nejdřív dokážu lemma: **(D → A) → ((¬D → A) → A)**  
  
(1) **|- (¬A → D) → ((D → A) → (¬A → A))**  ; tautologie: skládání implikací  
(2) **D → A, ¬D → A |- ¬D → A**  ; předpoklad navíc, v1 + VD  
(3) **D → A, ¬D → A |- ¬A → ¬¬D**  ; v5: (A → B) → (¬B → ¬A), MP  
(4) **D → A, ¬D → A |- ¬A → D**  ; VD, v4: ¬¬D → D, VD  
(5) **D → A, ¬D → A |- ((D → A) → (¬A → A))**  ; MP z (1), (4)  
(6) **D → A, ¬D → A |- ¬A → A**  ; MP z (5) a předpokladu  
(7) **D → A, ¬D → A |- (¬A → A) → A**  ; v7: (¬A → A) → A  
(8) **D → A, ¬D → A |- A**  ; MP z předchozích dvou  
(9) **|- D → A → ((¬D → A) → A)**  ; 2x VD  
  
Teď ten příklad, přepsán dle definice disjunkce: **(A → B) → ((C → D) → ((¬A → C) → (¬B → D))**  
  
(1) **A → B, C → D, ¬A → C |- (A → (¬B → D)) → ((¬A → (¬B → D)) → (¬B → D)) ** ; to lemma + předpoklady navíc  
(2) **A → B, C → D, ¬A → C, A |- B ** ; předpoklad A → B + VD  
(3) **A → B, C → D, ¬A → C, A |- B → (¬B → D) ** ; v2: A → (¬A → C)  
(4) **A → B, C → D, ¬A → C, A |- ¬B → D**  ; MP z předchozích dvou  
(5) **A → B, C → D, ¬A → C |- A → (¬B → D)**  ; VD  
(6) **A → B, C → D, ¬A → C |- (¬A → (¬B → D)) → (¬B → D) ** ; MP z (1), (5)  
(7) **A → B, C → D, ¬A → C, ¬A |- C**  ; předpoklad ¬A → C + VD  
(8) **A → B, C → D, ¬A → C, ¬A |- D ** ; MP z (7) a předpokladu  
(9) **A → B, C → D, ¬A → C, ¬A |- D → (¬D → B) ** ; v2  
(10) **A → B, C → D, ¬A → C, ¬A |- ¬D → B**  ; MP z předchozích dvou  
(11) **A → B, C → D, ¬A → C, ¬A |- ¬B → ¬¬D**  ; v5 + MP  
(12) **A → B, C → D, ¬A → C, ¬A |- ¬B → D**  ; VD + v4 + VD  
(13) **A → B, C → D, ¬A → C |- ¬A → (¬B → D) ** ; VD  
(14) **A → B, C → D, ¬A → C |- ¬B → D**  ; MP z (13) a (6)  
(15) **A → B, C → D,  |- (¬A → C) → (¬B → D) ** ; VD  
(16) **A → B |- (C → D) → ((¬A → C) → (¬B → D)) ** ; VD  
(17) **|- (A → B) → ((C → D) → ((¬A → C) → (¬B → D))) ** ; VD  
(18) **|- (A → B) → ((C → D) → ((A ∨ C) → (B ∨ D))) ** ; definice disjunkce
<{/ForumPost}>

<{ForumPost(poster="Mikina", timestamp=2009-01-18 14:13:03)}>
Jo super diky  :mrgreen:
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2009-01-19 21:14:23)}>
Už vám Malenkov napsal zápočet do sisu?
<{/ForumPost}>

<{ForumPost(poster="Mikina", timestamp=2009-02-06 11:28:40)}>
Rekl ze Pan stepanek bude psat zapocet.
<{/ForumPost}>

<{ForumPost(poster="Xerxes", timestamp=2009-02-14 11:33:53)}>
Ty formule z výrokové logiky se dají dokázat i mnohem snadněji s využitím dalších vět z přednášky, ta ze zadání je tak podrobně vyřešena například zde (hned druhý příklad):  
  
[http://www.ms.mff.cuni.cz/~pelcj6am/vpl_dukazy.pdf](http://www.ms.mff.cuni.cz/~pelcj6am/vpl_dukazy.pdf)  
  
Ne že by byl postup od hkvm špatně, ale já takové obří důkazy nikdy neuměl vymýšlet :-). Vždy si raději všechny předpoklady vhodně nacpu do množiny T, z nich dokážu tvrzení a pak to vrátím větou o dedukci do původní formy. Ušetří spoustu psaní  ;-).  
  
Jinak příklady 5 a 6 jsou ve zmíněném textu taky vyřešené (snad dobře... nikdo se mi neozval, že by to bylo špatně).  
  
P.S.:  
  
Naprosto identickou písemku (pokud si pamatuju) jsme s Malenkem psali loni...
<{/ForumPost}>