Reasoning

Dr K Ganesan
Professor – HAG
SCORE, VIT, Vellore – 632014
[email protected]
Ph: 6382203768
AI Rules for the traffic lights control: There are 4
membership functions for each input-output fuzzy variable
of the system.
Table below shows the fuzzy variables of Arrival, Queue and
Extension of the system, the right hand notations are used
to shorten these variables.
Table : Fuzzy variables of arrival, queue and extension of the
traffic light control.
The size of the matrix or the number of rules is equal to the
number of input combinations derived from the number of
membership functions per input.
For example, in the traffic control system there are 2 inputs
each having 4 membership functions, then number of rules
would be equal to 16.
• In AI, reasoning refers to the process of drawing
logical conclusions from available information or
data.
• It's about making sense of the information and
using it to reach decisions or solve problems.
• Reasoning in AI can be divided into various types -
deductive reasoning, inductive reasoning,
abductive reasoning, and analogical reasoning.
• Deductive reasoning: This involves drawing specific
conclusions from general principles or rules.
• Inductive reasoning: In contrast to deductive
reasoning, inductive reasoning involves making
generalizations based on specific observations.
• Abductive reasoning: This type of reasoning involves
making guesses or hypotheses to explain the
observations or data.
• It's about finding most likely explanation for a given
set of evidence.
• Analogical reasoning: Analogical reasoning involves
drawing conclusions by finding similarities between
different situations or domains.
• In AI, reasoning is crucial for tasks such as problem-
solving, decision-making, planning, understanding
natural language.
• Various AI techniques - logic-based approaches,
probabilistic reasoning, and machine learning
algorithms, are used to enable different forms of
reasoning in AI systems
• Logic Bases Approach
• Propositional logic (PL) is the simplest form of logic where all the
statements are made by propositions.
• A proposition is a declarative statement which is either true or false
and it is a technique of knowledge representation in logical and
mathematical form. Examples:
• a) It is Sunday.
• b) The Sun rises from West (False proposition)
• c) 3+3= 7(False proposition)
• d) 5 is a prime number.
• Some basic facts about propositional logic:
• Propositional logic is called Boolean logic when it works on 0 and 1.
• In propositional logic, we use symbolic variables to represent the
logic, and we can use any symbol for a representing a proposition,
such A, B, C, P, Q, R, etc. (For e.g, Fuzzy Logic – lingustic variables)
• Propositions can be either true or false, but it cannot be both.
• Propositional logic consists of an object, relations or
function, and logical connectives.
• These connectives are also called logical operators
which connects two sentences..
• A proposition formula which is always true is
called tautology, and it is also called a valid sentence.
• A proposition formula which is always false is
called Contradiction.
• Statements which are questions, commands, or
opinions are not propositions.
• For e.g, "Where is Rohini?",
• "How are you?",
• "What is your name?", are not propositions.
• There are 2 types of Propositions:
• Atomic Propositions
• Compound propositions
• Atomic Proposition: Atomic propositions are the simple
propositions. It consists of a single proposition symbol.
• These are sentences which must be either true or false.
• Example:
• a) 2+2 is 4, it is an atomic proposition as it is a true fact
• b) "The Sun is cold" is a proposition as it is a false fact.
• Compound proposition: They are constructed by combining
simpler or atomic propositions, using parenthesis & logical
connectives.
• Example:
• a) "It is raining today, and street is wet."
• b) “Rajan is a doctor, and his clinic is in Vellore."
• Logical connectives are used to connect two simpler
propositions or representing a sentence logically.
• We can create compound propositions using logical
connectives
• There are mainly five connectives, given as follows:
• Negation: A sentence such as ¬ P is called negation of P.
• For e.g, P = I like ice cream. ¬ P = I do not like ice cream.
• A literal can be either Positive literal or negative literal.
• Conjunction: A sentence which has ∧ (similar to AND
operator) connective such as, P ∧ Q is called a
conjunction.
Disjunction: A sentence which has ∨ connective (similar to
OR operator), such as P ∨ Q is called disjunction, where P
and Q are the propositions.
Implication: A sentence such as P → Q, is called an
implication.
• Implications are known as if-then rules.
• Biconditional:
• A sentence such as P⇔ Q is a Biconditional sentence.
• For e.g, If I am breathing, then I am alive.
• P= I am breathing, Q= I am alive, is represented as P ⇔ Q.
• Following is table for Propositional Logic Connectives:
• Truth Table:
• In propositional logic, we need to know the truth values of
propositions in all possible scenarios. We can combine all possible
combination with logical connectives, and the representation of
these combinations in a tabular format is called Truth table.
• Following are the truth table for all logical connectives:
• Truth table with three propositions:
• We can build a proposition composing three propositions P,
Q, and R. This truth table is made-up of 8n Tuples as we
have taken three proposition symbols.
•
• Precedence of connectives:
• In logic, precedence of connectives determines the order
in which logical operations are evaluated in an expression.
• A typical precedence hierarchy is from highest to lowest:
• Negation (¬)
• Conjunction (AND, ∧)
• Disjunction (OR, ∨)
• Conditional (IMPLIES, →)
• Biconditional (IF AND ONLY IF, ↔)
• This hierarchy ensures that operations are evaluated in a
consistent and predictable manner.
• For example, in an expression like "A ∧ B ∨ C," conjunction
(AND) takes precedence over disjunction (OR), so "A ∧ B"
would be evaluated first before the OR operation with C.
• Use parenthesis to overrule the precedence.
• We can add parentheses when ambiguity arises to clear
the order of operations.
• For example, the expression ¬p ∨ q ∧ r is equivalent to
the expression (¬p) ∨ (q ∧ r), while p ∨ q ∧ q ∨ r is
equivalent to p ∨ (q ∧ q) ∨ r.
• This leaves the question of which of the ∧ operators in
the expression p ∧q ∧ r is evaluated first.
• This is settled by the following rule:
• When several operators of equal precedence occur in
the absence of parentheses, they are evaluated from
left to right.
• Expression p ∧ q ∧ r is equivalent to (p ∧ q) ∧ r rather
than to p ∧ (q ∧ r)
• Logical equivalence:
• 2 propositions are said to be logically equivalent if and only
if columns in truth table are identical to each other
• Let's take two propositions A and B, so for logical
equivalence, we can write it as A⇔B. In the truth table
below, we can see that column for ¬A∨ B and A→B, are
identical hence A is Equivalent to B
•
• Let's consider the statements:
• Statement A: "If it is raining, then I will take my
umbrella."
• Statement B: "I will not take my umbrella unless it is
raining."
• These two statements are logically equivalent because
they convey the same meaning.
• If we break down the logic:
• If it is raining (A is true), then I will take my umbrella
(B is true).
• If I will not take my umbrella (B is false), then it is not
raining (A is false).
• In both cases, the truth values of the statements A and
B are the same.
• If A is true, then B is true; if A is false, then B is false.
• Properties of Operators:
• Commutativity:
– P∧ Q= Q ∧ P, or
– P ∨ Q = Q ∨ P.
• Associativity:
– (P ∧ Q) ∧ R= P ∧ (Q ∧ R),
– (P ∨ Q) ∨ R= P ∨ (Q ∨ R)
• Identity element:
– P ∧ True = P,
– P ∨ True= True.
• Distributive:
– P∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R).
– P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).
• DE Morgan's Law:
– ¬ (P ∧ Q) = (¬P) ∨ (¬Q)
– ¬ (P ∨ Q) = (¬ P) ∧ (¬Q).
• Double-negation elimination:
– ¬ (¬P) = P.
• Limitations of Propositional logic:
• We cannot represent relations like ALL, some, or none
with propositional logic. Example:
– All the girls are intelligent.
– Some apples are sweet.
• Propositional logic has limited expressive power.
• In propositional logic, we cannot describe statements in
terms of their properties or logical relationships.
• Inference: In AI, we need intelligent computers which can create
new logic from old logic or by evidence. Generating conclusions
from evidence and facts is termed as Inference.
• Inference rules: Inference rules are applied to derive proofs in
artificial intelligence, and the proof is a sequence of the conclusion
that leads to the desired goal.
• In inference rules, implication among all connectives plays an
important role.
• Some terminologies related to inference rules:
• Implication: It is one of the logical connectives which can be
represented as P → Q. It is a Boolean expression.
• Converse: Converse of implication means right-hand side
proposition goes to left-hand side & vice-versa. It is given as Q → P
• Contrapositive: The negation of converse is termed as
contrapositive, and it can be represented as ¬ Q → ¬ P.
• Inverse: The negation of implication is called inverse. It can be
represented as ¬ P → ¬ Q.
• From the above term notice that some of the compound statements
are equivalent to each other, which we can prove using truth table:

