Logika

• 26 hod. přednášky
• 26 hod. cvičení

• 60 bodů závěrečná zkouška
• 20 bodů půlsemestrální test
• 20 bodů numerická cvičení

Po absolvování předmětu získají studenti schopnost chápání principů axiomatických matematických teorií i schopnost přesného (formálního) matematického vyjadřování. Naučí se také formálně odvozovat nové formule a dokazovat formule dané. Uvědomí si efektivitu formálního uvažování, ale také jeho hranice.
Studenti se naučí exaktnímu formálnímu myšlení, které jim umožní provádět korektní a efektivní algoritmizaci řešení zadaných problémů. Také získají schopnost ověřovat správnost již vytvořených algoritmizací (verifikace programů).

Cílem předmětu je seznámit studenty se základními metodami uvažování v matematice. Studenti by si měli osvojit obecné principy predikátové logiky a získat tak schopnost přesného matematického uvažování a vyjadřování. Také by se měli naučit pracovat s některými dalšími důležitými formálními teoriemi využívanými v informatice.

Předpokládají se znalosti získané v předmětu Diskrétní matematika z bakalářského stupně studia.

• D.M. Gabbay, C.J. Hogger, J.A. Robinson, Handbook of Logic for Artificial Intellogence and Logic Programming, Oxford Univ. Press 1993
• A. Sochor, Klasická matematická logika, Karolinum, 2001
• V. Švejnar, Logika, neúplnost a složitost, Academia, 2002
• E. Mendelson, Introduction to Mathematical Logic, Chapman&Hall, 2001
• A. Nerode, R.A. Shore, Logic for Applications, Springer-Verlag 1993
• D.M. Gabbay, C.J. Hogger, J.A. Robinson, Handbook of Logic for Artificial Intelligence and Logic Programming, Oxford Univ. Press 1993
• G. Metakides, A. Nerode, Principles of logic and logic programming, Elsevier, 1996
• Melvin Fitting, First order logic and automated theorem proving, Springer, 1996
• Sally Popkorn, First steps in modal logic, Cambridge Univ. Press, 1994

1. Základy teorie množin a kardinální aritmetiky
2. Jazyk, formule a sémantika výrokové logiky
3. Formální systém výrokové logiky
4. Dokazatelnost ve výrokové logice, věta o úplnosti
5. Jazyk predikátové logiky, termy a formule
6. Sémantika predikátové logiky
7. Formální systém predikátové logiky 1. řádu
8. Dokazatelnost v predikátové logice
9. Věta o úplnosti a o kompaktnosti, prenexní tvar formulí
10. Teorie 1. řádu a jejich modely
11. Nerozhodnutelnost teorií prvního řádu, Gödelovy věty o neúplnosti
12. Teorie 2. řádu (monadická logika, SkS a WSkS)
13. Některé další logiky (intuicionistická, modální a temporální logika, Presburgerova aritmetika)

1. Relační systémy a univerzální algebry
2. Množiny, kardinální čísla a kardinální aritmetika
3. Výroky, výrokové spojky, pravdivostní tabulky, tautologie a kontradikce
4. Nezávislost logických spojek, axiomy výrokové logiky
5. Věta o dedukci a dokazování formulí výrokové logiky
6. Termy a formule predikátové logiky
7. Interpretace, splnitelnost a pravdivost
8. Axiomy a odvozovací pravidla predikátové logiky
9. Věta o dedukci a dokazování formulí v predikátové logice
10. Převody formulí na prenexní tvar
11. Teorie 1. řádu a jejich modely
12. Monadické logiky SkS a WSkS
13. Intuicionistická, modální a temporální logika, Presburgerova aritmetika

Půlsemestrální test.

Pravidelná docházka na cvičení a úspěšné složení obou kontrolních testů