Matematická logika

Předmět nesmí být zapsán současně s:

Matematická logika (BI-MLO)

Garant předmětu:

Přednášející:

Cvičící:

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:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

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)