Chapter 2: The Predicate Calculus

GL states that the "function of any representation scheme is to capture... the critical features of a problem domain and make that information accessible to a problem-solving procedure." (AI, 37)

In other words, representations are abstractions of a problem domain which can be used to solve or learn more about them. One such representation language, predicate calculus (PC), captures the properties and relations between things in a domain from which to reason. PC offers formal semantics and sound and complete inference rules.


2.1 The Propositional Calculus

I'm choosing to not outline this section as I mostly skimmed through it. It presents a general review of propositional calculus which can be found in any intro-level course on logic or C.S. math foundations.


2.2 The Predicate Calculus (PC)

PC allows us access to the individual components of assertions. Instead of "it rained on tuesday" being contained in the atomic component P of Propositional Calculus, we can make it into a predicate statement like weather(Tuesday, rain). In this format we now have a relationship between between the day and the weather. With inference rules we can then discover new expressions by manipulating previous ones.

So I guess predicate calculus lets us fit information, like a problem domain, into a formal system while still preserving the relations among its members. It also allows variables to be used and quantified. More on this next...

2.2.1 The Syntax of Predicates and Sentences

• Symbol - irreducible syntactic element. Symbols are used to denote objects, properties, or relations They may represent either variables, constants, functions, or predicates. I guess symbols are the "atomic" elements of PC.
• Improper Symbol - used to constructed well-formed expressions. These are parentheses, commas, and periods.
• Function - map one or more elements in a set (domain) into a unique element of another set (range)
• Atomic Sentence - predicate of arity n followed by n terms enclosed in parentheses and separated by commas
• Predicate - names a relationship between zero or more objects in the world. True of False.

A predicate relation is defined by its name AND its arity.

2.2.2 A Semantics for the Predicate Calculus
Predicate calculus semantics provide a formal basis for determining the truth value of well-formed expressions. Remember: constants, variables, and predicates are "mapped" onto objects and relations in the domain of discourse. They represent them. The truth of relationships in the domain determines the truth of the corresponding expressions. So PC is just our way of "viewing" the domain; this is why it's so important to map it correctly - we want our expressions to accurately reflect what they represent.

Interpretation - An interpretation over a nonempty set (Domain) maps the elements of D onto constant, variable, predicate, and function symbols of a PC expression. As I recall, an interpretation must ensure all expressions in the given set are true.

In PC variables can be quantified existentially or universally. Under the given interpretation, a subset of the constants of D can be substituted for a variable.

PC is considered undecidable because it has universal quantification; i.e. it can be computationally impossible to test all the substitutions for a universally-quantified variable.

2.2.3 A "Blocks World" Example of Semantic Meaning
An example predicate calculus description of a blocks world:

• on(c,a)
• on(b,d)
• ontable(a)
• ontable(d)
• clear(b)
• clear(c)
• hand_empty

and an example rule, describing when a block is clear:

\/X (!EY on(Y,X) -> clear(X))

This is read as: "For all X, if there is no Y such that Y is on X, then X is clear."

(Note: I haven't spent time figuring out how to use symbols in blogger so for now I'm using approximations.)

2.3 Using Inference Rules to Produce PC Expressions

2.3.1 Inference Rules

The semantics of PC allow us to logically infer new correct, consistent expressions from a set of true assertions. 

"An expression X logically follows from a set of expressions S if every interpretation that satisfies S also satisfies X." In other words, X logically follows if the same set of interpretations are possible with it included alongside S. Inference rules are used to determine if an expression logically follows, since the number of interpretations may be infinite!

Inference rules:

• produce new sentences based on the syntactic form of given logical assertions.
• are sound if the sentences it produces all logically follow from the set its operating on.
• are complete if it can produce every sentence that logically follows from a set. (e.g. Modus ponens)

2.3.2 Unification

Unification determines the substitutions needed to make two PC expressions match. For this to work, all variables must be universally quantified. Existentially quantified variables may be eliminated by replacing them with appropriate constants (to make them True). 

Unify pseudo-code on page 69.

(Attribution: these entries are my notes and reflections on George Luger's Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Some of what I write here may be direct from the text. In other words, if something you read strikes you as profound, original, or interesting, I probably didn't write it.)