• Hence from the above truth table, we can prove that P → Q is

equivalent to ¬ Q → ¬ P, and Q→ P is equivalent to ¬ P → ¬ Q.
• Types of Inference rules:1. Modus Ponens:
• Modus Ponens rule is one of the most important rules of inference,
and it states that if P and P → Q is true, then we can infer that Q
will be true.
• Here the numerator is read as IF part and the denominator is read
as the THEN part of the rule. Comma represents AND operation.
• Proof by Truth table:

1
• 2. Modus Tollens:
• The Modus Tollens rule state that if P→ Q is true and ¬ Q is
true, then ¬ P will also be true. It can be represented as:

• Proof by Truth table:

• 3. Hypothetical Syllogism:
• It states that if P→R is true whenever P→Q is true, and
Q→R is true.
• It can be represented as the following notation:
• Proof by truth table:
• 4. Disjunctive Syllogism:
• The Disjunctive syllogism rule states that if P∨Q is true, and
¬P is true, then Q will be true. It can be represented as:

• Proof by truth-table:
• 5. Addition:
• The Addition rule is one of the common inference
rule.It states that If P is true, then P∨Q will be true.
• 6. Simplification:
• The simplification rule state that if P∧ Q is true, then Q or
P will also be true. It can be represented as:

• Proof by Truth-Table:

