Cvičení

Týden	Náplň	Materiály	Videa	Domácí cvičení
1	Indukce.	Příklady k procvičení indukce.	Nejsou.	Přečtěte si Úlohu 1 a obě její řešení. Dokažte první rovnost z Úlohy 2 a ujistěte se, že byste ji byli na požádání schopni dokázat i “komicky podrobně”. Řešení prvního úkolu.
2	Přirozená dedukce.	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ří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.	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	Formalisace v jazyce PL.	Příručka pro formalisaci tvrzení v predikátové logice.	Nejsou.	Domácí úkol nebyl zadán.
6	Přirozená dedukce.	Příklady k procvičení přirozené dedukce v predikátové logice. Řešení k některým příkladům k procvičení přirozené dedukce v predikátové logice.	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.	Příklady k procvičení sémantiky predikátové logiky.	Nejsou.	Domácí úkol nebyl zadán.
9	Jednoduchá tvrzení o grafech. Páteční cvičení odpadá.	Základní grafové úlohy.	Hyperkrychle. Regulární grafy.
10	Test z logiky. (Jednoduchá tvrzení o grafech (pro odpadlá cvičení).)		Dostupnost je relace ekvivalence. Zkrácení sledu na cestu. Vzdálenost je metrika.Počet sledů dané délky. Hodnost matice incidence. Hledání eulerovského tahu. Kreslení více tahy. Rozklad na kružnice.
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.
12	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.
13	Barvení, nezávislost, dominance. Odpadá středeční cvičení.	Úlohy na barevnost, nezávislost, dominanci.	Sekvenční barvení: příklad.
14	Test. (Barvení, nezávislost, dominance (pro odpadlá cvičení).)

Podpůrné nástroje k logice

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.