====== Cvičení ======

^ Týden ^ Náplň ^ Materiály ^ Videa ^ Domácí cvičení ^
| 1  | Indukce. | {{indukce-priklady.pdf|Příklady k procvičení indukce.}} | Nejsou. | Přečtěte si {{indukce-priklady.pdf|Ú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ě". {{indukce-ukol.pdf|Řešení prvního úkolu.}} |
| 2  | Přirozená dedukce. | {{prirozena-dedukce-vl.pdf|Příklady k procvičení přirozené dedukce i s řešením.}} | [[https://www.youtube.com/watch?v=dsd0wyT2Hmc|Videocvičení z přirozené dedukce.]] | Sestrojte důkaz sekventu <code>a ∨ b, b ⇒ (¬ c ∨ e), a ⇒  (¬ c ∨ d) ⊢ c ⇒  (e ∨ d).</code> {{prirozena-dedukce-ukol-1.pdf|Řešení druhého úkolu.}} |
| 3  | Přirozená dedukce. | {{prirozena-dedukce-vl.pdf|Příklady k procvičení přirozené dedukce i s řešením.}} | [[https://www.youtube.com/watch?v=ItRlYulie0w|Videocvičení 1]], [[https://www.youtube.com/watch?v=dMO0BJkoj_o|Videocvičení 2]], [[https://www.youtube.com/watch?v=vkqEcKPb9gA|Videocvičení 3]] | Sestrojte důkaz sekventu <code>⊢ ((a ⇒ b) ⇒ a) ⇒ a.</code> {{prirozena-dedukce-ukol-2.pdf|Řešení třetího úkolu.}} | 
| 4  | Sémantika výrokové logiky. | {{semantika-vl.pdf|Příklady k procvičení sémantiky výrokové logiky.}} | [[https://www.youtube.com/watch?v=w84ubanTQ9Y|Splnitelnost, tautologie]]. [[https://www.youtube.com/watch?v=OwBWWyy76aE|ÚSS]]. [[https://www.youtube.com/watch?v=xuOQDLP92HA|Velká konjunkce]]. [[https://www.youtube.com/watch?v=YHUZX3Hxh0s|De Morgan]]. [[https://www.youtube.com/watch?v=UBBUoClkF0s|Převod do CNF]]. [[https://www.youtube.com/watch?v=6IL2UsZGKK8|CNF z tabulky]]. [[https://www.youtube.com/watch?v=X85TfXKyzHE|Splnitelnost]]. [[https://www.youtube.com/watch?v=bhT9dBuNG-Y|Sémantický důsledek]]. [[https://www.youtube.com/watch?v=rftvNFLPz68|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. | [[http://web.stanford.edu/class/archive/cs/cs103/cs103.1184/notes/Guide%20to%20Logic%20Translations.pdf|Příručka pro formalisaci tvrzení v predikátové logice.]] | Nejsou. | Domácí úkol nebyl zadán. |
| 6  | Přirozená dedukce. |{{prirozena-dedukce-pl.pdf|Příklady k procvičení přirozené dedukce v predikátové logice.}} {{prirozena-dedukce-pl-reseni.pdf|Řešení k některým příkladům k procvičení přirozené dedukce v predikátové logice.}} | Nejsou. | Sestrojte důkaz sekventu <code> ∀x(∃y(M(x,y) ∨ M(y,x)) ⇒ M(x,x)), ∃x∃yM(x,y) ⊢ ∃xM(x,x) </code> (Každý, kdo miluje či je milován, miluje sám sebe. Někdo někoho miluje. Tedy někdo miluje sám sebe.) {{prirozena-dedukce-ukol-3.pdf|Vypracovaný důkaz.}} |
| 7  | Přirozená dedukce. | {{cv-prir-dedukce-pokrocile.pdf|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. | {{cv-semantika-pl.pdf|Příklady k procvičení sémantiky predikátové logiky.}} | Nejsou. | Domácí úkol nebyl zadán. |
| 9  | Jednoduchá tvrzení o grafech. <fc #ff0000>Páteční cvičení odpadá.</fc> | {{zakladni-grafove-ulohy-s-resenim.pdf|Základní grafové úlohy.}} | [[https://www.youtube.com/watch?v=qJUFJ9hxyWA|Hyperkrychle.]] [[https://www.youtube.com/watch?v=qGQPOU9o_98|Regulární grafy.]] |
| 10 | Test z logiky. <fc #ff0000>(Jednoduchá tvrzení o grafech (pro odpadlá cvičení).)</fc> | | [[https://www.youtube.com/watch?v=gdPER3w5DtQ|Dostupnost je relace ekvivalence.]] [[https://www.youtube.com/watch?v=I4bSQKad3HE|Zkrácení sledu na cestu.]] [[https://www.youtube.com/watch?v=bO8HAXHY9-A|Vzdálenost je metrika.]][[https://www.youtube.com/watch?v=6dtHkeECem4|Počet sledů dané délky.]] [[https://www.youtube.com/watch?v=1cJUtvM2x7Q|Hodnost matice incidence.]] [[https://www.youtube.com/watch?v=wdytCJJhLtQ|Hledání eulerovského tahu.]] [[https://www.youtube.com/watch?v=h2zGKB4Uil4|Kreslení více tahy.]] [[https://www.youtube.com/watch?v=bPIRyhkHlIY|Rozklad na kružnice.]] |
| 11 | Stromy a minimální kostry. | {{grafove-ulohy-stromy.pdf|Grafové úlohy týkající se stromů.}} | [[https://www.youtube.com/watch?v=tGYeTOIGDtM|Stromy: mezi dvěma vrcholy právě jedna cesta.]] [[https://www.youtube.com/watch?v=bbdWMLNXaNU|Stromy: minimálně souvislé.]] [[https://www.youtube.com/watch?v=UW3znNtsK8g| Stromy: maximální bez kružnic.]] [[https://www.youtube.com/watch?v=OrjEfnAhAr4|Minimální kostra: Kruskal.]] [[https://www.youtube.com/watch?v=ZT1j3ZLsxhk|Minimální kostra: Jarník.]] |
| 12 | Orientované grafy. | {{lgr-cv-gr-ulohy3.pdf|Úlohy na orientované grafy.}} | [[https://www.youtube.com/watch?v=wVW7lxl865Y|Prohledávání do hloubky: příklad.]] [[https://www.youtube.com/watch?v=gju3hhxf9bg|DFS: pseudokód.]] [[https://www.youtube.com/watch?v=PwVzQxV9n6Q|DFS: Python.]] [[https://www.youtube.com/watch?v=Xr4Ka-ZSgAg|Topologické očíslování: příklad.]] [[https://www.youtube.com/watch?v=iL-nBMevUic|Jádro: příklad.]] |
| 13 | Barvení, nezávislost, dominance. <fc #ff0000>Odpadá středeční cvičení.</fc> | {{barevnost-nezavislost-dominance.pdf|Úlohy na barevnost, nezávislost, dominanci.}} |[[https://www.youtube.com/watch?v=k8mrLmeZpvA|Sekvenční barvení: příklad.]] | 
| 14 | Test. <fc #ff0000>(Barvení, nezávislost, dominance (pro odpadlá cvičení).)</fc> |

===== Podpůrné nástroje k logice =====
  * Ke kontrole příkladů z výrokové logiky můžete použít online nástroj [[http://logictools.org/prop.html|Logictools]]. Vedle položky Build můžete zkonstruovat pravdivostní tabulku formule i její klausální tvar.
  * Stavebnicová hra [[https://incredible.pm/|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 [[https://vprover.github.io/|Vampire]] využívající resoluční metodu.
  * Ve hře [[https://nandgame.com/]] si zkonstruujte vlastní procesor.