• 7. Resolution:
• The Resolution rule states that if P∨Q and ¬ P∧R is true,
then Q∨R will also be true. It can be represented as
Proof by Truth-Table:
• First-Order Logic in Artificial intelligence
• In Propositional logic, unfortunately we can only represent
the facts, which are either true or false.
• Hence, Propositional Logic is not sufficient to represent the
complex sentences or natural language statements.
• The propositional logic has very limited expressive power.
• Consider following sentence, which we cannot represent
using Propositional Logic logic.
• "Some humans are intelligent“ or
• "Sachin likes cricket."
• To represent above statements, PL logic is not sufficient, so
we need some more powerful logic, such as first-order logic.
• First-order logic is another way of knowledge representation
in AI and it is an extension to propositional logic.
• First-order logic is also known as Predicate logic or First-order
predicate logic and it can express relationship between those
objects.
• First-order logic (like natural language) does not only assume
that the world contains facts like propositional logic but also
assumes the following things in the world:
• Objects: A, B, people, numbers, colors, wars, theories, squares,
pits, …
• 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
• Function: Father of, best friend, third innings of, end of, ......
• As a natural language, first-order logic also has two main parts:
– Syntax & Semantics
• Syntax of FOL determines which collection of symbols is a
logical expression in first-order logic.
• 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:
• Atomic sentences are basic sentences of first-order logic.
• These sentences are formed from a predicate symbol followed by a
parenthesis with a sequence of terms.
• Predicate (term1, term2, ......, term n).
• Chinky is a cat: => cat (Chinky).
• Complex sentences are made by combining atomic sentences using
connectives.
• Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).
• First-order logic statements can be divided into two parts:
• Subject: Subject is the main part of the statement.
• Predicate: A predicate can be defined as a relation, which binds two
atoms together in a statement.
• Consider the statement: "x is an integer.", it consists of two parts,
first part x is subject of statement and second part "is an integer," is
known as a predicate.
• Quantifiers in First-order logic:
• A quantifier is a language element which generates
quantification, and specifies the quantity of specimen in the
universe of discourse.
• These are the symbols that allow us to determine or identify
the range and scope of the variable in the logical expression.
There are two types of quantifier:
– Universal Quantifier, (for all, everyone, everything)
– Existential quantifier, (for some, at least one).
• Universal Quantifier:
• Universal quantifier specifies that statement within its range
is true for everything or every instance of a particular thing.
• Universal quantifier is represented by a symbol ∀.
• In universal quantifier we use implication "→".
• If x is a variable, then ∀x is read as:
• For all x, For each x, For every x.
• Example: All man drink coffee.
• Let a variable x refers to a cat so all x can be represented in UOD as:
•

∀x man(x) → drink
(x, coffee).
It will be read as:
For all x where x is
a man who drinks
coffee.
• Existential quantifiers express that the statement
within its scope is true for at least one instance of
something.
• It is denoted by the logical operator ∃, which
resembles as inverted E.
• When it is used with a predicate variable then it is
called as an existential quantifier.
• Note: In Existential quantifier we always use AND or
Conjunction symbol (∧).
• If x is a variable, then existential quantifier will be ∃x or
∃(x). And it will be read as:
• There exists a 'x.'
• For some 'x.'
• For at least one 'x.'
• Example: Some boys are intelligent.

