Module 4

Knowledge Representation and

Reasoning
 Syllabus
• Logical Agents – Knowledge based agents,
• Logic, Propositional Logic, Propositional
• Theorem proving, Agents based on
• Propositional Logic.
• First Order Predicate Logic – Syntax and
• Semantics of First Order Logic, Using First
• Order Logic, Knowledge representation in
• First Order Logic.
• Inference in First Order Logic –
• Propositional Vs First Order inference,
• Unification and Lifting, Forward chaining,
• Backward chaining, Resolution.
 Logical Agents
• A logical agent is an AI agent that makes decisions
based on knowledge and reasoning(deriving new
information) using logic (usually propositional or first-
order logic).
• A logical agent Stores knowledge about the world in a
formal way (as sentences in logic).
• Uses inference rules to derive new information.
• Acts based on what it can logically conclude.
 Logical Agents
• Agents can form representations of a complex
world, use a process of inference to derive
new representations about the world and use
these new representations to deduce what to
do.
• Idea is that an agent can represent
knowledge of its world, its goals and the
current situation by sentence in logic.
 Logical Agents
• Logical Agents has a collection of sentences in
logic.
• By using these sentences the agent decided what
to do by inferring knowledge(conclusion)
• Conclusions are achieved by certain action or set
of actions that are appropriate to achieve its goal.
• Knowledge and reasoning are important to
logical agents, because they enable successful
behaviour to achieve a goal.
 Knowledge-Based Agent

• A Knowledge-Based Agent:
• Has a knowledge base (KB) containing facts
and rules about the world.
• Uses a reasoning or inference mechanism to
draw conclusions.
• Updates its knowledge as it perceives new
information.
• Acts based on what it knows and infers.
 Knowledge-Based Agents
• Central component of a Knowledge-Based
Agent is a Knowledge-Base
• A Knowledge-Base is a collection of
sentences.
• Sentence is not identical to sentences of
English and other natural langauges
• Sentences are expressed using a knowledge
representation language
 Knowledge-Based Agents
• Two generic functions:
• – TELL - add new sentences (facts) to the KB
“Tell it what it needs to know”
– ASK - query what is known from the KB
“Ask what to do next”
•
 Knowledge-Based Agents
• Composed of two main parts:
• [Link] base
• [Link] Engine
A simple knowledge-based agent
Logic
 Logics
• Logics are formal languages for representing
information such that conclusions can be drawn
• Syntax defines the sentences in the language
• Semantics define the "meaning" of sentences;
define truth of each sentence with respect to each
possible world.
• E.g., the language of arithmetic
• x+2 ≥ y is a sentence
• x2+y > {} is not a sentence
• x+2 ≥ y is true iff the number x+2 is no less than the
number y
 Entailment
• Entailment means a sentence follows logically
from another :
• to mean that the sentence α entails the
sentence β
• α |= β if and only if, in every model in which α is
true, β is also true
• α |= β if and only if M(α) ⊆ M(β) .
• Knowledge base KB entails sentence α if and
only if α is true in all worlds where KB is true
 Inference
• Inference is a procedure that allows new
sentences to be derived from a knowledge
base.
 Propositional Logic: A Very Simplest Logic

• Syntax of PL: defines the allowable sentences or

propositions.
• Definition (Proposition): A proposition is a
declarative statement (True or False).
• A fact, like “the Sun is hot.” The Sun cannot be
both hot and not hot at the same time.
• This declarative statement could also be referred
to as a proposition.
 Atomic proposition
• Atomic proposition: single proposition symbol.
• Each symbol is a proposition.
• Notation: upper case letters and may contain
subscripts.
• P: It is raining
• Q: The ground is wet
 Compound proposition
• Compound proposition: constructed from
atomic propositions using parentheses and
logical connectives.
• Example:
• P: It is raining
• Q: The ground is wet
• Then:
• P ∧ Q → “It is raining and the ground is wet.”
(compound)
 Compound propositions
• Examples of atomic propositions:
• 2+2=4 is a true proposition
• Examples of compound/complex propositions
• Conjunction p1 ∧ p2.
• ◦ Disjunction p1 ∨ p2
• ◦ Implication p1 → p2.
• ◦ If and only if p1 ↔ p2
 Truth Table
• The semantics define the rules to determine the
truth of a sentence.
• Semantics can be specified by truth tables.
• Boolean values domain: T,F , n-tuple: (x1, x2, ..., xn)
• Operator on n-tuples : g(x1 = v1, x2 = v2, ..., xn = vn)
• A truth table defines an operator g on n- tuples by
specifying a Boolean value for each tuple.
• Number of rows in a truth table? R = 2n
Building Propositions
 Precedence of operators
• 1. Expressions in parentheses are processed (inside
to outside)
• 2. Negation
• 3. AND
• 4. OR
• 5. Implication
• 6. Biconditional
• 7. Left to right
• • Use parentheses whenever you have any doubt!
Building proposition
 Logical Equivalence
• Two propositions p and q are logically
equivalent if and only if the columns in the
truth table giving their truth values agree.
We write this as p ⇔ q or p ≡ q.
Properties
 Tautology and contradiction
• Tautology is a proposition which is always true
• Contradiction is a proposition which is always
false
• Contingency is a proposition which is neither a
tautology or a contradiction
 Contrapositive and Inverse
• Given an implication p → q
• The converse is: q → p
• The contrapositive is: ¬q → ¬p
• The inverse is: ¬p → ¬q

• Conditional statement: “If it is raining, then the grass is wet.”

• The first step is to identify the hypothesis and conclusion
statements. Hypothesis, p: it is raining
• Conclusion, q: grass is wet
• Converse statement would be: “If the grass is wet, then it is
raining.”
• Inverse statement would be: “If it is NOT raining, then the grass is
NOT wet.”
• Contrapositive statement would be: “If the grass is NOT wet, then
it is NOT raining.
Inference (Modus Ponens)
If
and is true,
then must also be true.
Modus Tollens
 And Elimination, Unit Resolution
• f is true, then both and are true separately.
• Symbolically:

• Example:
• It is raining and it is cold.
→ Therefore, it is raining.
→ Therefore, it is cold.
• This rule “eliminates the AND” to separate the
statements.
• Unit Resolution

• Used in propositional logic (especially in automated reasoning

and AI) — it simplifies clauses during logical deduction.
• Form:
If one clause contains a literal and another contains its
negation , you can infer a new clause combining the remaining
parts.
• Symbolically:

• Example:
• Either it is raining or it is cloudy. →
• It is not raining. →
 DNF and CNF
• DNF: Disjunctive Normal Form
• OR of ANDs (terms)
• e.g. (p∧¬q) ∨ (¬p∧¬r)
• CNF: Conjunctive Normal Form
• “every sentence of propositional logic is
logically equivalent to a conjunction of clauses”
• AND of ORs (clauses)
• e.g. (p∨¬q) ∧ (¬p∨¬r)
 procedure for converting to CNF
Convert the sentence B1,1 ⇔ (P1,2 ∨ P2,1) into CNF
• Step 1: Eliminate bi-conditionals (↔)
• Replace any biconditional with:

• Then later simplify each implication.

• Step 2: Eliminate implications (→)

• Replace with:

• Step 3: Move NOT (¬) inwards (using De Morgan’s laws)

• Apply these rules repeatedly:

• Goal: The NOT operator should apply only to individual variables,

not to complex expressions.
• Step 4: Apply distributive laws
• Distribute OR (∨) over AND (∧) to get a conjunction of
disjunctions.
• Use:

• Repeat until the formula becomes a conjunction (AND) of

clauses, where each clause is a disjunction (OR) of literals.

• Step 5: Simplify
• Remove duplicate literals or clauses.
• Eliminate any tautological clauses (like ).
• Now the formula is in CNF ✅
• 🧠 Example Conversion
• Convert:

• Step 1: Eliminate implications

• Step 2: Move negations inward

• Step 3: Distribute OR over AND

 University qn

• What do you mean by Conjunctive Normal

Form? List the steps for converting
propositional logic statement to CNF.
• Convert (P → Q) → ((Q → R) → (P →R)) to CNF
using these rules.
 AGENTS BASED ON PROPOSITIONAL
LOGIC: Wumpus world – Knowledge Base
• Atomic propositions
Room[1,1], room does not have
wumpus(¬ W11), no stench (¬S11), no
Pit(¬P11), no breeze(¬B11), no gold
(¬G11), visited (V11), and the room is
Safe(OK11).
 Inference
