logic.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Explaining the logic.py module\n",
    "*Author: Chirag Vartak*<br>\n",
    "*Date: 23rd March 2016*\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## An Introduction\n",
    "\n",
    "Hello reader.<br>\n",
    "In this IPython notebook, I will help you a little so that you will become more comfortable with using the [logic.py](https://github.com/aimacode/aima-python/blob/master/logic.py) module. The `logic.py` module implements the algorithms given in Chapter 6 (Logical Agents), Chapter 7 (First-Order Logic) and Chapter 8 (Inference in First-Order Logic) of the book *Artificial Intelligence: A Modern Approach*.\n",
    "\n",
    "Before we begin, if you are unsure of how to use the [aima-python](https://github.com/aimacode/aima-python) repository or are not familiar with IPython notebooks you should read the [intro notebook](https://github.com/aimacode/aima-python/blob/master/intro.ipynb) first. Also, if you are more comfortable with Java than you are with Python we also have the [aima-java](https://github.com/aimacode/aima-java) repository.\n",
    "\n",
    "I am assuming that you have read at least Chapter 7 (Logical Agents). You really want to do this if you intend to make sense of anything I tell you in this notebook, or any code in the `logic.py` module, for that matter. If you haven't you should go back and read this chapter first, at least upto Sec. 7.5. As a side note, be sure to keep the `logic.py` module open and keep referring to it as you read this notebook. The docstrings of most classes and functions are well-written and will give you more insight and in some cases, even examples, of how to use that particular class or function.\n",
    "\n",
    "To briefly outline how I will proceed in this notebook, I will start by telling you more about the classes `KB` and `ProbKB`, the classes for the Knowledge Bases that we will be using. Next, we will begin with Propositional Logic; only after we are mostly done with it, we will be getting into First-Order Logic. In Propositional Logic, we will have a look at the class `Expr` and the `expr` function, and try to get more comfortable with using them to create and manipulate logical expressions. We will also play a little with other utility functions created to make working with statements easy. 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",
    "So let's get started."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Knowledge Bases: `KB` and `PropKB`\n",
    "\n",
    "The class `KB` is just a template class which you have to inherit to create a knowledge base class that you plan to use. This class reminds you to implement all the methods mentioned here and will scream at you if you forget to. It is, what you might call in Java, an abstract class. The class `PropKB` has been derived from the class `KB` and all the methods have been implemented in here. Let's have a look at these classes in somewhat more detail.\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": {
    "collapsed": true
   },
   "source": [
    "## Getting started with Propositional Logic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The `Expr` class\n",
    "\n",
    "The `Expr` class is the one that enables us to work with propositional logic. This class, combined with the `expr` function will enable us to work with propositional logic with much ease.\n",
    "\n",
    "An instance of the `Expr` class, an `Expr` object represents a symbolic mathematical expression. Truth be told, this class can handle not just Propositional Logic but also First-Order Logic. (As a matter of fact, you can also do arithmetic using this class but you would just be introducing unnecessary complication for a simple task). For the case of our Propositional Logic, an `Expr` object represents a propositional sentence. If you will have a look at its `__init__`, you will see that an `Expr` object just stores the operator and the arguments of a propositional sentence. This is important to note. The `Expr` class does not define the *logic* of Propositional Logic; nor will we be defining it ourselves. It just gives you a way to *represent* expressions. You won't be able to do any propositional math using `Expr`; you won't be be able assign a value of `True` to `P` and `False` to `Q` and then do a `P` &and; `Q` to get `False`. No, you won't be able to do that. What you will be able to do is to create a representation of sentence and assign it to `P`. Something like,\n",
    "\n",
    "```python\n",
    "sent = Expr(\"==>\", \"A & B\", \"C\")\n",
    "```\n",
    "\n",
    "which is represents the sentence\n",
    "\n",
    "> (A &and; B) &rarr; C\n",
    "\n",
    "That's not much, you say. We can create representations of sentences using strings, you continue. Well, we manipulate the `Expr` objects to convert a sentence to its CNF (`to_cnf`), check satisfiability of a sentence (`dpll_satisfiable`), use resolution to find out if a knowledge base entails a sentence (`pl_resolution`) and whatnot. Best of luck doing that with your string representations!\n",
    "\n",
    "So, the point to take away from the last two paragraphs: The `Expr` class just allows you to create good, easily manipulable representations of propositional sentences. It does a little more than that though. Before I get into that let us create a few expressions of our own to experiment with them later on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from logic import *\n",
    "\n",
    "P = Expr(\"P\")\n",
    "Q = Expr(\"Q\")\n",
    "R1 = Expr(\"&\", \"A\", \"B\")\n",
    "R2 = Expr(\"==>\", \"C | D\", \"E\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note here that you can create expressions that have no operators (like the literals `P` and `Q`), simple expressions of literals (like the sentence R1 which represents `A` &and; `B`) and also expressions that have, as their arguments, complex sentences represented as strings. But, these strings that are allowed as arguments, can use only certain symbols in them. This is the list of symbols that you should use when you want to put complex sentences as arguments to the `Expr` constructor:\n",
    "\n",
    "| Operation                | Propositional Symbol | Operator to use in Code |\n",
    "|--------------------------|----------------------|-------------------------|\n",
    "| Negation                 | &not;                | ~                       |\n",
    "| And                      | &and;                | &                       |\n",
    "| Or                       | &or;                 | &#124;                  |\n",
    "| Implies                  | &rarr;               | >> or ==>               |\n",
    "| Biconditional            | &harr;               | % or <=>                |\n",
    "| **Some additional ones** |                      |                         |\n",
    "| Inequality (Xor)         | (Dunno)              | =/= or ^                |\n",
    "| Reverse Implication      | &larr;               | << or <==               |\n",
    "\n",
    "Also, this is the precedence sequence with which the operators will be evaluated in code. The highest precedence operators are at the top:\n",
    "\n",
    "    ~\n",
    "    %   <=>\n",
    "    <<  <==  >>  ==>\n",
    "    &\n",
    "    ^\n",
    "    |\n",
    "    \n",
    "Note that the `<=>` and the implication operators are quite at the top. So make sure to use parenthesis correctly when using them with others like `&`, `^` and `|`. You might note that the precedence of these operators is the same as that in Python language. This is not just a coincidence. More about this later.\n",
    "\n",
    "Getting back to the `Expr` class and the expressions that we have created, lets create a more complex expression from the ones we have already created:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Cell: Creating complicated sentences\n",
    "R3 = Expr(\"<=>\", R1, Q)\n",
    "R4 = Expr(\"==>\", R2, P & ~Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, these are the expressions that we've created now. To display these expressions in a nice, intuitive form, the `__repr__` method has been implemented accordingly. It called when we put the variable in the interpreter or when we use the `print` function. Let's try both:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "P"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(A & B)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(((C | D) ==> E) ==> (P & ~Q))"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P\n",
      "(A & B)\n",
      "(((C | D) ==> E) ==> (P & ~Q))\n"
     ]
    }
   ],
   "source": [
    "print(P)\n",
    "print(R1)\n",
    "print(R4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, that's how it works. Now scroll above a little and have a look at the cell titled \"Creating complicated sentences\". Do you notice something amiss? Now note that, the third argument in the 2nd line is `P & ~Q`. Now, how is that done? It's a statement, for sure, but it's not in the form of a string. As a matter of fact, `P` and `Q` are both `Expr`s themselves.\n",
    "\n",
    "This is made possible because the `Expr` class overloads many operators. (It actually overloads mostly all the operators available in Python, but don't use them all; not, at least, for Propositional Logic.) Hence, you can do things like `P & ~Q` to *create `Expr`s by directly combining existing `Exprs`*. You might not immediately recognize the power and ease that this grants you, but I'll explain. Once, you have created some small, rudimentary expressions, you can use these overloaded operators to directly get your desired expressions; no need of using the `Expr` constructor each time. See how simple doing all that we did above becomes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P\n",
      "(A & B)\n",
      "(((C | D) >> E) >> (P & ~Q))\n"
     ]
    }
   ],
   "source": [
    "# Some simple, rudimentary sentences\n",
    "P = Expr(\"P\")\n",
    "Q = Expr(\"Q\")\n",
    "A = Expr(\"A\")\n",
    "B = Expr(\"B\")\n",
    "C = Expr(\"C\")\n",
    "D = Expr(\"D\")\n",
    "E = Expr(\"E\")\n",
    "\n",
    "# Now for our complex expressions\n",
    "R1 = A & B\n",
    "R2 = (C | D) >> E\n",
    "\n",
    "# And the more complex expressions\n",
    "R3 = R1 % Q\n",
    "R4 = R2 >> (P & ~Q)\n",
    "\n",
    "# Let's print them and see if they are the same as before\n",
    "print(P)\n",
    "print(R1)\n",
    "print(R4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes, yes they are. We cannot use `==>` and `<=>` when we use operator overloading, because those are not operators in Python. Instead, we have to use `>>` and `%` operators in their place. (Actually, `==>` and `<=>` are converted to `>>` and `%` internally.) Did you just cringe at using `%` for biconditionals? I am not too happy with that either. Ugly, I know, but for many reasons we *had to* implement it that way. But hey, it works like a charm.\n",
    "\n",
    "Before we move on, I would like to point out something that might cause you some confusion. The `==` and `!=` operators for `Expr`s. They do not logically evaluate two expressions and then check if they are equal. So don't do something like\n",
    "\n",
    "```python\n",
    "A & (B | C) == (A & B) | (A & C)\n",
    "```\n",
    "\n",
    "or even\n",
    "\n",
    "```python\n",
    "A & B == B & A\n",
    "```\n",
    "\n",
    "and expect it to return `True`. That's not how the `==` operator is intended to work. If you to know what it is supposed to do, have a look at the implementation of `__eq__`; that should tell you enough."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The `expr` function\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.4.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}