Výroková a predikátová logika – zkouška LS 2008

Zadání

27.5.2008 – «předtermín» – podle SISu tam mělo být 10 lidí, ale nakonec nás tam bylo minimálně 20 (údajně se domlouvali s prof. Štěpánkem přes email...)
http://forum.matfyz.info/viewtopic.php?f=239&t=4434

4. 6. 2008 – písemka
http://forum.matfyz.info/viewtopic.php?f=239&t=4488 (Sorry, Martine, takhle je to podle me lepsi, nez to sem cely kopirovat. ČH )

9. 6. 2008

Podobně jako dříve: 6 příkladů za max. 50 bodů. První tři na výrokovou a další tři na predikátovou logiku. Jednalo se o běžnou logiku «jako na přednášce», žádný tahák (jako axiomy nebo definice) tam nebyl, jen upřesnění značení (x, y, z, proměnné, p, ... predikátové, f, ... fční symboly apod.). Po paměti zadání, tak snad je to správně:

Je formule \left( (A \rightarrow (B \rightarrow A)) \,\&\, (B \rightarrow (\neg C \vee D)) \right) \;\rightarrow\; \left( (A \& B) \,\rightarrow\, (C \rightarrow D) \right) tautologie? Pokud ano, proveďte důkaz pomocí vhodných axiomů, základních vět výrokové logiky a odvozovacích pravidel. V opačném případě uveďte ohodnocení, při kterém formule není pravdivá. [5 bodů]
Totéž pro (A \rightarrow (B \rightarrow C) ) \leftrightarrow ((A \rightarrow B) \rightarrow C ) (nebo tak nějak, rozhodně to teda nerozdíl od 1. nebyla tautologie, neplatila třeba při ohodnocení všech A,B i C 0). [5 bodů]
(Snad si pamatuju.) Dokažte, že maximální bezesporná teorie obsahuje vždy buď \neg A nebo A. [10 bodů]
Dokažte: T \vdash A \;\Leftrightarrow\; T \cup \{ \neg\,\text{uzávěr}\,A \} \text{ je sporná} (důsledek věty o dedukci). [10 bodů]
Druha skupina mela presne napsat zneni vety o dedukci v predikatove logice a dokazat ji.
(Něco na úplnost teorie. Ukažte, že... Teď to nějak nemůžu dát dohromady.)) Doplňte to někdo, prosím, pokud si vzpomínáte. [10 bodů]
Myslím, že šlo o to, co je ve slajdech pod názvem «užitečné lemma», takže zadání rekonstruuju pomocí slajdů, snad je to ono:

Nechť L' je rozšířením jazyka L a nechť T je teorie s jazykem L a T' teorie s jazykem L'.

Dokažte: Je-li T' rozšířením T, tak redukt M'|L každého modelu M' teorie T' je modelem T. (Místo redukt bylo v písemce restrikce//, symbolický zápis ale stejný.) [4 body]
Dokažte obrácenou implikaci. (Tohle bylo formulováno nějak krkolomně, ale šlo o obrácenou implikaci.) [6 bodů]

Mně to přišlo docela těžké, ale hlavně proto, že mám dost maglajs v těch posledních přednáškách:/ (5., 6. příklad), tak ani nevím, jestli jsem tu zkoušku udělal (update: jo, udělal:)). Víc bych ocenil nějakou elementární aritmetiku, prenexní, normální tvary a tak, tam člověk ví na čem je;). Ale někdo by taky mohl říct, proč lezu na zkoušku, když to pořádně neumím — je fakt, že nic vyloženě záludného nebo nečekaného tam vlastně nebylo. — Adam

18.6.

Viz http://forum.matfyz.info/viewtopic.php?f=239&t=4567

24.6.

Viz http://forum.matfyz.info/viewtopic.php?f=239&t=4600

Poznámky

Zkouška je pouze písemná a trvá dvě hodiny. Prý je hodnocená poměrně mírně (ale moc bych na to nespoléhal). — To mi aspoň říkal Jakub Melka, který už na zkoušce byl. — Adam

Já to můžu potvrdit. Taky jsem se strachoval o svých 22 bodů, abych prolezl a nakonec mam dvojku. ČH
Tak já to nakonec dal na tři, takže nic moc, ale dobrý;). Zdá se, že je to fakt systém: těžké zadání + poměrně mírné hodnocení, což je docela fér. — Adam

Výsledky jsou po pár dnech v SISu. Pokud jste byli na zkoušce v úterý 10., tak teď už tam asi výsledky máte (mně se tam objevily už kolem 10. ráno v pátek 13. 6.).
Tak ja jsem na zkousce desateho byl, a v SISu jsem mel vysledek az v pondeli 16. No sice to trvalo ale aspon ze sem to dal (za tri :) ) Karl
No, já byl napjatej jak špagát (to je lepší než fotbal nebo nějaký reality show;)), takže nezávidím. Mmch, nevíš, jak byl ten pátej příklad (viz nahoře)? — Adam
Bohuzel, z toho zadani si pamatuju akorat to, ze jsem mel asi trochu jine nez ty. A dokazat vetu o dedukci coz jsem zvladl asi jen v jednom smeru. Karl
To je vlastně docela logický, když jsme seděli ve stejný lavici:).
Bylo jen 6 příkladů, 2x5 a 4x10 bodu.... mam za 1, zadani mi prislo oproti minulymu o dost jednodussi tk

Při zkoušce jsem se Štěpánka zeptal, zda je v důkazech v formulí v první části dovolené používat větu o ekvivalenci (přestože nebyla v zadání ve výčtu povolených prostředků). Prý samozřejmě ano. — Adam

Jsou u zkousky povoleny nejake pomucky jako zapisky, seznam vet z prednasky nebo neco takoveho? Diky Karl

Ne, dokonce výslovně řekl, že by nerad, kdybychom používali třeba vlastní čmárací papíry. (Každý příklad je na zvláštním listu, tak se bez toho dá obejít.) — Adam

Jinak ještě poznámka k temporální logice – vypadá to, že se nezkouší. Ale jestli tuhle wiki čte i Štěpánek, tak příště už to platit nebude (sakra, to zní skoro jako nějaký tvrzení v temporální logice) ČH

Jo, je to non A & ( B -> o A) :))