• ∃x: boys(x) ∧ intelligent(x)

• It will be read as:
• There are some x where x is a boy who is intelligent.
• Points to remember:
• Main connective for universal quantifier ∀ is implication →.
• The main connective for existential quantifier ∃ is and ∧.
• Properties of Quantifiers:
• In universal quantifier, ∀x∀y is similar to ∀y∀x.
• In Existential quantifier, ∃x∃y is similar to ∃y∃x.
• ∃x∀y is not similar to ∀y∃x.
• Some Examples of FOL using quantifier:
• 1. All birds fly.
• 2. Every man respects his parent.
• 3. Some boys play cricket.
4. Not all students like both Mathematics and Science.
5. Only one student failed in Mathematics.
• Free and Bound Variables:
• The quantifiers interact with variables which appear
in a suitable way. There are two types of variables
in First-order logic which are given below:
• Free Variable: A variable is said to be a free variable
in a formula if it occurs outside the scope of the
quantifier.
• Example: ∀x ∃(y)[P(x, y, z)], where z is a free
variable.
• Bound Variable: A variable is said to be a bound
variable in a formula if it occurs within the scope of
the quantifier.
• E.g ∀x [A(x) B( y)], here x and y are bound
variables.
• Inference in First-Order Logic
• It is used to deduce new facts or sentences from existing
sentences.
• Let's understand some basic terminologies of FOL.
• Substitution: It is a fundamental operation performed on
terms and formulas.
• It occurs in all inference systems in first-order logic.
• Substitution is complex in the presence of quantifiers in FOL.
• If we write F[a/x], refers to substitute a constant "a" in place
of variable "x".
• Equality
• First-Order logic does not only use predicate and terms for
making atomic sentences but also uses another way, which is
equality in FOL.
• For this, we can use equality symbols which specify that the
two terms refer to the same object.
• Example: Brother (John) = Smith.
• In the above e.g, the object referred by the Brother
(John) is similar to the object referred by Smith.
• Equality symbol can also be used with negation to
represent that two terms are not the same objects.
• Example: ￢(x=y) which is equivalent to x ≠y.
• FOL inference rules for quantifier:
• We also have inference rules in first-order logic.
• Universal Generalization
• Universal Instantiation
• Existential Instantiation
• Existential introduction
• Premise : For e.g, a person is reading a newspaper and comes
across the sentence: “Number of lung cancer diagnoses has
decreased by 50% as since smoking was banned 10 years ago."
• The person thinks critically about sentence and understands
that it is based on the following premises:
• 1) Smoking causes cancer. 2) The smoking ban stopped people
from smoking.
• Universal generalization is a valid inference rule which states
that if premise P(c) is true for any arbitrary element c in the
universe of discourse, we can have a conclusion as ∀ x P(x).
• It can be represented as: .
• This rule can be used if we want to show that every element
has a similar property.
• Example: Let's represent, P(c): "A byte contains 8 bits", so
for ∀x P(x) "All bytes contain 8 bits.", it will also be true.
• 2. Universal Instantiation:
• It is also called as universal elimination.
• This rule states that we can infer any sentence P(c) by substituting a
ground term c (a constant within domain x) from ∀ x P(x) for any
object in the universe of discourse.
• It can be represented as:
• 3. Existential instantiation is also called as Existential Elimination is a
valid inference rule in first-order logic.
• It is a rule of inference in logic that allows one to replace an
existential quantifier (∃) with a specific instance.
• It allows us to infer existence of a particular object based on the
existence of something in general.
• For example, if we know that "there exists a red apple," we can use
existential instantiation to conclude "this apple is red."
• This rule states that one can infer P(c) from the formula given in the
form of ∃x P(x) for a new constant symbol c.
• The restriction with this rule is that c used in the rule must be a new
term for which P(c ) is true.
• It can be represented as:
• 4. Existential introduction
• An existential introduction is also known as an
existential generalization and is a valid inference
rule in first-order logic.
• Existential generalization in predicate logic that
allows moving from a specific statement about one
instance to a more general statement that covers all
instances.
• It asserts that if something exists in the universe
with a certain property, then it can be concluded
that there exists something with that property in
general.
• It can be represented as:
• Forward & backward reasoning are 2 different approaches used in
problem-solving & decision-making processes
• Forward Reasoning:
– Definition: Forward reasoning, known as deductive reasoning or
forward chaining, starts with available facts and uses rules to
derive conclusions or make decisions. (bottom up approach)
– Process: In forward reasoning, we begin with initial data or
premises and then apply logical rules or algorithms to reach a
specific goal or conclusion.
– Example: In a medical diagnosis system, forward reasoning might
involve starting with symptoms reported by a patient and then
using medical knowledge and rules to identify diseases.
• Backward Reasoning:
– Definition: Backward reasoning, known as inductive reasoning
or backward chaining, starts with a desired goal or conclusion
and works backward to determine the sequence of steps or
conditions needed to achieve that goal. (top down approach)
 – Process: In backward reasoning, we start with desired
