Chapters 8 & 9 First-Order Logic: Dr. Daisy Tang

Chapters 8 & 9
First-Order Logic
Dr. Daisy Tang
In which we notice that the world is blessed with objects, some of which are
related to other objects, and in which we endeavor to reason about them.
Outline
 Why FOL?
 Syntax and semantics of FOL
 Using FOL
 Wumpus world in FOL
 Inference in FOL
CS 420: Artificial Intelligence 2

Pros and Cons of Pro. Logic
 Propositional logic is declarative
 Propositional logic allows partial/disjunctive/negated
information
 unlike most data structures and databases, which are domain-
specific
 Propositional logic is compositional

 meaning of B1,1  P1,2 is derived from meaning of B1,1 and of P1,2
 Meaning in propositional logic is context-independent

 (unlike natural language, where meaning depends on context)
 Propositional logic has very limited expressive power

 (unlike natural language)
 E.g., cannot say "pits cause breezes in adjacent squares“
 except by writing one sentence for each square

Our Approach
 Adopt the foundation of propositional logic – a
declarative, compositional semantics that is
context-independent and unambiguous – but with
more expressive power, borrowing ideas from
natural language while avoiding its drawbacks
 Important elements in natural language:

 Objects (squares, pits, wumpuses)
 Relations among objects (is adjacent to, is bigger than) or
unary relations or properties (is red, round)
 Functions (father of, best friend of)
 First-order logic (FOL) is built around the above 3
elements

Identify Objects, Relations, Functions
 One plus two equals three.
 Squares neighboring the wumpus are

smelly.
 Evil King John ruled England in 1200.

Prop. Logic vs. FOL
 Propositional logic assumes that there are facts that either
hold or do not hold
 FOL assumes more: the world consists of objects with certain
relations among them that do or do not hold
 Other special-purpose logics:
 Temporal logic: facts hold at particular times / T,F,U
 E.g., “I am always hungry”, “I will eventually be hungry”
 Higher-order logic: views the relations and functions in FOL as
objects themselves / T,F,U
 Probability theory: facts / degree of belief [0, 1]
 Fuzzy logic: facts with degree of truth [0, 1] / known interval
values
 E.g, “the temperature is very hot, hot, normal, cold, very cold”

First-Order Logic (FOL)
 Whereas propositional logic assumes the world
contains facts
 First-order logic (like natural language) assumes

the world contains
 Objects: people, houses, numbers, colors, baseball games,
wars, …
 Relations: red, round, prime, brother of, bigger than, part
of, comes between, …
 Functions: father of, best friend, one more than, plus, …

Models for FOL: Example

Example
 Five objects
 Two binary
relations
 Three unary
relations
 One unary
function

Syntax of FOL: Basic Elements
 Basic symbols: objects (constant symbols), relations
(predicate symbols), and functions (functional symbols).
 Constants King John, 2, Wumpus...
 Predicates Brother, >,...
 Functions Sqrt, LeftLegOf,...
 Variables x, y, a, b,...
 Connectives , , , , 
 Equality =
 Quantifiers , 
 A legitimate expression of predicate calculus is called well-
formed formula (wff), or simply, sentence

Relations (Predicates)
 A relation is the set of tuples of objects
 Brotherhood relationship {<Richard, John>, <John, Richard>}
 Unary relation, binary relation, …
 Example: set of blocks {a, b, c, d, e}

 The “On” relation includes:
 On = {<a,b>, <b,c>, <d,e>}
 the predicate On(A,B) can be interpreted as <a,b> Є On.
a
b d
c e

Functions
 In English, we use “King John’s left leg” rather than
giving a name to his leg, where we use “function
symbol”
 hat(c) = b
 hat(b) = a a
hat(d) is not defined d

b
c e

Terms and Atomic Sentences
Atomic sentence = predicate (term1,...,termn)
or term1 = term2
Term = function (term1,...,termn)
or constant or variable
 Atomic sentence states facts
 Term refers to an object
 For example:
 Brother(KingJohn,RichardTheLionheart)
 Length(LeftLegOf(Richard))
 Married(Father(Richard), Mother(John))

