Chapter 2

The Predicate Calculus

Contents
• The Propositional Calculus
• The Predicate Calculus
• Using Inference Rules to Produce
Predicate Calculus
• Application: A Logic-Based Financial
Advisor
CSC411 Artificial intelligence 11
CSC411 Artificial intelligence 22
CSC411 Artificial intelligence 33
CSC411 Artificial intelligence 44
 Proposition Equivalence
For propositional expressions P, Q and R:

CSC411 Artificial intelligence 55

 Truth Table
Truth table for the
operator .

Truth table demonstrating

the equivalence of P Æ Q
and ÿ P ⁄ Q.

CSC411 Artificial intelligence 66

CSC411 Artificial intelligence 77
CSC411 Artificial intelligence 88
CSC411 Artificial intelligence 99
CSC411 Artificial intelligence 10
10
 verify_sentence algorithm

CSC411 Artificial intelligence 11

11
CSC411 Artificial intelligence 12
12
CSC411 Artificial intelligence 13
13
 Equivalence
For predicates p and q, and variables
X and Y
 Xp(X)  Xp(X)
 Xp(X)  Xp(X)
 Xp(X)  Yp(Y)
 Xp(X)  Yp(Y)
 X(p(X)q(X))  Xp(X)Yq(Y))
 X(p(X)q(X))  Xp(X)Yq(Y) )

CSC411 Artificial intelligence 14

 Higher-order predicate calculi
– Allows quantified predicates
– E.g. (Likes) Likes(george, kate)

CSC411 Artificial intelligence 15

 A blocks world with its predicate calculate
description.

A rule for clear block:

X(Y on(Y,X)  clear(X))
CSC411 Artificial intelligence 16
 Inference
Logical inference – infer new correct
expressions from a set of true
assertions
New expressions must be consistent
with all previous expressions

CSC411 Artificial intelligence 17

CSC411 Artificial intelligence 18
CSC411 Artificial intelligence 19
CSC411 Artificial intelligence 20
CSC411 Artificial intelligence 21
 Unification
Unification -- An algorithm (procedure) for
determining the substitutions needed to make two
predicate calculus expressions match
Unifier -- a set of variable substitutions that make
two expressions identical
E.g, for expression foo(X, a, goo(Y))
Expressions Substitutions
foo(fred, a goo(Z)) {fred/X, Z/Y}
foo(W, a, goo(jack)) {W/X, jack/Y}
foo(Z, a, goo(moo(Z))) {Z/X, moo(Z)/Y}

CSC411 Artificial intelligence 22

 Unification Issues
 can be simply removed
 may be eliminated by replacing the variable with
the constant.
E.g. parent(X, tom)  parent(mary, tom)
Skolem function may be used to replace a variable
that depends on other variables
e.g. XYparent(X,Y)  parent(X,f(X))
A variable may be replaced by any terms, but not
the terms that contain it
A constant cannot be replaced by any terms
If a variable is bound to a constant, it my not be
re-bound
CSC411 Artificial intelligence 23
 Composition of Unification
Substitutions
If S and S’ are two substitution sets, the the
composition of S and S’, SS’, is obtained by
applying S’ to the elements of S and adding the
result to S
E.g. Consider three sets of substitutions:
{X/Y, W/Z}, {V/X}, {a/V, f(b)/W}
Compositing the third set with the second set:
{a/X, a/V, f(b)/W}
Composing this result with the first set:
{a/Y, a/X, a/V, f(b)/Z, f(b)/W}
Composition is associative but not commutative
CSC411 Artificial intelligence 24
 Most General Unifier (mgu)

The mgu for a set of expressions is unique except

for alphabetic variations
E.g. Unifying p(X) and p(Y),
– {fred/X, fred/Y} is an unifier, but not mgu
– Both {Z/X, Z/Y} and {W/X, W/Y} are mgus.

CSC411 Artificial intelligence 25

 Unification Algorithm

CSC411 Artificial intelligence 26

• Unifying parents(X, father(X), mother(bill)) and
parents(bill, father(bill), Y).
• Convert to List format first

CSC411 Artificial intelligence 27

 Final trace of the unification of (parents X (father
X) (mother bill)) and (parents bill (father bill) Y).

CSC411 Artificial intelligence 28

 A Logic-Based Financial Advisor
The advisor helps a user to decide whether to
invest in a savings account, or the stock market
What to invest depends on their income and the
current amount they have saved
Criteria:
– Individuals with an inadequate savings account should
always make increasing the amount saved their first
priority, regardless of their income
– Individuals with adequate savings account and an
adequate income should consider a riskier but potentially
more profitable investment in the stock market
– Individuals with a lower income who already have an
adequate savings account may want to consider splitting
their surplus income between savings and stocks, to
increase the cushion in savings while attempting to
increase their income through stocks

CSC411 Artificial intelligence 29

 Logic System

CSC411 Artificial intelligence 30

13
 Advisor System Inference
minsavings(X)  500*X
minincome(X)  15000+(4000*X)
Consider an user with three dependents, $220000
in savings, and steady income of $25000
– Add facts:
9. amount_saved(22000).
10. earnings(25000, steady).
11. dependents(3).
– Conjunct 10 and 11, unify with 7 under the substitution
{25000/X, 3/Y}, and use modus ponens
12. income(inadequate).
– Conjunct 9 and 11, unify with 4 under the substitution
{22000/X, 3/Y}, and use modus ponens
13. savings_account(adquate)
– Conjuct 12 and 13, use modus ponens with 3
14. investment(combination)

CSC411 Artificial intelligence 31