Cvičení

Týden	Náplň	Materiály	Videa	Domácí cvičení
1	Indukce.	Matematická indukce - příklady ze cvičení.	Nejsou.	Velmi podrobně dokažte matematickou indukcí první rovnost z Úlohy 2 v tomto souboru. Zde je řešení domácího cvičení (a jako bonus i řešení nerovnosti z Úlohy 2).
2	Přirozená dedukce.	Přirozená dedukce - příklady ze cvičení. Příklady k procvičení přirozené dedukce i s řešením.	Videocvičení z přirozené dedukce 0, Videocvičení 1, Videocvičení 2, Videocvičení 3	Sestrojte důkaz sekventu a ∨ b, b ⇒ (¬ c ∨ e), a ⇒ (¬c ∨ d) ⊢ c ⇒ (e ∨ d). Sestrojte důkaz sekventu ⊢ ((a ⇒ b) ⇒ a) ⇒ a. Řešení první úlohy. Řešení druhé úlohy.
3	Sémantika výrokové logiky.	Sémantika výrokové logiky. Příklady k procvičení sémantiky výrokové logiky.	Splnitelnost, tautologie. ÚSS. Velká konjunkce. De Morgan. Převod do CNF. CNF z tabulky. Splnitelnost. Sémantický důsledek. Sémantický důsledek 2.	Zahrajte si https://nandgame.com/ a vyřešte všechny úlohy z úrovně Logic Gates: Nand, Invert, And, Or, Xor.
4	Test z výrokové logiky.	Ukázkový test.
5	Úvod do predikátové logiky.	Základy predikátové logiky - příklady ze cvičení. Řešení. Příručka pro formalisaci tvrzení v predikátové logice. (Stanford, v angličtině.)	Nejsou.	Vyřešte úlohy z tohoto PDF. Výsledky s částečným řešením naleznete zde.
6	Sémantika predikátové logiky.	Sémantika predikátové logiky - příklady ze cvičení. Řešení. Příklady k procvičení sémantiky predikátové logiky.	Nejsou.	Vyřešte úlohy z tohoto PDF.
7	Přirozená dedukce.	Přirozená dedukce v PL - příklady ze cvičení. Sbírka základních úloh z přirozené dedukce v PL. Řešení.	Nejsou.	Sestrojte důkaz sekventu ∀x(∃y(M(x,y) ∨ M(y,x)) ⇒ M(x,x)), ∃x∃yM(x,y) ⊢ ∃xM(x,x) (Každý, kdo miluje či je milován, miluje sám sebe. Někdo někoho miluje. Tedy někdo miluje sám sebe.)
8	Přirozená dedukce.	Úlohy na pokročilou formalisaci a přirozenou dedukci v PL. Řešení.	Nejsou.	Formalisujte a proveďte důkazy všech úsudků z materiálů k tomuto týdnu. Vypracujte ukázkový test z PL.
9	Test z predikátové logiky.	Ukázkový test. Stručné řešení ukázkového testu. Řešení úlohy z přirozené dedukce.
10	Grafy - základní úlohy.	Grafy - příklady ze cvičení.	Hyperkrychle. Regulární grafy. Dostupnost je relace ekvivalence. Zkrácení sledu na cestu. Vzdálenost je metrika.Počet sledů dané délky. Hodnost matice incidence.
11	Stromy a eulerovské grafy.	Stromy, eulerovské grafy - příklady ze cvičení.	Stromy: mezi dvěma vrcholy právě jedna cesta. Stromy: minimálně souvislé. Stromy: maximální bez kružnic. Minimální kostra: Kruskal. Minimální kostra: Jarník. Hledání eulerovského tahu. Kreslení více tahy. Rozklad na kružnice.
12	Barvení grafů.	Barevnost, nezávislost, dominance.	Sekvenční barvení: příklad.
13	Orientované grafy.	Orientované grafy - příklady ze cvičení.	Prohledávání do hloubky: příklad. DFS: pseudokód. DFS: Python. Topologické očíslování: příklad. Jádro: příklad.	Prostudujte algoritmus DFS. Můžete se např. podívat na videa Prohledávání do hloubky: příklad. DFS: pseudokód. DFS: Python.
14	Reserva.