{"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_lab8.ipynb","provenance":[],"collapsed_sections":[]}},"cells":[{"cell_type":"markdown","metadata":{"id":"nITBbl4q_tth"},"source":["# PB016: Artificial Intelligence, labs 8 - Introduction to predicate logic\n","\n","Today's topic is the basics of first-order predicate logic (PL1). We will focus in particular on:\n","1. __Representation of expressions using PL1 formulas__\n","2. __Interpretation of formulas in PL1__\n","\n","First, however, a __quick introduction__ into what predicate logic is:\n","- Extension of propositional logic both in terms of syntax and semantics.\n","- Expressive tool for axiomatization of mathematical structures.\n","- Closer to natural language and suitable as a formal tool for encoding complex \"ontologies\" (machine-readable knowledge representations).\n","- The most important extensions:\n"," - quantifiers - existential $ \\exists $ (applies in at least one case) and universal $ \\forall $ (applies in all cases)\n"," - identity symbol $ = $\n"," - domain of interpretation - a set representing denotations, i.e. objects to which the expressions in PL1 relate (e.g. natural numbers, but can be any other set)\n"," - functional symbols for the representation of operations, resp. mappings over elements of the domain of interpretation (together with variables, they form a set of terms)\n"," - predicate symbols for representation of relations between objects\n","- Example - representation of commutative groups in PL1 can use a first-order language that has one constant symbol $0$, one unary function symbol $-$, one binary function symbol $+$, and one binary relational symbol $ \\leq $. Then:\n"," - The expressions $ + (x, y) $ and $ + (x, + (y, - (z))) $ are terms. They are usually written as $ x + y $ and $ x + y - z $.\n"," - The expressions $ + (x, y) = 0 $ and $ \\leq (+ (x, + (y, - (z))), + (x, y)) $ are atomic formulas. They are usually written as $ x + y = 0 $ and $ x + y - z \\leq x + y $.\n"," - The expression $ \\forall x \\forall y [\\leq (+ (x, y,), z) \\Rightarrow + (x, y) = 0] $ is a formula that is usually written as $ \\forall x \\forall y (x + y \\leq z) \\Rightarrow \\forall x \\forall y (x + y = 0) $. This formula has one free (also unbound) variable, $ z $.\n","  - The axioms of a given structure are then written as formulas, e.g. the commutativity in this example, corresponds to $ \\forall x \\forall y (x + y = y + x) $.\n"]},{"cell_type":"markdown","metadata":{"id":"rMB_46nl_tti"},"source":["---\n","\n","## 1. Representation of expressions using PL1 formulas\n","\n","- Conversion of sentences in natural language into the formal language of predicate logic.\n","- Possible uses: knowledge representation, natural language processing, etc."]},{"cell_type":"markdown","metadata":{"id":"Q5MFLutX_ttj"},"source":["### __Exercise 1.1__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Some students do not have musical talent.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"ymTQM0h_bV7H"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"fn9oCTq__ttp"},"source":["### __Exercise 1.2__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Some of the present people live in a hotel.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"6xe0m7kwMa_y"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"vPfG8I4Y_ttt"},"source":["### __Exerise 1.3__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Some students are neither gifted nor diligent.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"JN2OeASCMhAl"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"i1OPXXKA_tty"},"source":["### __Exercise 1.4__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Each number divisible by 8 is divisible by 4.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"NVLC_fSPMjDF"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"FdfmWYpB_tt3"},"source":["### __Exercise 1.5__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- He who sows the wind reaps the storm.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"VYDAhppLMl90"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"qdPsAVsh_tt7"},"source":["### __Exercie 1.6__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Dogs that bark a lot don't bite.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"JYbnSvG1MoKF"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"IYUgjHEB_tt_"},"source":["### __Exercise 1.7__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- No tyrant is fair.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"-b5QdpkaMp5F"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"jmB6CQo0_tuD"},"source":["### __Exercise 1.8__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Every person has a father and a mother.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"Tq61SQHzMsWV"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"oqlJHR4W_tuH"},"source":["### __Exercise 1.9__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Every person that has a father also has a mother.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"Tp9aCQwdMuD1"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"nzpX1Y2N_tuK"},"source":["### __Exercise 1.10__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Everyone is younger than their parents. (using terms)\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"AMDMuBGqMwKV"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"Nxsl3-UN_tuO"},"source":["### __Exercise 1.11__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- No good teacher would punish anyone unnecessarily.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"DR3jd2a9MyAF"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"bXEmVQuL_tuS"},"source":["### __Exercise 1.12__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Someone likes everyone.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"RdgNvAabMz8V"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"mVpsepuW_tuW"},"source":["### __Exercise 1.13__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Some like others.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"IEILc0tpM1v1"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"3--VIOxh_tua"},"source":["### __Exercise 1.14__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- Not all that glitters is gold.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"luANn688M3dF"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"NevzyNk__tud"},"source":["### __Exercise 1.15__\n","\n","Convert the following natural language sentence into formulas in predicate logic:\n","- All siblings have the same father. (using terms)\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"IS0N12FkM5XQ"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"-75HJfdB_tug"},"source":["### __Exercise 1.16__\n","\n","Let the expression $ L(l, e, p) $ mean \"Luboš lends Eva a pencil.\" Symbolically write the following statements:\n","1. Someone lends Eva a pencil.\n","2. Eva lends someone a pencil.\n","3. Eva lends something to someone.\n","4. Someone lends something to Eva.\n","5. Luboš lends something to everyone.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"DikX9A5bM7w1"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"Zz04JG_I_tuk"},"source":["### __Exercise 1.17__\n","\n","Use the $ L $ predicate for \"lending\" from the previous example, symbolically write the following general statements:\n","1. Someone lends something to someone.\n","2. Everyone lends something to someone.\n","3. Someone lends everything to everyone.\n","4. Someone does not lend anything to anyone.\n","5. There is no one who lends everything to everyone.\n","6. Everyone lends everything to everyone.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"6KzxWGOIM-wV"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"lKnHWymX_tun"},"source":["### __Exercise 1.18__\n","\n","Let $ S(p, t) $ mean \"I see the object $ p $ at the moment $ t $.\" Write the following sentences symbolically:\n","1. I see something at every moment.\n","2. At some point I don't see anything.\n","3. There are objects that I do not see at any time.\n","4. I see every thing at some point.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"e82zian3NATE"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"BAVc1LAo_tur"},"source":["---\n","\n","## 2. Interpretation of formulas in PL1\n","\n","- Basic tool for assigning meaning to expressions in PL1.\n","- Interpretation of a first-order language assigns each non-logical symbol in a given language with its denotation.\n","- It also specifies the scope of interpretation (also the interpretation domain) $ \\mathbf{D} $ - the set over which the quantifiers operate.\n","- The result of the interpretation are the following assignments:\n"," - each term is assigned the object from the set $ \\mathbf{D} $ it represents;\n"," - each predicate is assigned an object property;\n"," - each formula is assigned a truth value.\n","- A detailed study of interpretations of formal languages ​​is called formal semantics.\n","- Note: In determining the interpretation of formulas in PL1, it may be useful to convert them to another form more suitable for analysis, for which equivalence laws known from propositional logic can be used, together with the fact that negation changes $ \\forall $ to $ \\exists $ and vice versa when it is moved \"inside\" of quantified expressions. For more details, see e.g. [here](http://www.cs.um.edu.mt/gordon.pace/Teaching/DiscreteMaths/Laws.pdf)."]},{"cell_type":"markdown","metadata":{"id":"pYm-d1PO_tur"},"source":["### __Exercise 2.1__\n","\n","Find the negations of the formulas:\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","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"LhcY70-sNDq2"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"FMlx9k27_tuu"},"source":["### __Exercise 2.2__\n","\n","Determine for which interpretations the following formula is true:\n","- $ \\exists x \\forall y (P(y) \\Rightarrow (x=y)) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"hFBIUehyNE1l"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"q-OlSzPd_tux"},"source":["### __Exercise 2.3__\n","\n","Determine for which interpretations the following formula is true:\n","- $ \\exists x (P(x) \\wedge \\forall y (P(y) \\Rightarrow (x = y))) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"OIpfmaJaNGOU"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"-f1Y8UUI_tu2"},"source":["### __Exercise 2.4__\n","\n","Determine for which interpretations the following formula is true:\n","- $ \\forall x \\exists y \\exists z (((x=y) \\vee (x=z)) \\wedge (y \\not = z)) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"6XRxpDdaNHpU"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"22OUE5Aq_tu6"},"source":["### __Exercise 2.5__\n","\n","Determine for which interpretations the following formula is true:\n","- $ \\forall x \\exists y Q(x,y) \\Rightarrow \\exists x Q(x,x) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"d7zbAXwCNJdE"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"9RTrLUfQ_tu8"},"source":["### __Exercise 2.6__\n","\n","Determine for which interpretations the following formula is true:\n","- $ \\exists x \\forall y ((R(x,y) \\wedge \\neg R(y,x)) \\Rightarrow (R(x,x) \\Leftrightarrow R(y,y))) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"JOd8yi8-NKyU"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"6mskcYox_tvD"},"source":["### __Exercise 2.7__\n","\n","Determine whether the formula is a tautology:\n","- $ \\forall x (P(x) \\wedge Q(x)) \\Leftrightarrow (\\forall x P(x) \\wedge \\forall x Q(x)) $\n","\n","A little help: Showing that it is not a tautology can be done, for instance, by finding a counterexample.\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"ycyKM9v6NMYk"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"tSa6KXvK_tvG"},"source":["### __Exercise 2.8__\n","\n","Determine whether the formula is a tautology:\n","- $ \\exists x (P(x) \\vee Q(x)) \\Leftrightarrow (\\exists x P(x) \\vee \\exists x Q(x)) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"Ja7o-48JNOFT"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"_ByGy0qb_tvJ"},"source":["### __Exercise 2.9__\n","\n","Determine whether the formula is a tautology:\n","- $ \\forall x (A(x) \\vee B(x)) \\Rightarrow (\\forall x A(x) \\vee \\forall x B(x)) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"joshJ1OPNPQ1"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"EHwZbGrP_tvM"},"source":["### __Exercise 2.10__\n","\n","Determine whether the formula is a tautology:\n","- $ \\forall x \\forall y R(x,y) \\Leftrightarrow \\forall y \\forall x R(x,y) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"jQtgjEkGNQnv"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"r9kWHXSP_tvP"},"source":["### __Exercise 2.11__\n","\n","Determine whether the formula is a tautology:\n","- $ (\\exists x A(x) \\wedge \\exists x B(x)) \\Rightarrow \\exists x (A(x) \\wedge B(x)) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"810L87cvNR_j"},"source":["_TODO - complete yourself by editing this cell_"]},{"cell_type":"markdown","metadata":{"id":"QdQ2kOAF_tvS"},"source":["### __Exercise 2.12__\n","\n","Determine whether the formula is a tautology:\n","- $ (\\forall x P(x) \\Rightarrow \\forall x Q(x)) \\Rightarrow \\forall x (P(x) \\Rightarrow Q(x)) $\n","\n","### __Solution__"]},{"cell_type":"markdown","metadata":{"id":"KiLOcO_SNTWD"},"source":["_TODO - complete yourself by editing this cell_"]}]}