Composite Sentences
 Complex sentences are made from atomic
sentences using connectives
 S, S1  S2, S1  S2, S1  S2, S1  S2
For example:
Sibling ( John, Richard )  Sibling ( Richard , John)

Brother ( LeftLeg ( Richard ), John)
King ( Richard )  King ( John)
King ( Richard )  King ( John)

Intended Interpretation
 The semantics relate sentences to models to
determine truth
 Interpretation specifies exactly which objects,
relations and functions are referred to by the
constant, predicate, and function symbols
 Richard refers to Richard the Lionheart and John refers to
the evil King John
 Brother refers to the brotherhood relation; Crown refer to
the set of objects that are crowns
 LeftLeg refers to the “left leg” function
 There are many other possible interpretations that relate
symbols to model; Richard refers to the crown
 If there are 5 objects in the model, how many possible
interpretations are there for two symbols Richard and John?

Intended Interpretation (Con’t)
 The truth of any sentence is determined by a model
and an interpretation for the sentence’s model
 The entailment and validity are defined in terms of

all possible models and all possible interpretations
 The number of domain elements in each model may

be unbounded; thus the number of possible models
is unbounded
 Checking entailment by enumeration of all possible

models is NOT doable for FOL

In General
 Sentences are true with respect to a model and an
interpretation
 Model contains objects (domain elements) and
relations among them
 Interpretation specifies referents for
constant symbols → objects
predicate symbols → relations
function symbols → functional relations
 Once we have a logic that allows objects, it is

natural to want to express properties of entire
collections of objects, instead of enumerating the
objects by name  Quantifiers

Universal Quantifier
 Universal quantification ()
 “All kings are person”: x King(x)  Person(x)
 For all x, if x is a king, then x is a person
 In general, x P is true in a given model under a given

interpretation if P is true in all possible extended
interpretations
 In the above example, x could be one of the following:

 Richard, John, Richard’s left leg, John’s left leg, Crown
 5 extended interpretations
 A common mistake: x (King(x) ^ Person(x))

Existential Quantifier
 Existential quantification ()
 x Crown(x)  OnHead(x, John)
 There is an x such that x is a crown and x is on the John’s
head
 In general, x P is true in a given model under a given

interpretation if P is true in at least one extended
interpretation that assigns x to a domain element
 In the above example, “Crown(crown) 

OnHead(crown, John)” is true
 Common mistake: x Crown(x)  OnHead(x, John)

Nested Quantifiers
 Nested quantifiers
 x y [Brother(x, y)  Sibling(x, y)]
 x y Loves(x, y)
 y x Loves(x, y)
 x y is not the same as y x
 The order of quantification is important
 Quantifier duality: each can be expressed

using the other
 x Likes(x,IceCream) x Likes(x,IceCream)
 x Likes(x,Broccoli) x Likes(x,Broccoli)

Equality
 term1 = term2 is true under a given interpretation if
and only if term1 and term2 refer to the same object
 Can be used to state facts about a given function
 E.g., Father(John) = Henry
 Can be used with negation to insist that two terms are not
the same object
 E.g., definition of Sibling in terms of Parent:
 x,y Sibling(x,y)  [(x = y)  m,f  (m = f) 
Parent(m,x)  Parent(f,x)  Parent(m,y)  Parent(f,y)]

Using FOL
 Sentences are added to a KB using TELL, which is called
assertions
 Questions asked using ASK are called queries
 Any query that is logically entailed by the KB should be
answered affirmatively
 The standard form for an answer is a substitution or binding
list, which is a set of variable/term pairs
TELL( KB, King ( John))

TELL( KB, x King ( x)  Person( x))
ASK ( KB, King ( John))
ASK ( KB, Person( John))
ASK ( KB, x Person( x)) answer :{ x / John}

Example: The Kinship Domain
 An example KB includes things like:
 Fact:
 “Elizabeth is the mother of Charles”
 “Charles is the father of William”
 Rules:
 One’s grandmother is the mother of one’s parent”
 Object: people
 Unary predicate: Male, Female
 Binary predicate: Son, Spouse, Wife, Husband,
Grandparent, Grandchild, Cousin, Aunt, and Uncle
 Function: Mother, Father

Example: The Kinship Domain
One ' s mom is one ' s female parent.
m, c Mother (c)  m  Female( m)  Parent ( m, c)
One ' s husband is one ' s male spouse.
w, h Husband (h, w)  Male( h)  Spouse(h, w)
Paren and child are inverse relations.
p, c Parent ( p, c)  Child (c, p)
A grandparent is a parent of one ' s parent.
g , c Grandparent ( g , c)  p Parent ( g , p)  Parent ( p, c)
Practice:
Male and female are disjoint categories
A sibling is another child of one’s parents

Answer
 Male and female are disjoint categories:
 x Male(x)  Female(x)
 A sibling is another child of one’s parent:

 x,y Sibling(x, y)  x≠y ^ p Parent(p,x) ^
Parent(p, y)

The Wumpus World
 A percept is a binary predicate:
 Percept([Stench, Breeze, Glitter, None, None], 5)
 Actions are logical terms:
 Turn(Right), Turn(Left), Forward, Shoot, Grab, Release, Climb
 Query:
 a BestAction(a, 5)
 Answer: {a/Grab}
 Perception: percept implies facts:
  t, s, b, m, c Percept([s, b, Glitter, m, c], t)  Glitter(t)
 Reflex behavior:
  t Glitter(t)  BestAction(Grab, t)

The Wumpus World
 The Environment:
 Objects: squares, pits and the wumpus
 x,y,a,b Adjacent([x,y],[a,b]) 
[a,b]  {[x+1,y], [x-1,y],[x,y+1],[x,y-1]}
 A unary predicate Pit(x)
 s,t At(Agent,s,t)  Breeze(t)  Breezy(s), the agent infers
properties of the square from properties of its current

percept
 Breezy() has no time argument
 Having discovered which places are breezy or smelly, not
breezy or not smelly, the agent can deduce where the pits
are and where the wumpus is

Diagnostic Rules
 Diagnostic rule: lead from observed effects
to hidden causes
 If the square is breezy then adjacent square(s)
must contain a pit
s Breezy(s)  r Adjacent(r,s)  Pit(r)
 If the square is not breezy, no adjacent square
contains a pit
s Breezy(s)   (r Adjacent(r,s)  Pit(r))
 Combining both:
s Breezy(s)  r Adjacent(r,s)  Pit(r)

Causal Rules
 Causal rule: some hidden property of the
world causes certain percept to be
generated
 A pit causes all adjacent squares to be breezy
r Pit(r)  [s Adjacent(r,s)  Breezy(s)]
 If all squares adjacent to a given square are
pitless, the square will not be breezy
s [r [Adjacent(r,s)  Pit(r)]  Breezy(s)

Summary
 First-order logic:
 objects and relations are semantic primitives
 syntax: constants, functions, predicates,
equality, quantifiers
 Increased expressive power: sufficient to

define wumpus world

Exercises
 Represent the following sentences in FOL
 Some students took French in spring 2001.
 Every student who takes French passes it.
 Only one student took Greek in spring 2001.
 The best score in Greek is always higher than the best score in
French.
 Let the basic vocabulary be as follows:

Inference in FOL
 Two ideas:
 convert the KB to propositional logic and use
propositional inference
 a shortcut that manipulates on first-order
sentences directly (resolution, will not be
introduced here)

Universal Instantiation
 Universal instantiation
 infer any sentence by substituting a ground term
(a term without variables) for the variable
 v α
Subst({v/g}, α)
 for any variable v and ground term g
 Examples
 x King(x)  Greedy(x)  Evil(x) yields:
 King(John)  Greedy(John)  Evil(John)
 King(Richard)  Greedy(Richard)  Evil(Richard)
 King(Father(John))  Greedy(Father(John)) 
Evil(Father(John))

Existential Instantiation
 Existential instantiation
 For any sentence α, variable v, and constant symbol k that does
NOT appear elsewhere in the knowledge base, replace v with k
v α
Subst({v/k}, α)
 E.g., x Crown(x)  OnHead(x, John) yields:
Crown(C1)  OnHead(C1, John)
provided C1 is a new constant symbol, called a Skolem

constant

Exercise
 Suppose a knowledge base contains just one
sentence, x AsHighAs(x, Everest). Which of the
following are legitimate results of applying
Existential Instantiation?
 AsHighAs(Everest, Everest)
 AsHighAs(Kilimanjaro, Everest)
 AsHighAs(Kilimajaro, Everest) and AsHighAs(BenNevis,
Everest)

Reduction to Propositional Inference
Suppose the KB contains just the following:
x King(x)  Greedy(x)  Evil(x)
King(John)
Greedy(John)
Brother(Richard,John)
 Instantiating the universal sentence in all possible ways, we have:

King(John)  Greedy(John)  Evil(John)
King(Richard)  Greedy(Richard)  Evil(Richard)
King(John)
Greedy(John)
 The new KB is propositionalized: proposition symbols are

 King(John), Greedy(John), Evil(John), King(Richard), etc.
 What conclusion can you get?

Reduction Cont’d.
 Every FOL KB can be propositionalized so as to
preserve entailment
 (A ground sentence is entailed by new KB iff

entailed by original KB)
 Idea: propositionalize KB and query, apply

resolution, return result

Problems with Propositionalization
 Propositionalization seems to generate lots of irrelevant
sentences
 E.g., from:
King(John)
y Greedy(y)
 It seems obvious that Evil(John) is true, but

propositionalization produces lots of facts such as
Greedy(Richard) that are irrelevant
 With p k-ary predicates and n constants, there are p·nk

instantiations

Problems with Propositionalization
 When the KB includes a function symbol, the set of
possible ground term substitutions is infinite
 Father(Father(…(John)…))
 Theorem:
 If a sentence is entailed by the original, first-order KB, then
there is a proof involving just a finite subset of the
propositionalized KB
 First instantiation with constant symbols
 Then terms with depth 1 (Father(John))
 Then terms with depth 2 …
 Until the sentence is entailed

Unification and Lifting
Propositionalization approach is
rather inefficient
A First-Order Inference Rule
 If there is some substitution θ that makes the premise of the
implication identical to sentences already in the KB, then we
assert the conclusion of the implication, after applying θ

King(John)
What’s θ here?
Greedy(John)
 Sometimes, we need to do is find a substitution θ both for the

variables in the implication and in the sentence to be matched
King(John)
y Greedy(y) What’s θ here?

Generalized Modus Ponens
 For atomic sentences pi, pi’, and q, where there is a
substitution θ such that Subst(θ, pi’) = Subst(θ, pi), for all i:
p1', p2', … , pn', ( p1  p2  …  pn q)

Subst(θ, q)
p1' is King(John) p1 is King(x)

p2' is Greedy(y) p2 is Greedy(x)
θ is {x/John,y/John} q is Evil(x)
Subst(θ, q) is Evil(John)
Can be used with KB of definite clauses (exactly one positive literal)

Unification
 GMP is a lifted version of Modus Ponens – raises
Modus Ponens from propositional to first-order logic
 What’s the key advantage of GMP over

propositionalization?
 Lifted inference rules require finding substitutions

that make different logical expressions look
identical
 This process is called unification and is a key

component of all first-order inference algorithms

Unification
 The unify algorithm takes two sentences and
returns a unifier for them if one exists:
 UNIFY(p, q) = θ where Subst(θ, p) = Subst(θ, q)
p q θ
Knows(John,x) Knows(John,Jane)
Knows(John,x) Knows(y,OJ)
Knows(John,x) Knows(y,Mother(y))
Knows(John,x) Knows(x,OJ)

Unification
p q θ
Knows(John,x) Knows(John,Jane) {x/Jane}
Knows(John,x) Knows(y,OJ)

Unification
p q θ
Knows(John,x) Knows(y,OJ) {x/OJ,y/John}

Unification
p q θ
Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)}

Unification
p q θ
Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)}
Knows(John,x) Knows(x,OJ) {fail}
Standardizing apart: renaming variables to avoid name clashes

UNIFY(Knows(John, x), Knows(z, OJ)) = {x/OJ, z/John}

Unification Contd.
 To unify Knows(John, x) and Knows(y, z),
