Chapter Four

Knowledge and Reasoning

1
 Outlines
o Knowledge Representation
o Knowledge base agent
o Knowledge engineering
o Formal Logic
o Propositional Logic
o Quantification

2
 Knowledge Representation (KR)
Knowledge: What and Why?
o Knowledge includes facts about the real world entities
and the relationship between them
o Knowledge-based Systems (KBSs) are useless without
the ability to represent knowledge.

Why Knowledge is important ?

o We are living in complex environment where there are:
– Many actors, strong competitors, and high turnover
o It enables to:
o Automate reasoning , Discover new facts, Deduce
new facts that follow from the KB, and Answer users
queries
o Make quality decisions - select courses of actions,
etc.
o Hence, there is a need to represent knowledge to
3
ease the development of an intelligent system.
 Knowledge-based Agent (KBA)
o Agents can be seen as knowing about their world,
and reasoning about their possible courses of
action.
o KBA begins with some knowledge of the world
and of its actions.
– It uses logical reasoning to maintain a description of
the world as new percepts arrive
– Learn new facts/knowledge that are inferred and
unseen by current percepts
– Deduce a course of actions that will achieve its goals

o One can also design an autonomous agent that

– learns from experience and construct knowledge
with less human interventions 4
 Knowledge engineering (KE)
o KE is the process of building a knowledge base through
extracting the knowledge from the human expert.
o Knowledge engineering is the process of
–Extracting the knowledge from the human expert.
–Choose knowledge representation formalism
–Choose reasoning and problem solving strategy.
o A knowledge engineer is someone who investigates a
particular domain, determines what concepts are
important in that domain, and creates a formal
representation of the objects and relations in the
domain.
–A KE has to decide what objects and relations are worth
representing, and which relations hold among which objects
Knowledge Knowledge
acquisition Representation Knowledge
(Extract knowledge (choose KR Method & Base
of Human Expert) reasoning strategy)
5
 The two main tasks of KE
o Knowledge acquisition: The knowledge engineer
interview the real human experts to be educated
about the domain and to elicit the required
knowledge, in a process called knowledge acquisition
o Knowledge Representation techniques such as
logic are a powerful tool for KR and reasoning.
However, such techniques consists of only the syntax,
semantics and proof theory.
–KR techniques do not offer any guidance as to what facts should
be expressed, nor what vocabulary should be used to express
them
o Knowledge base is used to store a set of facts and
rules about the domain expressed in a suitable
representation language
–Each individual representation are called sentences
–Sentences are expressed in a (formal) knowledge 6
 Knowledge Representation & Reasoning
o Knowledge Representation (KR): express
knowledge explicitly in a computer-tractable
way such that the agent can reason out.
o Parts of KR language:
–Syntax of a language: describes the possible
configuration to form sentences. E.g.: if x & y denote
numbers, then x > y is a sentence about numbers
–Semantics: determines the facts in the world to which
the sentences refer. E.g.: x > y is false when y is
greater than x and true otherwise
o Reasoning: is the process of constructing new
sentences from existing facts in the KB.
–Proper reasoning ensures that the new configuration
represent facts that actually follow from the facts in the
7
KB.
 Logic as KR
o A Logic is a formal language in which knowledge
can be represented such that conclusions can
easily be drawn.
–It is a declarative language to assert sentences and
deduce from sentences.
o Components of a formal logic include syntax,
semantics, reasoning and inference mechanism .
–Syntax: what expressions/structures are allowed in
the language. Describes how to make sentences
E.g. mycar (red) is ok, but mycar(grey or green) is not.
–Semantics: express what sentences mean, in terms
of a mapping to real world.
•The meaning of a sentence is not intrinsic to that sentence.
Semantics relate sentences to reality.
•E.g. mycar (red) means that my car is red.
–Proof Theory: It is a means of carrying our reasoning
8
using a set of rules. It helps to draw new conclusions
 Why formal languages (Logic) ?
