V zimním semestru akademického roku 2012/2013 vedu jedno cvičení k přednášce Výroková a predikátová logika. Cvičení se koná v úterý od 17:20 v S6 na Malé Straně.

Požadavky na zápočet jsou částečně určené centrálně - získání jistého počtu bodů (bude upřesněno později) z krátkých testů (15 minut), dále je vyžadována prezence a aktivita (řešení úlohy u tabule, dobrý nápad vyřčený z lavice, ...).

Od 23.10.2012 se začínají na cvičení psát krátké testy. Úlohy na test budou čerpat z látky probrané na cvičení a přednášce.

6.11.2012 cvičení odpadá kvůli zahraniční cestě na konferenci.

20.11.2012 je cvičení zrušeno kvůli nemoci vyučujícího.

Aktuálně platná témata na krátký test

Vždy je třeba uvažovat také pojmy v rozumném okolí níže uvedených hesel.

• formule, struktury, pravdivost formule ve struktuře
• izomorfismus struktur, elementární ekvivalence, elementární podstruktury
• podstruktura, extenze, expanze, redukt
• vztah pravdivosti formule a logických spojek
• definovatelné množiny, vztah k relačním databázím
• kvantifikátory, volné a vázané proměnné, substituovatelnost, varianty formule
• axiomy, odvozovací pravidla, dokazatelnost formulí, teorie T, Thm(T)
• výroková logika, CNF, DNF tvar formule, korektnost, úplnost
• teorie uspořádání: LO, DeLO, DiLO, + konce
• teorie následníka: SC, SC₀, SCI
• aritmetické teorie: Pr, Q, P
• ekvivalence výroků a teorií, počty neekvivalentních výroků a teorié
• kompletní teorie, různé typy výroků: pravdivý, lživý, konzistentní
• axiomatizovatelnost, konečná axiomatizovatelnost, oddělitelnost, otevřenost, uzavřenost

Úlohy na domácí úkol

Následují jednoduché úlohy na domácí úkol. Každá úloha odpovídá jedné čárce za aktivitu.

1. Kolik kusů oblečení je potřeba, aby mohla každá žena mít svůj nezaměnitelný vkus?

2. Kolik existuje neekvivalentních výrokových formulí nad množinou prvovýroků P?

3. Kolik by mohlo existovat různých (tj. neekvivaletních) binárních logických spojek?

4. Je CNF/DNF tvar pro danou formuli jednozančný? Navrhněte metodu na zkrácení CNF/DNF reprezentace formule.

5. Jsou dány formule ψ a χ. Kolik je neekvivalentních výroků φ, že ψ|-φ a φ|-χ. Pracujeme se množinou prvovýroků P.

6. Ukažte, že množina K je konečně axiomatizovatelná, právě když K a -K jsou axiomatizovatelné.

7. Pracujme s množinou prvovýroků P (může být nekonečná). Mějme K₁,K₂,...,K_n, kde n∈N axiomatizovatelné množiny ohodnocení nad P. Napište axiomatiku ∪_i=1ⁿK_i.

8. Formulujte Pigeon Hole Principle pro 4 holuby a 3 díry jako splnitelnost CNF výrokové formule. Pomocí rezoluční metody ukažte, že daná úloha nemá řešení.

9. Ukažte, že množina přirozených čísel má menší mohutnost než množina všech jejích podmnožin.

10. Pracujme s množinou prvovýroků P (může být nekonečná). Existuje množina ohodnocení na P, která není axiomatizovatelná? Pokud ano, popište takovou množinu.