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í).) | | | |