460-2051/01 – Úvod do logického myšlení (ULM)
Garantující katedra | Katedra informatiky | Kredity | 5 |
Garant předmětu | Mgr. Marek Menšík, Ph.D. | Garant verze předmětu | Mgr. Marek Menšík, Ph.D. |
Úroveň studia | pregraduální nebo graduální | Povinnost | povinný |
Ročník | 1 | Semestr | zimní |
| | Jazyk výuky | čeština |
Rok zavedení | 2019/2020 | Rok zrušení | |
Určeno pro fakulty | FEI | Určeno pro typy studia | bakalářské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Po absolvování kurzu se studenti budou orientovat v terminologii pojmů množina, relace a funkce. Budou schopni provádět základní operace na množinách, relacích a funkcích a dokáží jasně a na příkladech uvézt příklady relací a funkcí.
V části týkající se základů logiky se studenti seznámí s problematikou formalizace tvrzení do formálního jazyka výrokové a predikátové logiky. Studenti budou schopni ověřovat logickou pravdivost či splnitelnost formulí a převádět formule do normálních forem. V neposlední řadě bude student schopen odvozovat a provádět důkazy v systémech výrokové logiky a predikátové logiky. Na základě daného formálního jazyka budou studenti schopni řešit logické hádanky, co vyplývá z dané báze dat a znalostí a další aplikace využitelné pro řešení reálných problémů. Budou rovněž schopni určit omezení daného formalizmu pro řešení konkrétního problému (kde již daná formalizace nestačí, jaká formalizace je dostatečná pro řešení daného problému atp.)
V sekci důkazových technik budou studenti schopni rozhodnout, jaký typ důkazu byl použit pro řešení daného problému. Budou rovněž umět zvolit typ důkazu, kterým je možno řešit daný problém a navrhnout řešení pomocí takového důkazu. Seznámí se s různými důkazovými technikami, jakou je např. přímý či nepřímý důkaz, tj. důkaz sporem, nebo také důkaz indukcí, a budou schopni takové důkazy provést, ať již formálně v daném logickém systému, či neformálně. V neposlední řadě se seznámí s vlastnostmi relací a funkcí, pojmem rekurze a využitím rekurzivních definic.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Předmět je koncipován formou seznámení se základními pojmy v oblasti teoretické informatiky, a to zejména diskrétních matematických struktur, které jsou pak využívány v reálných aplikacích. Spojuje aplikaci oblastí teorie množin, základů matematické logiky a důkazových technik. Předmět bude veden formou nejen teoretickou, ale také s návazností na praktické využití, aby studenti za každým teoretickým systémem viděli konkrétní praktické využití.
Povinná literatura:
Doporučená literatura:
Forma způsobu ověření studijních výsledků a další požadavky na studenta
V průběhu semestru studenti absolvují zápočtovou písemnou práci, ve které studenti předvedou praktické dovednosti z nabyté látky. Následně studenti absolvují zkoušku obsahující nejen praktické, ale i teoretické základy. Minimální povinná účast na cvičeních je 75%.
E-learning
Další požadavky na studenta
Další požadavky nejsou na studenty kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Témata probíraná na přednáškách:
1. Výroková logika – syntaxe, sémantika, formalizace vět v jazyce výrokové logiky
2. Výroková logika – ekvivalentní úpravy, normální formy formulí (konjunktivní, disjunktivní)
3. Výroková logika – splnitelnost, logická pravdivost, nesplnitelnost, odvozovací pravidla (modus ponens, modus tollens, ...)
4. Naivní teorie množin – množinové operace jako sjednocení, průnik, doplněk, potenční množina, kartézský součin, relace být podmnožinou mezi množinami, definice relace a funkce.
5. Predikátová logika – syntax, sémantika, formalizace vět v jazyce predikátové logiky prvního řádu
6. Predikátová logika – interpretace, modely, Vennovy diagramy, logická pravdivost, splnitelnost, nesplnitelnost formulí
7. Práce s kvantifikátory, normální formy formulí
8. Kardinalita množin, spočetné a nespočetné množiny.
9. Relace, vlastnosti relací, relační struktury, ekvivalence a částečné uspořádání, faktorová množina
10. Funkce, vlastnosti funkcí, surjekce (zobrazení na), injekce (prosté zobrazení do), bijekce (prosté zobrazení na), inverzní funkce, skládání funkcí
11. Pojem důkazu a dokazovací techniky – struktura důkazů, přímý důkaz, nepřímý důkaz
12. Induktivní důkazy a rekurze (důkaz matematickou indukcí, strukturální indukce vs. rekurze)
13. Rekurzivní matematické definice, rekurzivní funkce
Témata probíraná na cvičeních:
Jednotlivá cvičení kopírují témata přednášek. Na cvičeních bude studentům zadána samostatná práce v rozsahu jedné vyučovací hodiny jako domácí cvičení.
1. Výroková logika, jazyk a sémantika.
2. Formalizace vět v jazyce výrokové logiky
3. Výroková logika, ekvivalentní úpravy, použití dedukčních pravidel.
4. Naivní teorie množin.
5. Predikátová logika, jazyk a sémantika, modely.
6. Formalizace vět do predikátové logiky.
7. Vennovy diagramy, ekvivalentní úpravy, práce s kvantifikátory.
8. Spočetnost a nespočetnost množin, příklady.
9. Procvičování základních pojmů: relace, funkce, částečné uspořádání, ekvivalence.
10. Pokračování v procvičování funkcí a vlastností funkcí.
11. Procvičování vedení důkazů, typy důkazů.
12. Důkazy na rekurzi.
13. Rekurzivní funkce.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky