Výroková logika
Kód: Vybrat vše
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ů)
Kód: Vybrat vše
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ů)
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.