Knowledge Representation and Reasoning

25-11-2022 KNOWLEDGE REPRESENTATION - AI 1

Contents
Knowledge-based agents
Wumpus world
Logic in general - models and entailment
Propositional (Boolean) logic
Equivalence, validity, satisfiability
Inference rules and theorem proving
▪ Forward chaining
▪ Backward chaining
▪ Resolution

25-11-2022 KNOWLEDGE REPRESENTATION - AI 2

Logical Agents

Humans can know “things” and “reason”

Representation: How are things stored?
Reasoning: How is the knowledge used?
• To solve a problem…
• To generate more knowledge…
• Knowledge and reasoning are important to artificial agents because they
enable successful behaviors difficult to achieve otherwise
– Useful in partially observable environments

25-11-2022 KNOWLEDGE REPRESENTATION - AI 3

Logical Agents

“Logical AI:
The idea is that an agent can represent knowledge of its world,
its goals and the current situation by sentences in logic and decide
what to do by inferring that a certain action or course of action is
appropriate to achieve its goals.”

25-11-2022 KNOWLEDGE REPRESENTATION - AI 4

Knowledge-Based Agents
Central component of a Knowledge-Based Agent is a Knowledge-Base
A set of sentences in a formal language
Sentences are expressed using a knowledge representation language
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”

25-11-2022 KNOWLEDGE REPRESENTATION - AI 5

Knowledge Base

25-11-2022 KNOWLEDGE REPRESENTATION - AI 6

Knowledge Base
Performance Measure: Performance measure is the unit to define the success
of an agent. Performance varies with agents based on their different precepts.

Environment: Environment is the surrounding of an agent at every instant. It

keeps changing with time if the agent is set in motion.

Actuator: An actuator is a part of the agent that delivers the output of action to
the environment.

Sensor: Sensors are the receptive parts of an agent that takes in the input for
the agent.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 7

A simple knowledge-based agent

25-11-2022 KNOWLEDGE REPRESENTATION - AI 8

 The Wumpus World environment
The Wumpus computer game

The agent explores a cave consisting of rooms

connected by passageways
Lurking somewhere in the cave is the Wumpus, a beast
that eats any agent that enters its room
Some rooms contain bottomless pits that trap any agent
that wanders into the room
The Wumpus can fall into a pit too, so avoids them
Occasionally, there is a heap of gold in a room.
The goal is to collect the gold and exit the world without
being eaten

25-11-2022 KNOWLEDGE REPRESENTATION - AI 9

 AIMA’s Wumpus World

The agent always starts in the field

[1,1]

Agent’s task is to find the gold, return

to the field [1,1] and climb out of the
cave

25-11-2022 KNOWLEDGE REPRESENTATION - AI 10

 The Hunter’s first step

¬W

¬W

Since the agent is alive and perceives neither Moving to [2,1] is a safe move that reveals a
a breeze nor a stench at [1,1], it knows that breeze but no stench, implying that the Wumpus
[1,1] and its neighbors are OK is not adjacent but that one or more pits are
25-11-2022 KNOWLEDGE REPRESENTATION - AI 11
Exploring a wumpus world

A agent
B breeze
G glitter
OK safe cell
P pit
S stench
W wumpus

25-11-2022 KNOWLEDGE REPRESENTATION - AI 12

Exploring a wumpus world

A agent
B breeze
G glitter
OK safe cell
P pit
S stench
W wumpus

25-11-2022 KNOWLEDGE REPRESENTATION - AI 13

Exploring a wumpus world

A agent
B breeze
G glitter
OK safe cell
P pit
S stench
W wumpus

25-11-2022 KNOWLEDGE REPRESENTATION - AI 14

Exploring a wumpus world

A agent
B breeze
G glitter
OK safe cell
P pit
S stench
W wumpus

25-11-2022 KNOWLEDGE REPRESENTATION - AI 15

Exploring a wumpus world

A agent
B breeze
G glitter
OK safe cell
P pit
S stench
W wumpus

25-11-2022 KNOWLEDGE REPRESENTATION - AI 16

Exploring a wumpus world

A agent
B breeze
G glitter
OK safe cell
P pit
S stench
W wumpus

