Cs 371 - the Predicate Calculus

CS371 Lecture: The Predicate Calculus last revised 1/4/06

Objectives:

1. To introduce the first order predicate calculus, including the syntax of WFFs

2. To introduce formalization of knowledge using predicate calculus

3. To introduce resolution-refutation theorem proving, including unification and

conversion to clause form

4. To discuss the formal basis for Prolog in predicate calculus

5. To discuss resolution-refutation proof as a search problem

Materials:

1. Handout with laws of equivalence of formulas

2. Projectable Form of unification algorithm

3. Demonstration of Project 3

I. Introduction to the First Order Predicate Calculus

A. One notation system that is widely used in AI systems is the notation of

formal mathematical logic.

1. Formal logic is much older than AI or computer science. Formal logic

is a mathematical formalism for reasoning about assertions.

2. Formal logic is not only used by mathematicians, but also by

philosophers. Here at Gordon, the philosophy department teaches a

course that (among other things) teaches and uses formal logic.

3. Behind formal logic is a history of hundreds of years of work. Thus, it

is a well-understood tool. (In fact, it is generally recognized that the

work of logicians like Boole, Frege, Russell and others helped lay the

foundation for AI.)

4. The particular type of formal logic we will use is called the first order

predicate calculus. This is the formalism most widely used by AI

workers.

a) Predicate calculus formulas can easily be represented using LISP,

and some of the first work using predicate calculus for AI was done

in this language.

b) Predicate calculus is also the basis of Prolog. This will become

obvious in the next series of lectures (on Prolog).

1

c) Your book (and many AI books) eases into predicate calculus by

way of a less powerful system of notation called the

PROPOSITIONAL CALCULUS. Since you should have seen

some of this before in Discrete Math, we will jump straight into the

predicate calculus

(Predicate calculus is essentially propositional calculus with the

building blocks being predicates).

5. Predicate calculus is not a panacea for all problems, though. In

particular, it has serious difficulties dealing with realities we often

encounter in human reasoning, such as:

a) Incomplete knowledge. Example: in a medical diagnostic system it

may be necessary to take the patient's age into consideration in

certain cases. How shall the system cope with a situation where the

age of a particular patient is not known?

b) Inexact knowledge. To continue the above example, maybe all we

know is that the age is between 40 and 50.

c) Uncertain knowledge. Often times we face situations where we say

things like "I'm fairly sure that this is true".

d) Non-monotonic knowledge. Sometimes new information causes us

to invalidate a belief we had previously accepted. Example: if told

that a certain creature is a bird, we would ordinarily assume it can

fly. If we are later told it is a penguin, that assumption and all

inferences built on it would have to be canceled.

e) We will look at traditional formal logic now. Later in the course,

we will look briefly at some approaches to addressing issues like

these in the general context of formal logic.

6. Nonetheless, predicate calculus will serve our purposes well.

7. One good source if you wish to study this material beyond what is in

the text is:

Nils Nilsson. Principles of Artificial Intelligence. (Palo Alto: Tioga,

1980).

This book has a very readable and thorough discussion of predicate

calculus.

2

B. The first order predicate calculus is a formal language for expressing

propositions. Like any formal language, it has a well-defined syntax.

C. A properly-formed predicate calculus expression is called a well-formed

formula or WFF (pronounced wiff). WFFs are built up out of several

basic types of building block:

1. Constants: a constant is a symbolic name for a real-world person,

object, event etc.

Ex: Suppose we were building a database of information about pets in

my home. Constants that might appear would include:

rocco (my dog)

alexander (my cat)

etc.

a)