Diskrétní matematika a logika

Vztahy:

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

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

Předmět je ekvivalentní s BI-DML.21,BIE-DML.21 .

Garant předmětu:

Eva Pernecká

Přednášející:

Eva Pernecká

Cvičící:

Eva Pernecká

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í. Typy matematických důkazů.

4. Matematická indukce.

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

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. Laplaceovská pravděpodobnost.

10. Kombinace a variace s opakováním, Stirlingova čísla, vlastnosti binomických koeficientů.

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

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

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

Osnova cvičení:

1. Úvod do matematické logiky.

2. Formule, pravdivostní tabulky. Tautologie, kontradikce, splnitelnost; důsledek a ekvivalence.

3. Úplné systémy spojek. Disjunktivní a konjunktní normální tvar, minimalizace, Karnaughovy mapy

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

5. Formalizace matematických tvrzení. Typy matematických důkazů.

6. Matematická indukce.

7. Množiny a zobrazení.

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

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

10. Aplikace kombinatorických principů.

11. Pokročilé kombinatorické úlohy, pravděpodobnost,

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

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

Cíle studia:

Studijní materiály:

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