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

[ufi]

[Mikina]

Nekdo nemate reseni 1. priklad?
To vubec nejde.

[hkvm]

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

[Mikina]

Super ale v pripade
(A->B)->[(C->D)->((AvC)->(BvC))]
jak to resis?

[hkvm]

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

[Mikina]

Jo super diky

[Návštěvník]

Už vám Malenkov napsal zápočet do sisu?

[Mikina]

Rekl ze Pan stepanek bude psat zapocet.

[Xerxes]

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

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...