outcome and work backward through a series of steps to
determine what actions or decisions are necessary.
– Example: In a troubleshooting system for computers,
backward reasoning involve starting with the symptom
reported by a user (e.g., computer won't start) and then
working backward to identify potential causes & solutions.
• In summary, forward reasoning starts from available data and
applies rules to reach conclusions, while backward reasoning
starts from a desired outcome and works backward to
determine the necessary steps or conditions.
• Both approaches are used in various fields such as AI,
problem-solving, decision-making, and scientific reasoning.
• Let's consider a simple rule-based system for determining if a
person is eligible for a discount based on their age and membership
status.
• If a person is a member and their age is above 60, they get a 20%
discount.
• If a person is a member and their age is below 60, they get a 10%
discount.
• If a person is not a member and their age is above 60, they get a
15% discount.
• Now, let's say we have the following facts:
• Person A is a member.
• Person A's age is 65.
• Using forward chaining, system starts with facts and applies rules to
derive a conclusion.
• In this case, it would proceed as follows:
• Apply Rule 1: Person A is a member and their age is above 60, so
they get a 20% discount.
• Conclusion: Person A is eligible for a 20% discount.
• In this example, forward chaining started with the available facts
(membership status and age) and applied the rules to reach a
conclusion about the discount eligibility.
• Imagine we have a rule-based system for diagnosing diseases based
on symptoms. Let's say we have the following rules:
• If a patient has a fever and cough, they might have the flu.
• If a patient has a fever and joint pain, they might have arthritis.
• If a patient has a cough and runny nose, they might have a cold.
• Now, let's consider a patient's symptoms:
• Fever: Yes (1)
• Cough: Yes (1)
• Joint Pain: No (0)
• Runny Nose: No (0)
• We start with the given symptoms and apply the rules
to see if we can infer any conclusions:
• Rule 1: Fever (Yes) + Cough (Yes) -> Flu (Possible)
• Rule 2: Fever (Yes) + Joint Pain (No) -> Arthritis (Not
applicable)
• Rule 3: Cough (Yes) + Runny Nose (No) -> Cold (Not
applicable)
• Since we have fever and cough, according to Rule 1, it
suggests the possibility of the patient having the flu.
• This is an example of forward chaining, where we start
with the available data (symptoms) and use rules to
derive new information (diagnosis).
• In summary, forward chaining in AI involves iteratively
applying rules to given data to reach conclusions or
make decisions based on the available information.
• Backward chaining is a reasoning strategy in AI where
system starts with a goal and works backward to
determine which sequence of actions / events can
lead to that goal.
• It is commonly used in rule-based systems and expert
systems to reach a conclusion or make a decision.
• Here's an example to illustrate backward chaining:
• Let's say we have a rule-based system for diagnosing
diseases.
• The system has a set of rules (if-then statements)
based on symptoms and diseases. One rule could be:
• If a patient has a high fever and body aches, then they
might have the flu.
• Let's assume system is given goal of determining patient's disease.
• System will start by checking if the patient has a high fever and
body aches. If these conditions are met, it concludes that the
patient might have the flu, fulfilling the goal.
• If the initial conditions are not met, the system will backtrack and
look for other rules or conditions that could lead to the goal. For
example, it might have another rule:
• If a patient has a rash, itching they might have an allergic reaction.
• System will continue this backward reasoning process until it either
reaches a conclusion or exhausts all paths without reaching goal.
• Consider another problem: determining whether a student is eligible
for a scholarship based on their grades & extracurricular activities.
• We have the following rules:
• If a student has a GPA of 8.5 or higher, they are eligible for the
scholarship.
• If a student has participated in at least two extracurricular activities,
they are eligible for the scholarship.
• Let's say we want to determine if a specific student, Ram, is eligible
for the scholarship. We start with the goal (Ram being eligible for
the scholarship) and work backward to see if conditions are met.
• Goal: Ram is eligible for the scholarship.
• Rule 1: Check if Ram's GPA is 8.5 or higher.
– If true, Ram meets one condition for the scholarship.
– If false, we move to the next rule.
• Rule 2: Check if Ram has participated in at least 2 extracurricular
activities.
– If true, Ram meets the second condition for the scholarship.
– If false, Ram does not meet the conditions for the scholarship.
• Let's assume Ram's GPA is 8.6 and he has participated in three
extracurricular activities.
• Here, both conditions are true, and Ram is eligible for scholarship.
• Unification in reasoning refers to process of finding
substitutions for variables in logical expressions to make
them equivalent.
• It is used in automated reasoning systems  AI , logic
programming. Let's consider following logical expressions:
• ( P(x, y) ) - "x is a parent of y"
• ( P(John, Mary) ) - "John is a parent of Mary"
• ( P(Arun, Venkat) ) - “Arun is a parent of Venkat"
• Now, suppose we want to unify (P(x, y)) and (P(John, Mary)).
• Unification process involves finding substitutions for
variables x and y that make two expressions equivalent.
• Here, unification would result in the following substitutions:
• ( x ) is substituted with ( John )
• ( y ) is substituted with ( Mary )
• After unification, ( P(x, y) ) becomes ( P(John, Mary) ), which
means "John is a parent of Mary."
• Inference engine:
• The inference engine is the component of the
intelligent system in AI, which applies logical rules to
knowledge base to infer new info from known facts.
• Inference engine commonly proceeds in 2 modes:
• Forward chaining
• Backward chaining
• Horn Clause and Definite clause:
• Horn clause and definite clause are the forms of
sentences, which enables knowledge base to use a
more restricted and efficient inference algorithm.
• Logical inference algorithms use forward and backward
chaining approaches, which require KB in the form of
the first-order definite clause.
• Definite clause: It is a disjunction of literals
with exactly one positive literal and is also known as
or strict horn clause.
• Horn clause: It is a disjunction of literals with at most
one positive literal. All definite clauses are horn clauses
• Definite Clause: A definite clause is a logical statement
that consists of a head and a body.
• The head represents the conclusion or the fact being
asserted, while body contains the conditions or
premises that must be true for conclusion to hold.
• Example: loves(john, mary) :- happy(john), kind(mary)
• In this example, loves(john, mary) is the head,
representing the conclusion that John loves Mary.
• The body, happy(john), kind(mary), specifies the
conditions under which this conclusion is true—John
must be happy, and Mary must be kind.
• Horn Clause: It is a type of definite clause that has at
most one positive literal in the head.
• It can also have 0 or more negative literals in the body.
• Example: happy(john) :- kind(john), helpful(john).
• In this Horn clause, happy(john) is the head,
representing the conclusion that John is happy.
• The body, kind(john), helpful(john), contains
conditions for John to be happy - he must be kind and
helpful.
• Another example with a negative literal:
• likes(john, X) :- kind(X), not(happy(X)).
• Here, likes(john, X) asserts that John likes someone
(denoted as X).
• The body kind(X), not(happy(X)) specifies that John
likes someone who is kind but not happy.
• Forward chaining starts with atomic sentences in the
knowledge base and applies inference rules (Modus
Ponens) in the forward direction until goal is reached.
• This algo starts from known facts, triggers all rules
whose premises are satisfied, add their conclusion to
known facts
• Properties of Forward Chaining
• This process repeats until the problem is solved.
• It is a bottom-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 the goal using available data.
• "As per 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 missiles were sold to it by Robert, who is an
American citizen."
• Prove that "Robert is criminal."
• To solve the above problem, first, we will convert all the above
facts into first-order definite clauses, and then we will use a
forward-chaining algorithm to reach the goal.
• Facts Conversion into FOL:
• 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)
• 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)
• All of the missiles were sold to country A by Robert.
?p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A) ......(4)
• Missiles are weapons.
Missile(p) → Weapons (p) .......(5)
• Enemy of America is known as hostile.
Enemy(p, America) →Hostile(p) ........(6)
• Country A is an enemy of America.
Enemy (A, America) .........(7)
• Robert is American
American(Robert). ..........(8)
• Step-1:
• In the first step we will start with the known facts and will
choose the sentences which do not have implications, such
as: American(Robert), Enemy(A, America), Owns(A, T1), and
Missile(T1). All these facts will be represented as below.
•
• Step-2:
• At the second step, we will see those facts which infer
from available facts and with satisfied premises.
• Rule-(1) does not satisfy premises, so it will not be added in
the first iteration.
• Rule-(2) and (3) are already added.
• Rule-(4) satisfy with the substitution {p/T1}, so Sells
(Robert, T1, A) is added, which infers from the conjunction
of Rule (2) and (3)
• Rule-(6) is satisfied with the substitution(p/A), so Hostile(A)
is added and which infers from Rule-(7).
• Step-3: At step-3, as we can check Rule-(1) is satisfied with
the substitution {p/Robert, q/T1, r/A}, so we can add
Criminal(Robert) which infers all the available facts. And
hence we reached our goal statement.