θ = { y/John, x/z } or θ = { y/John, x/John, z/John}
 The first unifier is more general than the second
 There is a single most general unifier (MGU)
 MGU = {y/John, x/z}

Exercise
 For each pair of atomic sentences, give the
most general unifier if it exists:
 P(A, B, B), P(x, y, z)
 Q(y, G(A, B)), Q(G(x, x), y)
 Older(Father(y), y), Older(Father(x), John)
 Knows(Father(y), y), Knows(x, x)

Example Knowledge Base
 The law says that it is a crime for an American to sell weapons
to hostile nations. The country Nono, an enemy of America,
has some missiles, and all of its missiles were sold to it by
Colonel West, who is American.
 Prove that Colonel West is a criminal
American(x): x is an American
Weapon(x): x is a weapon
Hostile(x): x is a hostile nation
Criminal(x): x is a criminal
Missile(x): x is a missile
Owns(x, y): x owns y
Sells(x, y, z): x sells y to z
Enemy(x, y): x is an enemy of y
Constants: America, Nono, West

Example Knowledge Base
First-Order Definite Clauses
... it is a crime for an American to sell weapons to hostile nations:
American(x)  Weapon(y)  Sells(x,y,z)  Hostile(z)  Criminal(x)
Nono … has some missiles, i.e., x Owns(Nono,x)  Missile(x):
Owns(Nono,M1) and Missile(M1)
… all of its missiles were sold to it by Colonel West
Missile(x)  Owns(Nono, x)  Sells(West, x,Nono)
Missiles are weapons:
Missile(x)  Weapon(x)
An enemy of America counts as "hostile“:
Enemy(x, America)  Hostile(x)
West, who is American …
American(West)
The country Nono, an enemy of America …
Enemy(Nono,America)

Forward Chaining
 Starting from known facts, it triggers all the rules
whose premises are satisfied, adding their
conclusions to the known facts. This process will
continue until query is answered.
 When a new fact P is added to the KB:

 For each rule such that P unifies with a premise
 if the other premises are already known
 then add the conclusion to the KB and continue chaining
 Forward chaining is data-driven:
 inferring properties and categories from percepts

Forward Chaining Algorithm

Forward Chaining Proof



Analysis of Forward Chaining
 A fixed point of the inference process can be
reached
 The algorithm is sound and complete
 Its efficiency can be improved

FC Algorithm Analysis

Sources of Complexity
 1. “Inner loop” involves finding all possible unifiers
such that the premise of a rule unifies with facts in
the KB
 Often called “pattern matching”, very expensive
 2. The algorithm rechecks every rule on every

iteration to see whether its premises are met
 3. It might generate many facts that are irrelevant

to the goal

Matching Rules Against Known Facts
 Consider a rule:
 Owns(Nono, x)Missile(x)  Sells(West, x, Nono)
 We find all the objects owned by Nono in
constant time per object;
 Then, for each object, we check whether it’s a
missile.
 If more objects and very few missiles 
inefficient
 Conjunct ordering problem: NP-hard
 Heuristics?

Pattern Matching and CSP
 The most constrained variable heuristic used for CSPs would suggest
ordering the conjuncts to look for missiles first if there are fewer
missiles than objects owned by Nono
 We can actually express every finite-domain CSP as a single definite
clause together with some associated ground facts
Diff(wa, nt)  Diff(wa, sa) 

Diff(nt, q)  Diff(nt, sa) 
Diff(nsw, v)  Diff(nsw, v) 
Diff(v, sa)  Colorable()
Diff(R, B) Diff(R, G)
Diff(G, R) Diff(G, B)
Diff(B, R) Diff(B, G)

Incremental Forward Chaining
 Observation:
 Every new fact inferred on iteration t must be derived from
at least one new fact inferred on iteration t-1
 Modification:
 At iteration t, we check a rule only if its premise includes a
conjunct pi that unifies with a fact pi’ newly inferred at
iteration t-1
 Many real systems operate in an “update” mode wherein
forward chaining occurs in response to each new fact that is
TOLD to the system

Irrelevant Facts
 FC makes all allowable inferences based on
