UNIT II

Knowledge Representation & Reasons

Importance of Knowledge Representation in AI:
 Helps in Decision Making
 Supports Reasoning
 Improves Problem Solving
 Enables Learning
 Facilitates Communication
 Handles Complex Information
Knowledge Representation
Knowledge Representation (KR) is the process of representing information about the
world in a formal language (A formal language is a language with well-defined
symbols, grammar (syntax), and rules for writing valid statements ) so that an
intelligent agent can store, understand, and use that information to make
decisions. In a knowledge-based agent, all information is stored in a Knowledge Base
(KB) as logical sentences written in a knowledge representation language.
Each sentence represents an assertion or fact about the environment. Knowledge
representation enables the agent to organize information systematically and use it
for reasoning, planning, and problem solving. Instead of hard-coding behaviour,
the agent stores knowledge explicitly, making it easier to update and extend its
capabilities.
Reasoning
Reasoning is the process of deriving new knowledge or conclusions from the facts
already stored in the knowledge base. It uses an inference mechanism to analyze
existing knowledge and determine information that was not explicitly provided. A
knowledge-based agent reasons by applying logical rules to stored facts, allowing it
to make intelligent decisions even in situations where complete information is
unavailable. The reasoning process ensures that the conclusions drawn by the agent
logically follow from the knowledge available in the knowledge base.
Knowledge Representation = Storing knowledge.
Reasoning = Using that knowledge to reach conclusions and decide actions.
Logical Agents
A Logical Agent is an intelligent agent that represents knowledge using logic and
uses reasoning (inference) to decide what action to perform.
Unlike simple reflex agents that respond directly to percepts, logical agents
maintain knowledge about the environment and reason before acting.
The basic idea behind logical agents is similar to human intelligence: humans know
facts about the world, reason with that knowledge, and then decide what actions to
take.
Logical agents use:
 Knowledge Representation
 Logical Reasoning
 Inference
 Decision Making

This approach enables agents to solve more complex problems than simple problem-
solving agents because they can derive new information from existing knowledge
rather than relying only on predefined actions.
Why Logical Agents?
Problem-solving agents (such as BFS, DFS, and A*) have limited knowledge.
For example,
 They know how actions change states.
 But they cannot derive new facts.
Example:
An 8-puzzle program knows how tiles move.
However, it cannot conclude:
 Two tiles cannot occupy the same square.
 Certain puzzle states are impossible.
Logical agents overcome these limitations by storing explicit knowledge and
performing logical reasoning.
Knowledge-Based Agents
A Knowledge-Based Agent is an AI agent that maintains a Knowledge Base (KB)
containing facts and rules about the world. It uses an inference engine to derive new
knowledge and decide the best action based on its current knowledge and percepts.
A Knowledge-Based Agent (KBA) is an intelligent agent whose central component is
a Knowledge Base (KB). The knowledge base stores facts about the environment in
the form of logical sentences.
The agent continuously receives percepts from the environment, stores them in the
knowledge base, reasons about them using inference techniques, and then selects the
most appropriate action.
Because knowledge is explicitly represented, the agent can answer questions, derive
new facts, and modify its behavior when new information becomes available.

Components of Knowledge-Based Agent

1. Environment
The environment is the external world in which the agent operates. It contains
objects, events, and situations that the agent needs to observe and interact with. The
environment continuously provides information (called percepts or inputs) to the
agent through its sensors.
Example:
In the Wumpus World, the environment consists of rooms containing the Wumpus,
pits, gold, and empty spaces.
2. Input from Environment
The input represents the percepts received by the agent from the environment. These
percepts provide information about the current state of the surroundings.
Example:
 Breeze
 Stench
 Glitter
 Bump
 Scream
These percepts become new knowledge that the agent stores in its knowledge base.
3. Knowledge Base (KB)
The Knowledge Base is the memory of the agent. It stores facts, rules, and
previously acquired knowledge about the environment.
The knowledge base contains:
 Facts obtained from sensors.
 General rules about the environment.
 Previously inferred information.
 Results of earlier actions.
Breeze at (2,1)
If there is a breeze,
then there is a pit in one of the adjacent rooms.
Room (1,1) is safe.
The knowledge base is continuously updated whenever the agent receives new
information.
4. Inference Engine
The Inference Engine is the reasoning component of the agent. It examines the
information stored in the knowledge base and applies logical inference rules to derive
new knowledge.
Its main functions are:
 Reads facts from the Knowledge Base.
 Applies logical rules.
 Deduces new conclusions.
 Decides the best action.
Example:
Knowledge Base contains:There is a Breeze in Room (2,1).
A Breeze indicates that a Pit exists in one of the neighboring rooms.
Inference Engine concludes:
There may be a Pit in Room (2,2) or Room (3,1).
This newly inferred knowledge helps the agent avoid dangerous rooms.
5. Learning (Updating KB)
The Learning component improves the agent's performance by updating the
knowledge base whenever new experiences or observations are obtained.
Learning performs the following tasks:
 Adds new facts.
 Removes incorrect information.
 Updates existing rules.
 Improves future decision-making.
As the agent explores more of the environment, its knowledge becomes richer and
more accurate.
Example:
Initially:
Room (2,2) may contain a pit.
After exploration:
Room (2,2) is safe.
The learning component updates the Knowledge Base accordingly.

6. Output (Action)
After reasoning, the agent produces an output, which is the action to be performed.
Possible actions include:
 Move Forward
 Turn Left
 Turn Right
 Grab Gold
 Shoot Arrow
 Climb Out
The selected action is sent to the environment through the agent's actuators.
The Wumpus world:
Wumpus World is a classic imaginary environment used in Artificial Intelligence (AI)
to demonstrate how a knowledge-based agent uses logic and reasoning to make
intelligent decisions.
The Wumpus World is a classic artificial intelligence environment used to
demonstrate the capabilities of knowledge-based agents. It is designed to show how
an intelligent agent can use knowledge representation, logical reasoning, and
inference to make decisions in an environment where complete information is not
available.
Wumpus World is a cave-like environment consisting of rooms connected by
passageways. Lurking somewhere in the cave is the terrible wumpus, a beast that eats
anyone who enters its room. The wumpus can be shot by an agent, but the agent has
only one arrow. Some rooms contain bottomless pits that will trap anyone who
wanders into these rooms (except for the wumpus, which is too big to fall in). An AI
agent explores the cave to find the gold, avoid pits, and escape from the Wumpus
(a dangerous monster) by using logical reasoning based on percepts.
Components of Wumpus World
 Agent: Explores the cave and searches for the gold.
 Wumpus: A beast/monster that kills the agent if it enters the Wumpus's room.
 Gold: The treasure the agent wants to collect.
 Pits: Deep holes that the agent must avoid.
 Rooms: Connected squares forming a grid (typically 4 × 4).
Percepts (What the Agent Senses)
 Stench: Indicates the Wumpus is in a neighbouring room.
 Breeze: Indicates a pit is in a neighbouring room.
 Glitter: Indicates gold is in the current room.
 Bump: Indicates the agent has hit a wall.
 Scream: Indicates the Wumpus has been killed.
Goal of the Agent
1. Find the gold.
2. Avoid pits and the Wumpus.
3. Return safely to the starting position.
PEAS:
A sample wumpus world is shown in Figure 7.2. The precise definition of the task
environment is given
Performance measure: +1000 for climbing out of the cave with the gold,–1000 for
falling into a pit or being eaten by the wumpus, –1 for each action taken and –10 for
using up the arrow. The game ends either when the agent dies or when the agent
climbs out of the cave.
Environment: A4×4 grid of rooms. The agent always starts in the square labeled
[1,1], facing to the right. The locations of the gold and the wumpus are chosen
randomly, with a uniform distribution, from the squares other than the start square. In
addition, each square other than the start can be a pit, with probability 0.2.
Actuators: The agent can move Forward, Turn Left by 90◦,or Turn Right by 90◦. The
agent dies a miserable death if it enters a square containing a pit or a live wumpus. (It
is safe, albeit smelly, to enter a square with a dead wumpus.)
If an agent tries to move forward and bumps into a wall, then the agent does not
move. The action Grab can be used to pick up the gold if it is in the same square as
the agent.
The action Shoot can be used to fire an arrow in a straight line in the direction the
agent is facing. The arrow continues until it either hits (and hence kills) the wumpus
or hits a wall.
The agent has only one arrow, so only the first Shoot action has any effect. Finally,
the action Climb can be used to climb out of the cave, but only from square [1,1].
Sensors: The agent has five sensors, each of which gives a single bit of information
In the square containing the wumpus and in the directly (not diagonally) adjacent
squares, the agent will perceive a Stench.
In the squares directly adjacent to a pit, the agent will perceive a Breeze.
In the square where the gold is, the agent will perceive a Glitter.
When an agent walks into a wall, it will perceive a Bump.
When the wumpus is killed, it emits a woeful Scream that can be perceived any
where in the cave.

The percepts will be given to the agent program in the form of a list of five symbols;
for example, if there is a stench and a breeze, but no glitter, bump, or scream, the
agent program will get [Stench, Breeze, None, None, None].
Percept Value Meaning
Stench None No Wumpus nearby
Breeze None No pit nearby
Glitter None No gold here
Bump None Didn't hit a wall
Scream None Wumpus is alive

