Knowledge Representation

First Order Logic

1
Introduction
● Propositional logic is declarative
● Propositional logic allows partial/disjunctive/negated
information
(unlike most data structures and databases)
● 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 “if any student sits an exam they either pass
or fail”.
● Propositional logic is compositional
(meaning of B ^ P is derived from meaning of B and of P)
2
Introduction
● You see that we can convert the sentences into
propositional logic but it is difficult
● Thus, we will use the foundation of propositional
logic and build a more expressive logic

3
Introduction
● 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, …

4
Syntax of FOL: Basic Elements
● Constants KingJohn, 2, NUS,...
● Predicates Brother, >,...
● Functions Sqrt, LeftLegOf,...
● Variables x, y, a, b,...
● Connectives , , , , 
● Equality =
● Quantifiers , 

5
Examples
● King John and Richard the Lion heart are
brothers
Brother(KingJohn,RichardTheLionheart)
● The length of left leg of Richard is greater than
the length of left leg of King John
> (Length(LeftLegOf(Richard)),
Length(LeftLegOf(KingJohn)))

6
Atomic Sentences

7
Atomic Sentences

8
Complex Sentences
● Complex sentences are made from atomic sentences using
connectives:
S, S1  S2, S1  S2, S1  S2, S1  S2,

Example

Sibling(KingJohn,Richard)  Sibling(Richard,KingJohn)

9
Complex Sentences

10
FOL illustrated
● Five objects-
1. Richard the Lionheart
2. Evil King John
3. Left leg of Richard
4. Left leg of John
5. The crown

11
FOL illustrated
● Objects are related with
Relations
● For example, King John and
Richard are related with
Brother relationship
● This relationship can be
denoted by (Richard,John),
(John,Richard)

12
FOL illustrated
● Again, the crown and King
John are related with
OnHead Relationship-
OnHead (Crown,John)
● Brother and OnHead are
binary relations as they
relate couple of objects.

13
FOL illustrated
● Properties are relations that
are unary.
● In this case, Person can be
such property acting
upon both Richard and
John
Person (Richard)
Person (John)
● Again, king can be acted
only upon John
King (John)

14
FOL illustrated
● Certain relationships are
best performed when
expressed as functions.
● Means one object is related
with exactly one object.
Richard -> Richard’s left leg
John -> John’s left leg

15
Universal quantification
● <variables> <sentence>

x P(x)
● Translated into the English language, the expression is understood
as:
● "For all x, P(x) holds",
● "for each x, P(x) holds" or
● “for every x, P(x) holds"
● "All cars have wheels" could be transformed into the
propositional form, x P(x)
● P(x) is the predicate denoting: x has wheels, and
● the universe of discourse is only populated by cars.

16
Universal quantification
● If all the elements in the universe of discourse can
be listed then the universal quantification x P(x)
is equivalent to the conjunction:

P(x1) P(x2) P(x3)  ...  P(xn) .

For example, in the above example of x P(x), if

we knew that there were only 4 cars in our
universe of discourse (c1, c2, c3 and c4) then we
could also translate the statement as:
P(c1)  P(c2)  P(c3)  P(c4)
17
Universal quantification
● Remember, we had five
objects, let us replace them
with a variable x-
1. x ―›Richard the Lionheart
2. x ―› Evil King John
3. x ―› Left leg of Richard
4. x ―› Left leg of John
5. x ―› The crown

18
Universal quantification
● Now, for the quantified
sentence
x King (x)  Person
(x)

Richard is king  Richard is Person

John is king  John is person
Richard’s left leg is king  Richard’s
left leg is person
John’s left leg is king  John’s left leg
is person
The crown is king  the crown is
person

19
Universal quantification
Richard is king  Richard is
Person
John is king  John is person
Richard’s left leg is king 
Richard’s left leg is person
John’s left leg is king  John’s left
leg is person
The crown is king  the crown is
person

Only the second

sentence is correct,
the rest is incorrect

20
Existential quantification
●  <variables> <sentence>

 x P(x)
● Translated into the English language, the expression is understood
as:
● "There exists an x such that P(x)"
● "There is at least one x such that P(x)"
● "Someone loves you" could be transformed into the
propositional form,  x P(x)
● P(x) is the predicate meaning: x loves you,
● The universe of discourse contains (but is not limited
to) all living creatures.

21
Existential quantification
● If all the elements in the universe of discourse can
be listed, then the existential quantification x
P(x) is equivalent to the disjunction:
P(x1) P(x2)  P(x3)  ...  P(xn) .

For example, in the above example of  x P(x), if

we knew that there were only 5 living creatures in
our universe of discourse (say: me, he, she, rex and
fluff), then we could also write the statement as:
P(me)  P(he)  P(she)  P(rex)  P(fluff)

22
Order of application of quantifiers
● When more than one variables are quantified in a wff
such as  y  x P( x, y ), they are applied from the
inside, that is, the one closest to the atomic formula
is applied first.
● Thus  y  x P( x, y ) reads  y [ x P( x, y )],
and we say "there exists a y such that for every x, P(
x,
y ) holds" or "for some y, P( x, y ) holds for every x".

23
Order of application of quantifiers
● The positions of the same type of quantifiers can be
switched without affecting the truth value as long as
there are no quantifiers of the other type between the
ones to be interchanged.
● For example  x   z P(x, y , z) is equivalent to
y  z  y  x P(x, y , z),
 y  x  z P(x, y ,
● z),
It isetc.
the same for the universal quantifier.

24
Order of application of quantifiers
● However, the positions of different types of
quantifiers can not be switched.
● For example  x  y P( x, y ) is not
equivalent to
 y  x P( x, y ).

25
Order of application of quantifiers
● x y x<y

● “for every number x, there is a number y that is greater than x ”

● yx x<y

● “there is a number that is greater than every (any) number ”

26
Properties of quantifiers
● x y is the same as y x

● x y is the same as y x

● x y is not the same as y x

27
Properties of quantifiers
Quantifier duality: each can be expressed using the
other
● x Likes(x,IceCream) is equivalent to
x Likes(x,IceCream)

● x Likes(x,Broccoli) is equivalent to
x Likes(x,Broccoli)

28
Properties of quantifiers
● Equivalences-
 x P is equivalent to x P
 x P is equivalent to x P
 x P is equivalent to x P
 x P is equivalent to x P

29
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 Col. West is a criminal

30
Example knowledge base
... 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,
Owns(Nono,x)
Missile(x)
… 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)
31
West, who is American …
Forward Chaining
• Forward chaining (or forward reasoning) is one of the two main
methods of reasoning when using an inference engine and can
be described logically as repeated application of modus ponens.
• Forward chaining is a popular implementation strategy for
expert systems, business and production rule systems.
• Forward chaining starts with the available data and uses
inference rules to extract more data until a goal is reached.
• An inference engine using forward chaining searches the
inference rules until it finds one where the antecedent (If clause)
is known to be true.
• When such a rule is found, the engine can conclude, or infer, the
consequent (Then clause), resulting in the addition of new
information to its data. Inference engines will iterate through
32
this process until a goal is reached
Forward Chaining
American(x)  Weapon(y)  Sells(x,y,z)  Hostile(z) 
Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(x,America)  Hostile(x)
American(West)
Enemy(Nono,America)

33
Forward Chaining
American(x)  Weapon(y)  Sells(x,y,z)  Hostile(z) 
Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(x,America)  Hostile(x)
American(West)
Enemy(Nono,America)

34
Forward Chaining
American(West)  Weapon(y)  Sells(x,y,z)  Hostile(z)
 Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(x,America)  Hostile(x)
American(West)
Enemy(Nono,America)

35
Forward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(z)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(x,America)  Hostile(x)
American(West)
Enemy(Nono,America)

36
Forward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(z)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(x,America)  Hostile(x)
American(West)
Enemy(Nono,America)

37
Forward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(z)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America) 
Hostile(x) American(West)
Enemy(Nono,America)

38
Forward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(z)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono)
American(West)
Enemy(Nono,America)

39
Forward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(Nono)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono)
American(West)
Enemy(Nono,America)

40
Backward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(Nono)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono)
American(West)
Enemy(Nono,America)

41
Backward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(Nono)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono)
American(West)
Enemy(Nono,America)

42
Backward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(Nono)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono)
American(West)
Enemy(Nono,America)

43
Backward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(Nono)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x) Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono)
American(West)
Enemy(Nono,America)

44
Backward Chaining
American(West)  Weapon(y)  Sells(West,y,z) 
Hostile(Nono)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x) Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono)
American(West)
Enemy(Nono,America)

45
Backward Chaining
American(West)  Weapon(y)  Sells(West,y,Nono) 
Hostile(Nono)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x)  Owns(Nono,x) Sells(West,x,Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono)
American(West)
Enemy(Nono,America)

46
Backward Chaining
American(West)  Weapon(y)  Sells(West,y,Nono) 
Hostile(Nono)  Criminal(x)
Owns(Nono,x)
Missile(x)
Missile(x) 
Owns(Nono,x
)
Sells(West,x,
Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono) 47
…& the Inference
American(West)  Weapon(y)  Sells(West,y,Nono) 
Hostile(Nono)  Criminal(West)
Owns(Nono,x)
Missile(x)
Missile(x) 
Owns(Nono,x
)
Sells(West,x,
Nono)
Missile(x)  Weapon(x)
Enemy(Nono,America)  Hostile(Nono) 48
References
● Artificial Intelligence: A Modern Approach (2nd
Edition)
by Russell and Norvig Chapter 8
● http://www.cs.odu.edu/~toida/nerzic/content
/logic/pred

49