程序代写代做代考 AI algorithm prolog CMP2020M Artificial Intelligence

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
PQ
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