Matematická logika

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ý)

Předmět je ekvivalentní s BIE-LOG.21 .

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čebnamístnost T9:302 Trlifajová K. 14:30–16:00 (přednášková par. 1 paralelka 101) Dejvice NBFIT učebna
St
Čt
Pá

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Bc. specializace Informační bezpečnost, 2021 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2021 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2021 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2021 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2021 (VO)
• Bc. specializace Webové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2021 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2021 (PS)
• Bc. specializace Softwarové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2021 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2021 (volitelný předmět)
• Bc. specializace Informační bezpečnost, 2024 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2024 (VO)
• Bc. specializace Manažerská informatika, 2024 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2024 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2024 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2024 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2024 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2024 (PS)