The figures show how a Knowledge-Based Agent works in the Wumpus World
by perceiving the environment, updating its knowledge base, reasoning, and
choosing safe actions.
Let us watch a knowledge-based wumpus agent exploring the environment shown in
Figure 7.2. We use an informal knowledge representation language consisting of
writing down symbols in a grid (as in Figures 7.3 and 7.4).
The agent’s initial knowledge base contains the rules of the environment, as
described previously; in particular, it knows that it is in [1,1] and that [1,1] is a safe
square; we denote that with an “A” and “OK,” respectively, in square [1,1].
The first percept is [None,None,None,None,None], from which the agent can con
clude that its neighboring squares, [1,2] and [2,1], are free of dangers—they are OK.
Fig ure 7.3(a) shows the agent’s state of knowledge at this point. A cautious agent
will move only into a square that it knows to be OK. Let us suppose the agent
decides to move forward to [2,1].
The agent perceives a breeze (denoted by “B”) in [2,1], so there must be a pit in a
neighboring square. The pit cannot be in [1,1], by the rules of the game, so there
must be a pit in [2,2] or [3,1] or both.
The notation “P?” in Figure 7.3(b) indicates a possible pit in those squares. At this
point, there is only one known square that is OK and that has not yet been visited. So
the prudent agent will turn around, go back to [1,1], and then proceed to [1,2]. The
agent perceives a stench in [1,2], resulting in the state of knowledge shown in Figure
7.4(a).
The stench in [1,2] means that there must be a wumpus nearby. But the wumpus
cannot be in [1,1], by the rules of the game, and it cannot be in [2,2] (or the agent
would have detected a stench when it was in [2,1]). T
herefore, the agent can infer that the wumpus is in [1,3]. The notation W! indicates
this inference. Moreover, the lack of a breeze in [1,2] implies that there is no pit in
[2,2]. Yet the agent has already inferred that there must be a pit in either [2,2] or
[3,1], so this means it must be in [3,1].
This is a fairly difficult inference, because it combines knowledge gained at different
times in different places and relies on the lack of a percept to make one crucial step
The agent has now proved to itself that there is neither a pit nor a wumpus in [2,2],
so it is OK to move there.
We do not show the agent’s state of knowledge at [2,2]; we just assume that the
agent turns and moves to [2,3], giving us Figure 7.4(b). In [2,3], the agent detects a
glitter, so it should grab the gold and then return home.
Note that in each case for which the agent draws a conclusion from the available in
formation, that conclusion is guaranteed to be correct if the available information is
correct. This is a fundamental property of logical reasoning.
How the Knowledge-Based Agent Thinks
The agent repeatedly follows this cycle:
Perceive
↓
Update Knowledge Base
↓
Apply Logical Rules
↓
Infer New Facts
↓
Choose Safe Action
↓
Move
↓
Repeat

Logic:
Logic is a formal language used by intelligent agents to represent knowledge and
make correct decisions through reasoning.
Instead of guessing, the agent uses facts and logical rules to infer new knowledge.
Core Concepts:
[Link]: Defines the grammar of the language. Specifies how valid logical
sentences are written. Rules specifying which sentences are well-formed in a
representation language.
“x +y =4” is a well-formed sentence, whereas “x4y+=” is not.
Example: P ∧ Q ->Valid sentence
∧ P Q->Invalid sentence
2. Semantics: Semantics defines the meaning of logical sentences.
It tells whether a sentence is True or False in a particular world.
Defines the truth of each sentence with respect to each possible world.
The semantics defines the truth of each sentence with respect to each possible world.
For example, the semantics for arithmetic specifies that the sentence “x + y =4” is
true in a world where x is 2 and y is 2, but false in a world where x is 1 and y is 1. In
standard logics, every sentence must be either true or false in each possible world—
there is no “in between.
3. Model
A model is a possible assignment of values to the variables that gives meaning to
the sentence.
. A mathematical abstraction fixing the truth/falsehood of every relevant sentence
(formalizes "possible world")
Example: Informally, we may think of a possible world as, for example, having x men
and y women sitting at a table playing bridge, and the sentence x +y=4is true when
there are four people in total. Formally, the possible models are just all possible
assignments of real numbers to the variables x and y. Each such assignment fixes the
truth of any sentence of arithmetic whose variables are x and y. If a sentence α is true
in model m, we say that m satisfies α or sometimes m is a model of α. We use the
notation M(α) to mean the set of all models of α.
Example: for the sentence “x + y = 4” where 0 < x, y <= 3
 The possible models are just all possible assignments of numbers to the
variables x and y.
 (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2) and (3,3)
 The sentence is true in a world where
o x is 1 and y is 3,
o x is 2 and y is 2 and
o x is 3 and y is 1.
 – but false in all other cases.

4. Satisfaction
A model satisfies a sentence if the sentence is true in that model. A sentence α is true
in model m → m satisfies α, or m is a model of α. M(α) = set of all models of α.
Notation is m ⊨ α means Model m satisfies sentence α.
5. Entailment (⊨)
Entailment means one statement logically follows from another.
Model checking and theorem proving are two important approaches used to
determine logical entailment.
α ⊨ β (sentence α entails sentence β) means: in every model where α is true, β is
also true → M(α) ⊆ M(β)
α|=β if and only if M(α)⊆M(β).
α : x + y = 4 β : y >= 2 For all x, y <= 3
Models(possibleassignments):
(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2) and (3,3)
Select the model which is True for the given model
α is true when x is 1 and y is 3, x is 2 and y is 2 and x is 3 and y is 1.
Β is true when x is 1 and y is 3, x is 2 and y is 2
so (1,3),(2,2) these are the ones that get stored in the Knowledge Base.

Wumpus World Illustration (Fig 7.5) for Logical Entailment:

(If the Knowledge Base (KB) is true, then the conclusion (α) must also be true.)
We can apply the same kind of analysis to the wumpus-world reasoning example
given in the preceding section. Consider the situation in Figure 7.3(b): the agent has
detected nothing in [1,1] and a breeze in [2,1]. These percepts, combined with the
agent's knowledge of the rules of the wumpus world, constitute the KB. The agent is
interested (among other things) in whether the adjacent squares [1,2], [2,2], and [3,1]
contain pits. Each of the three squares might or might not contain a pit, so (for the
purposes of this example) there are 2³ = 8 possible models. These eight models are
shown in Figure 7.5.
The KB can be thought of as a set of sentences or as a single sentence that asserts all
the individual sentences. The KB is false in models that contradict what the agent
knows—for example, the KB is false in any model in which [1,2] contains a pit,
because there is no breeze in [1,1].
There are in fact just three models in which the KB is true, and these are shown
surrounded by a solid line in Figure 7.5. Now let us consider two possible
conclusions:
α₁ = "There is no pit in [1,2]."
α₂ = "There is no pit in [2,2]."
We have surrounded the models of α₁ and α₂ with dotted lines in Figures 7.5(a) and
7.5(b), respectively. By inspection, we see the following:
 in every model in which KB is true, α₁ is also true.
Hence, KB ⊨ α₁: there is no pit in [1,2]. We can also see that
 in some models in which KB is true, α₂ is false.
Hence, KB ⊭ α₂: the agent cannot conclude that there is no pit in [2,2]. (Nor can it
conclude that there is a pit in [2,2].)
Summarization:
Agent is currently in (2,1) He felt Breeze
3 cases
1st case-No pit in any square
2nd case-pit in exactly one square
3rd case- pit in exactly two squares
4th case-pit in exactly 3 squares
The above all are the possibilities
Based on percept and Wumpus world rules consider only true models.
Percept is breeze means possibility of pit in adjacent squares How many of these
squares are true.
3 models are true so these 3 models will be in knowledge base.
Query: 1. α₁ = "no pit in [1,2]"
2. α₂ = "no pit in [2,2]"

 Agent perceives: nothing in [1,1], breeze in [2,1]

  3 relevant squares → [1,2], [2,2], [3,1] → 2³ = 8 possible models(2 possibilties
for each square and total number of squares are 3 so 2^3=8)
 Only 3 models are consistent with KB
This illustrates the concept of logical entailment:

(KB ⊨ α).
 If a statement is true in every model of the KB, then KB entails the statement

 If it is not true in every model, then the KB does not entail it (KB ⊭ α).
 in every model in which KB is true, α1 is also true. Hence, KB |= α1: there is
no pit in [1,2]. We can also see that in some models in which KB is true, α2 is
false. Hence, KB ̸ |= α2: the agent cannot conclude that there is no pit in [2,2].
(Nor can it conclude that there is a pit in [2,2].)3

The preceding example not only illustrates entailment but also shows how the
definition of entailment can be applied to derive conclusions—that is, to carry out
logical inference. The inference algorithm illustrated in Figure 7.5 is called model

models in which KB is true, that is, that M(KB) ⊆ M(α).

checking, because it enu merates all possible models to check that α is true in all

An inference algorithm that derives only entailed sentences is called sound or truth
preserving.
The property of completeness is also desirable: an inference algorithm is complete if
it can derive any sentence that is entailed.
The final issue to consider is grounding—the connection between logical reasoning
processes and the real environment in which the agent exists
How do we know KB is true in the real world? → via the agent's sensors
 Percept sentences are grounded by the sensing process itself
 General rules (e.g., "wumpus causes smell in adjacent squares") come from
learning — and learning is fallible, so KB may not be perfectly true
Propositional Logic:
Propositional logic (also called sentential logic or statement logic) is a branch of
logic that studies how propositions /statements that are either true or false can be
combined and analyzed using logical operators.
A proposition is any declarative statement that has a definite truth value. For
example:
 "The sky is blue." → True
 "2 + 2 = 5." → False
 "Close the door." → Not a proposition (it's a command, not a statement with a
truth value)

Syntax
The syntax of propositional logic defines the allowable sentences. The atomic
sentences consist of a single proposition symbol. Each such symbol stands for a
proposition that can be true or false. We use symbols that start with an uppercase
letter and may contain other letters or subscripts, for example: P, Q, R, W1,3 .
There are two proposition symbols with fixed meanings:
 True is the always-true proposition
 and False is the always-false proposition.
Complex sentences are constructed from simpler sentences, using parentheses and
logical connectives. There are five connectives in common use:
BNF (Backus–Naur Form) is a notation used to describe the syntax (grammar) of a
language.
Semantics:
Semantics defines the meaning of propositional logic sentences. It tells us whether a
sentence is True or False in a given model (possible world).
A model assigns true/false to every proposition symbol.
All sentences are constructed from atomic sentences and the five connectives;
therefore, we need to specify how to compute the truth of atomic sentences and how
to compute the truth of sentences formed with each of the five connectives. Atomic
sentences are easy:
• True is true in every model and False is false in every model.
• The truth value of every other proposition symbol must be specified directly in the
model. For example, in the model m1 given earlier, P1,2 is false.
Recursive evaluation rules: For complex sentences, we have five rules, which hold
for any subsentences P and Q in any model m (here “iff” means “if and only if”):
 ¬P is true iff P is false
 P ∧ Q is true iff both true
 P ∨ Q is true iff at least one true
  P ⇒ Q is true unless P true and Q false
 P ⇔ Q is true iff both have the same truth value
The rules can also be expressed with truth tables that specify the truth value of a
complex sentence for each possible assignment of truth values to its components.
Truth tables for the five connectives are given in Figure 7.8. From these tables, the
truth value of any sentence s can be computed with respect to any model m by a
simple recursive evaluation

about the English words. The main point of possible confusion is that P ∨Q is true
The truth tables for “and,” “or,” and “not” are in close accord with our intuitions

when P is true or Q is true or both.

Implication (⇒)
The implication operator (⇒) is read as:
 "If P, then Q"
 "P implies Q"
It means: If P is true, then Q must also be true.
Important Rule
An implication P ⇒ Q is false only in one case:
 P is True and Q is False.
In all other cases, it is True.
Example 1
Statement:
"5 is odd implies Tokyo is the capital of Japan."
Here,
 P: 5 is odd → True
 Q: Tokyo is the capital of Japan → True
