CMP2020M Artificial Intelligence
Dr. Bashir Al-Diri
Dr. Marc Hanheide
Dr. Patrick Dickinson
Lincoln School of Computer Science
CM2020M Artificial Intelligence
Introduction to AI
Knowledge Representation
Planning
Logic Programming(2/3) Games AI
Probabilistic Reasoning
CMP2020M: Lecture 6 – Logic Programming
Lecture 6: Logic Programming
Predicate Calculus Inference Rules
Unification
Next week: Prolog Programming CMP2020M: Lecture 6 – Logic Programming
Logic Programming consists of A language
which tells us how to build up sentences in the language (i.e., syntax), and what a sentence means (i.e., semantics)
An inference procedure
which tells us which sentences are valid inference
from other sentences
CMP2020M: Lecture 6 – Logic Programming
Syntax: Predicate Calculus symbols
Symbols consists of:
The set of letters (both uppercase and lowercase): A … Z, a … z. The set of digits: 0 … 9
The underscore: _
Symbol must start with a letter.
CMP2020M: Lecture 6 – Logic Programming
Syntax: Predicate Calculus symbols
Symbols may represent either
Constants (must begin with a lowercase letter),
Variables (must begin with an uppercase letter), Functions (must begin with a lowercase letter), or
Predicates (must begin with a lowercase letter).
CMP2020M: Lecture 6 – Logic Programming
Terms
Syntax: symbols – Constants
They name specific objects or properties in the world
They must begin with a lowercase letter
Example: car, tree, blue, …
The constants true and false are reserved as truth symbols
CMP2020M: Lecture 6 – Logic Programming
Syntax: symbols – Variables
They are used to assign general classes of objects or
properties
They must begin with an uppercase letter Example: Car, Tree, Blue, …
CMP2020M: Lecture 6 – Logic Programming
Syntax: symbols – Functions
They must begin with an lowercase letter (like constant).
Example: father(david), plus(2,3), maximum_of(X,Y)
Replacing a function with its value is called evaluation.
Plus(2,3) whose value is the integer 5.
CMP2020M: Lecture 6 – Logic Programming
Example: father(david), plus(2,3), maximum_of(X,Y) Syntax: symbols – Functions
A function expression is a function symbol followed by its arguments.
The arguments are elements from the domain of the function.
The arity is the number of arguments.
The arguments are enclosed in parentheses and
separated by commas.
CMP2020M: Lecture 6 – Logic Programming
Syntax: symbols – Predicate
They begin with a lowercase letter (like constant and
function).
A predicate names a relationship between objects in the world.
Examples: likes(george, suzan), equals(X,Y), on(B1,B2)
Predicates are special functions with true/false as values.
Predicates with the same name but different arities are considered distinct.
likes(george, suzan)
likes(george,sarah,tuesday)
CMP2020M: Lecture 6 – Logic Programming
Constants
Terms
Variables
Functions
Predicates
likes(george, suzan)
likes(X,george)
likes(X,Y)
likes(george,sarah,tuesday) friends(bill,george)
friends(father_of(david), father_of(andrew))
terms (functions) CMP2020M: Lecture 6 – Logic Programming
Syntax: Examples
Symbols
terms (constants) terms (variables)
Predicates
Semantics: Predicate Calculus semantics
Terms (constants, variables, and functions) are mapped
to objects in a domain of discourse.
A predicate names a relationship between objects in the
world.
The semantics of predicate calculus provide a formal
basis for determining the truth value of an expression.
Truth values are then assigned to sentences to describe
the “state of the world”
CMP2020M: Lecture 6 – Logic Programming
Inference rules
Modus ponens
If P Q and P are true, then infer Q.
Modus tollens
If P Q and Q are true, then infer P.
And elimination
If P Q is true, then infer both P and Q are true.
And introduction
If both P and Q are true, then infer P Q.
CMP2020M: Lecture 6 – Logic Programming
Unification
The inference system must be able to determine when two
expressions are the same or match.
Two expressions match if and only if they are syntactically
identical.
This process is complicated by the existence of variables
Unification is an algorithm of determining the substitutions to make two predicate expressions match.
CMP2020M: Lecture 6 – Logic Programming
Unification algorithm
We can replace variables by other variables
constants
function expressions
High level algorithm:
Represent expressions as a list
Process the list one by one
Determine a substitution (if necessary)
Apply to the rest of the list before proceeding
CMP2020M: Lecture 6 – Logic Programming
Terms
Substitution
A substitution is assigned variables to values
Two terms unify if there is a substitution that makes those two terms identical
The notation X/Y indicates that X is substituted for the variable Y in the original expression
Example: unifying f(X, 2) and f(3, Y)
This substitution can be written as 3/X, 2/Y
CMP2020M: Lecture 6 – Logic Programming
produces X=3, Y=2
Substitution: Example
Given
p(Y,Z) q(Y,Z) q(W,b) r(W,b) p(a,X)
Modus ponens
If P and P Q are true, then infer Q.
P
Q
PQ
T
T
T
T
F
F
F
T
T
F
F
T
: p(a,X) q(a,X)
Modus ponens lets us infer q(a,X) under the substitution set {a/Y,
Match p(a,X) with p(Y,Z) q(Y,Z)
X/Z}
Match q(a,X) with q(W,b) r(W,b)
: q(a,b) r(a,b) We infer r(a,b) under the substitution set {a/W, b/X}
CMP2020M: Lecture 6 – Logic Programming
Unification examples
Unify p(a,X) and p(a,b) b/X
p(a,b) p(a,b) p(a,f(a))
Unify p(a,X) and p(Y,b) a/Y, b/X
Unify p(a,X) and p(Y, f(Y)) a/Y, f(a)/X
Unify p(a,X) and p(X,b) Failure {a/X, b/X } Unify p(a,b) and p(X,X) Failure {a/X, b/X }
CMP2020M: Lecture 6 – Logic Programming
Unification example
Let t1, t2 are two atoms t1 =p(f(X,Y), Z)
t2 =p(Z, f(a, Y))
Let w={f(a, Y)/Z, a/X}
Is w a unifier of the two atoms?
CMP2020M: Lecture 6 – Logic Programming
Unification example: Solution t1 =p(f(X,Y), Z)
t2 =p(Z, f(a, Y))
w={f(a, Y)/Z, a/X}
Is w a unifier of the two atoms?
Solution
w(t1) = w(p(f(X,Y),Z)) = p(f(a, Y), f(a, Y)) w(t2) = w(p(Z, f(a, Y)) = p(f(a, Y), f(a, Y))
Yes
CMP2020M: Lecture 6 – Logic Programming
Exercise 1
t1 = f(a, X), t2 = f(Y, b) and W={b/X, a/Y}.
Is w a unifier of the two atoms?
CMP2020M: Lecture 6 – Logic Programming
Solution of Exercise 1
t1 = f(a, X),
t2 = f(Y, b) and W={b/X, a/Y}.
Is w a unifier of the two atoms?
Solution
W(t1) = W( f(a, X) ) = f(a, b).
W(t2) = W( f(Y, b) ) = f(a, b).
Yes, W is a unifier of these two atoms.
CMP2020M: Lecture 6 – Logic Programming
Exercise 2
t1 =p(f(X,Y), Z),
t2 =p(Z, f(a, Y)) and
W = {f(a, b)/Z, a/X, b/Y}.
Is w a unifier of the two atoms?
CMP2020M: Lecture 6 – Logic Programming
Solution of Exercise 2
t1 =p(f(X,Y), Z),
t2 =p(Z, f(a, Y)) and
W = {f(a, b)/Z, a/X, b/Y}.
Is w a unifier of the two atoms?
Solution
W(t1) = W( p(f(X,Y), Z) ) = p(f(a, b), f(a, b)). W(t2) = W( p(Z, f(a, Y) ) = p(f(a ,b), f(a, b)). Yes, W is a unifier of these two atoms.
CMP2020M: Lecture 6 – Logic Programming
Exercise 3
t1 = p(f(g(X, a), X) , t2 = p(Z, b) and
w={f(g(b, X))/Z, b/X}.
Is w a unifier of the two atoms?
CMP2020M: Lecture 6 – Logic Programming
Solution of Exercise 3
t1 = p(f(g(X, a), X) ,
t2 = p(Z, b) and
w={f(g(b, X))/Z, b/X}.
Is w a unifier of the two atoms?
Solution
W(t1) = W( p(f(g(X, a), X) ) = p(f(g(b, a), b). W(t2) = W( p(Z, b) ) = p(f(g(b, a), b).
Yes, W is a unifier of these two atoms.
CMP2020M: Lecture 6 – Logic Programming
Next lecture: Prolog Programming Prolog Programming
CMP2020M: Lecture 6 – Logic Programming
A little reading
Luger, G.F. and Stubblefield, W.A., Artificial Intelligence – Structures and Strategies for Complex Problem Solving, (Addison-Wesley, 1998).
Chapter 2 (3rd edition) ‘The Predicate Calculus’
take care with alternative editions – chapter numbers differ, and later editions are by Luger only
CMP2020M: Lecture 6 – Logic Programming
Thank you for listening!
CMP2020M: Lecture 6 – Logic Programming