Cvičení

Týden	Náplň	Materiály	Videa	Domácí cvičení
1	Indukce.	Příklady k procvičení indukce.	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.	Sestrojte důkaz sekventu a ∨ b, b ⇒ (¬ c ∨ e), a ⇒ (¬c ∨ d) ⊢ c ⇒ (e ∨ d). Řešení druhého úkolu.
3	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í 1, Videocvičení 2, Videocvičení 3	Sestrojte důkaz sekventu ⊢ ((a ⇒ b) ⇒ a) ⇒ a. Řešení třetího úkolu.
4	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.
5	Úvod do predikátové logiky.	Příklady k základům predikátové logiky.Příručka pro formalisaci tvrzení v predikátové logice.	Nejsou.
6	Přirozená dedukce.	Příklady k procvičení přirozené dedukce v predikátové logice. Sbírka - přirozená dedukce v PL. Řešení k některým příkladům ze sbírky.	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.) Vypracovaný důkaz.
7	Přirozená dedukce.	Příklady k procvičení přirozené dedukce v predikátové logice.	Nejsou.	Formalisujte a proveďte důkazy všech úsudků z materiálů k tomuto týdnu.
8	Sémantika PL.	Několik příkladů k sémantice PL s výsledky. Příklady k procvičení sémantiky predikátové logiky.	Nejsou.	Zpracujte ukázkový semestrální test. Možné řešení semestrálního testu.
9	Jednoduchá tvrzení o grafech.	Základní grafové úlohy.	Hyperkrychle. Regulární grafy.	Připravte se na 1. semestrální test.
10	Test z logiky.		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 minimální kostry.	Grafové úlohy týkající se stromů.	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.	Dokažte, že pokud v grafu bez smyček existuje mezi každými dvěma vrcholy právě jedna cesta, pak je to strom.
12	Stromy (pokračování), kreslení jedním tahem.	Grafové úlohy týkající se stromů.	Hledání eulerovského tahu. Kreslení více tahy. Rozklad na kružnice.	Zpracujte ukázkový semestrální test.
13	Barvení, nezávislost, dominance.	Úlohy na barevnost, nezávislost, dominanci.	Sekvenční barvení: příklad.
14	Test z grafů. Orientované grafy.	Úlohy na orientované grafy.	Prohledávání do hloubky: příklad. DFS: pseudokód. DFS: Python. Topologické očíslování: příklad. Jádro: příklad.

Podpůrné nástroje k logice

Vyzkoušejte online interaktivní učebnici logiky Coqbook.
Ke kontrole příkladů z výrokové logiky můžete použít online nástroj Logictools. Vedle položky Build můžete zkonstruovat pravdivostní tabulku formule i její klausální tvar.
Stavebnicová hra The Incredible Proof Machine vám může pomoci pochopit přirozenou dedukci ve výrokové logice.
Zájemcům o automatické dokazování doporučuji nástroj Vampire využívající resoluční metodu.
Ve hře https://nandgame.com/ si zkonstruujte vlastní procesor.