Diskrétní matematika a logika
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
BI-DML.21 | Z,ZK | 5 | 2P+1R+1C | česky |
- Vztahy:
- 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ý)
- Předmět je ekvivalentní s BIE-DML.21,BIK-DML.21 .
- 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:
-
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 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 (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)
- Bc. specializace Informační bezpečnost, 2024 (povinný předmět programu)
- Bc. program, pro fázi studia bez specializace, 2024 (povinný předmět programu)
- Bc. specializace Manažerská informatika, 2024 (povinný předmět programu)
- Bc. specializace Počítačová grafika, 2024 (povinný předmět programu)
- Bc. specializace Softwarové inženýrství, 2024 (povinný předmět programu)
- Bc. specializace Webové inženýrství, 2024 (povinný předmět programu)
- Bc. specializace Počítačové sítě a Internet, 2024 (povinný předmět programu)
- Bc. specializace Počítačové inženýrství, 2024 (povinný předmět programu)
- Bc. specializace Počítačové systémy a virtualizace, 2024 (povinný předmět programu)
- Bc. specializace Umělá inteligence, 2024 (povinný předmět programu)
- Bc. specializace Teoretická informatika, 2024 (povinný předmět programu)