Unit-2

1. Write a note on Knowledge-based Agents.

Knowledge-based agents have explicit representation of knowledge that can

be reasoned. They maintain internal state of knowledge, reason over it,
update it and perform actions accordingly. These agents act intelligently
according to requirements.
A knowledge-based system has following features:
- Knowledge base (KB): It is the key component of a knowledge-based
agent. These deal with real facts of world. It is a mixture of
sentences which are explained in knowledge representation language.
- Inference Engine (IE): It is knowledge-based system engine used
to infer new knowledge in the system.
Actions performed by an agent:
Inference System is used when we want to update some information in
Knowledge-Based System and to know the already present information.
This mechanism is done by TELL and ASK operations.
Actions done by KB agent:
- It TELLS what it recognized from the environment and what it needs
to know to the knowledge base.
- It ASKS what actions to do? And gets answers from the knowledge base.
- It TELLS the which action is selected, then agent will execute
that action.
Algorithm:
Function KB_AGENT (percept) returns an action
KB: knowledge base
t : time (counter initially 0)
TELL(KB, MAKE_PERCEPT_SENTENCE(percept, t))
action = ASK(KB, MAKE_ACTION_QUERY (t))
TELL(KB, MAKE_ACTION_SENTENCE(action, t))
t=t+1
return action
 A knowledge based system behavior can be designed in following approaches:
- Declarative Approach: In this beginning from an empty knowledge
base, the agent can TELL sentences one after another till the agent has
knowledge of how to work with its environment.
- Procedural Approach: This converts required behaviors directly
into program code in empty knowledge-based system.
2. Write a note on Knowledge-base for Wumpus World.

Atomic Proposition variable for Wumpus world:

o Let Pi,j be true if there is a Pit in the room [i, j].
o Let Bi,j be true if agent perceives breeze in [i, j], (dead or alive).
o Let Wi,j be true if there is wumpus in the square[i, j].
o Let Si,j be true if agent perceives stench in the square [i, j].
o Let Vi,j be true if that square[i, j] is visited.
o Let Gi,j be true if there is gold (and glitter) in the square [i, j].
o Let OKi,j be true if the room is safe.
Some Propositional Rules for the Wumpus world:

Representation of Knowledge Base for Wumpus World:

Following is the simple KB for Wumpus world when an agent moves from room
[1,1] to room [2,1]:

Here in the first row, we have mentioned propositional variables for

room[1,1], which is showing that 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).
In the second row, we have mentioned propositional variables for room [1,2],
which is showing that there is no wumpus, stench and breeze are unknown as
an agent has not visited room [1,2], no Pit, not visited yet, and the room is
safe.
In the third row we have mentioned propositional variable for room[2,1],
which is showing that there is no wumpus(¬ W21), no stench (¬S21), no Pit
(¬P21), Perceives breeze(B21), no glitter(¬G21), visited (V21), and room is safe
(OK21).
3. List the properties and PEAS with respect to Wumpus world
game.
The Wumpus world is a cave with 16 rooms (4x4). Each room is connected to
others through walkways. The knowledge-based agent starts from Room[1,
1]. The cave has – some pits, a treasure and a beast named Wumpus. The
Wumpus can not move but eats the one who enters its room. If the agent
enters the pit, it gets stuck there. The goal of the agent is to take the
treasure and come out of the cave. The agent is rewarded, when the goal
conditions are met. The agent is penalized, when it falls into a pit or being
eaten by Wumpus.
Some elements support the agent to explore the cave, like
- The Wumpus’s adjacent rooms are stenchy.
- The agent is given one arrow which it can use to kill the Wumpus when
facing it.
- The adjacent rooms of the room with pits are filled with breeze
- The treasure room is always glittery.

PEAS Description for the Wumpus World problem:

a. Performance measures:
- Agent gets the gold and return back safe = +1000 points
- Agent dies = -1000 points
- Each move of the agent = -1 point
- Agent uses the arrow = -10 points
b. Environment:
- A cave with 16(4x4) rooms
- Rooms adjacent to the Wumpus are stinking
- Rooms adjacent to the pit are breezy
- The room with the gold glitters
- Agent’s initial position – Room[1,1] and facing right side
 - Location of Wumpus, gold and 3 pits can be anywhere, except in Room[1,1]
c. Actuators:
Devices that allow the agent to perform the following actions in the
environment.
- Move forward
- Turn right
- Turn left
- Shoot
- Grab
- Release
d. Sensors:
Devices which helps the agent in sensing the following from the environment.
- Breeze
- Stench
- Glitter
- Scream (When the Wumpus is killed)
- Bump (when the agent hits a
wall) Wumpus World
Characterization:
- Partially Observable: Knows only the local perceptions
- Deterministic: Outcome is precisely specified
- Sequential: Subsequent level of actions performed
- Static: Wumpus, pits are immobile
- Discrete: discrete environment
- Single agent: The knowledge-based agent is the only agent whereas the
Wumpus is considered as the environment’s feature.

4. Label the term “Fundamental of Logic Reasoning”.

Logic Reasoning:
- 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.
- The above is the fundamental of logic
reasoning Logic in General
- Logics are formal languages for representing information such that
conclusion can be drawn
- Syntax defines the sentence in the language.
- Semantics define the “meaning” of sentences;
a. i.e., define truth of a sentence in a world.
- E.g., the language of arithmetic
 a. X+2 ≥ y is sentence; x2 + y > {} is not a sentence
b. X + 2 ≥ y is true iff the number x+2 is no less than the number y
c. X + 2 ≥ y is true in a world where x = 7, y = 1
d. X + 2 ≥ y is false in a world where x = 0, y = 6
Entailment:
- We have a notion of truth, we are ready to study logical reasoning, which
involves logical entailment between sentences
- Entailment means that one thing follows from another:
KB |= α
| = means double turnstile, read as “entails”
- Knowledge base KB entails sentence α if and only if α is true in all worlds
where KB is true
Models:
- We use the term “model” to represent “possible world”
- We say m is a model of a sentence α if α is true in model m
- M(α) is the set of all models of α
- Then KB |= α iff M(KB) ⊆ M(α)
Soundness and Completeness:
- An inference algorithm that derives only entailed sentences is
called sound.
- An inference algorithm is complete if it can derive any sentence that
is entailed.
- If KB is true in the real world, then any sentence derived from KB by
a sound inference procedure is also true in the real world.
5. Write a note on Entailment, Model, Soundness and
Completeness.
Entailment:
- We have a notion of truth, we are ready to study logical reasoning, which
involves logical entailment between sentences
- Entailment means that one thing follows from another:
KB |= α
| = means double turnstile, read as “entails”
- Knowledge base KB entails sentence α if and only if α is true in all worlds
where KB is true
Models:
- We use the term “model” to represent “possible world”
- We say m is a model of a sentence α if α is true in model m
- M(α) is the set of all models of α
 - Then KB |= α iff M(KB) ⊆ M(α)
Soundness and Completeness:
- An inference algorithm that derives only entailed sentences is
called sound.
- An inference algorithm is complete if it can derive any sentence that
is entailed.
- If KB is true in the real world, then any sentence derived from KB by
a sound inference procedure is also true in the real world.
6. List the basic syntax in Propositional Logic.

The syntax of propositional logic defines the allowable sentences for the
knowledge representation. There are two types of propositions:
a. Atomic Propositions
b. Compound Propositions
Atomic Proposition: Atomic proposition are the simple propositions. It
consists of a single proposition symbol. These are the sentence which must
be either true or false.
Compound Proposition: Compound preposition are constructed by combining
simpler or atomic proposition, using parenthesis and logical connectives.
7. List the basic semantics in Propositional Logic.

Propositional Logic is based on proposition, statements about the world that

can be either true or false.
Propositional Symbols
Propositional symbols are most often letters (P, Q, R) that are used to
represent a proposition.
Logical Connectives
Logical connectives are logical symbols that connect propositional symbols in
order to reason in a more complex way about the world.
- Not(~) inverses the truth value of the proposition.
P ~P
false true
true false
- And(^) connects two different propositions. When these two proposition,
P and Q, are connected by ^, the resulting proposition P ^ Q is true only
in the case that both P and Q are true
P Q P^Q
false false false
false true false
true false false
 true true true
- Or(v) is true as long as either of its arguments is true. This means that
for P v Q to be true, at least one of P or Q has to be true.
P Q PvQ
false false false
false true true
true false true
true true true
There are two types of Or: an inclusive Or and an exclusive Or. In an
exclusive Or, P v Q is false if P ^ Q is true. That is, an exclusive Or requires
only one of its arguments to be true and not both. An inclusive Or is true if
any of P, Q or P ^ Q is true. In the case of Or (v) the intention is an inclusive
Or.
- Implication (🡪) represents a structure of “if P then Q”. In the case of P

implies Q (P 🡪 Q), P is called the antecedent and Q is called the

consequent.
When the antecedent is true, the whole implication is true in the case that
the consequent is true. When the antecedent is true, the implication is false
if the consequent is false. However, when the antecedent is false, the
implication is always true, regardless of the consequent. Logically, we can’t
learn anything from an implication if the antecedent (P) is false.
P Q P🡪Q

false false true

false true true
true false false
true true true
- Biconditional(⇔) is an implication that goes both directions. You can read
it as “if and only if”.

P Q P⇔Q
false false true
false true false
true false false
 true true true

8. List the Equivalence Rules and Inference Rules with respect to

Propositional Logic.
Inference rules allows us to generate new information based on existing
knowledge without considering every possible model. Inference rules are
usually represented using a horizontal bar that separates the top part, the
premise, from the bottom part, the conclusion. The premise is whatever
knowledge we have, and the conclusion is what knowledge we have, and the
conclusion is what knowledge can be generated based on the premise.
Modus Ponens:
It is a fancy way of saying that if we know an implication and its antecedent
to be true, then the consequent is true as well.

And Elimination:
If an And proposition is true, then any atomic proposition within it is true
as well.

Implication Elimination:
An implication is equivalent to an Or relation between the negated
antecedent and the consequent.
However, consider the following truth table:
P Q P🡪Q ~P v Q

false false true true

false true true true
true false false false
true true true true
Biconditional Elimination:
A biconditional proposition is equivalent to an implication and its inverse with
an And connective.

De Morgan’s Law:
It is possible to turn an And connective into an Or connective.

Similarly, it is possible to conclude the reverse.

 Distributive Property:
A proposition with two elements that are grouped with And or ‘Or’
connectives can be distributed, or broken down into, smaller units consisting
of ‘And’ and ‘Or’.

9. Write a note on Resolution process and CNF regarding the

Propositional Logic.
Resolution is a powerful inference rule that states that if one of two atomic
proposition in an Or proposition is false, the other has to be true. More
formally, we can define resolution the following way:

Resolution relies on Complementary Literals, two of the same atomic

propositions where one is negated and the other is not, such as P and ~P.
Complementary literals allows us to generate new sentences through
inferences by resolution. Thus, inference algorithms locate complementary
literals to generate new knowledge.
A Clause is a disjunction of literals. A disjunction consists of propositions
that are connected with an Or logical connective. A conjunction, on the other
hand, consists of propositions that are connected with an And logical
connective. Clauses allows us to convert any logical statement into a
Conjunctive Normal Form (CNF), which is a conjunction of clauses.
Steps in Conversion of Propositions to Conjunctive Normal Form
- Eliminate biconditionals

a. Turn α β into (α 🡪 β) ^ (β 🡪 α)

- Eliminate implications

a. Turn (α 🡪 β) into ~α v β

- Move negation inwards until only literals are being negated, using De
Morgan’s Laws.
a. Turn ~(α ^ β) into ~α v ~β
Occasionally, through the process of inference by resolution, we might end
up in cases where a clause contains the same literal twice. In these cases,
a process called factoring is used, where the duplicate literal is removed.
Resolving a literal and its negation, i.e. ~P and P, gives the empty clause ().
The empty clause is always false, and this makes sense because it is
impossible that both P and ~P are true. Thus fact is used by the resolution
algorithm.
- To determine KB |= α:
a. Check: is (KB ^ ~α) a contradiction?
If so, then KB |= α
Otherwise, no entailment.
Proof by contradiction is a tool used often in computer science. If our
knowledge base is true, and it contradicts ~α, it means that ~α is false, and,
therefore, α must be true. More technically, the algorithm would perform
the following actions:
- To determine if KB |= α:
 a. Convert (KB ^ ~α) to conjunctive normal form