known facts, even if they are irrelevant to
the goal at hand
 Similar to FC in propositional context
 Solution?

Backward Chaining
 p1  p2 … pn  q
 When a query q is examined:
 if a matching fact q' is known, return the unifier
 for each rule whose consequent q' matches q
 attempt to prove each premise of the rule by
backward chaining
 Backward chaining is the basis for “logic

programming,” e.g., Prolog

Backward Chaining Algorithm

Backward Chaining Example







Analysis of Backward Chaining
 Depth-first search: space is linear in size of
proof
 Repeated states and incompleteness
 can be fixed by checking current goal against
every goal on stack
 Inefficient due to repeated subgoals
 can be fixed by caching previous results
 Widely used in logic programming

Logic Programming
 Prolog
 Lisp
 Introduced in CS 352 (symbolic programming)
 http://www.cs.toronto.edu/~sheila/384/w11/simple
-prolog-examples.html

Exercise
 Write down logical representations for the following
sentences, suitable for use with Generalized Modus
Ponens
 Horses, cows, and pigs are mammals.
 An offspring of a horse is a horse.
 Bluebeard is a horse.
 Bluebeard is Charlie’s parent.
 Offspring and parent are inverse relations.
 Draw the proof tree generated by exhaustive backward-

chaining algorithm for the query h Horse(h), where
clauses are matched in the order given.

Chapters 8 & 9 First-Order Logic: Dr. Daisy Tang

Uploaded by

Copyright:

Available Formats

Chapters 8 & 9 First-Order Logic: Dr. Daisy Tang

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapters 8 & 9 First-Order Logic: Dr. Daisy Tang

Uploaded by

Copyright:

Available Formats

Chapters 8 & 9

Dr. Daisy Tang

CS 420: Artificial Intelligence 2

 Propositional logic is compositional

 Meaning in propositional logic is context-independent

 Propositional logic has very limited expressive power

CS 420: Artificial Intelligence 3

 Important elements in natural language:

CS 420: Artificial Intelligence 4

 One plus two equals three.

 Squares neighboring the wumpus are

 Evil King John ruled England in 1200.

CS 420: Artificial Intelligence 5

CS 420: Artificial Intelligence 6

 First-order logic (like natural language) assumes

CS 420: Artificial Intelligence 7

CS 420: Artificial Intelligence 8

CS 420: Artificial Intelligence 9

CS 420: Artificial Intelligence 10

 Example: set of blocks {a, b, c, d, e}

CS 420: Artificial Intelligence 11

CS 420: Artificial Intelligence 12

 Term refers to an object

CS 420: Artificial Intelligence 13

Sibling ( John, Richard )  Sibling ( Richard , John)

CS 420: Artificial Intelligence 14

CS 420: Artificial Intelligence 15

 The entailment and validity are defined in terms of

 The number of domain elements in each model may

 Checking entailment by enumeration of all possible

CS 420: Artificial Intelligence 16

 Once we have a logic that allows objects, it is

CS 420: Artificial Intelligence 17

 In general, x P is true in a given model under a given

 In the above example, x could be one of the following:

 A common mistake: x (King(x) ^ Person(x))

CS 420: Artificial Intelligence 18

 In general, x P is true in a given model under a given

 In the above example, “Crown(crown) 

 Common mistake: x Crown(x)  OnHead(x, John)

CS 420: Artificial Intelligence 19

 Quantifier duality: each can be expressed

CS 420: Artificial Intelligence 20

CS 420: Artificial Intelligence 21

TELL( KB, King ( John))

CS 420: Artificial Intelligence 22

CS 420: Artificial Intelligence 23

CS 420: Artificial Intelligence 24

 A sibling is another child of one’s parent:

CS 420: Artificial Intelligence 25

CS 420: Artificial Intelligence 26

 s,t At(Agent,s,t)  Breeze(t)  Breezy(s), the agent infers

properties of the square from properties of its current

 Having discovered which places are breezy or smelly, not

CS 420: Artificial Intelligence 27

CS 420: Artificial Intelligence 28

CS 420: Artificial Intelligence 29

 Increased expressive power: sufficient to

CS 420: Artificial Intelligence 30