• Hence it is proved that Robert is Criminal using forward

chaining approach.
• Backward-chaining used in inference engine is also known
as a backward deduction or backward reasoning method.
• A backward chaining algo 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.
• It is based on modus ponens inference rule.
• Here, goal is broken into 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 algo is used in game theory, automated
theorem proving tools, inference engines, proof assistants,
and various AI applications.
• The backward-chaining method mostly uses a depth-first
search strategy for proof.
• In backward-chaining, we use same e.g & will rewrite all rules.
• American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) →
Criminal(p) ...(1)
Owns(A, T1) ........(2)
• Missile(T1) …(3)
• ?p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A) ......(4)
• Missile(p) → Weapons (p) .......(5)
• Enemy(p, America) →Hostile(p) ........(6)
• Enemy (A, America) .........(7)
• American(Robert). ..........(8)
• In Backward chaining, we will start with our goal predicate,
which is Criminal(Robert), and then infer further rules.
• Step-1: At the first step, we will take goal fact. So our goal
fact is "Robert is Criminal," so following is the predicate of it.
• Step-2:
• At the second step, we will infer other facts from goal fact
which satisfies the rules.
• So as we can see in Rule-1, the goal predicate Criminal
(Robert) is present with substitution {Robert/P}.
• So we will add all the conjunctive facts below the first
level and will replace p with Robert.
• Here we can see American (Robert) is a fact, so it is
proved here.
• Step-3: At step-3, we will extract further fact
Missile(q) which infer from Weapon(q), as it
satisfies Rule-(5). Weapon (q) is also true with the
substitution of a constant T1 at q.
• At step-4, we can infer facts Missile(T1) and
Owns(A, T1) form Sells(Robert, T1, r) which
satisfies the Rule- 4, with the substitution of A in
place of r. So these two statements are proved
here.
• At step-5, we can infer the fact Enemy(A,
America) from Hostile(A) which satisfies Rule- 6.
And hence all the statements are proved true using
backward chaining.
•
• The resolution inference rule:
• Resolution is used, if there are various statements are given, and
we need to prove a conclusion of those statements.
• It is a deductive inference rule that allows us to resolve a
disjunction (disjunction implies that at least one statement is
true).
• If A implies B and C implies not B, then A implies not C.
• Resolution in AI - Example
• Steps for Resolution:
• Conversion of facts into first-order logic.
• Convert FOL statements into CNF
• Negate the statement which needs to prove (proof by
contradiction)
• Draw resolution graph (unification).
• To understand all the above steps, we will take an example in
which we will apply resolution.
• Example: John likes all kind of food.
• Apple and vegetable are food
• Anything anyone eats and not killed is food.
• Anil eats peanuts and still alive
• Harry eats everything that Anil eats.
• Prove by resolution that:
• John likes peanuts.
• Step-1: Conversion of Facts into FOL
• In the first step we will convert all the given
statements into its first order logic.

• Step-2: Conversion of FOL into CNF

• In First order logic resolution, it is required to
convert the FOL into CNF as CNF form makes easier
for resolution proofs.
• 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 example 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).
• Note: Statements "food(Apple) Λ food(vegetables)" and
"eats (Anil, Peanuts) Λ alive(Anil)" can be written in two
separate statements.
• 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:
• Now in this step, we will solve the problem by resolution tree using
substitution. For the above problem, it will be given as follows: