Zkouška 16. 9. 2008

Včerejší zkouška, skupina A:

Výroková logika

1)
a) Formulujte větu o důkazu rozborem případů. (1 bod)
b) Dokažte: (¬A -> B) <-> (¬B -> A) (4 body)

2) Dokažte větu o ekvivalenci. (5 bodů)

3) Množina formulí T je úplná, je-li bezesporná a pro každou formuli A platí T |= A nebo T |= ¬A.
Dokažte, že každá maximální bezesporná množina je úplná. (10 bodů)

Predikátová logika

4) Nechť T a T' jsou teorie.
a) Definujte, kdy je T' rozšířením T. (1 bod)
b) Dokažte, že je-li T' rozšířením T a T' je bezesporná, potom je i T bezesporná. (9 bodů)

5)
a) Formulujte větu o konstantách. (1 bod)
b) Formulujte větu o dedukci a ukažte, jak lze její použití rozšířit pomocí věty o konstantách. (9 bodů)

6) Jsou dány axiomy Peanovy aritmetiky. Dokažte:
a) 0 * y = y * 0 (3 body)
b) x * y = y * x (7 bodů)

Komentář

1. a) Viz přednáška.
   b) Stačí dokázat jednu implikaci, opačná se dokáže naprosto stejně přejmenováním formulí. Lze velmi snadno pomocí důkazu rozborem případů a monotonnosti disjunkce (jde vlastně o komutativitu disjunkce), ale to jsem si neuvědomil a dokazoval větu ¬A -> B, ¬B |- A, odkud plyne dokazovaná pomocí věty o dedukci. Další dva možné postupy jsou uvedeny v mém textu (je to věta (V5'), případně komutativita disjunkce).

2. Viz přednáška.

3. Nechť T je maximální bezesporná, potom je také bezesporná. Zbývá ukázat, že pro každou formuli A je T |= A nebo T |= ¬A. Pro spor nechť neplatí ani T |= A, ani T |= ¬A. Podle věty o úplnosti to znamená, že neplatí ani T |- A, ani T |- ¬A. To, že neplatí T |- ¬A, znamená, že ¬A není v T (sporem). To, že neplatí T |- A, znamená, že T u {¬A} je bezesporná (věta z přednášky). Protože ale víme, že ¬A není v T, není T maximální bezesporná a máme spor.

4. a) Viz přednáška.
   b) Viz přednáška, případně můj text.

5. a) Viz přednáška.
   b) Viz přednáška.

6. Oba důkazy přidám co nejdřív do svého textu.

Můj text:
http://forum.matfyz.info/viewtopic.php?f=239&t=4663

P.S.:
Známky slíbil do dvou dnů, ta má mi už došla. 8)

Nevíte někdo jak je to se zapisováním do indexu? zase v úterý při zkoušce? Jsem si byl skoro jistej, že neudělám, takže jsem se nezajímal :-)

Ano, prof. Štěpánek říkal, že u zkoušky bude. Psal jsem mu, že bych to potřeboval dříve, a odpověděl mi, že to mám zkusit v úterý před písemkou (cca po jedné hodině) v jeho pracovně. No uvidíme, potom si chci dát závod pražskou MHD na studijní oddělení a uzavřít si ročník... snad to stihnu, ve středu mají zavřeno a trčet kvůli tomu v Praze další dva dny se mi opravdu nechce...