b. Keep checking to see if we can use resolution to produce a new clause.
c. If we ever produce the empty clause, congratulations! We have
arrived at a contradiction, thus proving that KB |= α.
d. However, if contradiction is not achieved and no more clauses can be
inferred, there is no entailment.
10. Label the term “Horn Clauses” and list its properties.

Why Horn Clauses?

- In many practical situations, however, the full power of resolution is
not needed.
- Real-world KBs often contain some restricted clauses – Horn
clauses Horn Form:
- KB = conjunction of Horn clauses
- Horn clause = disjunction of literals of which at most one is
positive Properties of Horn Clauses:
- Every horn clause can be written as an implication whose premise is a
conjunction of positive literals and whose conclusion is a single positive
literal.
- Modus Ponens (for Horn Form): complete for Horn KBs

a1, …, an a1 ^ … ^ an 🡪 β
β
- Definite clause: horn clauses with exactly one positive literal
a. The positive literal is called the head and the negative literals from
the body
b. Definite clauses form the basis for logic programming
- Can be used with forward chaining or backward chaining
- These algorithms are very natural and run in linear time.
-

LONG Answers:

1. Explain the concept of Forward Chaining and Backward

Chaining in Propositional Logic with a suitable example.
Forward Chaining:
Forward chaining is a form of reasoning which start with atomic sentences in
the knowledge base and applies inference rules in the forward direction to
extract more data until a goal is reached.
Properties of Forward-Chaining:
- It is a down-up approach, as it moves from bottom to top.
- It is a process of making a conclusion based on known facts or data,
by starting from the initial state and reaches the goal state.
 - Forward-chaining approach is also called as data-driven as we reach
to goal using available data.
- Forward – chaining approach is commonly used in the expert system,
such as CLIPS, business, and production rule system.
Example:
"As per the law, it is a crime for an American to sell weapons to
hostile nations. Country A, an enemy of America, has some missiles,
and all the missiles were sold to it by Robert, who is an American
citizen."
Prove that "Robert is criminal."
Facts Conversion into FOL:
o It is a crime for an American to sell weapons to hostile nations. (Let's say
p, q, and r are variables)
American (p) 𝖠 weapon(q) 𝖠 sells (p, q, r) 𝖠 hostile(r) →
Criminal(p) ...(1)
o Country A has some missiles. ?p Owns(A, p) 𝖠 Missile(p). It can be written
in two definite clauses by using Existential Instantiation, introducing new
Constant T1.
Owns(A, T1) (2)
Missile(T1) (3)
o All of the missiles were sold to country A by Robert.
?p Missiles(p) 𝖠 Owns (A, p) → Sells (Robert, p, A) (4)
o Missiles are weapons.
Missile(p) → Weapons (p) (5)
o Enemy of America is known as hostile.
Enemy(p, America) →Hostile(p) (6)
o Country A is an enemy of America.
Enemy (A, America) (7)
o Robert is American
American(Robert). (8)
Forward Chaining proof:
Step-1:

Step-2:
Step-3:

Backward Chaining:
Backward chaining algorithm is a form of reasoning, which starts with
the goal and works backward, chaining through rules to find known facts
that support the goal.
Properties of Backward chaining:
- It is known as a top-down approach
- Backward-chaining is based on modus ponens inference rule.
- In Backward chaining, the goal is broken into sub-goal or sub-goals to
prove the facts true.
- It is called a goal driven approach, as a list of goals decides which rules
are selected and used.
- Backward – chaining algorithm is used in game theory, automated
theorem proving tools, inference engines, proof assistants, and various
applications.
- The backward-chaining method mostly used a depth-first search strategy
for proof.
Example:
o American (p) 𝖠 weapon(q) 𝖠 sells (p, q, r) 𝖠 hostile(r) → Criminal(p)
...(1)
Owns(A, T1) (2)
o Missile(T1)
o ?p Missiles(p) 𝖠 Owns (A, p) → Sells (Robert, p, A) (4)
o Missile(p) → Weapons (p) .......(5)
o Enemy(p, America) →Hostile(p) ........(6)
o Enemy (A, America) .........(7)
o American(Robert). ..........(8)
Backward-chaining proof:
Step-1:

Step-2:

Step-3:
Step-4:

