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

Matematická logika

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-LOG.21 Z,ZK 5 2P+2C česky
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra teoretické informatiky
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:
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ů:
Platnost dat k 18. 1. 2021
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet6615906.html