BI-MLO – Matematická logika

Cíl předmětu

Studenti se naučí logicky analyzovat text a rozumět mu, převést jednodušší texty do formálního zápisu. Budou umět rozhodnout o platnosti logických formulí a dokázat je. Porozumí rozdílu mezi syntaxí a sémantikou formální logiky, budou schopni pracovat s axiomatickými systémy a znát jejich základní matematické vlastnosti. Zvládnou Booleovu algebru, jak teoreticky jako formální systém a instanci univerzální algebry, tak prakticky jako nástroj sloužící k popisu číslicových systémů. Získají potřebné návyky pro práci s Booleovskými funkcemi, normálními formami, mapami a metodami minimalizace, které budou potřebovat v dalších předmětech. Své znalosti budou mít zasazeny do širšího historického kontextu.

Program přednášek

  1. Význam logiky, historie. Výroková logika. Formalizace přirozeného jazyka. Základní pojmy: jazyk, formule.
  2. Sémantika VL: ohodnocení, pravdivostní tabulky. Tautologie, kontradikce, splnitelnost, tautologický důsledek, základní zákony VL.
  3. Disjunktivní a konjunktní normální tvar formulí, rozkladové stromy. Logický rozbor textu.
  4. Booleova algebra. Minimalizace logické funkce. Mapy.
  5. Syntax VL: Hilbertův axiomatický systém. Formální důkaz, typy matematických důkazů.
  6. Věta o dedukci. Korektnost a úplnost. Věta o kompaktnosti.
  7. Predikátová logika. Formalizace přirozeného jazyka. Základní pojmy: jazyk, kvantifikátory, termy, formule.
  8. Sémantika PL: Tarskiho definice pravdy. Platnost formulí, logicky ekvivalentní formule, základní zákony PL.
  9. Interpretace, model, teorie. Rozkladové stromy.
  10. Příklady modelů a teorií.
  11. Logický rozbor textu. Prenexní tvar formulí.
  12. Syntax PL: Hilbertův axiomatický systém. Korektnost a úplnost.
  13. Základní myšlenky teorie množin: aktuální a potenciální nekonečno, význam množin, mohutnosti, hypotéza kontinua, axiom výběru, formální systémy, nezávislá tvrzení.

Program cvičení

  1. Formalizace jednoduchých textů ve VL.
  2. Pravdivostní tabulky. Určení tautologie, kontradikce, splnitelnosti, tautologického důsledku.
  3. Disjunktivní a konjunktní normální tvar formulí. Booleova algebra. Minimalizace, mapy.
  4. Rozkladové stromy. Logický rozbor textu.
  5. Důkazy v Hilbertově axiomatickém systému. Typy matematických důkazů.
  6. Formalizace jednoduchých textů do PL.
  7. Tři typy logické splnitelnosti v PL.
  8. Interpretace, model, teorie. Rozkladové stromy.
  9. Prenexní tvar formulí. Logický rozbor textu.
  10. Příklady modelů a teorií.
  11. Korektnost, bezespornost a úplnost.
  12. Mohutnosti množin, vzájemně jednoznačná zobrazení.



Poslední změna: 22.4.2009, 20:57