{"nbformat":4,"nbformat_minor":0,"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.6.1"},"colab":{"name":"PB016_cvi8_G02.ipynb","provenance":[],"collapsed_sections":[]}},"cells":[{"cell_type":"markdown","metadata":{"id":"nITBbl4q_tth"},"source":["# PB016: Umělá inteligence I, cvičení 8 - Základy predikátové logiky\n","\n","Dnešním tématem jsou základy predikátové logiky prvního řádu (PL1). Soustředit se budeme zejména na:\n","1. __Reprezentace tvrzení pomocí formulí PL1__\n","2. __Interpretace formulí v PL1__\n","\n","Nejprve ale __rychlý úvod__ do toho, co to vlastně predikátová logika je:\n","- Rozšíření výrokové logiky jak co do syntaxe, tak sémantiky.\n","- Expresivní nástroj pro axiomatizaci matematických struktur.\n","- Blížší k přirozenému jazyku a vhodná jako formální nástroj pro zápis komplexních \"ontologií\" (počítačově zpracovatelných reprezentací znalostí).\n","- Nejdůležitější rozšíření:\n"," - kvantifikátory - existenční $\\exists$ (platí aspoň v jednom případě) a univerzální $\\forall$ (platí ve všech případech)\n"," - symbol identity $=$\n"," - obor interpretace - množina reprezentující denotace, tj. objekty, k nimž se výrazy PL1 vztahují (např. přirozená čísla, ale může jít o jakoukoli jinou množinu)\n"," - funkční symboly pro reprezentaci operací, resp. zobrazení nad prvky oboru interpretace (spolu s proměnnými tvoří množinu termů)\n"," - predikátové symboly pro reprezentaci relací mezi objekty\n","- Příklad - reprezentace komutativních grup v PL1 využívá jazyka prvního řádu, který má jeden konstantní symbol $0$, jeden unární funkční symbol $-$, jeden binární funkční symbol $+$ a jeden binární relační symbol $\\leq$. Pak:\n"," - Výrazy $+ (x, y)$ a $+ (x, + (y, - (z)))$ jsou termy. Obvykle se zapisují jako $x + y$ a $x + y - z$.\n"," - Výrazy $+ (x, y) = 0$ a $\\leq (+ (x, + (y, - (z))), + (x, y))$ jsou atomické formule. Obvykle se zapisují jako $x + y = 0$ a $x + y - z \\leq x + y$.\n"," - Výraz $\\forall x \\forall y [\\leq(+(x,y,),z) \\Rightarrow +(x,y)=0]$ je formule, která se obvykle zapisuje jako $\\forall x \\forall y (x+y \\leq z) \\Rightarrow \\forall x \\forall y (x+y=0)$. Tato formule má jednu volnou proměnnou, $z$.\n","  - Axiomy dané struktury se pak zapisují jako formule, např. komutativitě v tomto příkladu odpovídá $\\forall x \\forall y (x+y = y+x)$."]},{"cell_type":"markdown","metadata":{"id":"rMB_46nl_tti"},"source":["---\n","\n","## 1. Reprezentace tvrzení pomocí formulí PL1\n","\n","- Převod vět v přirozeném jazyce do formálního jazyka predikátové logiky.\n","- Možná využití: reprezentace znalostí, zpracování přirozeného jazyka, atd."]},{"cell_type":"markdown","metadata":{"id":"Q5MFLutX_ttj"},"source":["### __Příklad 1.1__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Někteří studenti nemají hudební nadání.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"ymTQM0h_bV7H"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"WRP95jetb-HJ"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"M8oke8-B_6tj"},"source":["- $ \\exists x (S(x) \\wedge \\neg H(x)) $ kde $S(x)$ znamená \"$x$ je student\", $H(x)$ znamená \"$x$ má hudební nadání\"."]},{"cell_type":"markdown","metadata":{"id":"fn9oCTq__ttp"},"source":["### __Příklad 1.2__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Někteří přítomní bydlí v hotelu.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"WkMWHEKid39n"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"OWbYwvAnd39o"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"aOSDE2TH_-MW"},"source":["- $ \\exists x (P(x) \\wedge H(x)) $"]},{"cell_type":"markdown","metadata":{"id":"vPfG8I4Y_ttt"},"source":["### __Příklad 1.3__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Někteří studenti nejsou ani nadaní ani pilní.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"rHSH3h8pd4cc"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"O-SdThoPd4ce"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"bnjTvQ5I_-80"},"source":["- $ \\exists x (S(x) \\wedge \\neg N(x) \\wedge \\neg P(x)) $"]},{"cell_type":"markdown","metadata":{"id":"i1OPXXKA_tty"},"source":["### __Příklad 1.4__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Každé číslo dělitelné 8 je dělitelné 4.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"Q2SSma2Kd4y8"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"5TepW_Bdd4y_"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"zonjU9Nw__S0"},"source":["- $ \\forall x (D(x,8) \\Rightarrow D(x,4)) $"]},{"cell_type":"markdown","metadata":{"id":"FdfmWYpB_tt3"},"source":["### __Příklad 1.5__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Kdo seje vítr, ten sklízí bouři.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"o3OqlwwHd5MM"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"YI6Vkh8ud5MO"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"p5ofYnFQAAgk"},"source":["- jedno možné řešení: $ \\forall x (V(x) \\Rightarrow B(x)) $, kde $V(x)$ znamená \"$x$ seje vítr\" a $B(x)$ znamená \"$x$ sklízí bouři\" druhé možné řešení: $ \\forall x (Seje(x,vitr) \\Rightarrow Sklizi(x,boure)) $, kde \"vitr\" a \"boure\" jsou konstanty"]},{"cell_type":"markdown","metadata":{"id":"qdPsAVsh_tt7"},"source":["### __Příklad 1.6__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Psi, kteří hodně štěkají, nekoušou.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"A3jMU6v4d5lM"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"MKCdX39Id5lO"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"_CruJV3lACBE"},"source":["- $ \\forall x ((P(x) \\wedge S(x)) \\Rightarrow \\neg K(x)) $"]},{"cell_type":"markdown","metadata":{"id":"IYUgjHEB_tt_"},"source":["### __Příklad 1.7__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Žádný tyran není spravedlivý.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"3BVDqAPEd5-r"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"gTNKxp7vd5-u"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"krviL8CsAC50"},"source":["- $ \\forall x (T(x) \\Rightarrow \\neg S(x)) $, což je ekvivalentní formuli $ \\neg\\exists x (T(x) \\wedge S(x)) $"]},{"cell_type":"markdown","metadata":{"id":"jmB6CQo0_tuD"},"source":["### __Příklad 1.8__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Každý člověk má otce a matku.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"_OhBr8nJd6Zs"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"v86drlGkd6Zv"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"WTdhO2MIAFqF"},"source":["- $ \\forall x (C(x) \\Rightarrow ((\\exists y M(x,y)) \\wedge (\\exists z O(x,z)))) $"]},{"cell_type":"markdown","metadata":{"id":"oqlJHR4W_tuH"},"source":["### __Příklad 1.9__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Každý, kdo má otce, má i matku.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"tp9u8xiYd6zr"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"mHupybY_d6zu"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"oBGzoK9GASmk"},"source":["- $ \\forall x ((C(x) \\wedge (\\exists y O(x,y))) \\Rightarrow (\\exists z M(x,z))) $"]},{"cell_type":"markdown","metadata":{"id":"nzpX1Y2N_tuK"},"source":["### __Příklad 1.10__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Každý člověk je mladší než jeho rodiče. (pomocí termů)\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"5RQmG5WOd7N8"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"aa_Wbmgod7N_"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"OIalRLQOAS10"},"source":["- $ \\forall x \\forall y (R(x,y) \\Rightarrow Vetsi(vek(x),vek(y))) $, přičemž predikát $Vetsi$ se obvykle zapisuje infixovou notací, tedy v našem případě bychom napsali $vek(x) > vek(y)$"]},{"cell_type":"markdown","metadata":{"id":"Nxsl3-UN_tuO"},"source":["### __Příklad 1.11__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Žádný dobrý učitel nikoho zbytečně nepotrestal.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"7D3ojlj8d7pc"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"LTA_fNsId7pf"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"eWrBct1QAS_U"},"source":["- $ \\neg \\exists x (U(x) \\wedge D(x) \\wedge (\\exists y P(x,y))) $, kde $U, D, P$ odpovídá bytí učitelem, bytí dobrým a trestání."]},{"cell_type":"markdown","metadata":{"id":"bXEmVQuL_tuS"},"source":["### __Příklad 1.12__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Někdo má rád každého.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"7rec7A3Qd8JM"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"PSdzG3IXd8JP"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"Qfq9puc1ATJV"},"source":["- $ \\exists x \\forall y R(x,y) $"]},{"cell_type":"markdown","metadata":{"id":"mVpsepuW_tuW"},"source":["### __Příklad 1.13__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Někdo má rád ostatní.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"csYQI-Pwd838"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"PcseUkckd83-"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"dphHBpJ7ATUU"},"source":["- $ \\exists x \\forall y (x \\neq y \\Rightarrow R(x,y)) $"]},{"cell_type":"markdown","metadata":{"id":"3--VIOxh_tua"},"source":["### __Příklad 1.14__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Není všechno zlato, co se třpytí.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"iXWPZD9fd9U8"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"ZHEMlmkjd9U-"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"AhsA8TNXATeE"},"source":["- $ \\neg \\forall x (T(x) \\Rightarrow Z(x)) $"]},{"cell_type":"markdown","metadata":{"id":"NevzyNk__tud"},"source":["### __Příklad 1.15__\n","\n","Převeďte následující větu v přirozeném jazyce do formulí v predikátové logice:\n","- Všichni sourozenci mají stejného otce. (pomocí termů)\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"BoTKApB8d9yc"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"AAaiXl-Pd9yg"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"nRG9yMd9ATm9"},"source":["- $ \\forall x \\forall y (S(x, y) \\Rightarrow otec(x) = otec(y)) $"]},{"cell_type":"markdown","metadata":{"id":"-75HJfdB_tug"},"source":["### __Příklad 1.16__\n","\n","Nechť výraz $P(l,e,t)$ znamená \"Luboš půjčuje Evě tužku.\" Zapište symbolicky následující výroky:\n","1. Někdo půjčuje Evě tužku.\n","2. Eva půjčuje někomu tužku.\n","3. Eva někomu něco půjčuje.\n","4. Někdo Evě něco půjčuje.\n","5. Luboš každému něco půjčuje.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"fn9FlW_Qd-K7"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"WAOzb3Kjd-K-"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"xdwPVDYPATv1"},"source":["1. $\\exists x P(x,e,t)$\n","2. $\\exists x P(e,x,t)$\n","3. $\\exists x \\exists y P(e,x,y)$\n","4. $\\exists x \\exists y P(x,e,y)$\n","5. $\\forall x \\exists y P(l,x,y)$"]},{"cell_type":"markdown","metadata":{"id":"Zz04JG_I_tuk"},"source":["### __Příklad 1.17__\n","\n","Pomocí predikátu $P$ pro \"půjčit\" z předchozího příkladu zapište symbolicky následující obecné výroky:\n","1. Někdo někomu něco půjčuje.\n","2. Každý někomu něco půjčuje.\n","3. Někdo každému všechno půjčuje.\n","4. Někdo nikomu nic nepůjčuje.\n","5. Neexistuje člověk, který každému všechno půjčuje.\n","6. Všichni všechno všem půjčují.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"cp2QgVTPd-ut"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"1bbprfizd-uv"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"aP1keZpxAU3E"},"source":["1. $\\exists x \\exists y \\exists z P(x,y,z)$\n","2. $\\forall x \\exists y \\exists z P(x,y,z)$\n","3. $\\exists x \\forall y \\forall z P(x,y,z)$\n","4. $\\exists x \\neg (\\exists y \\exists z P(x,y,z))$\n","5. $\\neg (\\exists x \\forall y \\forall z P(x,y,z))$\n","6. $\\forall x \\forall y \\forall z P(x,y,z)$"]},{"cell_type":"markdown","metadata":{"id":"lKnHWymX_tun"},"source":["### __Příklad 1.18__\n","\n","Nechť $V(p,t)$ znamená \"vidím předmět $p$ v okamžiku $t$.\" Zapište symbolicky věty:\n","1. V každém okamžiku něco vidím.\n","2. V některém okamžiku nevidím nic.\n","3. Existují předměty, které nevidím v žádném okamžiku.\n","4. Každou věc vidím v některém okamžiku.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"Ob5qV8l7d_O8"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"Qcl8XTBjd_PA"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"NlsKHg7rAUk1"},"source":["1. $\\forall x \\exists y V(y,x)$\n","2. $\\exists x \\neg \\exists y V(y,x)$ nebo $\\exists x \\forall y \\neg V(y,x)$ (ekvivalentní zápis)\n","3. $\\exists y \\neg \\exists x V(y,x)$ nebo $\\exists y \\forall x \\neg V(y,x)$\n","4. $\\forall y \\exists x V(y,x)$"]},{"cell_type":"markdown","metadata":{"id":"BAVc1LAo_tur"},"source":["---\n","\n","## 2. Interpretace formulí v PL1\n","\n","- Základní nástroj pro přiřazení významu výrazům v PL1.\n","- Interpretace jazyka prvního řádu přiřadí denotaci každému nelogickému symbolu v daném jazyce. \n","- Určuje také obor interpretace (nebo také doménu) $\\mathbf{D}$ - množinu, nad níž operují kvantifikátory. \n","- Výsledkem intepretace jsou následující přiřazení:\n"," - každému termu je přiřazen objekt z množiny $\\mathbf{D}$, který představuje;\n"," - každému predikátu je přiřazena vlastnost objektů;\n"," - každé formuli je přiřazena pravdivostní hodnota.\n","- Detailní studium interpretací formálních jazyků se nazývá formální sémantika.\n","- Pozn.: V rámci určování interpretace formulí v PL1 se může hodit je převést do jiné, k analýze vhodnější formy, na čež se dají použít ekvivalentní úpravy známé z výrokové logiky, doplněné například o fakt, že negace mění při přesunu \"dovnitř\" kvantifikovaného výrazu $\\forall$ na $\\exists$ a naopak. Blíže viz např. [zde](http://www.cs.um.edu.mt/gordon.pace/Teaching/DiscreteMaths/Laws.pdf)."]},{"cell_type":"markdown","metadata":{"id":"pYm-d1PO_tur"},"source":["### __Příklad 2.1__\n","\n","Najděte negace formulí:\n","1. $ \\exists x ((P(x) \\wedge Q(x)) \\vee R(x)) $\n","2. $ \\forall x (P(x) \\Rightarrow \\forall y Q(y)) $\n","3. $ \\forall x (P(x) \\vee \\exists y Q(y)) $\n","4. $ \\forall x (P(x) \\Rightarrow Q(x)) \\wedge \\exists x (R(x) \\wedge S(x))$\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"p8tWFx5Nd_88"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"riYDBxewd_8_"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"YmQ18nmzBi7l"},"source":["1. $ \\neg (\\exists x ((P(x) \\wedge Q(x)) \\vee R(x))) \\equiv \\forall x \\neg ((P(x) \\wedge Q(x)) \\vee R(x))) \\equiv \\forall x ((\\neg P(x) \\vee \\neg Q(x)) \\wedge \\neg R(x))$\n","2. $ \\exists x (P(x) \\wedge \\exists y \\neg Q(y)) $\n","3. $ \\exists x (\\neg P(x) \\wedge \\forall y \\neg Q(y)) $\n","4. $ \\exists x (P(x) \\wedge \\neg Q(x)) \\vee \\forall x (\\neg R(x) \\vee \\neg S(x)) $"]},{"cell_type":"markdown","metadata":{"id":"FMlx9k27_tuu"},"source":["### __Příklad 2.2__\n","\n","Určete, pro které interpretace je pravdivá následující formule:\n","- $ \\exists x \\forall y (P(y) \\Rightarrow (x=y)) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"sYOxltbPeAc8"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"IguaPMt1eAc-"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"FdgnhbfmBjLw"},"source":["Formule je pravdivá v každé interpretaci s libovolným neprázdným oborem interpretace __D__ a s libovolným přiřazením unárního predikátu nad __D__ predikátové konstantě $P$, pokud $P(d)$ je pravda nejvýše pro jeden případ."]},{"cell_type":"markdown","metadata":{"id":"q-OlSzPd_tux"},"source":["### __Příklad 2.3__\n","\n","Určete, pro které interpretace je pravdivá následující formule:\n","- $ \\exists x (P(x) \\wedge \\forall y (P(y) \\Rightarrow (x = y))) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"OjtlwiApeBns"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"RhFaO_BSeBnv"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"_qjucSNRBjXw"},"source":["Formule je pravdivá v každé interpretaci s libovolným oborem interpretace __D__ a s libovolným přiřazením unárního predikátu nad __D__ predikátové konstantě $P$, pokud $P(d)$ je pravda právě v jednom případě."]},{"cell_type":"markdown","metadata":{"id":"-f1Y8UUI_tu2"},"source":["### __Příklad 2.4__\n","\n","Určete, pro které interpretace je pravdivá následující formule:\n","- $ \\forall x \\exists y \\exists z (((x=y) \\vee (x=z)) \\wedge (y \\not = z)) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"xms8fyZ2eCHc"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"mlmSuW-jeCHe"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"JeZMP8ZqBjiA"},"source":["Formule nabývá hodnoty pravda pro každý obor interpretace __D__, který je prázdný, nebo obsahuje alespoň dva prvky."]},{"cell_type":"markdown","metadata":{"id":"22OUE5Aq_tu6"},"source":["### __Příklad 2.5__\n","\n","Určete, pro které interpretace je pravdivá následující formule:\n","- $ \\forall x \\exists y Q(x,y) \\Rightarrow \\exists x Q(x,x) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"AiMyEVKfeCcs"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"3MwclE5NeCcu"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"g9zv2XbyBjsQ"},"source":["Formule je pravdivá v každé interpretaci s libovolným neprázdným oborem interpretace __D__ a s libovolným přiřazením binárního predikátu nad __D__ predikátové konstantě $Q$, pokud $Q(x,y)$ má alespoň jeden reflexivní prvek nebo pokud pro některý prvek $a$ z $D$ neexistuje prvek $b$ takový, že $Q(a,b)$."]},{"cell_type":"markdown","metadata":{"id":"9RTrLUfQ_tu8"},"source":["### __Příklad 2.6__\n","\n","Určete, pro které interpretace je pravdivá následující formule:\n","- $ \\exists x \\forall y ((R(x,y) \\wedge \\neg R(y,x)) \\Rightarrow (R(x,x) \\Leftrightarrow R(y,y))) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"BwQSFXq5eC8s"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"TdhSJMnVeC8u"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"euZHcqlCBj2Q"},"source":["Formule je pravdivá v každé interpretaci s libovolným neprázdným oborem interpretace __D__ a s libovolným přiřazením binárního predikátu nad __D__ predikátové konstantě $R$, pokud existuje prvek $x$,\n","- který je reflexivní a všechny prvky s ním asymetrické v $R$ jsou také reflexivní, nebo\n","- který není reflexivní a všechny prvky s ním asymetrické v $R$ také nejsou reflexivní.\n","(Všimněte si, že v uvedených bodech je zahrnuta i situace, kdy levá strana implikace je nepravdivá.)"]},{"cell_type":"markdown","metadata":{"id":"6mskcYox_tvD"},"source":["### __Příklad 2.7__\n","\n","Určete, zda je následující formule tautologie:\n","- $ \\forall x (P(x) \\wedge Q(x)) \\Leftrightarrow (\\forall x P(x) \\wedge \\forall x Q(x)) $\n","\n","Malá nápověda: Zdůvodnění, že se nejedná o tautologii, lze provést např. nalezením protipříkladu.\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"xF2Twjn1eDf8"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"_aUNuZm_eDf_"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"pBg7TPOsBkAQ"},"source":["Abychom dokázali, že se jedná o tautologii, je potřeba ukázat, že platí implikace zleva doprava i obráceně:\n","\n","\"$\\Rightarrow$\":\n","- Implikace neplatí pouze tehdy, je-li antecedent pravdivý a konsekvent nepravdivý. \n","- Ukážeme, že tento případ pro žádnou interpretaci nemůže nastat:\n"," - Pokud platí antecedent, musí pro každý prvek $d$ oboru interpretace platit $P(d)$ a zároveň $Q(d)$, tedy platí $\\forall x (P(x) \\wedge Q(x))$. \n"," - Potom ale také za stejných podmínek platí $P(d) \\wedge Q(d)$ a také celá formule $\\forall x P(x) \\wedge \\forall x Q(x)$ konsekventu.\n","\n","\"$\\Leftarrow$\":\n","- Na druhou stranu, platí-li $\\forall x P(x) \\wedge \\forall x Q(x)$, tj. pro každé $d$ platí $P(d)$ a zároveň pro každé $d$ platí $Q(d)$, potom také platí $P(d) \\wedge Q(d)$ a tedy také $\\forall x (P(d) \\wedge Q(d))$.\n","\n","Ukázali jsme, že pro libovolnou interpretaci platí obě implikace, tedy platí i ekvivalence a tedy celá formule."]},{"cell_type":"markdown","metadata":{"id":"tSa6KXvK_tvG"},"source":["### __Příklad 2.8__\n","\n","Určete, zda je následující formule tautologie:\n","- $ \\exists x (P(x) \\vee Q(x)) \\Leftrightarrow (\\exists x P(x) \\vee \\exists x Q(x)) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"62x92zzzeEG8"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"9Kn51WwFeEG-"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"WScg63FpBkLR"},"source":["Důkaz provedeme obdobným způsobem jako v předchozím případě."]},{"cell_type":"markdown","metadata":{"id":"_ByGy0qb_tvJ"},"source":["### __Příklad 2.9__\n","\n","Určete, zda je následující formule tautologie:\n","- $ \\forall x (A(x) \\vee B(x)) \\Rightarrow (\\forall x A(x) \\vee \\forall x B(x)) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"35JB055neE2s"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"jKyW_1lXeE2u"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"v8JNBpZgBkUg"},"source":["Protipříklad: Mějme doménu celých čísel, kde $A(x)$ je pravda pro lichá čísla a nepravda pro sudá čísla, $B(x)$ je pravda pro sudá čísla a nepravda pro lichá čísla. Potom $ \\forall x (A(x) \\vee B(x)) $ je pravda, ale $ \\forall x A(x) \\vee \\forall x B(x) $ ne."]},{"cell_type":"markdown","metadata":{"id":"EHwZbGrP_tvM"},"source":["### __Příklad 2.10__\n","\n","Určete, zda je následující formule tautologie:\n","- $ \\forall x \\forall y R(x,y) \\Leftrightarrow \\forall y \\forall x R(x,y) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"1u0ioJdNeFZ3"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"odLw90FSeFZ4"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"cnbarG5pBkeP"},"source":["Opět je potřeba dokázat, že platí obě implikace. Protože se pro všeobecný kvantifikátor jedná o zobecněnou konjunkci, přičemž je konjunkce komutativní, a oba kvatifikátory jsou stejné kvantity, můžeme je zaměnit."]},{"cell_type":"markdown","metadata":{"id":"r9kWHXSP_tvP"},"source":["### __Příklad 2.11__\n","\n","Určete, zda je následující formule tautologie:\n","- $ (\\exists x A(x) \\wedge \\exists x B(x)) \\Rightarrow \\exists x (A(x) \\wedge B(x)) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"7XPwahvmeF_8"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"2pVfbShgeF_-"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"-0eAsasYBkog"},"source":["Protipříklad: Mějme doménu, kde $A(x)$ je pravda právě pro jeden její prvek $a$ a $B(x)$ je pravda právě pro jeden její prvek $b$ různý od $a$. Potom $ \\exists x A(x) \\wedge \\exists x B(x) $ je pravda, ale $\\exists x (A(x) \\wedge B(x))$ ne. Např. $D=\\{1,2\\},A=\\{1\\},B=\\{2\\}$."]},{"cell_type":"markdown","metadata":{"id":"QdQ2kOAF_tvS"},"source":["### __Příklad 2.12__\n","\n","Určete, zda je následující formule tautologie:\n","- $ (\\forall x P(x) \\Rightarrow \\forall x Q(x)) \\Rightarrow \\forall x (P(x) \\Rightarrow Q(x)) $\n","\n","### __Řešení__"]},{"cell_type":"markdown","metadata":{"id":"KFk2LmlpeGgc"},"source":["_TODO - doplňte sami editováním této buňky_"]},{"cell_type":"markdown","metadata":{"id":"EqBj9apCeGgi"},"source":["### __Možné řešení__"]},{"cell_type":"markdown","metadata":{"id":"XfT0OEZPBlBR"},"source":["Protipříklad: Mějme doménu, kde pro nějakou konstantu $a$ je $P(x)$ pravda a $Q(x)$ nepravda a navíc pro nějakou hodnotu $P(x)$ je nepravda. Potom $\\forall x P(x)$ je nepravda a tedy $\\forall x P(x) \\Rightarrow \\forall x Q(x)$ je pravda. Dále pro $x = a$ je $P(x) \\Rightarrow Q(x)$ nepravda, tedy i $\\forall x (P(x) \\Rightarrow Q(x))$ je nepravda. Máme tedy $1 \\Rightarrow 0$, což je nepravda."]}]}