Truth value:
True ⇒ True = True
Although the two statements are unrelated, the implication is True because
propositional logic only considers truth values, not meaning or causation.
Example 2:
Statement:
"5 is even implies Sam is smart."
Here,
 P: 5 is even → False
 Q: Sam is smart → May be True or False
Truth value:
False ⇒ True = True
or
False ⇒ False = True
Since the antecedent (P) is false, the implication is always True, regardless of Sam's
intelligence.
Biconditional (⇔)
The biconditional operator (⇔) is read as
 "If and only if"
 "P iff Q"
It means:
P implies Q and Q also implies P.
Both directions must be true.
Mathematically,
P ⇔ Q = (P ⇒ Q) ∧ (Q ⇒ P)
Rule
A biconditional is True only when P and Q have the same truth value.
 Both True → True
 Both False → True
 Different values → False
Wumpus World Example
The rule is
B₁,₁ ⇔ (P₁,₂ ∨ P₂,₁)
where
 B₁,₁ = Breeze is present in square [1,1]
 P₁,₂ = Pit in square [1,2]
 P₂,₁ = Pit in square [2,1]
This means:
 If there is a pit in either neighboring square, then there is a breeze in [1,1].
 If there is a breeze in [1,1], then at least one neighboring square must
contain a pit.
So the breeze and the neighboring pit condition are equivalent.
A simple knowledge base :
Now that we have defined the semantics for propositional logic, we can construct a
knowledge base for the wumpus world. We focus first on the immutable aspects of
the wumpus world, leaving the mutable aspects for a later section. For now, we need
the following symbols for each [x,y] location:

The sentences we write will suffice to derive ¬P1,2 (there is no pit in [1,2]), as was
done informally in Section 7.3. We label each sentence Ri so that we can refer to
them
• There is no pit in [1,1]:
 R1 : ¬P1,1 .
• A square is breezy if and only if there is a pit in a neighboring square. This has to be
stated for each square; for now, we include just the relevant squares:
R2 : B1,1 ⇔ (P1,2∨P2,1).
R3 : B2,1 ⇔ (P1,1∨P2,2∨P3,1).
The preceding sentences are true in all wumpus worlds. Now we include the breeze
percepts for the first two squares visited in the specific world the agent is in, leading
up to the situation in Figure 7.3(b).
R4 : ¬B1,1 .
R5 : B2,1 .
A simple inference procedure:
model-checking approach to entailment in propositional logic:
Entailment (KB ⊨ α): A sentence α is entailed by a knowledge base KB if α is
true in every model where KB is true.
Model: An assignment of truth values (True/False) to all proposition symbols.
Model Checking: Enumerate all possible models, check which satisfy KB, and
then see if α holds in all of them.
Wumpus World Example
 Relevant symbols: B1 ,1 , B2 ,1 , P1 ,1 , P1 , 2 , P2 ,1 , P 2, 2 , P3 ,1.
 With 7 symbols → 27=128 possible models.
 Only 3 models satisfy KB.
 In those 3 models:
o ¬ P1 ,2 is always true → no pit in [1,2].
o P2 ,2 is true in 2 models, false in 1 → uncertain.

TT-ENTAILS? Algorithm (Figure 7.10)

 Recursive enumeration of assignments to symbols.
 Sound: Directly implements definition of entailment.
 Complete: Works for any KB and α, always terminates (finite models).
 Complexity:
 o Time: O ( 2n )(exponential in number of symbols).
o Space: O ( n )(depth-first enumeration).

Complexity & Limitations

 Exponential growth: For n symbols → 2nmodels.

 Propositional entailment is co-NP-complete.
 All known algorithms have worst-case exponential complexity.
 Later chapters introduce more efficient methods (e.g., resolution, SAT solvers)

The table has 7 propositional symbols:

Each proposition can have 2 values: True (T) or False (F)

Since there are 7 propositions, the total number of possible models is

uses ⋮ (dots) to skip the remaining rows.

So the complete table actually has 128 rows. The book shows only a few rows and

How are the rows generated?

Think of True = 1 and False = 0.

Then every row is just like counting in binary.

R1 : ¬P1,1 .

R2 : B1,1 ⇔ (P1,2∨P2,1).

R3 : B2,1 ⇔ (P1,1∨P2,2∨P3,1).

R4 : ¬B1,1 .

R5 : B2,1 .

For each model (each row):

1. Check whether R1 is true.

2. Check whether R2 is true.
3. Check whether R3 is true.
4. Check whether R4 is true.
5. Check whether R5 is true.

 If all five rules are true, then KB = True, so that model is kept.
 If any one rule is false, then KB = False, so that model is discarded.

In propositional logic, the Knowledge Base (KB) is the conjunction (AND) of all the
rules. Therefore,

KB=R1∧R2∧R3∧R4∧R5

That is why, out of the 128 possible models, only three models satisfy all five rules
simultaneously. Those are the three rows marked with ✓ in the figure.
Propositional Theorem Proving:

If the Knowledge Base (KB) is true, then the conclusion (α) must also be true-
Logical entailment

Propositional Theorem Proving is a method of proving that a statement logically

follows from a Knowledge Base (KB) by applying logical inference rules, instead
of checking all possible models.

we will need some additional concepts related to entailment.

The first concept is logical equivalence: two sentences α and β are logically
equivalent if they are true in the same set of models. We write this as α ≡ β.

For example, we can easily show (using truth tables) that P ∧ Q and Q ∧ P are
logically equivalent; P ∧ Q ≡ Q ∧ P

An alternative definition of equivalence is as follows: any two sentences α and β are

equivalent only if each of them entails the other:
 α ≡β if and only if α |= β and β |= α.

The second concept we will need is validity. A sentence is valid if it is true in all
models

For example, the sentence P ∨¬P is valid.

Valid sentences are also known as tautologies—they are necessarily true. Because
the sentence True is true in all models, every valid sentence is logically equivalent to
True. What good are valid sentences? From our definition of entailment, we can
derive the deduction theorem, which was known to the ancient Greeks:

For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid.

The final concept we will need is satisfiability. A sentence is satisfiable if it is true

in, or satisfied by, some model.

For example, the knowledge base given earlier, (R1 ∧ R2 ∧ R3 ∧R4 ∧R5), is
satisfiable because there are three models in which it is true, as shown in Figure 7.9

Validity and satisfiability are of course connected: α is valid iff ¬α is unsatisfiable;

contrapositively, α is satisfiable iff ¬α is not valid.

We also have the following useful result: α |= β if and only if the sentence (α ∧¬β) is
unsatisfiable. Proving β from α by checking the unsatisfiability of (α ∧¬β)
corresponds exactly to the standard mathematical proof technique of reductio ad
absurdum (literally, “reduction to an absurd thing”).

It is also called proof by refutation or proof by contradiction. One assumes a

α.This contradiction is exactly what is meant by saying that the sentence (α ∧¬β) is
sentence β to be false and shows that this leads to a contradiction with known axioms

unsatisfiable.
Inference and proofs:

This section covers inference rules that can be applied to derive a proof—a chain
of conclusions that leads to the desired goal. The best-known rule is called
Modus Ponens :

{α ⇒ β , α }⊢ β
(or)

The notation means that, whenever any sentences of the form α ⇒ β and α are given,
then the sentence β can be inferred.

For example, if (WumpusAhead ∧WumpusAlive) ⇒ Shoot and (WumpusAhead

∧WumpusAlive) are given, then Shoot can be inferred.

α =¿ WumpusAhead ∧ WumpusAlive β=¿ Shoot

And-Elimination:

Another useful inference rule is And-Elimination, which says that, from a

conjunction, any of the conjuncts can be inferred:

And-Elimination is an inference rule used to get an individual statement from a

statement containing AND (∧).

(or) AND-Elimination has two forms:

If "A AND B" is true, then A is true and B is true individually.

By considering the possible truth values of α and β, one can show easily that Modus
Ponens and And-Elimination are sound once and for all. These rules can then be used
in any particular instances where they apply, generating sound inferences without the
need for enumerating models.

Biconditional elimination

Biconditional elimination is an inference rule used to remove the biconditional (⇔)

and convert it into two implication (⇒) rules.

All of the logical equivalences in Figure 7.11 can be used as inference rules. For
example, the equivalence for biconditional elimination yields the two inference rules

Not all inference rules work in both directions like this.

For example, we cannot run Modus Ponens in the opposite direction to obtain α ⇒ β
and α from β.

Let us see how these inference rules and equivalences can be used in the wumpus
world.

This is a Wumpus World logical inference example.

The goal is to prove: there is no pit in square [1,2] and no pit in square [2,1].

First, we apply biconditional elimination to R2 to obtain R6

 R2 : B1,1 ⇔ (P1,2∨ P2,1)

Step 1: Use the definition of biconditional

The biconditional can be expressed as:
 Proof search can be framed as a search problem:
• INITIAL STATE: the initial knowledge base.
• ACTIONS: the set of actions consists of all the inference rules applied to all
the sentences that match the top half of the inference rule.
• RESULT: the result of an action is to add the sentence in the bottom half of the
inference rule.
• GOAL: the goal is a state that contains the sentence we are trying to prove.
Monotonicity: KB ⊨ α ⟹ KB ∧ β ⊨ α — adding info can never invalidate prior
conclusions

Proof by Resolution:
Resolution is a single inference rule used to prove whether a query logically follows
from a Knowledge Base (KB).
It is a sound(An inference rule never produces a false conclusion when the
premises are true.), and complete (No missing conclusions) inference method for
propositional logic.
Earlier inference rules like Modus Ponens and And-Elimination are soundbut they
alone cannot prove every logical conclusion.
Resolution overcomes this limitation because it is complete, meaning it can derive
every logically entailed conclusion.
The Resolution Algorithm is a theorem-proving method used to determine whether a
query (α) logically follows from a Knowledge Base (KB). It works using the
principle of proof by contradiction (refutation).

Principle of Proof by Contradiction

Instead of proving directly that KB ⊨ α we assume the opposite is true.
That is, we add the negation of the query to the knowledge base. KB ∧ ¬α
If this assumption leads to a contradiction, then the original query α must be true.
Steps of the Resolution Algorithm
Step 1: Form the Expression
Combine the knowledge base with the negation of the query. KB ∧ ¬α
Step 2: Convert to CNF
Convert the entire expression into Conjunctive Normal Form (CNF).
Step 3: Apply Resolution
 Find pairs of clauses containing complementary literals (e.g., P and ¬P).
 Resolve them to generate new clauses.
 Add each new clause if it is not already present.