Step-5:
2. Summarize the advantages and disadvantages of
Propositional Logic.
Pros and Cons of propositional Logic:
- Propositional logic is declarative: pieces of syntax correspond to facts.
- Propositional logic allows partial/disjunctive/negated information
(unlike most data structures and databases)
- Propositional logic is compositional: meaning of B1,1 ^ P1,2 is derived from
meaning of B1,1 and P1,2
- Meaning is propositional logic is context-independent (unlike natural
language, where meaning depends on context)
- Propositional logic has very limited expressive power (unlike
natural language)
3. Label the term FOL and lists its elements.

- First order logic is another way of knowledge representation in

artificial intelligence. 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 is a powerful language that develops information
 about the objects in a more easy way and can also express the
relationship between those objects.
- First-order logic does not only assume that the world contains facts
like propositional logic but also assumes the following things in the
world:
a. Objects: A, B, people, numbers, colors, ward, theories, squares, pits,
Wumpus, …
b. Relations: It can be unary relation such as: red, round, is adjacent,
or n-any relation such as: the sister of, brother of, has color, comes
between
c. Function: Father of, best friend, third inning of, end of, …
- As a natural language, first-order logic also has two main parts:
a. Syntax
b. Semantics
Syntax of First-Order logic:
The syntax of FOL determines which collection of symbols is a logical
expression in first-order logic. The basic syntactic elements of first-order
logic are symbols. We write statements in short-hand notation in FOL.
Basic Elements of First-order logic:
Following are the basic elements of FOL syntax:
Constant 1,2,A,John,Mumbai, cat, …
Variables X, y, z, a, b, …
Predicates Brother, Father, >, …
Function Sqrt, leftlegof, …
Connectives ^,v,~,🡪, ⇔

Equality ==
Quantifier ∀, ∃
Atomic Sentences:
- 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.
- We can represent atomic sentences as Predicate (term1, term2, ,
term n).
Complex Sentences:
- Complex sentences are made by combining atomic sentences
using connectives.
First order logic statements can be divided into two parts:
- Subject: It is the main part of the statement.
 - Predicate: It can be defined as a relation, which binds two
atoms together in a statement.
4. Write a note on Universal Quantifier, Existential
Quantifier and Nested Quantifiers.
Quantifiers allows us to determine or identify the range and scope of the
variable in a logical expression.
There are two quantifiers:
a. Universal quantifier: For all, everyone, everything.
b. Existential quantifier: for some, at least
one. Universal quantifier:
Universal quantifiers specify that the statement within the range is true for
everything or every instance of a particular.
Universal quantifiers are denoted by a symbol(∀) that looks like an inverted

A. In a universal quantifier, we use 🡪.

If x is a variable, then ∀x can read as:
a. For all x
b. For every x
c. For each x
Existential
quantifier:
Existential quantifiers are used to express that the statement within their
scope is true for at least one instance of something.
∃, which looks like an inverted E, is used to represent them. We always use
AND or conjunction symbols.
If x is a variable, the existential quantifier will be ∃x:
a. For some x
b. There exists an x
c. For at least
one x Nested
quantifiers::
We can use both quantifiers together, but its not a type of quantifier;
rather, it’s an outlier category.
- Nested quantifier refers to when one quantifier is within the scope
of another quantifier,
- These quantifiers can be represented using the ∃x∀x signs.
- Here are some examples to understand this type of quantifier.
 ∃xy ∀x ∀y((x< 0) 𝖠 (y< 0) → (xy = 8))

5. Define the term “Kinship Domain”

The kinship domain:

1. Domain objects: humans
 2. Two unary predicates Male and Female, binary predicates for
kinship relations
3. Functions for Mother and Father since they are unique for an individual.
• One's mother is one's female parent:
∀m,c Mother(c) = m ⇔ (Female(m) 𝖠 Parent(m,c))
• Husband is one’s male spouse:
∀w,h Husband (w,h) ⇔ (Male(h) 𝖠 Spouse (h,w))
• Male and female are disjoint categories:
∀x Male(x) ⇔ ¬Female(x)
• Parent and child are inverse relations:
∀p,c Parent(p,c) ⇔ Child(c,p)
• “Sibling” is symmetric
∀x,y Sibling(x,y) ⇔ Sibling(y,x)
• A grandparent is a parent of one’s parents:
∀g,c Grandparent(g,c) ⇔ ∃p Parent(g,p) 𝖠 Parent(p,c)
• A sibling is another child of one’s parents:
∀x,y Sibling(x,y) ⇔ x≠y 𝖠 ∃ p Parent(p,x) 𝖠 Parent(p,y)
6. List the steps for Inference in FOL.

FOL inference rules for quantifier:

First-order logic has inference rules similar to propositional logic, therefore
here are some basic inference rules in FOL:
- Universal Generalization
- Universal Instantiation
- Existential Instantiation
- Existential Introduction
Universal Generalization:
- Universal generalization is a valid inference rule that states that if
premise P(c) is true for any arbitrary element c in the universe of
discourse, we can arrive at the conclusion x P(x)
- It can be represented as:
- If we want to prove that every element has a similar property, we
can apply this rule.
- x must not be used as a free variable in this rule.
Universal Instantiation:
- A valid inference rule is universal instantiation, often known as universal
elimination or UI. It can be used to add additional sentences many
times.
 - The new knowledge base is logically equal to the existing knowledge base.
- We can infer any phrase by replacing a ground word for the
variable according to UI
- The UI rule say that we can infer any sentence P(c) by substituting a
ground term c from ∀ x P(x) for any object in the universe of discourse.
- It can be represented as

Existential Instantiation:
- Existential instantiation is also known as Existential Elimination, and it
is a legitimate first-order logic inference rule.
- It can only be used to replace the existential sentence once.
- Although the new KB is not conceptually identical to the old KB, it will
be satisfiable if the old KB was.
- This rule states that for a new constant symbol c, one can deduce
P(c) from the formula given in the form of x P(x).
- The only constraint with this rule is that c must be a new word for which
P(c) is true.
- It’s written like this:

Existential Introduction:
- An existential generalization is a valid inference rule in first-order
logic that is also known as an existential introduction.
- This rule argues that if some element c in the universe of discourse
has the property P, we can infer that something in the universe has the
attribute P.
- It’s written like this:

7. Explain the process of Unification and Lifting.

Generalized Modus Ponens Rule:

- In FOL, we use a single inference rule called Generalized Modus Ponens
for the inference process. It’s modified form of Modus ponens.
- “P implies Q, and P is declared to be true, hence Q must be true,”
summarizes Generalized Modus Ponens.
 - Modus Ponens states that for atomic phrases pi, pi’, q. Where there is
