Matematická logika
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| BI-MLO | Z,ZK | 5 | 2+1.5 | česky |
- Přednášející:
- Kateřina Trlifajová (gar.), Alena Šolcová
- Cvičící:
- Kateřina Trlifajová (gar.), Zdeněk Konfršt, Marta Nollová, Alena Šolcová, Daniel Vašata
- Předmět zajišťuje:
- katedra aplikované matematiky
- Anotace:
-
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.
- Požadavky:
-
Předpokládá se schopnost práce s matematickou abstrakcí na úrovni získané středoškolským studiem matematiky.
- Osnova 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í.
- Osnova 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í.
- Cíle studia:
-
Cílem předmětu je ukázat, proč je v matematice užitečné namísto přirozeného jazyka používat formule výrokového a predikátového kalkulu, jakým způsobem se formalizuje pojem pravdivosti a dokazatelnosti a jak se pracuje s axiomatickými systémy. Booleova algebra je předvedena jako příklad matematické teorie a zároveň jako nástroj sloužící popisu číslicových systémů, přitom se rovněž vyloží standardní postupy sloužící minimalizaci vyjádření Booleovských funkcí.
- Studijní materiály:
-
1. M. Demlová, B. Pondělíček: Matematická logika. ČVUT Praha, 1997.
3. V. Švejdar: „Logika - neúplnost, složitost a nutnost.“ Academia Praha, 2002.
4. A. Sochor: „Klasická matematická logika.“ Karolinum Praha, 2001.
- Poznámka:
-
Rozsah=prednasky+proseminare+cviceni:2p+1c
- Rozvrh na zimní semestr 2011/2012:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - Rozvrh na letní semestr 2011/2012:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Teoretická informatika - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
- Počítačové inženýrství - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
- Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
- Web a multimedia - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
- Informační systémy a management - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
- Informační technologie - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
- Informatika, plán pro fázi studia bez oboru - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
- Informatika, plán pro fázi studia bez oboru - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
- Informační systémy a management - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
- Informační technologie - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
- Počítačové inženýrství - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
- Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
- Teoretická informatika - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
- Web a multimedia - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)