Toto je stará verze stránky VýrokováAPredikátováLogika/ZkouškaLS2008 z 2008-06-11 00:52:47..

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ů]
(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). Víc bych ocenil nějakou elementární aritmetiku, prenexní, normální tvary a tak;). 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

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

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.

Jsou u zkousky povoleny nejake pomucky jako zapisky, seznam vet z prednasky nebo neco takoveho? Diky Karl
Tak to netuším. Zkus spíš fórum. Výslovně nic takovýho ale neříkal. ČH

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) :))