Detail předmětu

Logika

LOG Ak. rok 2022/2023 letní semestr 5 kreditů

Aktuální akademický rok

V předmětu budou systematicky vyloženy základy výrokové a zejména predikátové logiky. Nejprve budou studenti seznámeni se syntaxí a sémantikou těchto logik, pak budou logiky studovány jako formální teorie s důrazem na problematiku dokazování formulí. Prodiskutovány budou také klasické věty o korektnosti,  úplnosti a kompaktnosti. Po probrání převodu formulí na prenexní tvar budou uvedeny některé vlastnosti a modely teorií 1. řádu. Pozornost bude také věnována nerozhodnutelnosti teorií 1. řádu vyplývající ze známých Gödelových vět o neúplnosti. Závěrem předmětu bude pojednáno o některých dalších významných logikách, které nacházejí uplatnění v informatice.

Garant předmětu

Šlapal Josef, prof. RNDr., CSc. (ÚM OAAG)

Koordinátor předmětu

Vojnar Tomáš, prof. Ing., Ph.D. (UITS)

Jazyk výuky

česky

Zakončení

zápočet+zkouška (písemná)

Rozsah

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

Bodové hodnocení

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

Zajišťuje ústav

ÚM-odbor algebry a diskrétní matematiky (ÚM OAAG)

Přednášející

Lieberman Michael Joseph, Ph.D. (ÚM OAAG)
Šlapal Josef, prof. RNDr., CSc. (ÚM OAAG)

Získané dovednosti, znalosti a kompetence z předmětu

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íle předmětu

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.

Požadované prerekvizitní znalosti a dovednosti

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

Literatura studijní

  • D.M. Gabbay, C.J. Hogger, J.A. Robinson, Handbook of Logic for Artificial Intellogence and Logic Programming, Oxford Univ. Press 1993
  • V. Švejnar, Logika, neúplnost a složitost, Academia, 2002
  • E. Mendelson, Introduction to Mathematical Logic, Chapman&Hall, 2001
  • Melvin Fitting, First order logic and automated theorem proving, Springer, 1996
  • Sally Popkorn, First steps in modal logic, Cambridge Univ. Press, 1994

Osnova přednášek

  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)

Osnova numerických cvičení

  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

Průběžná kontrola studia

Půlsemestrální test.

Podmínky zápočtu

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

Zařazení předmětu ve studijních plánech

Nahoru