====== 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. | Velmi podrobně dokažte matematickou indukcí první rovnost z Úlohy 2 {{indukce-priklady.pdf|v tomto souboru}}. {{indukce-ukol.pdf|Zde je řešení domácího cvičení}} (a jako bonus i řešení nerovnosti z Úlohy 2).| | 2 | Přirozená dedukce. | {{cv-prir-dedukce-vl.pdf|Přirozená dedukce - příklady ze cvičení.}} {{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 a ∨ b, b ⇒ (¬ c ∨ e), a ⇒ (¬c ∨ d) ⊢ c ⇒ (e ∨ d). {{prirozena-dedukce-ukol-1.pdf|Řešení druhého úkolu.}}| | 3 | Přirozená dedukce. | {{cv-prir-dedukce-vl-2.pdf|Přirozená dedukce - příklady ze cvičení.}} {{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 ⊢ ((a ⇒ b) ⇒ a) ⇒ a. {{prirozena-dedukce-ukol-2.pdf|Řešení třetího úkolu.}} | | 4 | Sémantika výrokové logiky. | {{cv-sem-vl-bez-reseni.pdf|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 | Úvod do predikátové logiky. | {{lgr-cv-uvodpl.pdf|Příklady k základům predikátové logiky.}}[[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. | | | 6 | Přirozená dedukce. | {{cv-prir-dedukce-pl.pdf|Příklady k procvičení přirozené dedukce v predikátové logice.}} {{prirozena-dedukce-pl.pdf|Sbírka - přirozená dedukce v PL.}} {{prirozena-dedukce-pl-reseni.pdf|Ř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.) {{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-sem-pl.pdf|Několik příkladů k sémantice PL s výsledky.}} {{cv-semantika-pl.pdf|Příklady k procvičení sémantiky predikátové logiky.}} | Nejsou. | {{sem-pis-1.pdf|Zpracujte ukázkový semestrální test.}} {{sem-pis-1-res.pdf|Možné řešení semestrálního testu.}} | | 9 | Jednoduchá tvrzení o grafech. | {{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.]] | Připravte se na 1. semestrální test. | | 10 | Test z logiky. | | [[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.]] | | 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.]] | 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. | {{grafove-ulohy-stromy.pdf|Grafové úlohy týkající se stromů.}} | [[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.]] | {{sem-pis-2.pdf|Zpracujte ukázkový semestrální test.}} | | 13 | Barvení, nezávislost, dominance. | {{barevnost-nezavislost-dominance.pdf|Úlohy na barevnost, nezávislost, dominanci.}} |[[https://www.youtube.com/watch?v=k8mrLmeZpvA|Sekvenční barvení: příklad.]] | | 14 | Test z grafů. 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.]] | ===== Podpůrné nástroje k logice ===== * Vyzkoušejte online interaktivní učebnici logiky [[https://coqbook.netlify.app|Coqbook]]. * 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.