Step 4: Repeat
Continue resolving clauses until one of the following occurs:
Case 1: Empty Clause (□) is Produced
 A contradiction is found.
 Therefore,
KB ⊨ αThe query is proved.
Case 2: No New Clauses Can Be Generated
 Resolution stops.
  Therefore,
KB ⊭ α
The query cannot be proved.
Example:
Let's prove R using Proof by Resolution step by step.
Given 1. P∨Q 2. P⇒R 3. Q⇒R
Negate the conclusion ¬R
This figure shows how PL-RESOLUTION proves that
from the clauses in the top row.
The important idea is:
Resolution combines two clauses containing opposite literals and removes that
pair.

We begin by using a simple version of the resolution rule in the wumpus world. Let
us consider the steps leading up to Figure 7.4(a): the agent returns from [2,1] to [1,1]
and then goes to [1,2], where it perceives a stench, but no breeze. We add the
following facts to the knowledge base:
R11 : ¬B1,2 .
R12 : B1,2 ⇔ (P1,1 ∨P2,2 ∨P1,3) .
By the same process that led to R10 earlier, we can now derive the absence of pits in
[2,2] and [1,3] (remember that [1,1] is already known to be pitless):
R13 : ¬P2,2 .
R14 : ¬P1,3 .
We can also apply biconditional elimination to R3, followed by Modus Ponens with
R5, to obtain the fact that there is a pit in [1,1], [2,2], or [3,1]:
R15 : P1,1 ∨P2,2 ∨P3,1 .
Now comes the first application of the resolution rule: the literal ¬P2,2 in R13
resolves with the literal P2,2 in R15 to give the resolvent
R16 : P1,1 ∨P3,1 .
In English; if there’s a pit in one of [1,1], [2,2], and [3,1] and it’s not in [2,2], then it’s
in [1,1]or [3,1]. Similarly, the literal ¬P1,1 in R1 resolves with the literal P1,1 in R16
to give
R17 : P3,1

Conjunctive normal form

The resolution rule applies only to clauses (that is, disjunctions of literals), so it
would seem to be relevant only to knowledge bases and queries consisting of clauses.
How, then, can it lead to a complete inference procedure for all of propositional
logic? The answer is that every sentence of propositional logic is logically equivalent
to a conjunction of clauses.
A sentence expressed as a conjunction of clauses is said to be in conjunctive normal

We illustrate the procedure by converting the sentence B1,1 ⇔ (P1,2 ∨ P2,1) into
form or CNF (see Figure 7.14). We now describe a procedure for converting to CNF.

CNF. The steps are as follows:

1. Eliminate ⇔, replacing α ⇔ β with (α ⇒ β)∧(β ⇒ α).
(B1,1 ⇒ (P1,2 ∨P2,1)) ∧((P1,2 ∨ P2,1) ⇒ B1,1) .
2. Eliminate ⇒, replacing α ⇒ β with ¬α ∨β:
(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬(P1,2 ∨ P2,1) ∨ B1,1)
3. CNF requires ¬ to appear only in literals, so we “move ¬ inwards” by repeated
appli
cation of the following equivalences from Figure 7.11:
¬(¬α) ≡ α (double-negation elimination)
¬(α ∧β) ≡(¬α∨¬β) (DeMorgan)
¬(α ∨β) ≡(¬α∧¬β) (DeMorgan)
In the example, we require just one application of the last rule:
(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ ((¬P1,2 ∧¬P2,1) ∨B1,1) .
4. Now we have a sentence containing nested ∧ and ∨ operators applied to literals.
We
apply the distributivity law from Figure 7.11, distributing ∨ over ∧ wherever
possible.
(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬P1,2 ∨B1,1) ∧ (¬P2,1 ∨ B1,1) .
The original sentence is now in CNF, as a conjunction of three clauses. It is much
harder to read, but it can be used as input to a resolution procedure Amresolution
algorithm
Inference procedures based on resolution work by using the principle of proof by

(KB ∧¬α) isunsatisfiable. We do this by proving a contradiction.

contradicttion introduced on page 250. That is, to show that KB |= α, we show that

A resolution algorithm is shown in Figure 7.12. First, (KB ∧¬α) is converted into
CNF. Then, the resolution rule is applied to the resulting clauses. Each pair that
contains complementary literals is resolved to produce a new clause, which is added
to the set if it is not already present. The process continues until one of two things
happens:
• there are no new clauses that can be added, in which case KB does not entail α;or,
• two clauses resolve to yield the empty clause, in which case KB entails α.
The empty clause—a disjunction of no disjuncts—is equivalent to False because a
disjunction is true only if at least one of its disjuncts is true. Another way to see that
an empty clause represents a contradiction is to observe that it arises only from
resolving two complementary unit clauses such as P and ¬P.
We can apply the resolution procedure to a very simple inference in the wumpus
world.
When the agent is in [1,1], there is no breeze, so there can be no pits in neighboring
squares.
The relevant knowledge base is
KB =R2∧R4 =(B1,1 ⇔ (P1,2 ∨P2,1))∧¬B1,1 and we wish to prove α which is, say,
¬P1,2. When we convert (KB ∧¬α) into CNF, we obtain the clauses shown at the top
of Figure 7.13. The second row of the figure shows
clauses obtained by resolving pairs in the first row. Then, when P1,2 is resolved with
¬P1,2,we obtain the empty clause, shown as a small square. Inspection of Figure 7.13

B1,1∨¬B1,1∨P1,2 is equivalent to True ∨ P1,2 which is equivalent to True.

reveals that many resolution steps are pointless. For example, the clause

Deducing that True is true is not very [Link], any clause in which two
complementary literals appear can be discarded

Completeness of Resolution
 Resolution is complete means it can find a contradiction whenever the given
clauses are unsatisfiable.
 Resolution Closure, RC(S) is the set of all clauses obtained by repeatedly
applying resolution.
 RC(S) contains the original clauses and all newly derived clauses.
 RC(S) is finite because only a limited number of clauses can be formed from
the given symbols.
 Therefore, the resolution process will always terminate.
 The Ground Resolution Theorem says: if S is unsatisfiable, RC(S) contains
the empty clause (□).
 The empty clause □ means contradiction.
 To prove this, we use the contrapositive: if RC(S) does not contain □, then S is
satisfiable.
 We assign True or False values to the propositional symbols one by one to
construct a model.
 Therefore, if S is unsatisfiable, resolution will eventually derive □, proving
that resolution is complete.
Horn clauses and definite clauses:
Horn clause:
A Horn clause is a clause that contains at most one positive literal. A literal can be:
Positive( P) or Negative(¬P). =
So, a Horn clause can have:0 positive literals, or 1 positive literal.
Example: ¬P∨¬Q∨R
Positive literals = R → 1Therefore, it is a Horn clause.

Example 2: ¬P∨¬Q
Positive literals = 0 Therefore, it is also a Horn clause.
Example 3: P∨Q
Positive literals = P, Q → 2 Therefore, it is NOT a Horn clause.
Definite Clause:
A definite clause contains exactly one positive literal.
Example1: ¬P∨¬Q∨R
It can be written as an implication: P∧Q⇒R
So: If P and Q are true, then R is true.
Example 2: ¬A∨B means: A⇒B

Goal Clause / Negative Horn Clause:

A Horn clause with no positive literals is called a goal clause.
Example: ¬P∨¬Q
It can be understood as: P∧Q ⇒False
This means: P and Q cannot both be true.
Knowledge bases containing only definite clauses are interesting for three
reasons:
 1. Every definite clause can be written as an implication whose premise is a

Exercise 7.13.) For example, the definite clause (¬L1,1 ∨¬Breeze ∨ B1,1) can be
conjunction of positive literals and whose conclusion is a single positive literal. (See

written as the implication (L1,1 ∧ Breeze) ⇒ B1,1. In the implication form, the
sentence is easier to understand: it says that if the agent is in [1,1] and there is a
breeze, then [1,1] is breezy. In Horn form, the premise is called the body and the

as L1,1, is called a fact. It too can be written in implication form as True ⇒ L1,1, but
conclusion is called the head. A sentence consisting of a single positive literal, such

it is simpler to write just L1,1

2. Inference with Horn clauses can be done through the forward-chaining and
backward chaining algorithms, which we explain next. Both of these algorithms are
natural, in that the inference steps are obvious and easy for humans to follow. This
type of inference is the basis for logic programming, which is discussed in Chapter 9.
3. Deciding entailment with Horn clauses can be done in time that is linear in the size
of the knowledge base

Forward and backward chaining:

The forward-chaining algorithm PL-FC-ENTAILS?(KB,q) determines if a single
proposition symbol q—the query—is entailed by a knowledge base of definite
clauses.
It begins from known facts (positive literals) in the knowledge base. If all the
premises of an implication are known, then its conclusion is added to the set of
known facts.
For example,
if L1,1 and Breeze are known(Facts)
and (L1,1 ∧ Breeze) ⇒ B1,1 is in the knowledge base(Rules)
, then B1,1 can be derived.

This process continues until the query q is added or until no further inferences can be
made.

The best way to understand the algorithm is through an example and a picture.
Figure 7.16(a) shows a simple knowledge base of Horn clauses with A and B as
known facts. Figure 7.16(b) shows the same knowledge base drawn as an AND–OR
graph (see Chap ter 4).
In AND–OR graphs, multiple links joined by an arc indicate a conjunction—every
link must be proved—while multiple links without an arc indicate a disjunction—any
link can be proved.
It is easy to see how forward chaining works in the graph. The known leaves (here, A
and B) are set, and inference propagates up the graph as far as possible. Wher ever a
conjunction appears, the propagation waits until all the conjuncts are known before
proceeding.

1. Start: A and B are given as facts. Agenda = {A, B}.

2. Process A. A appears in the premises of A∧P⇒L (still waiting on P) and
A∧B⇒L (now only waiting on B).
3. Process B. B appears in B∧L⇒M (still waiting on L) and A∧B⇒L — its last
unsatisfied premise. Both A and B are now true, so A∧B⇒L fires: L is
inferred.
4. Process L. L appears in L∧M⇒P (still waiting on M) and B∧L⇒M — its last
unsatisfied premise (B was already known). B∧L⇒M fires: M is inferred.
5. Process M. M was the last unsatisfied premise of L∧M⇒P. It fires: P is
inferred.
6. Process P. P was the only premise of P⇒Q. It fires: Q is inferred — the goal
is reached, so inference halts.
Forward Chaining is sound and complete
Sound means:
Whatever Forward Chaining concludes is actually true according to the KB.
Forward chaining uses Modus Ponens.
Complete means:
If a conclusion is logically entailed by the KB, Forward Chaining will eventually
derive it.
Suppose the algorithm has finished. It has reached a fixed point.
Fixed point means:
No more new facts can be derived.

Forward chaining is a method of reasoning that starts with known facts/data and
uses rules to find new facts.
It is called data-driven reasoning because the reasoning starts from the available
data, not from a specific question.
Simple example

Suppose we have Facts:

It is raining.
I am indoors.
Rule: Rain → Picnic cancelled
Forward chaining works like this:
Known fact: It is raining
↓
Apply rule: If it rains → picnic is cancelled
↓
New conclusion: Picnic is cancelled
The new conclusion can then be used with other rules to derive more conclusions.
Backward-chaining algorithm
The backward-chaining algorithm, as its name suggests, works backward from the
query. If the query q is known to be true, then no work is needed.
Otherwise, the algorithm finds those implications in the knowledge base whose
conclusion is q.
If all the premises of one of those implications can be proved true (by backward
chaining), then q is true. When applied to the query Q in Figure 7.16, it works back
down the graph until it reaches a set of known facts, A and B, that forms the basis for
a proof.
The algorithm is essentially identical to the AND-OR-GRAPH-SEARCH algorithm
in Figure 4.11. As with forward chaining, an efficient implementation runs in linear
time.
Backward chaining is a form of goal-directed reasoning.

Example:

1. Goal: prove Q. Only rule concluding Q is P ⇒ Q, so the new subgoal is P.

 2. Prove P. Only rule concluding P is L ∧ M ⇒ P, so both L and M must be

3. Prove L. Rule A ∧ P ⇒ L is tried first, but P isn't known yet (proving it would
proved.

loop back into the goal we're already chasing), so it's set aside. Rule A ∧ B ⇒

4. Prove M. Only rule concluding M is B ∧ L ⇒ M — B is a known fact and L

L is tried next — A and B are both known facts, so L is proved.

was just proved in step 3, so M is proved.

5. Since L and M are both proved, P is proved.
6. Since P is proved, Q is proved.
First order logic:(FOL)
Basic Definition
Propositional Logic (PL):
• It deals with simple, declarative statements (propositions) that can either
be true or false.
• It does not concern itself with the internal structure of these propositions.
Predicate Logic (First-Order Logic - FOL):
• It extends propositional logic by dealing with the internal structure of
propositions.
• It allows reasoning about objects, their properties, and their relationships
using quantifiers like "for all" (∀) and "there exists" (∃).
Components of PL and FOL
Propositional Logic: The basic components are propositions (like p, q, r) and
logical connectives (like AND, OR, NOT, etc.).
Example: p ∨ q, ¬p.
Predicate Logic: The basic components include predicates (like P(x), Q(x, y)),
variables (like x, y), constants, quantifiers, and logical connectives.
Example: ∀x(P(x) → Q(x)).
Expressiveness
Propositional Logic:
• It has limited expressiveness as it only represents simple statements
without distinguishing between objects or their relationships.
Example:
 • "John is tall" and "Mary is tall" are treated as independent
propositions, not as statements involving objects and properties.
Predicate Logic:
• It is more expressive as it can represent relationships between objects
and their properties.
Example: "John is taller than Mary" can be written as Taller(John, Mary)
indicating a relationship between two individual.
Drawbacks of Propositional Logic:
 No data structure: propositional logic has no way to represent structured
information the way a programming language can.
 Not sufficient for complex/natural language sentences.
o Example: "Some students in KEC are intelligent" cannot be expressed —
propositional logic has no notion of objects or quantification.
 Very limited expressive power.
o Example: you cannot say "pits cause breezes in adjacent squares" as a
general rule — you would need a separate sentence for every single
square.
Introduction to First-Order Logic
 Also known as Predicate Logic or First-order predicate logic.
 Like natural language, FOL has well-defined syntax and semantics.
 FOL assumes the world contains:

1. Objects:( Anything that we want to talk about or represent in our knowledge

base) people, houses, numbers, theories, Ronald McDonald, colors, baseball
games, wars, centuries ...
2. Relations:

these can be unary relations or properties such as red, round, prime, multi
storied ..., or more general n-ary relations such as brother of, bigger than,
inside, part of, has color, occurred after, owns, comes between, ...
3. Functions: (Give another object when applied to an object) father of, best
friend, third inning of, one more than, beginning of

Examples:
1.“One plus two equals three.”
 Objects: one, two, three, one plus two; Relation: equals; Function: plus.
(“One plus two” is a name for the object that is obtained by applying the
function “plus” to the objects “one” and “two.” “Three” is another name for
this object.)

2. “Squares neighbouring the wumpus are smelly.”

Objects: wumpus, squares; Property: smelly; Relation: neighbouring.

3.“Evil King John ruled England in 1200.”

Objects: John, England, 1200; Relation: ruled; Properties: evil, king

Conversion of English statement into FOL:

Example 1:“If a person is tired, they will sleep”
Let:
Person(x): “x is a person”
Tired(x): “x is tired”
Sleep(x): “x will sleep”
FOL expression:
∀x(Person(x)∧Tired(x)→Sleep(x))
This means:
“For every x, if x is a person and x is tired, then x will sleep.”
2. Some cats are black”
Let:
 Cat(x): “x is a cat”
 Black(x): “x is black”
FOL expression: ∃x(Cat(x)∧Black(x))
This means:
“There exists an such that is a cat and is black.”
Why FOL is useful
 Can represent facts about some or all of the objects and relations in the
universe (via quantifiers).
 Can represent laws and rules extracted from the real world.
 A useful language for Mathematics, Philosophy, and AI.
 Represents facts in a realistic manner, not just as true/false propositions.
 Makes an ontological commitment .The word ontology means the study of
what exists. — i.e., it commits to the existence of objects, relations, and
functions as the building blocks of reality (unlike propositional logic, which
only commits to facts being true/false/unknown).

This table (Figure 8.1 ) compares different formal languages based on two key
dimensions: what they assume exists in the world (ontology) and how they
represent an agent's knowledge about that world (epistemology)
SYNTAX AND SEMANTICS OF FIRST-ORDER LOGIC

Syntax of FOL: Basic Elements

 Element Examples
Constants KingJohn, 2, NUS, …
Predicates Brother, >, …
Functions Sqrt, LeftLegOf, …
Variables x, y, a, b, …
Connectives ¬, ∧, ∨, ⇒, ⇔ (logical connectives)
Equality =
Quantifiers ∀ (for all), ∃ (there exists)
Sentences Atom or complex sentence
Atom True, False, or an atomic proposition (AP)
Complex sentence (sentence), connective sentence, or ¬sentence

Models for first-order logic:

The models of a logical language are the formal structures that constitute the
possible worlds under consideration. Each model links the vocabulary of the logical
sentences to elements of the possible world, so that the truth of any sentence can be
determined.

Interpretation means assigning meaning to symbols.

A model mainly tells us:
1. What objects exist in the world.
2. What each constant refers to.
3. What each predicate/relation means.
4. What each function means.
Example Model:
 Richard the Lionheart was King of England from 1189 to 1199.
 His younger brother was the evil King John, who ruled from 1199 to 1215.
 The left legs of Richard and John were different.
 John had a crown (because he was king).
Model components:
Objects:
 Person King John
 Person Richard
 Crown
 Left leg of John
 Left leg of Richard
Relations:
 "on head" ⟨the crown, King John⟩
 "brother" ⟨John, Richard⟩
 "person" ⟨John⟩
 "person" ⟨Richard⟩
 "king" ⟨John⟩
Functions: LeftLeg(x) — a unary function
 LeftLeg(Richard) = the leg-object connected to R
 LeftLeg(John) = the leg-object connected to J
Symbols, Interpretations:
Basic Syntactic Elements (Symbols)
FOL has three kinds of symbols, each standing for something different:
Symbol Type Stands For Example
Constant symbol Objects Richard, John
Brother, OnHead, Person, King,
Predicate symbol Relations
Crown
Function symbol Functions LeftLeg

 Convention: All symbols begin with an uppercase letter.

 Naming is arbitrary — chosen by the user, just like proposition symbols in
propositional logic.
  Every predicate and function symbol has an arity — a fixed number of
arguments it takes.
 E.g., Brother(x, y) has arity 2; OnHead(x, y) has arity 2; LeftLeg(x) has arity 1.
As in propositional logic, every model must provide the information required to deter
mine if any given sentence is true or false. Thus, in addition to its objects, relations,
and functions, each model includes an interpretation that specifies exactly which
objects, relations and functions are referred to by the constant, predicate, and function
symbols.
One possible interpretation for our example—which a logician would call the
intended interpretation—is as follows:
• Richard refers to Richard the Lionheart and John refers to the evil King John.
• Brother refers to the brotherhood relation, that is, the set of tuples of objects given
in Equation (8.1); OnHead refers to the “on head” relation that holds between the
crown and King John; Person, King,andCrown refer to the sets of objects that are
persons, kings, and crowns.
• LeftLeg refers to the “left leg” function, that is, the mapping given in Equation
(8.2).
Terms: A term is a logical expression that refers to an object.
Two kinds of terms:
1. Constant symbols — simplest terms (direct names), e.g., John
2. Complex terms — a function symbol + parenthesized list of argument terms,
e.g., LeftLeg(John)
Why use function symbols?
 Avoids needing a separate name for every object.
 E.g., instead of naming King John's leg, we write LeftLeg(John) rather than
inventing a constant like JohnsLeg.
A complex term is just a complicated name — NOT a subroutine call that
"returns a value."
 There is no actual LeftLeg subroutine computing an output.
 We can reason about left legs (e.g., "everyone has a left leg" → "John has a
left leg") without ever defining what LeftLeg computes.
  This is different from programming languages, where a function must be
defined/executed to produce a value.
Formal Semantics of Terms
For a term f(t₁, ..., tₙ):
1. Function symbol f refers to some function F in the model.
2. Argument terms t₁, ..., tₙ refer to objects d₁, ..., dₙ.
3. The whole term refers to the object that is F(d₁, ..., d ₙ) — i.e., the value of
applying F to those objects.
Example: If LeftLeg refers to the left-leg function, and John refers to King John,
then LeftLeg(John) refers to King John's actual left leg (an object in the
domain).
Atomic sentences:
An atomic sentence (or atom for short) is formed from a predicate symbol optionally
followed by a parenthesized list of terms, such as
Brother(Richard,John).
This states, under the intended interpretation given earlier, that Richard the Lionheart
is the brother of King John. Atomic sentences can have complex terms as arguments.
Thus,
Married(Father (Richard),Mother(John))
states that Richard the Lionheart’s father is married to King John’s mother (again,
under a suitable interpretation).
An atomic sentence is true in a given model if the relation referred to by the predicate
symbol holds among the objects referred to by the arguments.
Complex sentences:
We can use logical connectives to construct more complex sentences, with the same
syntax and semantics as in propositional calculus. Here are four sentences that are
true in the model of Figure 8.2 under our intended interpretation:
¬Brother(LeftLeg(Richard),John)
Brother(Richard,John) ∧ Brother(John,Richard)
King(Richard) ∨ King(John)
¬King(Richard) ⇒ King(John)
Quantifiers:
A quantifier is a symbol in First-Order Logic (FOL) used to specify how many
objects a statement applies to.
A quantifier allows us to talk about a collection of objects without mentioning every
object separately.
FOL has two main quantifiers: universal and existential.
∀ → check every object
∃ → find at least one object

Universal quantification (∀):

It says that a statement is true for every object in the domain.
Example: All kings are persons.
In FOL: ∀x(King(x)⇒Person(x))
Read as: For all x, if x is a king, then x is a person.
Here:
∀ → for all
x → variable
King(x) → x is a king
Person(x) → x is a person
∀ is usually pronounced “For all ...”. (Remember that the upside-down A stands for
“all.”) Thus, the sentence says, “For all x, if x is a king, then x is a person.” The
symbol x is called a variable.
By convention, variables are lowercase letters.
A variable is a term all by itself, and as such can also serve as the argument of a
function—for example, LeftLeg(x).
ground term: A term with no variables is called a ground term.
Example: John
LeftLeg(John)
how universal quantification works using the model from Figure 8.2.
The main statement is:

For every object x, if x is a king, then x is a person.

We can extend the interpretation in five ways:
x →Richard the Lionheart,
x →KingJohn,
x →Richard’s left leg,
x →John’s left leg,
x →the crown.
Replace x with Richard:
First object: Richard the Lionheart
King(Richard)⇒Person(Richard)
Richard the Lionheart is a king ⇒ Richard the Lionheart is a person.
According to the model:
 Richard is not a king
 Richard is a person
So: An implication is true when the premise is false.
Therefore: true
So Richard does not cause any problem.

Second object: King John

Replace x with John: King(John)⇒Person(John)
King John is a king ⇒ King John is a person.
From the model:
John is a king → True
John is a person → True
Therefore: True⇒True
which is:True
So this case is also true.
Third object: Richard's left leg
Replace x with Richard's left leg:
King(RichardLeftLeg)⇒Person(RichardLeftLeg)
Richard’s left leg is a king ⇒ Richard’s left leg is a person.
According to the model:
Richard's left leg is not a king
Richard's left leg is not a person
So: False⇒False
An implication with a false premise is true.
Therefore:True
Fourth object: John's left leg
Replace x with John's left leg:
King(JohnLeftLeg)⇒Person(JohnLeftLeg)
John’s left leg is a king ⇒ John’s left leg is a person.
According to the model:

John's left leg is not a king → False

John's left leg is not a person → False
Therefore:
False⇒False
which is:True
Fifth object: The crown
Replace x with the crown:
King(Crown)⇒Person(Crown)
The crown is a king ⇒ the crown is a person
According to the model:
Crown is not a king → False
Crown is not a person → False
Therefore:
False⇒False
which is:True
All five cases are True.
Therefore: ∀x(King(x)⇒Person(x))=True

Acommon mistake, made frequently even by diligent readers who have read this
paragraph several times, is to use conjunction instead of implication.
The sentence: ∀x King(x)∧Person(x)would be equivalent to asserting
Richard the Lionheart is a king ∧ Richard the Lionheart is a person,
King John is a king ∧King John is a person,
Richard’s left leg is a king ∧ Richard’s left leg is a person,
and so on. Obviously, this does not capture what we want

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) .
There exists an object such that is a crown AND is on John's head.
∃x is pronounced “There exists an x such that ...”or“ For some x...”
Intuitively, the sentence ∃xP says that P is true for at least one object x. Mo re
precisely, ∃ xPis true in a given model if P is true in at least one extended
interpretation that assigns x to a domain element. That is, at least one of the following
is true:
Why do we use AND (∧)?We need both conditions to be true for the same object x.
We need:Crown(x)ANDOnHead(x,John)
So:Crown(x)∧OnHead(x,John)
means:x is a crown and x is on John's head.
Replace x with all 5 objects of model
1. Richard
2. John
3. Richard's left leg
4. John's left leg
5. Crown
[Link](Richard)∧OnHead(Richard,John) (False)
Richard the Lionheart is a crown ∧ Richard the Lionheart is on John’s head;
[Link](John)∧OnHead(John,John) (False)
King John is a crown ∧ King John is on John’s head;
[Link](RichardLeftLeg)∧OnHead(RichardLeftLeg,John) (False)
Richard’s left leg is a crown ∧ Richard’s left leg is on John’s head;
4. Crown(JohnLeftLeg)∧OnHead(JohnLeftLeg,John) (False)
John’s left leg is a crown ∧ John’s left leg is on John’s head;
5. Crown(Crown)∧OnHead(Crown,John) (True)
The crown is a crown ∧ the crown is on John’s head.
We need: at least ONE object to satisfy it. Therefore the existential statement is
TRUE.
Just as ⇒ appears to be the natural connective to use with ∀, ∧ is the natural
connective to use with ∃.
Using∧ as the main connective with ∀ led to an overly strong statement in the
example in the previous section; using ⇒ with ∃ usually leads to a very weak
statement, indeed.
Consider the following sentence:
∃x Crown(x) ⇒ OnHead(x,John).
On the surface, this might look like a reasonable rendition of our sentence. Applying
the semantics, we see that the sentence says that at least one of the following
assertions is true:
Richard the Lionheart is a crown ⇒ Richard the Lionheart is on John’s head;
King John is a crown ⇒ King John is on John’s head;
Richard’s left leg is a crown ⇒ Richard’s left leg is on John’s head;
and so on. Now an implication is true if both premise and conclusion are true, or if its
premise is false. So if Richard the Lionheart is not a crown, then the first assertion is
true and the existential is satisfied. So, an existentially quantified implication
sentence is true whenever any object fails to satisfy the premise; hence such
sentences really do not say much at all.

Nested quantifiers:
When more than one quantifier appears in a sentence, we call them nested
quantifiers.
For example, “Brothers are siblings” can be written as
∀x ∀y Brother(x,y) ⇒ Sibling(x,y)
For every x and for every y, if x is a brother of y, then x is a sibling of y.
Consecutive quantifiers of the same type can be written as one quantifier with
several variables
Instead of:
∀x∀y P(x,y) we can write: ∀x,y P(x,y)
Similarly:
∃x∃y P(x,y)can be written as:∃x,y P(x,y)
For example, to say that siblinghood is a symmetric relationship, we can write
∀x,y Sibling(x,y) ⇔ Sibling(y,x)
Order of Quantifiers
The order of quantifiers can completely change the meaning.
“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) .
Some confusion can arise when two quantifiers are used with the same variable
name. Consider the sentence
∀x (Crown(x)∨(∃x Brother(Richard,x))) .
Better way to write it Instead of using x twice, write:
∀x(Crown(x)∨(∃yBrother(Richard,y)))
Connections between ∀ and ∃
The two quantifiers are connected through negation.
This is similar to De Morgan's laws that you studied in propositional logic.
∀x¬P(x)≡¬∃xP(x)
Asserting that everyone dislikes parsnips is the same as asserting there does not exist
someone who likes them, and vice versa:
∀x ¬Likes(x,Parsnips) is equivalent to ¬∃x Likes(x,Parsnips)
We can go one step further: “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)
Because ∀ is really a conjunction over the universe of objects and ∃ is a disjunction,
it should not be surprising that they obey De Morgan’s rules. The De Morgan rules
for quantified and unquantified sentences are as follows:
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.
The equality symbol can be used to state facts about a given function, as we just did
for the Father symbol. It can also be used with negation to insist that two terms are
not the same object.
To say that Richard has at least two brothers, we would write
∃x,y Brother(x,Richard) ∧ Brother(y,Richard) ∧¬(x=y) .
¬(x=y) means (x and y are not the same person.)
The sentence
∃x,y Brother(x,Richard) ∧ Brother(y,Richard)
does not have the intended meaning. In particular, it is true in the model of Figure
8.2, where Richard has only one brother. To see this, consider the extended
interpretation in which both x and y are assigned to King John. The addition of
¬(x=y) rules out such models. The notation x̸ = y is sometimes used as an
abbreviation for ¬(x=y).
Continuing the example from the previous section, suppose that we believe
that Richard has two brothers, John and Geoffrey.
Can we capture this state of affairs by asserting
Brother(John,Richard) ∧ Brother(Geoffrey,Richard)?
(8.3) Not quite. First, this assertion is true in a model where Richard has only one
brother— we need to add John ̸ = Geoffrey. Second, the sentence doesn’t rule out
models in which Richard has many more brothers besides John and Geoffrey. Thus,
the correct translation of “Richard’s brothers are John and Geoffrey” is as follows:

Brother(John,Richard) ∧ Brother(Geoffrey,Richard) ∧ John ̸ = Geoffrey

∧∀x Brother(x,Richard) ⇒ (x=John ∨x=Geoffrey) .
Anyone who is Richard's brother must be either John or Geoffrey.
Standard FOL vs Database Semantics
The text then introduces a different way of interpreting FOL called database
semantics. The standard FOL semantics allows the possibility that there are objects
we don't know about.
For example:
Unique-Names Assumption
Different names refer to different objects automatically.
For example :John/=Richard
Closed-World Assumption
This means:
If something is not known to be true, assume it is false.
For example, suppose the database contains:
Brother(John,Richard)
but does not contain:Brother(Geoffrey,Richard)
Under the closed-world assumption, we assume:¬Brother(Geoffrey,Richard)
Domain Closure
Domain closure means:
The only objects that exist are the objects named by the constants.
Suppose our constants are: Under domain closure, the domain contains only:
{John,Richard,Geoffrey}
There cannot be some unknown fourth person..

PROPOSITIONAL VS. FIRST-ORDER INFERENCE:

first-order inference can be done by converting the knowledge base to propositional
logic and using propositional inference, which we already know how to do.
Inference rules for quantifiers:
our knowledge base contains the standard axiom stating that
“all greedy kings are evil:”
∀x King(x)∧Greedy(x) ⇒ Evil(x)
Then it seems quite permissible to infer any of the following sentences:
King(John) ∧Greedy(John) ⇒ Evil(John)
King(Richard) ∧ Greedy(Richard) ⇒ Evil(Richard)
King(Father (John)) ∧ Greedy(Father(John)) ⇒ Evil(Father (John)) .
The first step is eliminating universal quantifiers
1. Universal Instantiation(UI)
2. Existential Instantiation(EI)