a substitution θ such that SUBST (θ, pi',) = SUBST(θ, pi), it can be
represented as:

Unification:
- GMP is a lifted version of Modus Ponens – raises Modus Ponens from
propositional to first-order logic
- Lifted inference rules require finding substitutions that make
different logical expression look identical
- This process is called unification and is a key component of all first-order
inference algorithms.
- The unify algorithm takes two sentences and returns a unifier for
them if one exists:
UNIFY(p, q) = θ where Subst(θ, p) = Subst(θ, q)

p q θ
Knows(John, x) Knows(John, Jane) {x/Jane}
Knows(John, x) Knows(y, OJ) {x/OJ, y/John}
Knows(John, x) Knows(y, Mother(y)) {y/John,
x/Mother(John)}
Knows(John, x) Knows(x, OJ) {fail}
Standardizing apart: renaming variables to avoid name clashes
UNIFY(Knows(John, x), Knows(z, OJ)) = {x/OJ, z/John}
- To unify Knows(John, x) and Knows(y, z), θ = { y/John, x/z } or θ =
{ y/John, x/John, z/John}
- The first unifier is more general than the second
- There is a single most general unifier (MGU)
- MGU = {y/John, x/z}

8. List the differences between Backward and Forward

Chaining.
Forward Chaining Backward Chaining
When based on available data a Backward chaining starts from the
decision is taken then process goal and works backward to
is called as Forward chaining determine what facts must be
asserted so that the goal can be
achieved.
 Forward chaining is known as data- Backward chaining is known as goal-
driven techniques because we driven technique because we start
reaches to the goal using the from the goal and reaches the
available data. initial state in order to extract the
facts.
It is a bottom-up approach It is a top-down approach
It applies the Breadth-First It applies the Depth-First
Strategy Strategy.

Its goal is to get the conclusion Its goal is to get the possible
facts or the required data.

Slow as it has to use all the rules. Fast as it has to use only few rules.
It operates in forward direction i.e. It operates in backward direction
it works from initial state to final
i.e. it works from goal to reach
decision.
initial state.
Forward chaining is used for the It is used in automated inference
planning, monitoring, control, and engines, theorem proofs, proof
interpretation application assistants and other artificial
intelligence applications.

9. Explain the steps for resolution with a suitable example.

Consider the following knowledge base:

a. Gita likes all kinds of food
b. Mango and chapati are food
c. Gita eats almond and is still alive
d. Anything eaten by anyone and is still alive is food
Goal: Gita likes almond
Solution: Convert the given sentences into FOPL as:
Let, x be the light sleeper.
a. ?x: food(x) ? likes(Gita, x)
b. Food(Mango), food(chapati)
c. ?x?y: eats(x,y) ? ~ killed(x ? food(y))
d. Eats(Gita, almonds) ? alive(Gita)
e. ?x: ~killed(x) ? alive(x)
f. ?x: alive(x) ? ~ killed(x)
Goal: likes(Gita, almond)
Negated goal: ~likes(Gita, almond)
Now, rewrite in CNF form:
a. ~food(x) v likes(Gita, x)
b. Food(Mango), food(chapati)
 c. ~eats(x, y) v killed(x) v food(y)
d. Eats(Gita, almond), alive(Gita)
e. Killed(x) v alive(x)
f. ~alive(x) v ~killed(x)
Finally, construct the resolution graph:

Hence, we have achieved the given goal with the help of Proof by
Contradiction. Thus, it is proved that Gita likes almond.
10. Consider the following statements.
a. John likes all kind of food

b. Apple and vegetable are food

c. Anything anyone eats and not killed is food.

d. Anil eats peanuts and still alive

e. Harry eats everything that Anil eats.

Prove by resolution that: “John likes peanuts”.

Step-1: Conversion of Facts into FOL

Step-2: Conversion of FOL into CNF

- Eliminate all implication (🡪) and rewrite

∀x ¬ food(x) V likes(John, x)
food(Apple) Λ food(vegetables)
∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)
eats (Anil, Peanuts) Λ alive(Anil)
∀x ¬ eats(Anil, x) V eats(Harry, x)
∀x¬ [¬ killed(x) ] V alive(x)
∀x ¬ alive(x) V ¬ killed(x)
likes(John, Peanuts).
- Move negation (~) inwards and rewrite
∀x ¬ food(x) V likes(John, x)
food(Apple) Λ food(vegetables)
∀x ∀y ¬ eats(x, y) V killed(x) V food(y)
eats (Anil, Peanuts) Λ alive(Anil)
∀x ¬ eats(Anil, x) V eats(Harry, x)
∀x ¬killed(x) ] V alive(x)
∀x ¬ alive(x) V ¬ killed(x)
likes(John, Peanuts).
- Rename variables or standardize variables
∀x ¬ food(x) V likes(John, x)
food(Apple) Λ food(vegetables)
∀y ∀z ¬ eats(y, z) V killed(y) V food(z)
eats (Anil, Peanuts) Λ alive(Anil)
∀w¬ eats(Anil, w) V eats(Harry, w)
∀g ¬killed(g) ] V alive(g)
∀k ¬ alive(k) V ¬ killed(k)
 likes(John, Peanuts).
- Eliminate existential instantiation quantifier by elimination.
In this step, we will eliminate existential quantifier ∃, and this process is
known as Skolemization. But in this problem since there is no existential
quantifier so all the statements will remain same in this step.
- Drop Universal quantifiers.
In this step we will drop all universal quantifier since all the statements
are not implicitly quantified so we don’t need it.
¬ food(x) V likes(John, x)
food(Apple)
food(vegetables)
¬ eats(y, z) V killed(y) V food(z)
eats (Anil, Peanuts)
alive(Anil)
¬ eats(Anil, w) V eats(Harry, w)
killed(g) V alive(g)
¬ alive(k) V ¬ killed(k)
likes(John, Peanuts).
- Distribute conjunction ^ over disjunction ~.
This step will not make any change in this problem.
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)
Step-4: Draw Resolution graph