Unit 3
Unit 3
Unit 3
Year 1996
Page 1152
Knowledge Representation Techniques
• Frames are derived from semantic networks and later evolved into our modern-day
classes and objects. A single frame is not much useful. Frames system consist of a
collection of frames which are connected
Advantages of frame representation:
• The frame representation is comparably flexible and used by many applications in
AI.
• It is very easy to add slots for new attribute and relations.
• It is easy to include default data and to search for missing values.
Disadvantages of frame representation:
• In frame system inference mechanism is not be easily processed.
• Frame representation has a much generalized approach.
4. Production Rules
• Production rules system consist of (condition, action) pairs which mean, "If
condition then action". It has mainly three parts:
• The set of production rules
• Working Memory
• The recognize-act-cycle
Knowledge Representation Techniques
• In production rules agent checks for the condition and if the condition exists then
production rule fires and corresponding action is carried out.. This complete process
is called a recognize-act cycle.
Example:
• IF (at bus stop AND bus arrives) THEN action (get into the bus)
• IF (on the bus AND paid AND empty seat) THEN action (sit down).
Advantages of Production rule:
• The production rules are expressed in natural language.
• The production rules are highly modular, so we can easily remove, add or modify
an individual rule.
Disadvantages of Production rule:
• Production rule system does not exhibit any learning capabilities, as it does not
store the result of the problem for the future uses.
• During the execution of the program, many rules may be active hence rule-based
production systems are inefficient.
Propositional logic In Artificial intelligence
• Proposition is a declarative statement which is either true or false. It is a technique
of knowledge representation in logical and mathematical form.
Facts about propositional logic:
• Propositional logic is also called Boolean logic as 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.
• Propositional logic consists of an object, relations or function, and logical
connectives. These connectives are also called logical operators.
• The propositions and connectives are the basic elements of the propositional logic.
• Connectives can be said as a logical operator 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 such
as "Where is Rohini", "How are you", "What is your name", are not propositions.
Types of Propositions
Atomic Proposition:
• Atomic propositions are the simple propositions. It consists of a single proposition
symbol. These are the 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 also a proposition as it is a false fact.
Compound proposition:
• Compound propositions are constructed by combining simpler or atomic
propositions, using parenthesis and logical connectives.
• Example:
• a) "It is raining today, and street is wet."
• b) "Ankit is a doctor, and his clinic is in Mumbai."
Logical Connectives:
• Logical connectives are used to connect two simpler propositions or representing a
sentence logically. We can create compound propositions with the help of logical
connectives. There are mainly five connectives, which are given as follows:
Logical Connectives
Truth Table
• We can combine all the possible combination with logical connectives, and the
representation of these combinations in a tabular format is called Truth table.
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
• First Precedence
• Parenthesis
• Second Precedence
• Negation
• Third Precedence
• Conjunction(AND)
• Fourth Precedence
• Disjunction(OR)
• Fifth Precedence
• Implication
• Six Precedence
• Biconditional
Logical equivalence:
• Logical equivalence is one of the features of propositional logic. Two propositions
are said to be logically equivalent if and only if the columns in the truth table are
identical to each other.
Propositional logic In Artificial intelligence
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)
Propositional logic In Artificial intelligence
• 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.
– All the girls are intelligent.
– Some apples are sweet.
• Propositional logic has limited expressive power.
First-Order Predicate logic(FOPL)
• It is an extension to propositional logic.
• First-order logic is also known as Predicate logic or First-order predicate logic.
• First-order logic 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, wumpus,
• 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 inning of, end of, ......
• As a natural language, first-order logic also has two main parts:
Syntax
Semantic
Syntax of First-Order logic:
• The syntax of FOL determines which collection of symbols is a logical expression
in first-order logic. The basic syntactic elements of first-order logic are symbols. We
write statements in short-hand notation in FOL.
First-Order Predicate logic(FOPL)
Constant 1, 2, A, John, Mumbai, cat,....
Variables x, y, z, a, b,....
Connectives ∧, ∨, ¬, ⇒, ⇔
Equality ==
Quantifier ∀, ∃
First-Order Predicate logic(FOPL)
Atomic sentences:
• Atomic sentences are the most basic sentences of first-order logic. These sentences
are formed from a predicate symbol followed by a parenthesis with a sequence of
terms.
• We can represent atomic sentences as Predicate (term1, term2, ......, term n).
• Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).
Chinky is a cat: => cat (Chinky).
Complex Sentences:
• Complex sentences are made by combining atomic sentences using connectives.
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.
Example:
• "x is an integer.", it consists of two parts, the first part x is the subject of the
statement and second part "is an integer," is known as a predicate.
First-Order Predicate logic(FOPL)
Quantifiers in First-order logic:
• These are the symbols that permit to determine or identify the range and scope of
the variable in the logical expression. There are two types of quantifier:
– Universal Quantifier, (for all, everyone, everything)
– Existential quantifier, (for some, at least one).
Universal Quantifier:
• Universal quantifier is a symbol of logical representation, which specifies that the
statement within its range is true for everything or every instance of a particular
thing.
• The Universal quantifier is represented by a symbol ∀, which resembles an inverted
A.
• 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.
First-Order Predicate logic(FOPL)
Example:
• All man drink coffee.
• ∀x man(x) → drink (x, coffee).
• It will be read as: There are all x where x is a man who drink coffee.
Existential Quantifier:
• Existential quantifiers are the type of quantifiers, which express that the statement
within its scope is true for at least one instance of something.
• It is denoted by the logical operator ∃, which resembles as inverted E. When it is
used with a predicate variable then it is called as an existential quantifier.
• 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.
First-Order Predicate logic(FOPL)
• ∃x: boys(x) ∧ intelligent(x)
• It will be read as: There are some x where x is a boy who is intelligent.
Notes:
• The main connective for universal quantifier ∀ is implication →.
• The main connective for existential quantifier ∃ is and ∧.
knowledge-engineering
• The process of constructing a knowledge-base in first-order logic is called as
knowledge- engineering. In knowledge-engineering, someone who investigates a
particular domain, learns important concept of that domain, and generates a formal
representation of the objects, is known as knowledge engineer.
Inference in First-Order Logic
• Inference in First-Order Logic is used to deduce new facts or sentences from
existing sentences
Unification
• Unification is a process of making two different logical atomic expressions identical by
finding a substitution. Unification depends on the substitution process.
• It takes two literals as input and makes them identical using substitution.
• Let Ψ1 and Ψ2 be two atomic sentences and 𝜎 be a unifier such that, Ψ1𝜎 = Ψ2𝜎, then it
can be expressed as UNIFY(Ψ1, Ψ2).
Example:
Find the MGU for Unify{King(x), King(John)}
• Let Ψ1 = King(x), Ψ2 = King(John),
• Substitution θ = {John/x} is a unifier for these atoms and applying this substitution,
and both expressions will be identical.
• The UNIFY algorithm is used for unification, which takes two atomic sentences and
returns a unifier for those sentences (If any exist).
• Unification is a key component of all first-order inference algorithms.
• It returns fail if the expressions do not match with each other.
• The substitution variables are called Most General Unifier or MGU.
Conditions for Unification:
• Predicate symbol must be same, atoms or expression with different predicate symbol
can never be unified.
Unification
• Number of Arguments in both expressions must be identical.
• Unification will fail if there are two similar variables present in the same expression.
Algorithm: Unify(Ψ1, Ψ2)
• Step. 1: If Ψ1 or Ψ2 is a variable or constant, then:
• a) If Ψ1 or Ψ2 are identical, then return NIL.
• b) Else if Ψ1is a variable,
• a. then if Ψ1 occurs in Ψ2, then return FAILURE
• b. Else return { (Ψ2/ Ψ1)}.
• c) Else if Ψ2 is a variable,
• a. If Ψ2 occurs in Ψ1 then return FAILURE,
• b. Else return {( Ψ1/ Ψ2)}.
• d) Else return FAILURE.
• Step.2: If the initial Predicate symbol in Ψ1 and Ψ2 are not same, then return
FAILURE.
• Step. 3: IF Ψ1 and Ψ2 have a different number of arguments, then return FAILURE.
• Step. 4: Set Substitution set(SUBST) to NIL.
Unification Algorithm
Step. 5: For i=1 to the number of elements in Ψ1.
a) Call Unify function with the ith element of Ψ 1 and ith element of Ψ2, and put the result into S.
b) If S = failure then returns Failure
c) If S ≠ NIL then do,
a. Apply S to the remainder of both L1 and L2.
b. SUBST= APPEND(S, SUBST).
Step.6: Return SUBST.
Implementation of the Algorithm
Step.1: Initialize the substitution set to be empty.
Step.2: Recursively unify atomic sentences:
Check for Identical expression match.
• If one expression is a variable vi, and the other is a term ti which does not contain variable vi,
then:
– Substitute ti / vi in the existing substitutions
– Add ti /vi to the substitution setlist.
– If both the expressions are functions, then function name must be similar, and the
number of arguments must be the same in both the expression.
• For each pair of the following atomic sentences find the most general unifier (If exist).
Inference Engine
• The inference engine is the component of the intelligent system in artificial intelligence,
which applies logical rules to the knowledge base to infer new information from known
facts. The first inference engine was part of the expert system. Inference engine commonly
proceeds in two modes, which are:
• 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: A clause which is a disjunction of literals with exactly one positive
literal is known as a definite clause or strict horn clause.
• Horn clause: A clause which is a disjunction of literals with at most one positive literal is
known as horn clause. Hence all the definite clauses are horn clauses.
Example:
(¬ p V ¬ q V k). It has only one positive literal k.
• It is equivalent to p ∧ q → k.
Forward Chaining
• Forward chaining is also known as a forward deduction or forward reasoning
method when using an inference engine. Forward chaining is a form of reasoning
which start with atomic sentences in the knowledge base and applies inference rules
(Modus Ponens) in the forward direction to extract more data until a goal is
reached.
• The Forward-chaining algorithm starts from known facts, triggers all rules whose
premises are satisfied, and add their conclusion to the known facts. This process
repeats until the problem is solved.
Properties of Forward-Chaining:
• It is a down-up approach, as it moves from bottom to top.
• It is a process of making a conclusion based on known facts or data, by starting
from the initial state and reaches the goal state.
• Forward-chaining approach is also called as data-driven as we reach to the goal
using available data.
• Forward -chaining approach is commonly used in the expert system, such as CLIPS,
business, and production rule systems.
Forward Chaining
• "As per the law, it is a crime for an American to sell weapons to hostile nations.
Country A, an enemy of America, has some missiles, and all the missiles were
sold to it by Robert, who is an American citizen."Prove that "Robert is
criminal.“
• Facts Conversion into FOL:
• 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)
Backward Chaining
5. Forward chaining tests for all the available rules Backward chaining only tests for few
required rules.
6. Forward chaining is suitable for the planning, monitoring, control, Backward chaining is suitable for
and interpretation application. diagnostic, prescription, and
debugging application.
7. Forward chaining can generate an infinite number of possible Backward chaining generates a finite
conclusions. number of possible conclusions.
Reasoning
2. Inductive Reasoning:
• Inductive reasoning is a form of reasoning to arrive at a conclusion using limited
sets of facts by the process of generalization. It starts with the series of specific
facts or data and reaches to a general statement or conclusion.
• Inductive reasoning is a type of propositional logic, which is also known as cause-
effect reasoning or bottom-up reasoning.
• In inductive reasoning, we use historical data or various premises to generate a
generic rule, for which premises support the conclusion.
• In inductive reasoning, premises provide probable supports to the conclusion, so
the truth of premises does not guarantee the truth of the conclusion.
• Example:
• Premise: All of the pigeons we have seen in the zoo are white.
• Conclusion: Therefore, we can expect all the pigeons to be white
Reasoning
3. Abductive reasoning:
• Abductive reasoning is a form of logical reasoning which starts with single or
multiple observations then seeks to find the most likely explanation or conclusion
for the observation.
• Abductive reasoning is an extension of deductive reasoning, but in abductive
reasoning, the premises do not guarantee the conclusion.
• Example:
• Implication: Cricket ground is wet if it is raining
• Axiom: Cricket ground is wet.
• Conclusion It is raining.
Reasoning
5. Monotonic Reasoning:
• In monotonic reasoning, once the conclusion is taken, then it will remain the same
even if we add some other information to existing information in our knowledge
base. In monotonic reasoning, adding knowledge does not decrease the set of
prepositions that can be derived. Example:
• Earth revolves around the Sun.
• It is a true fact, and it cannot be changed even if we add another sentence in
knowledge base like, "The moon revolves around the earth" Or "Earth is not
round," etc.
Advantages of Monotonic Reasoning:
• In monotonic reasoning, each old proof will always remain valid.
• If we deduce some facts from available facts, then it will remain valid for always.
Disadvantages of Monotonic Reasoning:
• We cannot represent the real world scenarios using Monotonic reasoning.
• Since we can only derive conclusions from the old proofs, so new knowledge from
the real world cannot be added.
Reasoning
6. Non-monotonic Reasoning
• In Non-monotonic reasoning, some conclusions may be invalidated if we add some
more information to our knowledge base.
• Example: Birds can fly
• Penguins cannot fly
• Pitty is a bird
• So from the above sentences, we can conclude that Pitty can fly.
• However, if we add one another sentence into knowledge base "Pitty is a penguin",
which concludes "Pitty cannot fly", so it invalidates the above conclusion.
Advantages of Non-monotonic reasoning:
• In Non-monotonic reasoning, we can choose probabilistic facts or can make
assumptions. Also used in Robot Navigation.
Disadvantages of Non-monotonic Reasoning:
• In non-monotonic reasoning, the old facts may be invalidated by adding new
sentences.
• It cannot be used for theorem proving.
Resolution
• Resolution is a theorem proving technique that proofs by contradictions. It was
invented by a Mathematician John Alan Robinson in the year 1965.
• Resolution is used, if there are various statements are given, and we need to prove a
conclusion of those statements. Unification is a key concept in proofs by resolutions.
Resolution is a single inference rule which can efficiently operate on the conjunctive
normal form or clausal form.
• Clause: Disjunction of literals (an atomic sentence) is called a clause. It is also known
as a unit clause.
• Conjunctive Normal Form: A sentence represented as a conjunction of clauses is
said to be conjunctive normal form or CNF.
The resolution inference rule:
• .
– ¬ eats(Anil, w) V eats(Harry, w)
– killed(g) V alive(g)
– ¬ alive(k) V ¬ killed(k)
– likes(John, Peanuts).
• Distribute conjunction ∧ over disjunction ¬.
This step will not make any change in this problem.
• Step-3: Negate the statement to be proved
• In this statement, we will apply negation to the conclusion statements, which will be
written as ¬likes(John, Peanuts)
• Step-4: Draw Resolution graph:
• Now in this step, we will solve the problem by resolution tree using substitution.
For the above problem, it will be given as follows: