Logic: logic.py; Chapters 6-8

This notebook describes the 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. See the intro notebook for instructions.

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.

But the first step is to load the code:

Logical Sentences

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:

Or we can define multiple symbols at the same time with the function symbols:

We can combine Exprs with the regular Python infix and prefix operators. Here's how we would form the logical sentence "P and not Q":

This works because the Expr class overloads the & operator with this definition:

def __and__(self, other): return Expr('&',  self, other)

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. By "expression," I mean either an instance of Expr, or a number. Let's take a look at the fields for some Expr examples:

It is important to note that the Expr class does not define the logic of Propositional Logic sentences; it just gives you a way to represent expressions. Think of an Expr as an 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. Here is a deply nested Expr:

Operators for Constructing Logical Sentences

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 have to use a more verbose notation that Python does allow: |'==>'| instead of just ==>. Alternately, you can always use the more verbose Expr constructor forms:

Here's an example of defining a sentence with an implication arrow:

expr: a Shortcut for Constructing Sentences

If the |'==>'| notation looks ugly to you, you can use the function expr instead:

expr takes a string as input, and parses it into an Expr. The string can contain arrow operators: ==>, <==, or <=>, which are handled as if they were regular Python infix operators. And expr automatically defines any symbols, so you don't need to pre-define them:

For now that's all you need to know about expr. Later we will explain the messy details of how expr is implemented and how |'==>'| is handled.

Propositional Knowledge Bases: PropKB

The class PropKB can be used to represent a knowledge base of propositional logic sentences.

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.

The class PropKB now.

• __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 ors.
• 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 telling 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.
• 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.
• 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.

TODO: More on KBs, plus what was promised in Intro Section

TODO: fill in here ...

Appendix: The Implementation of |'==>'|

Consider the Expr formed by this syntax:

What is the funny |'==>'| syntax? The trick is that "|" is just the regular Python or-operator, and so is exactly equivalent to this:

In other words, there are two applications of or-operators. Here's the first one:

What is going on here is that the __or__ method of Expr serves a dual purpose. If the right-hand-side is another Expr (or a number), then the result is an Expr, as in (P | Q). But if the right-hand-side is a string, then the string is taken to be an operator, and we create a node in the abstract syntax tree corresponding to a partially-filled Expr, one where we know the left-hand-side is P and the operator is ==>, but we don't yet know the right-hand-side.

The PartialExpr class has an __or__ method that says to create an Expr node with the right-hand-side filled in. Here we can see the combination of the PartialExpr with Q to create a complete Expr:

This trick is due to Ferdinand Jamitzky, with a modification by C. G. Vedant, who suggested using a string inside the or-bars.

Appendix: The Implementation of expr

How does expr parse a string into an Expr? It turns out there are two tricks (besides the Jamitzky/Vedant trick):

1. We do a string substitution, replacing "==>" with "|'==>'|" (and likewise for other operators).
2. We eval the resulting string in an environment in which every identifier is bound to a symbol with that identifier as the op.

In other words,

is equivalent to doing:

One thing to beware of: this puts ==> at the same precedence level as "|", which is not quite right. For example, we get this:

which is probably not what we meant; when in doubt, put in extra parens:

Authors

This notebook by Chirag Vertak and Peter Norvig.