o An obvious way of expressing or representing facts
and thoughts is by writing them in a natural
language such as English, Amharic, etc. However ,
– The meaning of a sentence depends on the sentence
itself and on the context on which the sentence was
spoken
e.g. Look!
– Natural languages exhibit ambiguity.
E.g. small dogs and cats.
– A single sentence can usually be interpreted in more
than one way, possibly inhibiting reasoning. Consider
English sentences like:
“The boy saw a girl with a telescope”
“Our shoes are guaranteed to give you a fit”
o Ambiguity makes reasoning difficult and incomplete .
– Hence we need formal languages to express facts and9
concepts in an unambiguous and well-defined way.
 Propositional logic
o A simple language useful for showing key ideas
and definitions
o Syntax: PL allows facts about the world to be
represented as sentences formed from:
 Logical constants: True, False
 Proposition symbols (P, Q, R, …) are used to
represent facts about the world: e.g.: P = "It is hot“,
Q = "It is humid“, R = "It is raining“
 Logical connectives: not (), and (), or (), implies
(), is equivalent, if and only if ().
 Precedence order from highest to lowest is: , ,,, 
e.g. The sentence P v Q  R  S is equivalent to
[(P) v (Q  R)]  S
 Parenthesis ( ): Used for grouping sentences and to
specify order of precedence 10
 Propositional logic (PL) sentences
o A sentence is made by linking prepositional
symbols together using logical connectives.
– There are atomic and complex sentences.
– Atomic sentences consist of propositional symbol
(e.g. P, Q, TRUE, FALSE)
– Complex sentences are combined by using
connectives or parenthesis:
– while S and T are atomic sentences, S  T, (S  T), (S 
T), (S  T), and (S  T) are complex sentences.

Examples: Given the following sentences

about the “weather problem” convert them
into PL sentences:
Q
• “It is humid.”: QP
• “If it is humid, then it is hot” : (P  Q)  R11
• “If it is hot and humid, then it is raining”:
 Example
Convert the following English sentences to Propositional
logic. Let:
A = Lectures are active
R = Text is readable
P = Kebede will pass the exam
o the lectures are not active:
A
o the lectures are active and the text is readable:
AR
o either the lectures are active or the text is readable:
AVR
o if the lectures are active, then the text is not
readable:
AR
o the lectures are active if and only if the text is
readable: AR

 (R
o if the lectures are active, then ifAthe textisP )
not 12
readable, Kebede will not pass the exam:
 Terminology
o Valid sentence: A sentence is valid sentence
or tautology if and only if it is True under all
possible interpretations in all possible worlds.
Example: “It’s raining or it’s not raining.” (R  R).
o Satisfiable: A sentence is satisfiable if and
only if there is some interpretations in some
world for which the sentence is True.
Example: “It is raining or it is humid”. R v Q, R
o Unsatisfiable: A sentence is unsatisfiable
(inconsistent sentence or self- contradiction) if
and only if it is not satisfiable, i.e. a sentence
that is False under all interpretations. The world
is never like what it describes.
Example: “It’s raining and it's not raining.” R  R 13
 Cont’d
o Entailment: mirrors the relation of one
fact following from another.
– New sentences are generated that are
necessarily true, given that the old
sentences are true.
– KB entails α (KB |= α) if and only if the
conclusion α is true in every logically
possible worlds in which all the premises in
KB are true.
o Derivation:
– KB |- Q, Q is derived from KB if there is a
proof consisting of a sequence of valid
inference steps starting from the premises
in KB and resulting in Q 14
 Proof: Inference Rules
o Inference is used to create new sentences that
logically follow from a given set of sentences in
the KB.
–It captures patterns of inferences that occur
over & over again.
–Once a rule is established, it can be used to
make inferences without going through the
tedious process of building truth tables
o Given set of inference rules (I) and set of
sentences (KB); Inference is the process of
applying successive inference rules from I to KB,
each rule inferring new facts and adding its
conclusion to KB
–Example: Modus Ponens: {  ,  } |- 
–There are different inference rules (including
logical equivalence) that can be used for 15

proofing and reasoning purpose.

 Logical equivalence