Universal Instantiation(UI):
The rule of Universal Instantiation (UI for short) says that we can infer any sentence
ob tained by substituting a ground term (a term without variables) for the variable.1
To write out the inference rule formally, we use the notion of substitutions introduced
in Section 8.3. Let SUBST(θ,α) denote the result of applying the substitution θ to the
sentence α. Then the rule is written

for any variable v and ground term g. For example, the three sentences given earlier
are obtained with the substitutions
{x/John}, {x/Richard},and{x/Father (John)}.
Existential Instantiation:
the variable is replaced by a single new con stant symbol. The formal statement is as
follows: for any sentence α,variablev, and constant symbol k that does not appear
elsewhere in the knowledge base

For example, from the sentence

∃x Crown(x)∧OnHead(x,John)
we can infer the sentence
Crown(C1) ∧OnHead(C1,John)
as long as C1 does not appear elsewhere in the knowledge base.
The new constant introduced during Existential Instantiation is called a Skolem
constant.
Skolemization is the process of removing existential quantifiers (∃) from a First-
Order Logic sentence by replacing the existentially quantified variable with a new
constant or function.
Inferential Equivalence
After Existential Instantiation, the new knowledge base is not strictly logically
equivalent to the original knowledge base.
However, it is inferentially equivalent in terms of satisfiability.

Reduction to propositional inference:

Reduction to propositional inference means Converting a First-Order Logic (FOL)
problem into a Propositional Logic problem so that we can use propositional
inference methods to solve it.
For example, suppose our knowledge base contains just the sentences
∀x King(x) ∧ Greedy(x) ⇒ Evil(x)
King(John)
Greedy(John)
Brother(Richard, John)
The first sentence contains the universal quantifier ∀x.
Apply Universal Instantiation
to the first sentence using all possible ground-term substitutions from the vocabulary
of the knowledge base—in this case, {x/John} and {x/Richard}. We obtain
King(John) ∧Greedy(John) ⇒ Evil(John)
King(Richard) ∧ Greedy(Richard) ⇒ Evil(Richard)
treat Ground Sentences as Propositions
Now consider:
 King(John) → proposition
 Greedy(John) → proposition
 Evil(John) → proposition
 King(Richard) → proposition
 Greedy(Richard) → proposition
There are no variables or quantifiers now.
Therefore, the KB can be treated as a propositional knowledge base.
Propositionalization: Propositionalization is the process of converting a first-order
knowledge base into propositional sentences by generating appropriate ground
instances.
There is an important problem when the KB contains function symbols.
Suppose we have:
Father(John)
Then we can construct:
 Father(John)
 Father(Father(John))
 Father(Father(Father(John)))
 Father(Father(Father(Father(John))))
 ...
There is no end.
Therefore, the number of possible ground terms becomes infinite.
Herbrand's Theorem
Fortunately, Jacques Herbrand provided an important result.
Herbrand's theorem says:If a sentence is entailed by a first-order knowledge base,
then there is a proof using only a finite subset of the propositionalized knowledge
base.
We can generate terms in increasing [Link] the constants are:John, Richard
and the function is:Father
We generate:
Depth 0
 John
 Richard
Depth 1
 Father(John)
 Father(Richard)
Depth 2
 Father(Father(John))
 Father(Father(Richard))
Depth 3
 Father(Father(Father(John)))
 Father(Father(Father(Richard)))
Continue until the required propositional proof is found.
This approach is complete. Complete means:If the query is actually entailed by the
knowledge base, the procedure will eventually find a proof.
So:If KB ⊨ α then eventually: KB ⊢ α
What happens when the sentence is not entailed? The algorithm may continue
generating:
 more constants
 more terms
 deeper function terms
 more propositional instances

This leads to an important property of First-Order Logic:

Entailment in First-Order Logic is semidecidable.

—that is, algorithms exist that say yes to every entailed sentence, but no algorithm
exists that also says no to every non entailed sentence.

UNIFICATION AND LIFTING:

Unification:

Lifted inference rules require finding substitutions that make different logical
expressions 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)

Rules:

[Link] symbol must be [Link] with different predicate symbol can

never be unified.

[Link] of arguments in both expressions must be identical.

[Link] will fail if there are two similar variables present in the same
expression.

Here are the results of unification with four different sentences that might be in the k
nowledge base:

UNIFY(Knows(John,x), Knows(John,Jane)) = {x/Jane}

UNIFY(Knows(John,x), Knows(y,Bill)) = {x/Bill,y/John}

UNIFY(Knows(John,x), Knows(y,Mother(y))) = {y/John,x/Mother(John)}

UNIFY(Knows(John,x), Knows(x,Elizabeth)) = fail .

The last unification fails because x cannot take on the values John and Elizabeth at
the same time.

Now, remember that Knows(x,Elizabeth) means “Everyone knows Elizabeth,” so we

should be able to infer that John knows Elizabeth.

The problem arises only because the two sentences happen to use the same variable
name, x.

The problem can be avoided by standardizing apart one of the two sentences being
unified, which means renaming its variables to avoid name clashes.

For example, we can rename x in Knows(x,Elizabeth) to x17 (a new variable name)

without changing its meaning. Now the unification will work:
UNIFY(Knows(John,x), Knows(x17,Elizabeth)) = {x/Elizabeth,x17/John} .

There is one more complication: we said that UNIFY should return a substitution that
makes the two arguments look the same. But there could be more than one such uni
fier.

For example, UNIFY(Knows(John,x),Knows(y,z))

could return {y/John,x/z} or {y/John,x/John,z/John}.

The first unifier gives Knows(John,z) as the result of unifi cation, whereas the
second gives Knows(John,John).

The second result could be obtained from the first by an additional substitution
{z/John};

we say that the first unifier is more general than the second, because it places
fewer restrictions on the values of the variables.

It turns out that, for every unifiable pair of expressions, there is a single most general
unifier(or MGU)that is unique up to renaming and substitution of variables.

(For example, {x/John} and {y/John} are considered equivalent, as are

{x/John,y/John} and {x/John,y/x}.) In this case it is {y/John,x/z}.

Lifting in First-Order Logic

Lifting means: Performing inference directly in First-Order Logic using variables and
substitutions, instead of first converting everything into propositional logic.

Propositional inference:
First remove variables → create all possible instances → then infer.

Lifted inference:
Keep the variables → find the required substitution → infer directly.

Suppose we have:King(x) ∧ Greedy(x) ⇒ Evil(x)

And the KB contains: King(John), Greedy(John)

We want to prove:Evil(John)

We find the substitution:θ = {x/John}

Apply it to the rule:

King(John) ∧ Greedy(John) ⇒ Evil(John)

Since both premises are in the KB:King(John) Greedy(John)

Therefore: Evil(John) This is Generalized Modus Ponens (GMP).

The basic Modus Ponens rule in propositional logic is: P ⇒ Q PTherefore: Q

For example:

King(John) ∧ Greedy(John) ⇒ Evil(John)

King(John) ∧ Greedy(John)

Therefore: Evil(John)

This is ground/propositional reasoning.

Generalized Modus Ponens lifts it to FOL:

King(x) ∧ Greedy(x) ⇒ Evil(x)

with appropriate substitutions.

So:Lifting = extending a propositional inference rule so that it works directly

with variables and substitutions in First-Order Logic.

Why is Lifting Better Than Propositionalization?

Suppose there are 1,000 people in the KB.

Propositionalization approach

We may generate:

King(Person1) ∧ Greedy(Person1) ⇒ Evil(Person1)

King(Person2) ∧ Greedy(Person2) ⇒ Evil(Person2)

...

King(Person1000) ∧ Greedy(Person1000) ⇒ Evil(Person1000)

A huge number of sentences may be generated.

Lifting approach

Keep only:

King(x) ∧ Greedy(x) ⇒ Evil(x)

When we need to prove something about John:

θ = {x/John}

When we need Richard:

θ = {x/Richard}

Only the necessary substitutions are made.

FORWARDCHAINING:

A forward-chaining algorithm idea is simple: start with the atomic sentences in the
knowledge base and apply Modus Ponens in the forward direction, adding new
atomic sentences, until no further inferences can be made.

Consider the following problem:

The law says that it is a crime for an American to sell weapons to hostile nations. The
country Nono, an enemy of America, has some missiles, and all of its missiles were
sold to it by Colonel West, who is American.

West Is a Criminal

The goal is to prove:

Criminal(West)

We convert the English statements into First-Order Definite Clauses and then use
Forward Chaining.

[Link] is a crime for an American to sell weapons to hostile nations.

FOL rule:American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒ Criminal(x)

2. Nono has some missiles.

Original:∃x Owns(Nono,x) ∧ Missile(x)

Using Existential Instantiation, introduce a new constant:M1

Therefore:

Owns(Nono,M1)

Missile(M1)

Here, M1 is a Skolem constant representing one of Nono's missiles.

3.“All of its missiles were sold to it by Colonel West”:

Missile(x) ∧ Owns(Nono,x) ⇒ Sells(West,x,Nono) .

[Link] Missile Is a Weapon

Missile(x) ⇒ Weapon(x)

[Link] must know that an enemy of America counts as “hostile”

Enemy(x,America) ⇒ Hostile(x) .

[Link] Is American

American(West) .

7. The country Nono, an enemy of America ...”:

Enemy(Nono,America)
The goal is to prove Criminal(West).
Forward chaining starts with the known facts and repeatedly applies rules to derive
new facts.
Step 1: Start with the given facts
From the knowledge base:
1. American(West)
2. Enemy(Nono, America)
3. Owns(Nono, M1)
4. Missile(M1)
These are the initial facts.
Step 2: Derive Weapon(M1)
We have the rule:Missile(x) ⇒ Weapon(x)
We already know:Missile(M1) Substitute:x = M1
Therefore:Weapon(M1)
Step 3: Derive Sells(West, M1, Nono)
Rule:Missile(x) ∧ Owns(Nono,x) ⇒ Sells(West,x,Nono)
We have:
Missile(M1)
Owns(Nono,M1) Both conditions are true.
Therefore:Sells(West,M1,Nono)
This is the middle branch in the diagram.
step 4: Derive Hostile(Nono)
Rule:Enemy(x,America) ⇒ Hostile(x)
We have:Enemy(Nono,America)
Substitute:x = Nono
Therefore:Hostile(Nono)
This is the right branch in the diagram.
Step 5: Apply the final criminal rule
The main rule is:
American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒ Criminal(x)
So substitute:
x=West
y=M1
z = Nono
The rule becomes:
American(West) ∧ Weapon(M1) ∧ Sells(West,M1,Nono) ∧ Hostile(Nono) ⇒
Criminal(West)
All four premises are true.
Therefore: Criminal(West)
BACKWARDCHAINING:
Backward chaining is an inference method used in Artificial Intelligence and expert
systems. It starts with a goal (query) and works backward to find the facts and rules
needed to prove that goal.