• Prove that wumpus is in the room (1, 3) using
propositional rules which have been derived
for the wumpus world and using inference
rule.
• Apply Modus Ponens with ¬S11 and R1:
• Apply And-Elimination Rule:
• After applying And-elimination rule to ¬ W11 ∧ ¬ W12 ∧ ¬
W21, we will get three statements:
• ¬ W11, ¬ W12, and ¬W21.
• •Apply Modus Ponens to ¬S21, and R2:
• Now we will apply Modus Ponens to ¬S21 and R2 which is
¬S21 → ¬ W21 ∧¬ W22 ∧¬ W31, which will give the Output
as ¬ W21 ∧ ¬ W22 ∧¬ W31
• Apply And -Elimination rule:
• Now again apply And-elimination rule to ¬ W21 ∧ ¬
W22 ∧¬ W31, We will get three statements:
• ¬ W21, ¬ W22, and ¬ W31.
• •Apply MP to S12 and R4:
• Apply Modus Ponens to S12 and R4 which is S12 →
W13 ∨. W12 ∨. W22 ∨.W11, we
• will get the output as W13∨ W12 ∨ W22 ∨.W11.
• Apply Unit resolution on W13 ∨ W12 ∨ W22
∨W11 and ¬ W11 :
• After applying Unit resolution formula on W13
∨ W12 ∨ W22 ∨W11 and ¬ W11 we will get
W13 ∨ W12 ∨ W22.
• Apply Unit resolution on W13 ∨ W12 ∨ W22
and ¬ W22 :
• After applying Unit resolution on W13 ∨ W12
∨ W22, and ¬W22, we will get W13 ∨ W12 as
output.
• Apply Unit Resolution on W13 ∨ W12 and ¬
W12 :
• After Applying Unit resolution on W13 ∨ W12
and ¬ W12, we will get W13 as an output,
• hence it is proved that the Wumpus is in the
room [1, 3].
 Demerit of Propositional Logic
• Propositional logic can only represent the facts,
which are either true or false.
• PL is not sufficient to represent the complex
sentences or natural language statements.
• The propositional logic has very limited
expressive power.
• Consider the following sentence, which we
cannot represent using PL logic.
• •"Some humans are intelligent", or
• •"Sachin likes cricket."
 First-Order Logic (FOL)
• It is an extension to propositional logic.
• FOL is sufficiently expressive to represent the
natural language statements in a concise way.
• First-order logic is also known as Predicate
logic or First-order predicate logic.
 First-order Logic
• First-order logic (FOL) models the world in terms of
• Objects, which are things with individual identities
• Properties of objects that distinguish them from
other objects
• Relations that hold among sets of objects
• Functions, which are a subset of relations where
there is only one “value” for anygiven “input”
• Examples:
• Objects: Students, lectures…
• Relations: Brother-of, biggerthan, outside..
• Properties: blue, oval, even, large, ...
• Functions: father-of, best-friend,second-half, one-more-
than ...
• Also called as Predicate Logic
• It is a generalization of Propositional Logic that allows
us to express and infer arguments in infinite models, Eg,
• ◦ Some birds can fly
• ◦ All men are mortal
• ◦ At least one student has course registered
Basic Element in FOL
 Terms
• A term is a logical expression that refers to an
object.
• Constant symbols are therefore terms, but it is
not always convenient to have a distinct symbol
to name every object.
• For example, in English we might use the
expression “King John’s left leg”rather than
giving a name to his leg.
• This is what function symbols are for: instead of
using a constant symbol,we use LeftLeg(John).
 Atomic Sentences in FOL
• Atomic sentences are the most basic sentences
of first-order logic.
• These sentences are formed from a predicate
symbol followed by a parenthesis with a
sequence of terms.
• Atomic sentences are represented as Predicate
(term1, term2, ......, term n).
• Example: Ravi and Ajay are brothers: =>
Brothers(Ravi, Ajay).
• Chinky is a cat: => cat (Chinky).
 Complex sentences
• Complex sentences are made by combining atomic
sentences using connectives.
• We can use logical connectives to construct more
complex sentences, with the same syntax and
semantics as in propositional calculus.
• ¬Brother (LeftLeg(Richard), John)
• Brother (Richard, John) ∧ Brother (John,Richard)
• King(Richard) ∨ King(John)
• ¬King(Richard) ⇒ King(John)
 Quantifiers
• Quantifiers express properties of entire
collections of objects
• First-order logic contains two standard
quantifiers,called
• universal and
• existential.
 Universal quantification (∀)
• Expression of general rules in propositional
logic
• The second rule, “All kings are persons,” is
written in first-order logic
• As ∀ x King(x) ⇒ Person(x) // “For all x, if x is a
king, then x is a person.”
• ∀ is usually pronounced “For all ...”.
 Existential quantification (∃)
• Universal quantification makes statements about every
object.
• Similarly, we can make a statement about some object in the
universe without naming it, by using an existential quantifier.
• To say, for example, that King John has a crown on his head,
we write
• ∃ x Crown(x) ∧ OnHead(x, John)
• ∃x is pronounced “There exists an x such that ...” or “For
some x...”.
• the sentence ∃ x P says that P is true for at least one object x.
 Nested quantifiers
