Transcript First-order Logic

DCP 1172
Introduction to Artificial Intelligence
Lecture notes for Ch.8 [AIAM-2nd Ed.]
First-order Logic (FOL)
Chang-Sheng Chen
1
Midterm format
•
•
•
•
•
•
•
Date: 11/19/2004 from 10:15 am – 11:55 am
Location: EC016
Credits: 25% of overall grade
Approx. 5 problems, several questions in each.
Material: everything so far (or, up to Sec. 8.3).
No books (or other material) are allowed.
Duration will be 100 minutes.
DCP1172, Ch.8
2
Question 1 – problems with short answer
• Problem 1-1: Forward search vs. backward search.
Please explain with your example.
• Problem 1-2: Translate the following English sentences
to FOL. …
• Problem 1-3: Please explain the phrase " Truth depends
on interpretation.” by showing with an example.
…
DCP1172, Ch.8
3
Question Type 2: multiple-choices
•
Please choose the topics that are candidates for the
midterm exam ?
(a) Informed search
(b) Logical programming
(c) Constraint Searching Program
(d) Decision making under uncertainty
(e) Probability Reasoning System
Answer: (a), (c)
DCP1172, Ch.8
4
Question Type 3- Matching
• Here are a few things that are related to NCTU and
NTHU, please match the correct ones to each of them.
(a) http://www.nctu.edu.tw
(b) http://www.ust.edu.tw
(c) IPv4 address range, 140.114.*.*
(d) The current administrator of TANet Hsinchu-Miaoli regional
center
(e) The university with the largest number of students in Taiwan
Answer: <NCTU, {(a), (b), (d)} >, <NTHU, {(b),(c)} >
DCP1172, Ch.8
5
Question type 4 – calculation or inference
(with much more detailed involved)
• Problem 4-1: Please find an optimal solution to go from
NCTU to the Hsinchu Railway Station. Here is the related
information …
• the most economic way (e.g., less money)
• the most efficient way (e.g., less time)
...
DCP1172, Ch.8
6
Last time: Logic and Reasoning
• Knowledge Base (KB): contains a set of sentences expressed using a
knowledge representation language
• TELL: operator to add a sentence to the KB
• ASK: operator to query the KB
• Logics are KRLs where conclusions can be drawn
• Syntax
• Semantics
• Entailment: KB |= α iff a is true in all worlds where KB is true
• Inference: KB |–i
procedure i
α,
sentence α can be derived from KB using
• Sound: whenever KB |–i α then KB |= α is true
• Complete: whenever KB |= a then KB |–i a
DCP1172, Ch.8
7
Last Time: Syntax of propositional logic
DCP1172, Ch.8
8
Last Time: Semantics of Propositional logic
DCP1172, Ch.8
9
Last Time: Inference rules for propositional logic
DCP1172, Ch.8
10
This time
• First-order logic
• Syntax
• Semantics
• Wumpus world example
• Ontology (ont = ‘to be’; logica = ‘word’):
• kinds of things one can talk about in the language
DCP1172, Ch.8
11
Why first-order logic?
• We saw that propositional logic is limited because it
only makes the ontological commitment that the
world consists of facts.
• Difficult to represent even simple worlds like the Wumpus
world; e.g.,
“don’t go forward if the Wumpus is in front of you”
takes 64 rules
DCP1172, Ch.8
12
First-order logic (FOL)
• Ontological commitments:
• Objects: wheel, door, body, engine, seat, car,
passenger, driver
• Relations: Inside(car, passenger), Beside(driver,
passenger)
• Functions: ColorOf(car)
• Properties: Color(car), IsOpen(door), IsOn(engine)
• Functions are relations with single value for each
object
DCP1172, Ch.8
13
Semantics
there is a correspondence between
• functions, which return values
• predicates, which are true or false
Function: father_of(Mary) = Bill
Predicate: father_of(Mary, Bill)
DCP1172, Ch.8
14
Examples:
• “One plus two equals three”
Objects:
one, two, three, one plus two
Relations: equals
Properties: -Functions: plus
(“one plus two” is the name of the object obtained
by applying function plus to one and two; three is
another name for this object)
• “Squares neighboring the Wumpus are smelly”
Objects:
Wumpus, square
Relations: neighboring
Properties: smelly
Functions: -DCP1172, Ch.8
15
FOL: Syntax of basic elements
• Constant symbols: 1, 5, A, B, Alex, Manos, …
• Predicate symbols: >, Friend, Student, Colleague, …
• Function symbols: +, sqrt, SchoolOf, TeacherOf, ClassOf, …
• Variables: x, y, z, next, first, last, …
• Connectives: , , , 
• Quantifiers: , 
• Equality: =
DCP1172, Ch.8
16
Syntax of Predicate Logic
• Symbol set
•
•
•
•
•
•
constants
Boolean connectives
variables
functions
predicates (relations)
quantifiers
DCP1172, Ch.8
17
Syntax of Predicate Logic
• Terms: a reference to an object
• variables,
• constants,
• functional expressions (can be arguments to
predicates)
• Examples:
• first([a,b,c]), sq_root(9), sq_root(n), tail([a,b,c])
DCP1172, Ch.8
18
Syntax of Predicate Logic
• Sentences: make claims about objects
• Well-formed formulas, (wffs)
• Atomic Sentences (predicate expressions):
• Loves(John,Mary), Brother(John,Ted)
• Complex Sentences (Atomic Sentences
connected by booleans):
• ¬ Loves(John,Mary)
• Brother(John,Ted) ^ Brother(Ted,John)
• Mother(Alice, John) ⇒ Mother(Alice,Ted)
DCP1172, Ch.8
19
Examples of Terms: Constants, Variables and Functions
• Constants: object constants refer to individuals
• Alan, Sam, R225, R216
• Variables
• PersonX, PersonY, RoomS, RoomT
• Functions
• father_of(PersonX)
• product_of(Number1,Number2)
DCP1172, Ch.8
20
Examples of Predicates and Quantifiers
• Predicates
• In(Alan,R225)
• PartOf(R225,BuildingEC3)
• FatherOf(PersonX,PersonY)
• Quantifiers
• All dogs are mammals.
• Some birds can’t fly.
• 3 birds can’t fly.
DCP1172, Ch.8
21
Semantics
• Referring to individuals
• Jackie
• son-of(Jackie), Sam
• Referring to states of the world
• person(Jackie), female(Jackie)
• mother(Sam, Jackie)
DCP1172, Ch.8
22
FOL: Atomic sentences
AtomicSentence  Predicate(Term, …) | Term = Term
Term  Function(Term, …) | Constant | Variable
• Examples:
• SchoolOf(Manos)
• Colleague(TeacherOf(Alex), TeacherOf(Manos))
• >((+ x y), x)
DCP1172, Ch.8
23
FOL: Complex sentences
Sentence  AtomicSentence
| Sentence Connective Sentence
| Quantifier Variable, … Sentence
|  Sentence
| (Sentence)
• Examples:
• S1  S2, S1  S2, (S1  S2)  S3, S1  S2, S1 S3
• Colleague(Paolo, Maja)  Colleague(Maja, Paolo)
Student(Alex, Paolo)  Teacher(Paolo, Alex)
DCP1172, Ch.8
24
Semantics of atomic sentences
• Sentences in FOL are interpreted with respect to a model
• Model contains objects and relations among them
• Terms: refer to objects (e.g., Door, Alex, StudentOf(Paolo))
• Constant symbols: refer to objects
• Predicate symbols: refer to relations
• Function symbols: refer to functional Relations
• An atomic sentence predicate(term1, …, termn) is true iff the
relation referred to by predicate holds between the objects referred
to by term1, …, termn
DCP1172, Ch.8
25
Example model
• Objects: John, James, Marry, Alex, Dan, Joe, Anne, Rich
• Relation: sets of tuples of objects
{<John, James>, <Marry, Alex>, <Marry, James>, …}
{<Dan, Joe>, <Anne, Marry>, <Marry, Joe>, …}
• E.g.:
Parent relation -- {<John, James>, <Marry, Alex>, <Marry, James>}
then Parent(John, James) is true
Parent(John, Marry) is false
DCP1172, Ch.8
26
Quantifiers
• Expressing sentences about collections of objects
without enumeration (naming individuals)
• E.g., All Trojans are clever
Someone in the class is sleeping
• Universal quantification (for all): 
• Existential quantification (three exists): 
DCP1172, Ch.8
27
Universal quantification (for all): 
 <variables> <sentence>
• “Every one in the DCP1172 class is smart”:
 x In(DCP1172, x)  Smart(x)
•  P corresponds to the conjunction of
instantiations of P
In(DCP1172, Manos)  Smart(Manos) 
In(DCP1172, Dan)  Smart(Dan) 
…
In(DCP1172, Clinton)  Smart(Clinton)
DCP1172, Ch.8
28
Universal quantification (for all): 
•  is a natural connective to use with 
• Common mistake: to use  in conjunction with 
e.g:  x In(DCP1172, x)  Smart(x)
means “every one is in DCP1172 and everyone is smart”
DCP1172, Ch.8
29
Existential quantification (there exists): 
 <variables> <sentence>
• “Someone in the dcp1172 class is smart”:
 x In(dcp1172, x)  Smart(x)
•  P corresponds to the disjunction of
instantiations of P
In(dcp1172, Manos)  Smart(Manos) 
In(dcp1172, Dan)  Smart(Dan) 
…
In(dcp1172, Clinton)  Smart(Clinton)
DCP1172, Ch.8
30
Existential quantification (there exists): 
•  is a natural connective to use with 
• Common mistake: to use  in conjunction with 
e.g:  x In(dcp1172, x)  Smart(x)
is true if there is anyone that is not in dcp1172!
(remember, false  true is valid).
DCP1172, Ch.8
31
Properties of quantifiers
Not all by one
person but
each one at
least by one
Proof?
DCP1172, Ch.8
32
Proof
• In general we want to prove:
 x P(x) <=> ¬  x ¬ P(x)
  x P(x) = ¬(¬( x P(x))) = ¬(¬(P(x1) ^ P(x2) ^ … ^
P(xn)) ) = ¬(¬P(x1) v ¬P(x2) v … v ¬P(xn)) )
  x ¬P(x) = ¬P(x1) v ¬P(x2) v … v ¬P(xn)
 ¬ x ¬P(x) = ¬(¬P(x1) v ¬P(x2) v … v ¬P(xn))
