Knowledge Representation Using

Predicate Logic

• Representing Simple Facts in Logic

• Representing Instance and Isa

Relationships

• Computable Functions and

Predicates

• Resolution

• Natural Deduction

Chapter 5 1
Representing Simple Facts in
Logic

1. Marcus was a man

man(Marcus)

2. Marcus was a Pompiean

Pompiean(Marcus)

3. All Pmpien are Romans

νx: Pompiean(x) -> Roman(x)

4. Caesar was a ruler

ruler(Caesar )

5. All Romans were either loyal to

Caesar or hated him
ν x: Roman(x) -> loyalto(x,Caesar) v hate(x,Caesar)

Chapter 5 2
6. Everyone is loyal to someone
ν x:∋ y : loyal(x,y)

7. People only try to assassinate

rulers they are not loyal to
ν x: ν y : person(x) Λ ruler(y) Λ tryassassinate(x,y) -> not
loyalto(x,y)

8. Marcus tried to assassinate Caesar

tryassassinate(Marcus,Caesar)

9. All men are people

ν x: man(x) -> person(x)

Chapter 5 3
not loyalto(Marcus,Caesar)

(7, substitution)

person(Marcus)
ruler(Caesar)
tryassassinate(Marcus,Caesar)

(4)

person(Marcus)
tryassassinate(Marcus,Caesar)

(8)

person(Marcus)

An Attempt to Prove
not loyalto(Marcus,Caesar)

Chapter 5 4
Representing Instance and Isa
Relationships
1. man(Marcus)
2. Pompiean(Marcus)
3. ν x: Pompiean(x) -> Roman(x)
4. ruler(Caesar )
5. ν x: Roman(x) -> loyalto(x,Caesar) ν hate(x,Caesar)

1. instance(Marcus,man)
2. instance(Marcus, Pompiean)
3. ν x: instance(x, Pompiean)->instance(x,Roman)
4. instance(Caesar,ruler)
5. ν x: instance(x, Roman)->loyalto(x,Caesar) ν hate(x,Caesar)

1. instance(Marcus,man)
2. instance(Marcus, Pompiean)
3. isa(Pompiean,Roman)
4. instance(Caesar,ruler)
5. ν x: instance(x, Roman)->loyalto(x,Caesar) hate(x,Caesar)
6. ν x: ν y: ν z: instance(x,y)Λ isa(y,z)-> instance(x,z)

Three Ways of Representing Class

Membership

Chapter 5 5
 Conversion to Clause Form

ν x: [R(x)Λ k(x,M)] ->

[h(x,C) ν ( ν y: ∋ z: h(y,z) -> t(x,y))]

1.Eliminate -> using the fact a->b is eq. to not a ν b

ν x: not [R(x) Λ k(x,M)]
ν [h(x,C) ν ( ν y:not(∋ z: h(y,z))ν t(x,y))]

2.Reduce the scope of each not to a single

term using not (not p) = p, deMorgan's law, and the
standard correspondence between quantifiers
[not ν x:P(x)= ∋ x: not P(x) and
not ∋ x:P(x)= ν x:-P(x)]

ν x: [not R(x) ν not k(x,M)]

ν [h(x,C) ν ( ν y:ν z: not h(y,z)ν t(x,y))]
3.Standardize variables
For example
ν x: P(x) ν ν x:Q(x)
would be converted to
νx: P(x) ν ν y:Q(y)

Chapter 5 6
4.Move all quantifiers to the left of the formula
ν x:ν y: ν z: [ not R(x) ν not k(x,M)]
ν [h(x,C) ν (not h(y,z)ν t(x,y))] (prenex normal
form)

5.Eliminate existential quantifier

∋ y: President(y) can be transformed into the formula
President(S1)
where S1 is a function with no argument that somehow
produces a value that satisfies President

ν x: ∋ y: father-of(y,x) can be transformed into

ν x: father-of(S2(x),x))

6.Drop the prefix

not R(x) ν not k(x,M) ν h(x,C) ν not h(y,z)ν t(x,y)

7.Convert the matrix into a conjunction of disjuncts

You can use the distribution law in this step but
we don have in this example

8.Create a separate clause for each conjunct

We have only one clause

Chapter 5 7
9. Standardize apart the variables in the set of clauses
generated in step 8

Chapter 5 8
Resolution in Propositional Logic

Given Axioms Converted to Clause Form

P P
(P Λ Q) -> R not P ν not Q ν R
(S ν T) -> Q not S ν Q
not T ν Q
T T

A Few Facts in Propositional Logic

-Pν-Qν R -R

-P ν -Q P

-T Q -Q

-T T

Resolution in Propositional Logic

Chapter 5 9
Resolution in Predicate Logic
Axioms in clause form:
1.man(Marcus)
2.Pompiean(Marcus)
3.- Pompiean(x1) ν Roman(x1)
4.ruler(Caesar )
5.- Roman(x2) ν loyalto(x2,Caesar) ν hate(x2,Caesar)
6. loyal(x3,f(x3))
7.- man(x4) ν - ruler(y1) ν - tryassassinate(x4,y1) ν
loyalto(x4,y1)
8.tryassassinate(Marcus,Caesar)
Prove: hate(Marcus,Caesar)
- hate(Marcus,Caesar) 5

3 - Roman(Marcus) ν loyalto(Marcus,Caesar)

Pompiean(Marcus) ν loyalto(Marcus,Caesar) 2

7 loyalto(Marcus,Caesar)

1 - man(Marcus) ν- ruler(Caesar)νtryassassi..(Marcus,Caesar)

- ruler(Caesar) ν - tryassassinate(Marcus,Caesar) 4

- tryassassinate(Marcus,Caesar) 8

A Resolution Proof
Chapter 5 10
Prove: loyalto(Marcus,Caesar)

- loyalto(Marcus,Caesar) 5

3 - Roman(Marcus) ν hate(Marcus,Caesar)

- Pompiean(Marcus) ν hate(Marcus,Caesar) 2

10 hate(Marcus,Caesar)

9 persecute(Caesar,Marcus)

hate(Marcus,Caesar)

An Unsuccessful Attempt at
Resolution

Chapter 5 11
 Given

1. father (x,y) ν - women(x)

2. mother(x,y) ν women(x)
3. mother(Chris, Mary)
4. father(Chris, Bill)

1 2

- father(x,y) ν - mother(x,y) 3

- father(Chris,Mary)

The need to Standardize Variables

1 2

- father(a,y) ν - mother(a,b) 3

- father(Chris,y) 4

Chapter 5 12
Prove:∋x: hate(Marcus,x)Λ ruler(x)
(negate):- ∋ x: hate(Marcus,x) Λ ruler(x)
(clausify): - hate(Marcus,x) ν - ruler(x)

- hate(Marcus,x) ν - ruler(x) hate(Marcus, Paulus)

- ruler(x)

(a)

- hate(Marcus,x) ν - ruler(x) hate(Marcus, Julian)

- ruler(Julian)

(b)

- hate(Marcus,x) ν - ruler(x) hate(Marcus, Caesar)

- ruler(Caesar) ruler(Caesar)

-
(c)
Trying Several Substitution

Chapter 5 13
- ∋ t: died(Marcus,t) = - died(Marcus,t)

- Pompeian(x1) ν died(x1,79) - died(Marcus,t)

79/t,Marcus/x1
- Pompeian(Marcus) Pompeian(Marcus)

(a)

- Pompeian(x1) νdied(x1,79) - died(Marcus,t)νdied(Marcus,t)

79/t,Marcus/x1

- Pompeian(Marcus) ν died(Marcus,t)
Pompeian(Marcus)

died(Marcus,79)

Answer Extraction Using Resolution

Chapter 5 14