• We want to express more complex sentences
using multiple quantifiers
• For example, “Brothers are siblings” can be
written as
• ∀ x ∀ y Brother (x, y) ⇒ Siblings(x, y) .
• Consecutive quantifiers of the same type can be
written as one quantifier with several variables.
• For example, to say that siblinghood is a symmetric
relationship, we can write
• ∀ x, y Sibling(x, y) ⇔ Sibling(y, x) .
• In other cases we will have mixtures. “Everybody
loves somebody” means that for every person, there
is someone that person loves:
• ∀ x ∃ y Loves(x, y) .
• On the other hand, to say “There is someone who is
loved by everyone,” we write
• ∃ y ∀ x Loves(x, y) .
 Connections between ∀ and ∃
• The two quantifiers are actually intimately connected
with each other, through negation.
• Asserting that everyone dislikes Apple is the same as
asserting there does not exist someone who likes them,
and viceversa:
• ∀ x ¬Likes(x,Apple ) is equivalent to ¬∃ x Likes(x,Apple) .
• “Everyone likes ice cream” means that there is no one
who does not like ice cream:
• ∀ x Likes(x,IceCream) is equivalent to ¬∃ x
¬Likes(x,IceCream)
De Morgan rules for quantified and
unquantified sentences
 Equality

• We can use the equality symbol to signify that

two terms refer to the same object.
• For example, Father (John) = Henry
• says that the object referred to by Father (John)
and the object referred to by Henry are the
same.
• Because an interpretation fixes the referent of
any term, determining the truth of an equality
sentence is simply a matter of seeing that the
referents of the two terms are the same object.
• To say that Richard has at least two brothers,
we would write
 FOL
• Points to remember:
• The main connective for universal quantifier ∀ is
implication →.
• The main connective for existential quantifier ∃ is
and ∧.
• Properties of Quantifiers:
• In universal quantifier, ∀x∀y is similar to ∀y∀x.
• ◦In Existential quantifier, ∃x∃y is similar to ∃y∃x.
• ∃x∀y is not similar to ∀y∃x.
 Examples of FOL
• 1. All birds fly.
• In this question the predicate is "fly(bird)."
• And since there are all birds who fly so it will be represented as follows.
• ∀x bird(x) →fly(x).

• 2. Every man respects his parent.

• In this question, the predicate is "respect(x, y)," where x=man, and y=
parent.
• Since there is every man so will use ∀, and it will be represented as follows:
• ∀x man(x) → respects (x, parent).

• 3. Some boys play cricket.

• In this question, the predicate is "play(x, y)," where x= boys, and y= game.
Since
• there are some boys so we will use ∃, and it will be represented as:
• ∃x boys(x) → play(x, cricket).
• 4. Not all students like both Mathematics and Science.
• In this question, the predicate is "like(x, y)," where x= student, and
y=subject.
• Since there are not all students, so we will use ∀ with negation,
• so following representation for this:
• ¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].

• 5. Only one student failed in Mathematics.

