Detail předmětu

Logika

FIT-LOGAk. rok: 2019/2020

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

prof. RNDr. Josef Šlapal, CSc.

Zajišťuje ústav

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

Výsledky učení 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ů).

Prerekvizity

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

Literatura

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

Způsob a kritéria hodnocení

Půlsemestrální test.
Podmínky zápočtu:
Pravidelná docházka na cvičení a úspěšné složení obou kontrolních testů

Jazyk výuky

čeština

Cíl

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.

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

  • Program IT-MGR-2 magisterský navazující

    obor MBS , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MBI , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MIS , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MIN , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MMI , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MMM , libovolný ročník, letní semestr, 5 kreditů, povinný
    obor MGM , libovolný ročník, letní semestr, 5 kreditů, volitelný
    obor MPV , libovolný ročník, letní semestr, 5 kreditů, volitelný

  • Program MITAI magisterský navazující

    specializace NBIO , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NISD , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NISY , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NIDE , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NCPS , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NSEC , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NMAT , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NGRI , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NNET , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NVIZ , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NSEN , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NMAL , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NHPC , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NVER , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NEMB , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NADE , libovolný ročník, letní semestr, 5 kreditů, volitelný
    specializace NSPE , libovolný ročník, letní semestr, 5 kreditů, volitelný

  • Program IT-MGR-2 magisterský navazující

    obor MSK , 1. ročník, letní semestr, 5 kreditů, povinně volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Josef Šlapal, CSc.

Osnova

  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)

Cvičení odborného základu

26 hod., povinná

Vyučující / Lektor

prof. RNDr. Josef Šlapal, CSc.

Osnova

  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