{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Logic: `logic.py`; Chapters 6-8" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This notebook describes the [logic.py](https://github.com/aimacode/aima-python/blob/master/logic.py) module, which covers Chapters 6 (Logical Agents), 7 (First-Order Logic) and 8 (Inference in First-Order Logic) of *[Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu)*. See the [intro notebook](https://github.com/aimacode/aima-python/blob/master/intro.ipynb) for instructions.\n", "\n", "We'll start by looking at `Expr`, the data type for logical sentences, and the convenience function `expr`. Then we'll cover `KB` and `ProbKB`, the classes for Knowledge Bases. Then, we will construct a knowledge base of a specific situation in the Wumpus World. We will next go through the `tt_entails` function and experiment with it a bit. The `pl_resolution` and `pl_fc_entails` functions will come next. \n", "\n", "But the first step is to load the code:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from logic import *" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Logical Sentences" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The `Expr` class is designed to represent any kind of mathematical expression. The simplest type of `Expr` is a symbol, which can be defined with the function `Symbol`:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "x" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Symbol('x')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Or we can define multiple symbols at the same time with the function `symbols`:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "(x, y, P, Q, f) = symbols('x, y, P, Q, f')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can combine `Expr`s with the regular Python infix and prefix operators. Here's how we would form the sentence for \"P and not Q\":" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(P & ~Q)" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P & ~Q" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This works because the `Expr` class overloads the `&` operator with this definition:\n", "\n", "```python\n", "def __and__(self, other): return Expr('&', self, other)```\n", " \n", "and does similar overloads for the other operators. An `Expr` has two fields: `op` for the operator, which is always a string, and `args` for the arguments, which is a tuple of 0 or more expressions. Let's take a look at the fields for some `Expr` examples:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'&'" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sentence = P & Q\n", "\n", "sentence.op" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(P, Q)" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sentence.args" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'P'" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.op" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "()" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.args" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'P'" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Pxy = P(x, y)\n", "\n", "Pxy.op" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(x, y)" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Pxy.args" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is important to note that the `Expr` class does not define the *logic* of Propositional Logic; it just gives you a way to *represent* expressions. Think of an `Expr` as an [abstract syntax tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree). Each of the `args` in an `Expr` can be either a symbol, a number, or a nested `Expr`. We can nest these trees to any depth. An `Expr` can represent any kind of mathematical expression, not just logical sentences. For example:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(((3 * f(x, y)) + (P(y) / 2)) + 1)" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "3 * f(x, y) + P(y) / 2 + 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Operators for Constructing Logical Sentences\n", "\n", "Here is a table of the operators that can be used to form sentences. Note that we have a problem: we want to use Python operators to make sentences, so that our programs (and our interactive sessions like the one here) will show simple code. But Python does not allow implication arrows as operators, so for now we will create them using functions (but Python will display them using arrows). Alternately, you can always use the more verbose `Expr` constructor forms:\n", "\n", "| Operation | Book | Python Input | Python Output | `Expr` Input\n", "|--------------------------|----------------------|-------------------------|---|---|\n", "| Negation | ¬ P | `~P` | `~P` | `Expr('~', P)`\n", "| And | P ∧ Q | `P & Q` | `P & Q` | `Expr('&', P, Q)`\n", "| Or | P ∨ Q | `P` | `Q`| `P` | `Q` | `Expr('`|`', P, Q)\n", "| Inequality (Xor) | P ≠ Q | `P ^ Q` | `P ^ Q` | `Expr('^', P, Q)`\n", "| Implication | P → Q | `implies(P, Q)` | `P ==> Q` | `Expr('==>', P, Q)`\n", "| Reverse Implication | Q ← P | `rimplies(P, Q)` |`Q <== P` | `Expr('<==', Q, P)`\n", "| Equivalence | P ↔ Q | `equiv(P, Q)` |`P ==> Q` | `Expr('==>', P, Q)`\n", "\n", "Here's an example of defining a sentence:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(~(P & Q) <=> (~P | ~Q))" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "equiv(~(P & Q), (~P | ~Q))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## `expr`: a Shortcut for Constructing Sentences\n", "\n", "We can't write `(~(P & Q) <=> (~P | ~Q))` as a Python expression, because Python does not have the `<=>` operator. But we can do something almost as good:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(~(P & Q) <=> (~P | ~Q))" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "expr('~(P & Q) <=> (~P | ~Q)')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The function `expr` takes a string as input, and parses it into an `Expr`. The string can contain arrow operators: `==>`, `<==`, or `<=>`. And `expr` automatically defines any symbols, so you don't need to pre-define them:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "sqrt(((b ** 2) - ((4 * a) * c)))" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "expr('sqrt(b ** 2 - 4 * a * c)')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For now that's all you need to know about `expr`. Later we will explain the messy details of how it is implemented." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Propositional Knowledge Bases: `PropKB`\n", "\n", "The class `PropKB` can be used to represent a knowledge base of propositional logic sentences.\n", "\n", "We see that the class `KB` has four methods, apart from `__init__`. A point to note here: the `ask` method simply calls the `ask_generator` method. Thus, this one has already been implemented and what you'll have to actually implement when you create your own knowledge base class (if you want to, though I doubt you'll ever need to; just use the ones we've created for you), will be the `ask_generator` function and not the `ask` function itself.\n", "\n", "The class `PropKB` now.\n", "* `__init__(self, sentence=None)` : The constructor `__init__` creates a single field `clauses` which will be a list of all the sentences of the knowledge base. Note that each one of these sentences will be a 'clause' i.e. a sentence which is made up of only literals and `or`s.\n", "* `tell(self, sentence)` : When you want to add a sentence to the KB, you use the `tell` method. This method takes a sentence, converts it to its CNF, extracts all the clauses, and adds all these clauses to the `clauses` field. So, you need not worry about `tell`ing only clauses to the knowledge base. You can `tell` the knowledge base a sentence in any form that you wish; converting it to CNF and adding the resulting clauses will be handled by the `tell` method.\n", "* `ask_generator(self, query)` : The `ask_generator` function is used by the `ask` function. It calls the `tt_entails` function, which in turn returns `True` if the knowledge base entails query and `False` otherwise. The `ask_generator` itself returns an empty dict `{}` if the knowledge base entails query and `None` otherwise. This might seem a little bit weird to you. After all, it makes more sense just to return a `True` or a `False` instead of the `{}` or `None` But this is done to maintain consistency with the way things are in First-Order Logic, where, an `ask_generator` function, is supposed to return all the substitutions that make the query true. Hence the dict, to return all these substitutions. I will be mostly be using the `ask` function which returns a `{}` or a `False`, but if you don't like this, you can always use the `ask_if_true` function which returns a `True` or a `False`.\n", "* `retract(self, sentence)` : This function removes all the clauses of the sentence given, from the knowledge base. Like the `tell` function, you don't have to pass clauses to remove them from the knowledge base; any sentence will do fine. The function will take care of converting that sentence to clauses and then remove those." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# TODO: More on KBs, plus what was promised in Intro Section" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Appendix: The Messy Details of the Implementation of `expr`\n", "\n", "How does `expr` parse a string into an `Expr`? It turns out there three tricks:\n", "\n", "1. We do a string substitution, replacing `\"==>\"` with `\"|InfixOp('==>', None)|\"`.\n", "2. We `eval` the resulting string in an environment in which every identifier\n", "is bound to a symbol with that identifier as the name.\n", "3. A coordination between `Expr` and `InfixOp` creates the proper nested `Expr`.\n", "\n", "\n", "That must sound very confusing, so we'll explain it in detail. Consider the sentence `\"P ==> Q\"`. If we try to evaluate that we get a `SyntaxError` because `==>` is not valid Python syntax. So we substitute it away, using the function `expr_handle_infix_ops` (from the `utils` module):" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "\"P |InfixOp('==>', None)| Q\"" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "expr_handle_infix_ops('P ==> Q')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What does that mean? To Python, for any expression `op`, \"`P |op| Q`\" is the same as \"`((P | op) | Q)`\". So the first step is:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "InfixOp('==>', P)" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first = (P | InfixOp('==>', None))\n", "\n", "first" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`InfixOp('==>', P)` means an infix operator whose operator string is `'==>'` and whose left-hand element is `P`. What happened here is that the `__or__` method in `Expr` says that if the object on the right is an `InfixOp`, then the result is an `InfixOp` whose `lhs` is the `Expr` on the left of the `\"|\"`.\n", "\n", "In the second step, we combine this with `Q`:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(P ==> Q)" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "first | Q" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What happened here is that the `__or__` method for `InfixOp` says that when combined with anobject on the right, return a new `Expr` whose `op` and first `arg` comes from the `InfixOp` and whose second `arg` is the object on the right. This [trick](http://code.activestate.com/recipes/384122-infix-operators/) is due to [Ferdinand Jamitzky](http://code.activestate.com/recipes/users/98863/).\n", "\n", "Note that we can also use this notation in our own code, or in an interactive session, like this:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "((P & Q) ==> P)" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P & Q |implies| P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Unfortunately, this puts `implies` at the same precedence as `\"|\"`, which is not quite right. We get this:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(((P & Q) ==> P) | Q)" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P & Q |implies| P | Q" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "which is probably not what we meant; when in doubt, put in extra parens:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "((P & Q) ==> (P | Q))" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P & Q |implies| (P | Q)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Authors\n", "\n", "This notebook by [Chirag Vertak](https://github.com/chiragvartak) and [Peter Norvig](https://github.com/norvig).\n", "\n" ] } ], "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.5.1" } }, "nbformat": 4, "nbformat_minor": 0 }