•Two sentences are logically equivalent iff they are true
in same models
pνq≡qνp Commutativity of disjunction
pΛq≡qΛp Commutativity of conjunction
(p Λ q) Λ r ≡ p Λ (q Λ r) Associativity of conjunction
(p ν q) ν r ≡ p ν (q ν r) Associativity of disjunction
( ( p) ≡ p Double Negation elimination
pq≡qp contraposition
pq≡pνq implication elimination
(p ν q) ≡ ( p Λ q) De-Morgan
(p Λ q) ≡ ( p ν  q) De-Morgan
(p  q) ≡ (p q) Λ (q  p) Biconditional elimination
p Λ (q ν r) ≡ (p Λ q) ν (p Λ r) Distributive of Λ over ν
p ν (q Λ r) ≡ (p ν q) Λ (p ν r) Distributive of ν over Λ 16
 Inference Rules
RULE PREMISE CONCLUSION
Modus Ponens A, A  B B
Modus Tolens B, A  B A
And Elimination AB A
And Introduction A, B AB
Or Introduction A A1  A2 …  An
Double Negation  A A
Elimination
Unit Resolution A  B, B A
Resolution A  B, B  C AC
Hypothetical Syllogism PQ, QR PR
o In the case of modus ponens, if A is true and A  B is true, then conclude B is true.
17
 Example
o Example 1: Given the following facts and rules
that relates facts; What can we say about the
weather condition?
– It is humid:
– If it is humid, then it is hot :
– If it is hot and humid, then it is raining:
1.Q Premise
2.Q  P Premise
3.(P  Q)  R Premise
4.P using Modes Ponens (1 & 2)
5.P  Q using AND introduction (1 & 4)
6.R using Modes Ponens (3 & 5)

o Example 2: Is the following statements valid?

Proof.
A  B  C 18

BC
 Two important properties of inference
Completeness: If KB |= Q then KB |- Q
oA logic is complete if it is capable of proving all
consequences that can be represented in it.
– If Q is entailed by a set of sentences in KB, then Q can
be derived from KB using inference rules.
– Hence, inference produces all entailments, or all valid
sentences can be proved from the premises.
oA set of inference rules is complete if every
entailed sentences can be obtained by applying
some finite
succession of these rules
– Modus ponens alone is not complete. For example,
what can we concluded
A from the statement:
•[A  B & B] ?
A
•[A  B & B] ? 19
•[A  B & BC]???
 Cont’d
Soundness: If KB |- Q then KB |= Q
•A logic is sound if it preserves truth (i.e. if a set of
premises are all true, any conclusion drawn from
those premises must also be true).
– If Q is derived from a set of sentences in the KB using a
given set of rules of inference, then Q is entailed by KB.
– Hence, inference produces only real entailments, or any
sentence that follows deductively from the premises is
valid.
– We can proof soundness by constructing the truth
table.
•An inference rule is sound if it generates only
entailed sentences
• All inference rules previously given are sound
– A rule is sound if its conclusion is true whenever the


premise is true.
E.g. modus ponens: {   , } 


• The following rule: {   , }  is unsound, 20

 Example
[Link]-OK  Bulbs-OK  Headlights-Work
[Link]-OK  Starter-OK  Empty-Gas-Tank 
Engine-Starts
[Link]-Starts  Flat-Tire  Car-OK
[Link]-Work
[Link]-OK
[Link]-OK
7.Empty-Gas-Tank
8.Car-OK Proof
9. Battery-OK  Starter-OK  (5+6)
Proof: Flat-Tire 10. Battery-OK  Starter-OK  Empty-
Gas-Tank  (9+7)
11. Engine-Starts  (2+10)
12. Engine-Starts  Flat-Tire  (3+8)
13. Flat-Tire  (11+12) 21
 Example
Construct formal proof of validity for the following
problem:
If the investigation continues, then new evidence
is brought to light. If new evidence is brought to
light, then several leading citizens are
implicated. If several leading citizens are
implicated, then the newspapers stop publicizing
the case. If continuation of the investigation
implies that the newspapers stop publicizing the
case, then the bringing to light of new evidence
implies that the investigation continues. The
investigation does not continue. Therefore, new
evidence is not brought to light.
Represent using PL and proof the conclusion that
“new evidence is not brought to light”. 22
 Solution
Let
C: The investigation continues.
B: New evidence is brought to light.
I: Several leading citizens are implicated.
S: The newspapers stop publicizing the case.
1. CB
2. BI
3. IS
4. (C  S)  (B  C)
5. C
6. CI 1,2 (Hypothetical Syllogism)
7. CS 6,3 (Hypothetical
Syllogism)
8. B  C 7,4 (Modus Ponens)
9. B 8,5 (Modus Tollens) 23
 Exercise
Let p stand for the proposition “I bought a
lottery ticket” and q for “I won the jackpot”.
• Express the following as natural English
sentences:
(a) ¬p
(b) p  q
(c) p  q
(d) p  q
(e) ¬p  ¬q
(f) ¬p  (p  q)

24
 Propositional logic is a weak language
o PL cannot handle even a domain with small
worlds. The problem is that there are just too
many propositions to handle since it only has one
representational device: the proposition
o In PL world consists of just facts. It is hard to :
–Identify individuals: E.g., Mary, 3
–Describe properties of (or relations between)
individuals. E.g. Belete is taller than Gelaw
–Generalize for a given universe. E.g., all triangles
have 3 sides

o Example: Prove that “my dog Fido is Nice, given

that “all dogs are Nice.”
–This requires to get at the structure and
meanings of statements (where FOL is useful).
25
 First Order Logic
o First-Order Logic (FOL) is expressive enough
to concisely represent any kind of situation
that are expressed in natural language.
–FOL represents objects and relations
between objects, variables, and quantifiers
in addition to propositions
Every elephant is gray:
 x (elephant(x) → gray(x))

There is a white alligator:

 x (alligator(X) ^ white(X))

26
 Syntax of FOL
o Constants symbol
– names (like Jonas, Kebede, …), numbers (like 1, 2, …
n), ...
o Predicates:
– Predicates used to relate one object with another.
E.g. brother, >,...
o Functions: Returns value (Sqrt, mother-of,...)
o Variables: x, y, a, b,...
– Important to increase generalization capability of KB
o Connectives:
– retains connectives used in PL (, , , , )
o Quantifiers:
– Quantifiers specify whether all or some objects
satisfy properties or relations between objects
– Two standard quantifiers: Universal (" for all, for
every) and Existential ($ there exists, some) 27
Quantification

28
 Universal quantification
o Universal Quantifiers: makes statements about every
object
<variables> <sentence>
–Everyone at AAU is smart:
x At(x,AAU)  Smart(x)
–All cats are mammals:
x cat(x)  mammal(x)

 x sentence P is true iff P is true with x being each

possible object in the given universe
–The above statement is equivalent to the conjunction
At(Jonas, AAU)  Smart(Jonas) 
At(Rawad, AAU)  Smart(Rawad) 
...
• A common mistake to avoid
–Typically,  is the main connective with 
–Common mistake: the use of  as the main connective with :
x At(x,AAU)  Smart(x) is true if “Everyone is at AAU & everyone29is
smart”
 Existential quantification
o Makes statements about some objects in the
universe
<variables> <sentence>
–Someone at AAU is smart:
x At(x,AAU)  Smart(x)
–Spot has a sister who is a cat:
x sister(spot,x)  cat(x)
o x sentence P is true iff P is true with x being some
possible objects
–The above statement is equivalent to the disjunction
At(Jonas, AAU)  Smart(Jonas) 
At(Alemu, AAU)  Smart(Alemu) 
…..
o Common mistake to avoid
–Typically,  is the main connective with 
–Common mistake: using  as the main connective with :
30
x At(x,AAU)  Smart(x) is true if there is anyone who is not at AAU
 Nested quantifiers
x,y parent(x,y)  child(y,x)
–for all x and y, if x is the parent of y then y is the child of x.
x y Loves(x,y)
–There is a person who loves everyone in the given world
y x Loves(x,y)
–Everyone in the given universe is loved by at least one person
Properties of quantifiers
   is the same as  
x y y x
   is the same as  
x y y x
   is not the same as  
x y y x

oQuantifier duality: each can be expressed using the

other, using negation ()
x Likes(x,icecream) x Likes(x,icecream)
–Everyone likes ice cream means that there is nobody
who dislikes ice creamx Likes(x,cake)
x Likes(x,cake)
31
–There is someone who likes cake means that there is no one who
dislikes cake
 Sentence structure
In FOL the basic unit is a predicate (argument/terms)
structure called sentence to represent facts.
oTerms refer to objects
Example: likes(muhe, chocolate); tall(fred)
–Terms or arguments can be any of: Constant symbol, such
as ‘muhe’, variable symbol, such as X , functions, such as
motherof(fred), father-of( father-of( john))
oA predicate is the one that says something about
the subject. E.g., There is a red book
•Subject: color of the book, represented as: x
book(x)^red(x)
–Predicate also refers to a particular relation between
objects
•Example: likes(X, richard)
friends(motherof(jonas), motherof(semu)) 32

–A predicate statement takes the value true or false

 Sentences
Atomic sentences: formed from a predicate
symbol followed by a parenthesized list of terms
Atomic sentence = predicate (term1,...,termn)
Example: Brother(John, Richard)
•Atomic sentences can have arguments that are
complex terms (e.g. term = function (term1,...,termn) )
Example: married(fatherof(Richard),motherof(John))
Complex sentences: complex sentences are made
by combining atomic sentences using connectives:
S, S1  S2, S1  S2, S1  S2, S1  S2,
Ex. likes(john, mary)  tall(mary)
tall(john)  handsome(john)
Sibling(John, Richard)  Sibling(Richard, John)
•Sentences can also be formed using quantifiers to
indicate how to treat variables:
– Universal quantifier: x lovely(x) - Everything is lovely. 33
– Existential quantifier: x lovely(x) - Something is lovely.
 Cont’d
•Can have several quantifiers, e.g.,
x y loves(x, y)
x handsome(x)  y loves(y, x)
Represent the following in FOL:
•Everything in the garden is lovely x in(x,
 garden)  lovely(x)
•Everyone likes ice cream xlikes(x, icecream)
y friends(y, Peter)
•Peter has some friends 
•John plays the piano or the violin
plays(john, piano) v plays(john, violin)
x(person(x) Λ likes(x, snakes))
•Some people like snakes --
write( winston, hamlet)
•Winston did not write Hamlet –
•Nobody wrote Hamlet –x write(x, hamlet)
•Every city has a dogcatcher who has been bitten by
every dog in town
x {city(x)  y{dogcatcher(y, x) Λ z{[dog(z) Λ live- in(z, x)]  bit(z, y)}}} 34
 Semantics
•There is a precise meaning to expressions in predicate
logic.
•Like in propositional logic, it is all about determining
whether something is true or false.
x P(x) means that P(x) must be true for every object x
in the domain of interest.
x P(x) means that P(x) must be true for at least one
object x in the domain of interest.
– So if we have a domain of interest consisting of just two
people, john and mary, and we know that tall(mary) and
tall(john) are true, we can say that x tall(x) is true.
•Atomic sentence is true if the relation referred by the
predicate holds b/n the objects referred by the
arguments
brother(John, Richard)
•The truth value of complex sentences depends on
logical connectives used 35
 Proof and inference
•We can define inference rules allowing us to say that if
certain things are true, certain other things are sure to
be true,
E.g. All men are mortal
Aristotle is a man
using logical inferences we can deduce that: Aristotle
is mortal

x man(x) mortal(x)
man(Aristotle)
so we can conclude that: mortal(Aristotle)
–This involves matching man(x) against man(Aristotle)
and binding the variable x to Aristotle.

36
 Unification
•Unification is an algorithm for determining the
substitutions needed to make two expressions match
– Unification is a "pattern matching" procedure that
takes two atomic sentences as input, and returns
the most general unifier, i.e., a shortest length
substitution list that makes the two literals match.
– E.g: To make, say p(X, X) and p( Y, Z) match, subst(X/ Y)
or subst(X/ Z)
•Note: It is possible to substitute two variables with the
same value, but not the same variables with different
values.

•Example
Sentence 1 Sentence 2 Unifier
{x/Bill, y/dog(Bill)}
group(x, cat(x), dog(Bill)) group(Bill, cat(Bill),{x/Bill,
y) y/Bill, z/dog(Bill)}
group(x, cat(x), dog(Bill)) group(Bill, cat(y), z)Failure
37
group(x, cat(x), dog(Jane)) group(Bill, cat(y), dog(y))
 Cont’d
•A variable can never be replaced by a term containing that
variable. For example, x/f(x) is illegal.
•Unification and inference rules allows us to make inferences
on a set of logical assertions. To do this, the logical database
must be expressed in an appropriate form
•A substitution α unfies atomic sentences p and q if pα = qα
p q α
Knows(John,x) Knows(John,Jane) {x/Jane}
Knows(John,x) Knows(y, Abe) {y/John, x/Abe}
Knows(John,x) Knows(y,Mother(y)) {y/John, x/Mother(John)}
Knows(John,x) Knows(x,Abe) Fail

Unify rule: Premises with known facts apply unifier to

conclusion
Example. if we know q and Knows(John,x) →
Likes(John,x)
then we conclude Likes(John,Jane) 38
 Inference rules
• Rules for PL apply to FOL as well. For example,
– Modus Ponens & Tollens
– Resolution and Unit Resolution
– AND-introduction
– AND-elimination,
– OR introduction,
– etc.

• New (sound) inference rules for use with

quantifiers:
– Universal Elimination
– Existential Introduction
– Existential Elimination
39
 Sound Inference Rules
•Universal Elimination: If x P(x) is true, then P(c) is
true, where c is a constant in the domain of x.
Example: x eats(x, IceCream).
Using the substitution (x/Ben) we can infer eats(Ben, Icecream).
– The variable symbol can be replaced by any constant symbol or
function symbol.
•Existential Introduction: If P(c) is true, then x P(x) is
inferred.
Example: eats(John, IceCream) we can infer x eats(x, icecream).
– All instances of the given constant symbol are replaced by the
new variable symbol.
•Existential Elimination: From x P(x) infer P(c).
Example: x eats(Sol, x) infer eats(Sol, Cheese)
– Note that the variable x is replaced by a brand new constant (like
Cheese) that does not occur in this or any other sentence in the
KB
– If x is within the scope of y it is replaced by new function f(y)
40
 Cont’d
Example 1: What can we conclude from the
following?
x tall(x)  strong(x)
tall(john)
 x strong(x)  loves(mary, x)

Example 2: Every metal is dissolved by

sulphuric acid
copper is a metal
can we conclude:
Copper is dissolved by sulphuric acid

41
 Proofs
•Sound inference: find α such that KB |= α
•Proof process is a search, operators are
inference rules
– It requires the operation of a series of inference rule
to come up with some conclusion
Example:
Bob is a buffalo. Pat is a pig. Buffaloes outrun pigs
Conclude: Bob outruns Pat
1. Buffalo(Bob)
2. Pig(Pat)
3. x,y Buffalo(x) ^ Pig(y) → outrun(x,y)
4. Buffalo(Bob) ^ Pig(Pat) And Introduction (1, 2)
5. Buffalo(Bob) ^ Pig(Pat) → outrun (Bob, Pat)
Universal Elimination (3,
{x/Bob,y/Pat}) 42
6. outrun(Bob,Pat) Modus Ponens (6, 7)
 Generalized Modus Ponens
(GMP)
•Combines And-Introduction, Universal-Elimination, and
Modus Ponens
• Given atomic sentences P1, P2, ..., PN, and implication
sentence (Q1 ^ Q2 ^ ... ^ QN)  R, where Q1, ..., QN and R
are atomic sentences, derive new sentence R. That is,
• from P(c), Q(c), and x (P(x) ^ Q(x)  R(x)), derive R(c)
Example: Given Faster(Bob,Pat), Faster(Pat,Steve) and
Faster(x,y) ^ Faster(y,z)  Faster(x,z);
by substituting {x/Bob, y/Pat, z/Steve}
infer in one step the new sentence: Faster(Bob,
Steve)
•GMP is not complete for FOL. Natural deduction using
GMP is possible only for KBs containing Horn clauses.
• A Horn clause is a sentence of the form:
x (P1(x) ^ P2(x) ^ ... ^ Pn(x))  Q(x)
43
where there are zero or more Pi‘s
 Inference Mechanisms
• Inference is a means of interpretation of
knowledge in the KB to reason and give advise
to users query.
• There are two inference strategies to control
and organize the steps taken to solve problems:
– Forward chaining: also called data-driven
chaining
• It starts with facts and rules in the KB and try to
draw conclusions from the data
– Backward chaining: also called goal-driven
chaining
• It starts with possible solutions/goals and tries to
gather information that verifies the solution
44
 Conclude by Chaining
•Forward chaining
–Proofs start with the given axioms/premises in KB,
deriving new sentences using GMP until the goal/query
sentence is derived.
–This defines a forward chaining inference procedure
because it moves "forward" from the KB to the goal.
•Example: All cats like fish, cats eat everything they
like, and Ziggy is a cat. Goal query: Does Ziggy eat
fish?
1. x cat(x)  likes(x, Fish)
2. x,y (cat(x) ^ likes(x,y))  eats(x,y)
3. cat(Ziggy)
–Proof: 4. likes(Ziggy, Fish) Using GMP with (1) and
(3) & subst{x/Ziggy}
5. eats(Ziggy, Fish) Using GMP with (3), (4)
and (2) So, Yes, Ziggy eats fish. 45
 Cont’d
•Backward chaining:
–Proofs start with the goal query, find implications that
would allow you to prove it, and then prove each of the
antecedents in the implication, continuing to work
"backwards" until we get to the axioms, which we know
are true.
–To prove eats(Ziggy, Fish), first see if this is known from
one of the axioms directly. Otherwise, see if there is a
Horn clause that has the consequent (i.e., right-hand side
(RHS)) of the implication matching the goal. Here,
•Goal matches RHS of (2), so prove new sub-goals
cat(Ziggy) and likes(Ziggy, Fish) that correspond to the LHS
of (2)
•cat(Ziggy) matches axiom (3), so we've "solved" that sub-goal
•likes(Ziggy, Fish) matches the RHS of (1), so prove cat(Ziggy)
•cat(Ziggy) matches (3), so we've solved this sub-goal
•There are no unsolved sub-goals, 46
So we conclude. Yes, Ziggy eats fish
 Generalized Resolution
•Resolution procedure is a sound and complete inference
procedure for FOL
–It uses a single resolution rule of inference: which is
generalization of the same rule used in PL.
•Resolution Rule for PL: From sentence P1 v P2 v ... v Pn
and sentence P1 v Q2 v ... v Qm derive resolvent
sentence:
P2 v ... v Pn v Q2 v ... v Qm
•Resolution Rule for FOL:
•Given sentence P1 v ... v Pn and sentence Q1 v ... v Qm
where each Pi and Qi is a predicate sentences, if Pj and Qk
unify with substitution list θ, then derive the sentence:
P1 v ... v Pj-1 v Pj+1 v ... v Pn v Q1 v ... Qk-1 v Qk+1 v ... V Qm

Examples:
–Given: Rich(ken); Rich(x) v unhappy(x)
using subst {x/ken}
47
we can conclude that: unhappy(ken)
 Generalized Resolution: proof by
refutation
•Generalized Resolution inference rule
provides a complete system for proof by
refutation.
– Resolution is a generalization of modus ponens
– It requires a normal form, but any sentence can be
put into CNF
•Conjunctive normal form (CNF)
– Each individual sentence is a disjunction of literals.
This form is CNF
– CNF is more common. For instance,
P(x) v R(x)
Q(y) v S(y)
•Conversion to CNF:
– any FOL sentence can be put into normal form 48
 Steps to convert a FOL sentence
to(PCNF
•Eliminate  connectives: replace  Q) by ((P  Q) ^ (Q  P))

•Eliminate  connectives: replace each instance (P  Q) by (P v Q)

•Reduce the scope of negation:

P to P; (P v Q) to P ^ Q; (P ^ Q) to P v Q; x P(x) to x P(x),
and x P(x) to x P(x)
•Eliminate  by introducing Skolem symblos/function.
 x P(x) converted to P(c) where c is a brand new Skolem constant
symbol that is not used in any other sentence.
– If  is within the scope of a universal quantified variable, then introduce
a Skolem function (f). Example, xyP(x,y) is converted to xP(x, f(x)).
E.g.: x y loves(x,y) converted to x loves(x,f(x)) where f(x) specifies the
person that x loves. (If everyone loved their mother, then f could be
mother_of (x) function)
•Drop  x quantifiers. For example, convert x P(x) to P(x).

•Distribute "and" over "or" to get conjunctive normal form.

Convert (P ^ Q) v R to (P v R) ^ (Q v R), & (P v Q) v R to (P v Q v R).
•And Elimination: Split each conjunct into a separate clause.
(P v R) ^ (Q v R) into (P v R), (Q v R)
49
 Example
Convert the following sentence to CNF
x (P(x)  (y (P(y)  P(f(x,y))) ^ y(Q(x,y)  P(y)))
•Eliminate :
(x)(P(x) v ((y)(P(y) v P(f(x,y))) ^ (y)(Q(x,y) v P(y))))
•Reduce scope of  :
(x)(P(x) v ((y)(P(y) v P(f(x,y))) ^ (y)(Q(x,y) ^ P(y))))
•Standardize variables:
(x)(P(x) v ((y)(P(y) v P(f(x,y))) ^ (z)(Q(x,z) ^ P(z))))
•Eliminate :
(x)(P(x) v ((y)(P(y) v P(f(x,y))) ^ (Q(x,g(x)) ^ P(g(x)))))
•Drop universal quantification
(P(x) v ((P(y) v P(f(x,y))) ^ (Q(x,g(x)) ^ P(g(x)))))
•Convert to conjunction of disjunctions
(P(x) v P(y) v P(f(x,y))) ^ (P(x) v Q(x,g(x))) ^ (P(x) v
P(g(x)))
•Create separate clauses (And Elimination)
P(x) v P(y) v P(f(x,y)), P(x) v Q(x,g(x)), P(x) v P(g(x))
•Standardize variables 50
P(x) v P(y) v P(f(x,y)), P(z) v Q(z,g(z)), P(w) v P(g(w))
 More Example:
Convert the following sentence to CNF
• Everyone who loves all animals is loved
by someone.

x[(y animal(y)  loves(x,y))  z

loves(z,x) ]

51
 Resolution: Proof by
Example
Refutation
• Jack owns a dog. Every dog owner is an
animal lover. No animal lover kills an animal.
Either Jack or Curiosity killed the cat, who is
named Tuna. Did Curiosity kill the cat?

• FOL representation:
A. (x) Dog(x)  Owns(Jack,x)
B. (x) ((y) Dog(y)  Owns(x, y))  AnimalLover(x)
C. (x) AnimalLover(x)  ((y) Animal(y)  Kills(x,y))
D. Kills(Jack,Tuna)  Kills(Curiosity,Tuna)
E. Cat(Tuna)
F. (x) Cat(x)  Animal(x)
G. Kills(Curiosity, Tuna)
52
 Properties of Good KB
•A KB should be clear, correct, expressive, concise, context-
insensitive and effective.
– The relations that matter should be defined, and the irrelevant
details should be suppressed
•Separate the KB from inference procedure.
– This allows the KE (creator of the KB) to focus on the content of
the KB, and not about how it will be used by the inference
procedure
•Define a generally applicable KB.
– Every KB has two potential consumers: human readers and
inference procedure
– A common mistake is to choose predicate names that are
meaningful to the human readers, and then assume that the
name is somehow meaningful to the inference procedure as
well
•E.g. consider the sentence: BearOfVerySmallBrain(Lilly). Do
you think the Inference engine be able to infer from this
sentence facts such as: Lilly is a bear or Lilly has a very
small brain; that it has a brain at all
– Such very long names do not scale up well
– In a properly designed KB, facts that were entered for one 53
situation should be used in new situations as well
 Most general KB design
•In a good KB, BearOfVerySmallBrain(Lilly)
would be replaced by the following
– Lilly is a bear; bears are animals; animals are physical
things
• Bear(Lilly)
 x bear(x)  animal(x)
 y animal(y)  physicalThing(y)
– All animals have a brain, which is a part of the animal
 z animal(z)  brain(brainOf(z))
 x partOf(brainOf(x),x)
– Lilly has a very small brain
• relativeSize(BrainOf(Lilly), BrainOf(typicalBear)) =
very(small)
– If something is part of a physical thing, then it is also a
physical thing
 x,y part-of(x,y) ^ physicalThing(y)  54
physicalThing(x)
Thank you!!!

55