DCP1172, Ch.8
33
Example sentences
• Brothers are siblings
 x, y Brother(x, y)  Sibling(x, y)
• Sibling is transitive
 x, y, z Sibling(x, y)  Sibling(y, z)  Sibling(x, z)
• One’s mother is one’s sibling’s mother
 m, c,d Mother(m, c)  Sibling(c, d)  Mother(m, d)
• A first cousin is a child of a parent’s sibling
 c, d FirstCousin(c, d) 
 p, ps Parent(p, d)  Sibling(p, ps)  Parent(ps, c)
DCP1172, Ch.8
34
Example sentences
• One’s mother is one’s sibling’s mother


 m, c,d Mother(m, c)  Sibling(c, d)  Mother(m, d)
 c,d m Mother(m, c)  Sibling(c, d)  Mother(m, d)
m
Mother of
c
d
sibling
DCP1172, Ch.8
35
Translating English to FOL
• Every gardener likes the sun.
 x gardener(x) => likes(x,Sun)
• You can fool some of the people all of the time.
 x  t (person(x) ^ time(t)) => can-fool(x,t)
DCP1172, Ch.8
36
Translating English to FOL
• You can fool all of the people some of the time.
 x  t (person(x) ^ time(t) =>
can-fool(x,t)
• All purple mushrooms are poisonous.
 x (mushroom(x) ^ purple(x)) =>
poisonous(x)
DCP1172, Ch.8
37
Translating English to FOL…
• No purple mushroom is poisonous.
¬( x) purple(x) ^ mushroom(x) ^ poisonous(x)
or, equivalently,
( x) (mushroom(x) ^ purple(x)) =>
¬poisonous(x)
DCP1172, Ch.8
38
Translating English to FOL…
• There are exactly two purple mushrooms.
( x)( y) mushroom(x) ^ purple(x) ^
mushroom(y) ^ purple(y) ^ ¬(x=y) ^ ( z)
(mushroom(z) ^ purple(z)) => ((x=z) v (y=z))
• Deb is not tall.
¬tall(Deb)
DCP1172, Ch.8
39
Translating English to FOL…
• X is above Y if X is on directly on top of Y or else there is a
pile of one or more other objects directly on top of one
another starting with X and ending with Y.
( x)( y) above(x,y) <=> (on(x,y) v ( z)
(on(x,z) ^ above(z,y)))
DCP1172, Ch.8
40
Equality
DCP1172, Ch.8
41
Higher-order logic?
• First-order logic allows us to quantify over objects
(= the first-order entities that exist in the world).
• Higher-order logic also allows quantification over
relations and functions.
e.g., “two objects are equal iff all properties applied to
them are equivalent”:
 x,y (x=y)  ( p, p(x)  p(y))
• Higher-order logics are more expressive than first-order;
however, so far we have little understanding on how to
effectively reason with DCP1172,
sentences
Ch.8 in higher-order logic. 42
Logical agents for the Wumpus world
Remember: generic knowledge-based agent:
1.
TELL KB what was perceived
Uses a KRL to insert new sentences, representations of facts, into KB
2.
ASK KB what to do.
Uses logical reasoning to examine actions and select best.
DCP1172, Ch.8
43
Using the FOL Knowledge Base
Set of solutions
DCP1172, Ch.8
44
Wumpus world, FOL Knowledge Base
DCP1172, Ch.8
45
Deducing hidden properties
DCP1172, Ch.8
46
Situation calculus
DCP1172, Ch.8
47
Describing actions
May result in
too many
frame axioms
DCP1172, Ch.8
48
Describing actions (cont’d)
DCP1172, Ch.8
49
Planning
DCP1172, Ch.8
50
Generating action sequences
[ ] = empty plan
Recursively continue until it gets to empty plan [ ]
DCP1172, Ch.8
51
Summary
DCP1172, Ch.8
52