Diskrétní matematika a logika

Předmět BI-DML.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-DML.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-ZDM (vztah je symetrický)

Předmět BI-DML.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-DML.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-ZDM (vztah je symetrický)

Garant předmětu:

Jan Spěvák

Přednášející:

Daniel Dombek, Jiřina Scholtzová, Jan Spěvák

Cvičící:

Jakub Čermák, Daniel Dombek, Jan Legerský, Jitka Rybníčková, Jiřina Scholtzová, Jan Spěvák, Irena Šindelářová

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

Studenti se seznámí se základními pojmy výrokové a predikátové logiky a naučí se pracovat s jejími zákony. Budou vysvětleny potřebné pojmy z teorie množin. Zvláštní pozornost je věnována relacím, jejich obecným vlastnostem a jejich typům, zejména zobrazení, ekvivalenci a uspořádání. Předmět dále položí základy pro kombinatoriku a teorii čísel s důrazem na modulární aritmetiku.

Požadavky:

Bez požadavků.

Osnova přednášek:

1. Výroková logika. Formule. Pravdivost formulí. Splnitelnost, tautologie, kontradikce. Logická ekvivalence. Základní zákony výrokové logiky.

2. Disjunktivní a konjunktivní normální tvary formulí. Úplné tvary. Logický důsledek.

3. Predikátová logika. Formalizace matematických tvrzení.

4. Množiny a zobrazení: základní vlastnosti, základní číselné množiny, mohutnost množin.

5. Matematická indukce. Typy matematických důkazů.

6. Binární relace (vlastnosti, reprezentace), skládání relací.

7. Ekvivalence a uspořádání.

8. Kombinatorika, základní principy (sčítací, násobicí, doplňkový, inkluze a exkluze).

9. Kombinace a variace s opakováním, Stirlingova čísla, vlastnosti binomických koeficientů. Laplaceovská pravděpodobnost.

10. Základy teorie čísel, modulární aritmetika.

11. Vlastnosti prvočísel, základní věta aritmetiky.

12. Diofantické rovnice, lineární kongruence, Čínská věta o zbytcích.

Osnova cvičení:

1. Úvod do matematické logiky. Formule, pravdivostní tabulky. Tautologie, kontradikce.

2. Důsledek a ekvivalence. Úplné systémy spojek.

3. Disjunktivní a konjunktivní normální tvar.

4. Syntax predikátové logiky. Formalizace tvrzení v predikátové logice.

5. Matematická indukce.

6. Množiny a zobrazení.

7. Binární relace (vlastnosti, reprezentace), skládání relací.

8. Ekvivalence a uspořádání.

9. Aplikace kombinatorických principů, pravděpodobnost,

10. Pokročilé kombinatorické principy.

11. Dělitelnost. Řešení diofantických rovnic.

12. Řešení lineárních kongurencí a jejich soustav.

Cíle studia:

Studijní materiály:

K předmětu je k dispozici vlastní studijní text. Dále lze využít následující literaturu.

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

2. Chartrand G., Zhang P.: Discrete Mathematics; Waveland;2011; ISBN 978-1577667308

3. Graham R. L., Knuth D. E., Patashnik O.: Concrete Mathematics: A Foundation for Computer Science (2nd Edition); Addison-Wesley Professional; 1994; ISBN 978-0201558029

4. Trlifajová K., Vašata D.: Matematická logika; ČVUT2017; ISBN 978-80-01-05342-3

5. Nešetřil J., Matoušek J.: Kapitoly z diskrétní matematiky; Karolinum 2007; ISBN 978-80-246-1411-3

Poznámka:

Další informace:

https://courses.fit.cvut.cz/BI-DML

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

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 (povinný předmět programu)
• Bc. specializace Manažerská informatika, 2021 (povinný předmět programu)
• Bc. specializace Počítačová grafika, 2021 (povinný předmět programu)
• Bc. specializace Počítačové inženýrství, 2021 (povinný předmět programu)
• Bc. program, pro fázi studia bez specializace, 2021 (povinný předmět programu)
• Bc. specializace Webové inženýrství, 2021 (povinný předmět programu)
• Bc. specializace Umělá inteligence, 2021 (povinný předmět programu)
• Bc. specializace Teoretická informatika, 2021 (povinný předmět programu)
• Bc. specializace Softwarové inženýrství, 2021 (povinný předmět programu)
• Bc. specializace Počítačové systémy a virtualizace, 2021 (povinný předmět programu)
• Bc. specializace Počítačové sítě a Internet, 2021 (povinný předmět programu)