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

Diskrétní matematika a logika

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
BIK-DML.21 Z,ZK 5 14KP+4KC česky

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ý)

Garant předmětu:
Přednášející:
Cvičící:
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
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 29. 3. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6539606.html