25-11-2022 KNOWLEDGE REPRESENTATION - AI 17

Exploring a wumpus world

A agent
B breeze
G glitter
OK safe cell
P pit
S stench
W wumpus

25-11-2022 KNOWLEDGE REPRESENTATION - AI 18

Exploring a wumpus world

A agent
B breeze
G glitter
OK safe cell
P pit
S stench
W wumpus

25-11-2022 KNOWLEDGE REPRESENTATION - AI 19

Exploring a wumpus world

A agent
P?
B breeze
G glitter
OK safe cell
P pit
P?
S stench
W wumpus

In each case where the agent draws a conclusion from the available
Information, that conclusion is guaranteed to be correct if the available
Information is correct…

This is a fundamental property of logical reasoning

25-11-2022 KNOWLEDGE REPRESENTATION - AI 20

Logic as a KR language

Multi-valued Modal Temporal Non-monotonic

Logic Logic

Higher Order
Probabilistic
Logic First Order

Fuzzy Propositional Logic

Logic

25-11-2022 KNOWLEDGE REPRESENTATION - AI 21

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 a sentence in a
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
❖ x+2 ≥ y is true in a world where x = 7, y = 1

25-11-2022 KNOWLEDGE REPRESENTATION - AI 22

Knowledge Representation

25-11-2022 KNOWLEDGE REPRESENTATION - AI 23

Entailment
Entailment means that one thing follows logically from another: KB ╞ α

Knowledge base KB entails sentence α if and only if α is true in all worlds

where KB is true

Eg. the KB containing “the Phillies won” and “the Reds won” entails “Either
the Phillies won or the Reds won”

Eg. x+y = 4 entails 4 = x+y

Entailment is a relationship between sentences (i. e. , syntax) that is based

on semantics
25-11-2022 KNOWLEDGE REPRESENTATION - AI 24
Inference and Entailment

Inference is a procedure that allows new sentences to be derived from a

knowledge base.

Understanding inference and entailment: think of

Set of all consequences of a KB as a haystack

α as the needle

Entailment is like the needle being in the haystack

Inference is like finding it

25-11-2022 KNOWLEDGE REPRESENTATION - AI 25

Inference and Entailment
M is a model of a sentence α if α is true in M

M(α) is the set of all models of α

25-11-2022 KNOWLEDGE REPRESENTATION - AI 26

 Propositional Logic 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: single proposition symbol. Each symbol is a proposition.

Notation: upper case letters and may contain subscripts.

Compound proposition: constructed from atomic propositions using parentheses and

logical connectives.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 27

Atomic Proposition
Examples of atomic propositions:

2+2=4 is a true proposition

W1,3 is a proposition. It is true if there is a Wumpus in [1,3]

“If there is a stench in [1,2] then there is a Wumpus in [1,3]”

is a proposition

“How are you?” or “Hello!” are not propositions. In general,

statement that are questions, commands, or opinions are not
propositions.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 28

Examples of compound/complex propositions
Let p, p1, and p2 be propositions

• Negation ¬p is also a proposition. A literal is either an atomic proposition or

its negation. E.g., W1,3 is a positive literal, and ¬W1,3 is a negative literal.

• Conjunction p1 ∧ p2. E.g., W1,3 ∧ P3,1

• Disjunction p1 ∨ p2 E.g., W1,3 ∨ P3,1

• Implication p1 → p2. E.g., W1,3 ∧ P3,1 → ¬W2,2

• If and only if p1 ↔ p2. E.g., W1,3 ↔ ¬W2,2

25-11-2022 KNOWLEDGE REPRESENTATION - AI 29
 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

25-11-2022 KNOWLEDGE REPRESENTATION - AI 30
Building Propositions

Negation Conjunction If and only if

Exclusive OR Disjunction Implication

25-11-2022 KNOWLEDGE REPRESENTATION - AI 31

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!

25-11-2022 KNOWLEDGE REPRESENTATION - AI 32

Building proposition

25-11-2022 KNOWLEDGE REPRESENTATION - AI 33

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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 34

 Properties
• Commutativity: • ¬(¬p) = p
p∧q=q∧p •p∧p=pp∨p=p

p∨q=q∨p • Distributivity:
• Associativity: p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r)
p ∧ q) ∧ r = p ∧ (q ∧
r)
• p ∧ (¬p) = False and p ∨ (¬p) = T
(p ∨ q) ∨ r = p ∨ (q ∨ rue
r)
• Identity element: • DeMorgan’s laws:
¬(p ∧ q) = (¬p) ∨ (¬q)
p ∧ T rue = p
¬(p ∨ q) = (¬p) ∧ (¬q)
p ∨ T rue = T rue
25-11-2022 KNOWLEDGE REPRESENTATION - AI 35
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

25-11-2022 KNOWLEDGE REPRESENTATION - AI 36

 Contrapositive and Inverse
Conditional statement: “If it is raining, then the grass is wet.”
Given an implication p → q
• The converse is: q → p The first step is to identify the hypothesis and conclusion
statements. Hypothesis, p: it is raining
• The contrapositive is: ¬q → Conclusion, q: grass is wet
¬p
• The inverse is: ¬p → ¬q 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.”
25-11-2022 KNOWLEDGE REPRESENTATION - AI 37
Inference (Modus Ponens)

25-11-2022 KNOWLEDGE REPRESENTATION - AI 38

Modus ponens- Truth Table

Implication

25-11-2022 KNOWLEDGE REPRESENTATION - AI 39

Modus Tollens

25-11-2022 KNOWLEDGE REPRESENTATION - AI 40

And Elimination, Unit Resolution

25-11-2022 KNOWLEDGE REPRESENTATION - AI 41

DNF and CNF
DNF: Disjunctive Normal Form
◦ OR of ANDs (terms)
e.g. (p∧¬q) ∨ (¬p∧¬r)

CNF: Conjunctive Normal Form

◦ AND of ORs (clauses)
e.g. (p∨¬q) ∧ (¬p∨¬r)

25-11-2022 KNOWLEDGE REPRESENTATION - AI 42

Wumpus world – Knowledge Base
Atomic propositions

25-11-2022 KNOWLEDGE REPRESENTATION - AI 43

Wumpus world – Knowledge Base

25-11-2022 KNOWLEDGE REPRESENTATION - AI 44

Propositional Rules

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).

25-11-2022 KNOWLEDGE REPRESENTATION - AI 45

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:

25-11-2022 KNOWLEDGE REPRESENTATION - AI 46

Inference
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

25-11-2022 KNOWLEDGE REPRESENTATION - AI 47

Inference
•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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 48

Inference
•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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 49

Inference
•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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 50

Inference
•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].

25-11-2022 KNOWLEDGE REPRESENTATION - AI 51

 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."

25-11-2022 KNOWLEDGE REPRESENTATION - AI 52

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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 53

First-order Logic
First-order logic (FOL) models the world in
terms of

◦ Objects, which are things with individual Examples:

identities Objects: Students, lectures…
◦ Properties of objects that distinguish them Relations: Brother-of,
from other objects bigger-than, outside..
◦ Relations that hold among sets of objects Properties: blue, oval, even,
large, ...
◦ Functions, which are a subset of relations
where there is only one “value” for any Functions: father-of,
given “input” best-friend, second-half,
one-more-than ...
25-11-2022 KNOWLEDGE REPRESENTATION - AI 54
Basic Element in FOL

25-11-2022 KNOWLEDGE REPRESENTATION - AI 55

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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 56

 Parts of FOL
First-order logic statements can be divided into two
parts:
•Subject: Subject is the main part of the statement.
•Predicate: A predicate can be defined as a relation,
which binds two atoms together in a statement.

Consider the statement: "x is an integer.", it consists

of two parts, the first part x is the subject of the
statement and second part "is an integer," is known as
a predicate.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 57

Quantifiers in First-order logic
A quantifier is a language element which generates quantification, and
quantification specifies the quantity of specimen in the universe of discourse.

These are the symbols that permit to determine or identify the range and scope
of the variable in the logical expression. There are two types of quantifier:
Universal Quantifier, (for all, everyone, everything)
Existential quantifier, (for some, at least one).

25-11-2022 KNOWLEDGE REPRESENTATION - AI 58

Universal Quantifier
Universal quantifier is a symbol of logical representation, which specifies that the statement
within its range is true for everything or every instance of a particular thing.
The Universal quantifier is represented by a symbol ∀, which resembles an inverted A.
If x is a variable, then ∀x is read as:
•For all x
•For each x
•For every x.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 59

Universal Quantifier
Example: All man drink coffee.
Let a variable x which refers to a man so all x can be represented in UOD as below:

It will be read as: There are all x where x is a

man who drink coffee.
25-11-2022 KNOWLEDGE REPRESENTATION - AI 60
Existential Quantifier
Existential quantifiers are the type of quantifiers, which express that the
statement within its scope is true for at least one instance of something.
It is denoted by the logical operator ∃, which resembles as inverted E.
When it is used with a predicate variable then it is called as an existential
quantifier.
If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be
read as:

25-11-2022 KNOWLEDGE REPRESENTATION - AI 61

Existential Quantifier

It will be read as: There are some x where x is a

boy who is intelligent.
25-11-2022 KNOWLEDGE REPRESENTATION - AI 62
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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 63

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).

25-11-2022 KNOWLEDGE REPRESENTATION - AI 64

Examples of FOL
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=
subject.
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)].

25-11-2022 KNOWLEDGE REPRESENTATION - AI 65

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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 66

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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 67

The Unification Algorithm

25-11-2022 KNOWLEDGE REPRESENTATION - AI 68

Unification Example

Let Ψ1 = King(x), Ψ2 = King(John),

Substitution θ = {John/x} is a unifier for these
atoms and applying this substitution, and both
expressions will be identical.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 69

Unification Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 70

Conditions for Unification:
Following are some basic conditions for unification:
•Predicate symbol must be same, atoms or expression with different predicate
symbol can never be unified.
•Number of Arguments in both expressions must be identical.
•Unification will fail if there are two similar variables present in the same
expression.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 71

Resolution
Resolution is a single inference rule which can efficiently operate on
the conjunctive normal form or clausal form.
Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 72

Steps for resolution

25-11-2022 KNOWLEDGE REPRESENTATION - AI 73

Resolution- Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 74

25-11-2022 KNOWLEDGE REPRESENTATION - AI 75
25-11-2022 KNOWLEDGE REPRESENTATION - AI 76
25-11-2022 KNOWLEDGE REPRESENTATION - AI 77
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)

25-11-2022 KNOWLEDGE REPRESENTATION - AI 78

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

25-11-2022 KNOWLEDGE REPRESENTATION - AI 79

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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 80

Forward Chaining
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)

25-11-2022 KNOWLEDGE REPRESENTATION - AI 81

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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 82

FC: 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
∃x Owns(Nono, x) ∧ Missiles(x)

Owns(Nono, M1) and Missle(M1)

…all of its missiles were sold to it by Col. West
∀x Missle(x) ∧ Owns(Nono, x) ⇒ Sells( West, x, Nono)

Missiles are weapons

Missle(x) ⇒ Weapon(x)

25-11-2022 KNOWLEDGE REPRESENTATION - AI 83

FC: Example Knowledge Base
An enemy of America counts as “hostile”
Enemy( x, America ) ⇒ Hostile(x)

Col. West who is an American

American( Col. West )

The country Nono, an enemy of America

Enemy(Nono, America)

25-11-2022 KNOWLEDGE REPRESENTATION - AI 84

FC: Example Knowledge Base

25-11-2022 KNOWLEDGE REPRESENTATION - AI 85

FC: Example Knowledge Base

25-11-2022 KNOWLEDGE REPRESENTATION - AI 86

FC: Example Knowledge Base

25-11-2022 KNOWLEDGE REPRESENTATION - AI 87

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.

25-11-2022 KNOWLEDGE REPRESENTATION - AI 88

Backward Chaining Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 89

 Backward Chaining Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 90

 Backward Chaining Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 91

Backward Chaining Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 92

 Backward Chaining Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 93

 Backward Chaining Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 94

 Backward Chaining Example

25-11-2022 KNOWLEDGE REPRESENTATION - AI 95

 Thank You

25-11-2022 KNOWLEDGE REPRESENTATION - AI 96