• In this question, the predicate is "failed(x, y)," where x= student,
and y= passed student.
• Since there is only one student who failed in Mathematics, so we
will use following representation for this:
• ∃(x) [ student(x) → failed (x, Mathematics) ∧∀ (y) [¬(x==y) ∧
• student(y) → ¬failed (x, Mathematics)].
• `
• A. Emily is either a surgeon or a lawyer.
• Occupation(Emily, Surgeon) ∨ Occupation(Emily, Lawyer)
or
• Occupation(Emily, Surgeon) ⇔ ¬Occupation(Emily,
Lawyer)

• B. Joe is an actor, but he holds another job.

• Occupation(Joe, Actor) ∧ ∃ o [Occupation(Joe, o) ∧ ¬ (o
= Actor)]
or
• Occupation(Joe, Actor) ∧ [ Occupation(Joe, Doctor) ∨
Occupation(Joe, Surgeon) ∨ Occupation(Joe, Lawyer) ]
• C. All surgeons are doctors.
• ∀ p [Occupation(p, Surgeon) ⇒ Occupation(p,
Doctor)]
• D. Joe does not have a lawyer (i.e., Joe is not a
customer of any lawyer).
• ∀ p [Occupation(p, Lawyer) ⇒ ¬ Customer(Joe, p)]
Or
• ¬ ∃ p [Occupation(p, Lawyer) ∧ Customer(Joe, p)]
or
• ∀ p [Customer(Joe, p) ⇒ ¬ Occupation(p, Lawyer)]
• E. Emily has a boss who is a lawyer.
• ∃ p1 [Boss(p1, Emily) ∧ Occupation(p1, Lawyer)]
• F. There exists a lawyer all of whose clients are
doctors (i.e., all of whose customers are
doctors).
• ∃ p1 ∀ p2 Occupation(p1, Lawyer) ∧
[Customer(p2, p1) ⇒Occupation(p2, Doctor)]
• Or
• ∃ p1 Occupation(p1, Lawyer) ∧ [∀ p2
Customer(p2, p1) ⇒ Occupation(p2, Doctor)]
• Every surgeon has a lawyer (i.e., every surgeon
is a customer of a lawyer).
• ∀ p1 ∃ p2 Occupation(p1, Surgeon) ⇒
[Customer(p1, p2) ∧ Occupation(p2, Lawyer)]
• Or
• ∀ p1 Occupation(p1, Surgeon) ⇒ [∃ p2
Customer(p1, p2) ∧ Occupation(p2, Lawyer)]
 Free and Bound Variable
• There are two types of variables in First-order logic
which are given below:
• Free Variable: A variable is said to be a free variable in a
formula if it occurs outside the scope of the quantifier.
• Example: ∀x ∃(y)[P (x, y, z)], where z is a free variable.
• Bound Variable: A variable is said to be a bound
variable in a formula if it occurs within the scope of the
quantifier.
• Example: ∀x [A (x) B( y)], here x and y are the bound
variables.
 Unification
• The process of finding a substitution for predicate
parameters is called unification.
• We need to know:
• ◦ that 2 literals can be matched.
• ◦ the substitution is that makes the literals
identical.
• There is a simple algorithm called the unification
algorithm that does this.
• The substitution variables are called Most General
Unifier(MGU)
The Unification Algorithm
Unification Example
 Conditions for Unification:
• Following are some basic conditions for
unification:
• Predicate symbol must be same, atoms or
expression with different predicate symbol can
neverbe unified.
• Number of Arguments in both expressions
must be identical.
• Unification will fail if there are two similar
variables present in the same expression.
 Resolution
• Resolution is a single inference rule which can
efficiently operate on the conjunctive normal form
or clausal form.
Steps for resolution
Resolution- Example
Drop Universal Quantifier
Step-3: Negate the statement to be
proved
In this statement, we will apply
negation to the conclusion
statements, which will be written as
¬likes(John, Peanuts)
 University Qn
• Consider the following facts in a knowledge base

• 1. Gita likes all kinds of food.

• 2. Mango and chapati are food.
• 3. Gita eats almond and is still alive.
• 4. Anything eaten by anyone and is still alive is food.
• Prove “Gita likes Almond” using resolution
technique.
 University Qn
• Consider the following statements:
• a) Everyone who loves all animals is loved by someone.
• b) Anyone who kills an animal is loved by no one.
• c) Jack loves all animals.
• d) Either Jack or Curiosity killed the cat, who is named
Tuna.
• Represent the sentences using First Order Logic.
Answer the following question using proof by
resolution.
• "Did Curiosity kill the cat?"
 Inference engine
• The inference engine is the component of the
intelligent system in artificial intelligence, which
applies logical rules to the knowledge base to
infer new information from known facts.
• Inference engine commonly proceeds in two
modes, which are:
• Forward chaining
• Backward chaining
 Forward Chaining
• Forward chaining is a form of reasoning which start
with atomic sentences in the knowledge base and
applies inference rules (Modus Ponens) in the
forward direction to extract more data until a goal
is reached.
• The Forward-chaining algorithm starts from known
facts, triggers all rules whose premises are
satisfied, and add their conclusion to the known
facts.
• This process repeats until the problem is solved.
• Given a new fact, generate all consequences
• Assumes all rules are of the form
• C1 and C2 and C3 and…. --> Result
• Each rule & binding generates a new fact
• This new fact will “trigger” other rules
• Keep going until the desired fact is generated
• (Semi-decidable as is FOL in general)
 FC: 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 America, has some missiles,
and all of its missiles were sold to it by Col.
West, who is an American.
• Prove that Col. West is a criminal.
FC: Example Knowledge Base
FC: Example Knowledge Base
 Backward Chaining
• Consider the item to be proven a goal
• Find a rule whose head is the goal (and
bindings)
• Apply bindings to the body, and prove these
(subgoals) in turn
• If you prove all the subgoals, increasing the
binding set as you go, you will prove the item.
Backward Chaining Example