Step 1: Start with the goal

The goal is:Criminal(West)
We use the rule:American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒
Criminal(x)
To make the conclusion equal to our goal:Criminal(x) = Criminal(West)
we substitute:{x/West}
So the rule becomes:American(West) ∧ Weapon(y) ∧ Sells(West,y,z) ∧ Hostile(z)
These are the four conditions that must be proved.
step 2: Prove American(West)
We need:American(West)
The KB already contains:American(West)
So it is immediately [Link] substitution shown below it is:{}
{} means no substitution is needed.
Step 3: Prove Weapon(y)
We need:Weapon(y)
We have the rule:Missile(y) ⇒ Weapon(y)
So we need to find something that is a missile.
The KB contains:Missile(M1)
Therefore, match: Missile(y) with Missile(M1)
This gives:{y/M1}
Meaning:Replace y with [Link]:
Weapon(y)becomes:Weapon(M1)
So:Missile(M1) → Weapon(M1)
step 4: Prove Sells(West,y,z)
We need:Sells(West,y,z)
We have the rule:Missile(x) ∧ Owns(Nono,x) ⇒ Sells(West,x,Nono)
Compare:Sells(West,y,z)with:Sells(West,x,Nono)
From this matching:
 West = West
 x=y
 z = Nono
The important substitution is:{z/Nono}
And because Step 3 already gave:{y/M1}
we get:Sells(West,M1,Nono)
step 5: Prove the two conditions for Sells
The rule says:Missile(x) ∧ Owns(Nono,x)We need [Link] condition
Missile(M1)
This is already in the [Link]:{}No substitution is needed.
Second condition
Owns(Nono,M1)
This is also already in the KB.
So:
{}
Again, no substitution is needed.
Therefore:Missile(M1) ∧ Owns(Nono,M1) allows us to conclude:
Sells(West,M1,Nono).
Step 6: Prove Hostile(Nono)
We need:Hostile(Nono)
We have the rule:Enemy(x,America) ⇒ Hostile(x)
The KB contains:Enemy(Nono,America)
Match:Enemy(x,America)
with:Enemy(Nono,America)
Therefore:{x/Nono}
and we get:Hostile(Nono).
The fact itself needs no further substitution, hence {} is shown below it.
Step 7: Now all four conditions are satisfied
We have obtained:
1. American(West)
2. Weapon(M1)
 3. Sells(West,M1,Nono)
4. Hostile(Nono)
Therefore the original rule:
American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒ Criminal(x)
can be instantiated as:
American(West) ∧ Weapon(M1) ∧ Sells(West,M1,Nono) ∧ Hostile(Nono) ⇒
Criminal(West)
Hence: Criminal(West)
Resolution
• Convert everything to CNF
• Resolve, with unification
• If resolution is successful, proof succeeds
• If there was a variable in the item to prove, return variable’s value from
unification bindings
Conjunctive normal form for first-order logic:
CNF (Conjunctive Normal Form) means an expression written as an AND of
ORs.

As in the propositional case, first-order resolution requires that sentences be in

conjunctive normal form (CNF)—that is, a conjunction of clauses, where each clause
is a disjunction of literals. Literals can contain variables, which are assumed to be
universally quantified. For example, the sentence
∀x American(x)∧Weapon(y)∧Sells(x,y,z) ∧Hostile(z) ⇒ Criminal(x)
becomes, in CNF,
¬American(x) ∨¬Weapon(y) ∨¬Sells(x,y,z) ∨¬Hostile(z) ∨ Criminal(x)
Here there is only one OR clause: A single clause is also considered a valid CNF.
This is a CNF clause.
Every sentence of first-order logic can be converted into an inferentially equivalent
CNF sentence.
Example:
“Everyone who loves all animals is loved by someone,”
∀x [∀y Animal(y) ⇒ Loves(x,y)] ⇒ [∃y Loves(y,x)] .
The steps are as follows:
• Eliminate implications:
∀x [¬∀y ¬Animal(y)∨Loves(x,y)] ∨[∃y Loves(y,x)] .
• Move ¬inwards: In addition to the usual rules for negated connectives, we need
rules for negated quantifiers. Thus, we have
¬∀x p becomes ∃x ¬p
¬∃x p becomes ∀x ¬p
Our sentence goes through the following transformations:
∀x [∃y ¬(¬Animal(y)∨Loves(x,y))] ∨[∃y Loves(y,x)] .
∀x [∃y ¬¬Animal(y)∧¬Loves(x,y)] ∨[∃y Loves(y,x)] .
∀x [∃y Animal(y)∧¬Loves(x,y)] ∨[∃y Loves(y,x)] .
Notice how a universal quantifier (∀y) in the premise of the implication has become
an existential quantifier. The sentence now reads “Either there is some animal that x
doesn’t love, or (if this is not the case) someone loves x.” Clearly, the meaning of the
original sentence has been preserved.
Standardize variables: For sentences like (∃xP(x))∨(∃xQ(x)) which use the same
variable name twice, change the name of one of the variables. This avoids confusion
later when we drop the quantifiers.
Thus, we have
∀x [∃y Animal(y)∧¬Loves(x,y)] ∨[∃z Loves(z,x)] .
Skolemize: Skolemization is the process of removing existential quantifiers by elimi

9.1: translate ∃ xP(x) into P(A),where A is a new constant. However, we can’t apply
nation. In the simple case, it is just like the Existential Instantiation rule of Section

∃vα; only parts of the sentence match the pattern. If we blindly apply the rule to the
Ex istential Instantiation to our sentence above because it doesn’t match the pattern

two matching parts we get

∀x [Animal(A)∧¬Loves(x,A)] ∨Loves(B,x)
which has the wrong meaning entirely: it says that everyone either fails to love a par
ticular animal A or is loved by some particular entity B. In fact, our original
sentence allows each person to fail to love a different animal or to be loved by a
different person. Thus, we want the Skolem entities to depend on x and z:
∀x [Animal(F(x)) ∧¬Loves(x,F(x))] ∨ Loves(G(z),x) .
Here F and G are Skolem functions. The general rule is that the arguments of the
Skolem function are all the universally quantified variables in whose scope the exis
tential quantifier appears. As with Existential Instantiation, the Skolemized sentence
is satisfiable exactly when the original sentence is satisfiable
Drop universal quantifiers: At this point, all remaining variables must be
universally quantified. Moreover, the sentence is equivalent to one in which all the
universal quan tifiers have been moved to the left. We can therefore drop the
universal quantifiers:
[Animal(F(x)) ∧¬Loves(x,F(x))] ∨ Loves(G(z),x)
Distribute ∨ over ∧:
[Animal(F(x)) ∨ Loves(G(z),x)] ∧ [¬Loves(x,F(x)) ∨ Loves(G(z),x)] .
This step may also require flattening out nested conjunctions and disjunctions.
The sentence is now in CNF and consists of two clauses. It is quite unreadable. (It
may help to explain that the Skolem function F(x) refers to the animal potentially
unloved by x, whereas G(z) refers to someone who might love x.) Fortunately,
humans seldom need look at CNF sentences—the translation process is easily
automated.

Resolution Example proofs

Resolution proves that KB |= α by proving KB ∧¬α unsatisfiable, that is, by deriving
the empty clause.
A resolution proof that west is a criminal.
We also include the negated goal ¬Criminal(West)
Apply Unification to make two logical expressions match by finding suitable
substitutions for their variables.
In resolution, there are mainly two important stopping conditions:
1. Stop when you derive the empty clause
2. Stop when no new clauses can be generated
The sentences in CNF are

Example2:
Everyone who loves all animals is loved by someone.
Anyone who kills an animal is loved by no one.
Jack loves all animals.
Either Jack or Curiosity killed the cat, who is named Tuna.
Did Curiosity kill the cat?
First, we express the original sentences, some background knowledge, and the
negated goal G in first-order logic:
Completeness of Resolution:
Refutation-completeness: If a set of sentences is unsatisfiable, resolution will

by showing KB ∧ ¬Q(x) is unsatisfiable.

always derive a contradiction (the empty clause). This lets us answer any query Q(x)

Proof structure (3 steps):

1. Herbrand's theorem — If S is unsatisfiable, some finite subset of ground
instances of S is also unsatisfiable.
2. Ground resolution theorem — Propositional resolution is complete for ground
sentences, so it can find the contradiction in that finite ground subset.
3. Lifting lemma — Any propositional resolution proof on ground instances
corresponds to a first-order resolution proof on the original (non-ground)
sentences.

1. Any set of sentences can be converted to clause form

At the top: “Any set of sentences S is representable in clause form.”
This means any First-Order Logic sentences can be converted into CNF / clause
form.
For example: P ⇒ Q becomes: ¬P ∨ Q
So we start with: S → Clause form
2. Assume S is unsatisfiable
The proof assumes: S is unsatisfiable.
That means there is no possible interpretation/model in which all sentences in S are
true simultaneously.
For example: P and ¬Pcannot both be true.
Therefore: S = {P, ¬P}is unsatisfiable.
3. Herbrand's Theorem
The next step says:Some set S′ of ground instances is unsatisfiable.
This is the important result of Herbrand's theorem.
What is a ground instance?
A ground instance is a sentence in which there are no variables.
Example:
P(x) ⇒ Q(x)
can be instantiated with John:
P(John) ⇒ Q(John)
This is a ground instance.
Herbrand's theorem says:
If the original FOL set S is unsatisfiable, then we can find some finite set of ground
instances S′ that is also unsatisfiable.
So:
FOL sentences
↓
Ground instances
↓
Unsatisfiable S′

4. Ground Resolution Theorem

Now we have: S′ = a set of ground clauses
Since there are no variables, we can treat them like propositional clauses.
The Ground Resolution Theorem tells us:
If a set of ground clauses is unsatisfiable, resolution can derive a contradiction.
Therefore:
S′ is unsatisfiable
↓
Resolution
↓
□
The empty clause means contradiction.
5. Lifting Lemma
But there is a problem.
We found a resolution proof for the ground instances S′.
How can we get a proof for the original FOL clauses S?
This is where the Lifting Lemma is used.
The Lifting Lemma says, roughly:
If a ground resolution step can be performed, then a corresponding resolution step
can be performed at the first-order level.
In simple words: Ground resolution proof can be lifted back to First-Order resolution
proof.