Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Matematická logika

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-LOG.21 Z,ZK 5 2P+2C česky
Vztahy:
Předmět BI-LOG.21 nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BI-MLO (vztah je symetrický)
Předmět BI-LOG.21 nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BI-MLO (vztah je symetrický)
Garant předmětu:
Kateřina Trlifajová
Přednášející:
Kateřina Trlifajová
Cvičící:
Kateřina Trlifajová
Předmět zajišťuje:
katedra aplikované matematiky
Anotace:

Předmět je zaměřen na základy výrokové a predikátové logiky. Začíná ze sémantické stránky. Na podkladě pojmu pravdivosti je definována splnitelnost, logická ekvivalence a logický důsledek formulí. Jsou vysvětleny metody pro určení splnitelnosti formulí, z nichž některé se používají pro automatické dokazování. Je poukázáno na souvislost s P vs. NP problémem a s booleovskými funkcemi ve výrokové logice. V predikátové logice se předmět dále zabývá formálními teoriemi, například aritmetikou, a jejich modely. Syntaktický přístup k matematické logice je předveden na axiomatickém systému výrokové logiky a jeho vlastnostech. Jsou vysvětleny Gödelovy věty o neúplnosti.

Požadavky:

Znalost základních matematických struktur z algebry a analýzy.

Osnova přednášek:

1.Historický úvod. Syntax a sémantika výrokové logiky. Důkaz indukcí.

2.Logická ekvivalence. Úplné a minimální konjunktivní a disjunktivní tvary.

3.Logický důsledek. Tablo metoda pro výrokovou logiku.

4.Rezoluční metoda. SAT problém, P vs. NP.

5.Booleova algebra. Booleovské funkce.

6.Predikátová logika. Syntax. Interpretace. Formalizace.

7.Pravdivost, splnitelnost, kontradikce. Logická ekvivalence.

8.Logický důsledek. Tablo metoda pro predikátovou logiku.

9.Prenexní tvar. Rezoluční metoda pro predikátovou logiku.

10.Teorie 1. řádu: uspořádání, ekvivalence, aritmetika. Modely teorií.

11.Axiomatický systém výrokové logiky.

12.Korektnost, úplnost, bezespornost.

13.Gödelovy věty o neúplnosti.

Osnova cvičení:

1.Výrokové formule. Pravdivostní tabulky. Formalizace.

2.Základní zákony. Universální systém spojek.

3.Disjunktivní a konjunktivní tvary. Logický důsledek.

4.Tablo metoda. Rezoluční metoda.

5.Booleova algebra: vlastnosti, počítání, uspořádání, atomy.

6.Predikátová logika. Jazyk, term, formule. Formalizace.

7.Trojí typ pravdivosti. Logická ekvivalence.

8.Platnost v interpretaci. Splnitelné formule.

9.Logický důsledek. Tablo metoda.

10.Prenexní tvar. Resoluční metoda.

11.Teorie a jejich modely. Isomorfní a elementárně ekvivalentní modely.

12.Hilbertův axiomatický systém.

13.Opakování.

Cíle studia:

Cílem je naučit se pracovat ve formální matematické logice, rozumět jejímu syntaxu a sémantice. Umět pracovat s teoriemi jakožto s axiomatickými systémy a odvozovat jejich důsledky. Vědět, co znamená korektnosti, úplnost, bezespornost a rozhodnutelnost teorií, a jaké problémy se k tomu váží. Rozumět Booleově algebře jakožto zobecnění výrokové logiky.

Studijní materiály:

1.Trlifajová K., Vašata D.,: Matematická logika. CVUT, 2017. ISBN 978-80-01-05342-3.

2.Mendelson E.: Introduction to Mathematical Logic (6th Edition). Chapman and Hall, 2015. ISBN 978-1482237726.

3.Bergmann M., Moor J., Nelson J.: The Logic Book (6th Edition). McGraw-Hill, 2013. ISBN 978-0078038419.

Poznámka:
Rozvrh na zimní semestr 2024/2025:
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
místnost T9:302
Trlifajová K.
12:45–14:15
(přednášková par. 1)
Dejvice
NBFIT učebna
místnost T9:302
Trlifajová K.
14:30–16:00
(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
St
Čt

Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 10. 10. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6615906.html