Chapter Three
Knowledge Representation and
Reasoning
1 / 57
What is Knowledge-Based Agent?
●
An intelligent agent needs knowledge about the real world for
taking decisions and reasoning to act efficiently.
●
Knowledge-based agents have the capability of
– maintaining an internal state of knowledge
– reasoning over that knowledge,
– updating their knowledge after observations and take
actions.
●
These agents can represent the world with some formal
representation and act intelligently.
●
Knowledge-based agents are composed of two main parts:
– Knowledge-base and
– Inference system.
2 / 57
The Architecture of KBA
3 / 57
Important Definitions
●
Knowledge base:
– It is a central component of a knowledge-based agent.
– It is a collection of sentences (here 'sentence' is a technical
term and it is not identical to sentence in English).
– These sentences are expressed in a language which is called
a knowledge representation language.
– It stores fact about the world.
●
Inference system.
– Inference system allows us to add a new sentence to the
knowledge base.
– A sentence is a proposition about the world.
– Inference system applies logical rules to the KB to deduce
new information so that an agent can update the KB.
4 / 57
Cont’d
●
An inference system works mainly in two rules which are given
as:
– Forward chaining
●
The inference system starts with the available
information and iteratively applies rules to derive new
conclusions until a goal is reached.
– Backward chaining
●
The inference system starts with a goal and works
backward to find a sequence of rules and facts that lead
to the goal.
5 / 57
Operations Performed by KBA
●
Following are three operations which are performed by KBA in
order to show the intelligent behavior:
– TELL: This operation tells the knowledge base about what
the agent perceives from the environment
– ASK: This operation asks the knowledge base to determine
the appropriate action it should perform.
– Perform: It performs the selected action.
6 / 57
What is Knowledge Representation?
●
It is responsible for representing information about the real
world in a way that a computer can understand and utilize this
knowledge to solve complex real-world problems.
●
Examples include diagnosing a medical condition or
communicating with humans in natural language.
●
It also describes how we can represent knowledge in artificial
intelligence.
●
It goes beyond merely storing data into a database; it enables
an intelligent machine to learn from that knowledge and
experiences, allowing it to behave intelligently, akin to a
human.
7 / 57
Types of Knowledge
8 / 57
Types of Knowledge
●
Declarative Knowledge:
– Declarative knowledge is knowing about something.
– It includes concepts, facts, and objects.
– Also known as descriptive knowledge and expressed in
declarative sentences.
●
Procedural Knowledge:
– Also known as imperative knowledge.
– Procedural knowledge is responsible for knowing how to do
something.
– Includes rules, strategies, procedures, agendas, etc.
9 / 57
Types of Knowledge
●
Meta-knowledge:
– Knowledge about other types of knowledge is called Meta-
knowledge.
●
Heuristic Knowledge:
– It represents the knowledge of experts in a field or subject.
– It consists of rules of thumb based on previous experiences
and awareness of approaches, which are good to work but
not guaranteed.
●
Structural Knowledge:
– Structural knowledge is basic knowledge related to problem-
solving.
– It explains the relationships that exist between concepts or
objects.
10 / 57
Approaches to Knowledge
Representation
●
Simple Relational Knowledge:
– It is the simplest way of storing facts, which uses the
relational method. Each fact about a set of objects is
systematically set out in columns.
– This approach to knowledge representation is well-known in
database systems where the relationship between different
entities is represented.
11 / 57
Approaches to Knowledge
Representation
●
Inheritable Knowledge:
– In this approach, all data must be
stored into a hierarchy of classes. The
inheritance property is applied.
Elements inherit values from other
members of a class. This approach
contains inheritable knowledge,
showing a relation between instance
and class.
– Every individual frame can represent
the collection of attributes and its
value. In this approach, objects and
values are represented in boxed nodes.
Arrows are used to point from objects
to their values.
12 / 57
Approaches to Knowledge
Representation
●
Inferential Knowledge:
– The inferential knowledge approach represents knowledge
in the form of formal logics.
– This approach can be used to derive more facts and is
guaranteed correctness.
– Example: Let’s suppose there are two statements:
●
Marcus is a man
●
All men are mortal
– Then it can be represented as:
●
man(Marcus)
●
∀x = man(x) −→ mortal(x)
13 / 57
Approaches to Knowledge
Representation
●
Procedural Knowledge:
– The procedural knowledge approach uses small programs
and codes that describe how to do specific things and how
to proceed.
– In this approach, an important rule used is the If-Then rule.
Various coding languages such as LISP language and Prolog
language can be used in this knowledge representation
approach.
14 / 57
Propositional Logic
●
What is Propositional Logic:
– Propositional logic (PL) is the simplest form of logic where all
the statements are made by propositions.
– A proposition is a declarative statement that is either true or
false.
– It is a technique of knowledge representation in logical and
mathematical form.
15 / 57
Syntax of Propositional Logic
●
Syntax of Propositional Logic:
– Atomic Proposition:
●
It consists of a single proposition symbol. These are the
sentences which must be either true or false.
●
2 + 2 is 4, it is an atomic proposition as it is a true fact.
●
”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 parentheses and
logical connectives.
●
”It is raining today, and the street is wet.”
●
”Ankit is a doctor, and his clinic is in Mumbai.”
16 / 57
Logical Connectives
●
Logical Connectives:
– Logical connectives are used to connect two simpler
propositions or represent a sentence logically.
●
Negation: A sentence such as ¬P is called negation of P.
A literal can be either a Positive literal or a negative
literal.
●
Conjunction: A sentence which has ∧ connective such
as P ∧ Q is called a conjunction.
●
Disjunction: A sentence which has ∨ connective, 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 also known as if-then rules.
●
Biconditional: A sentence such as P ↔ Q is a
Biconditional sentence, for example, ”If I am breathing,
17 / 57
then I am alive.”
Cont’d
18 / 57
Truth Table
19 / 57
Truth Table
20 / 57
Truth Table
21 / 57
Precedence of Connectives
22 / 57
Logical Equivalence
●
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.
23 / 57
Properties of Operators
●
Commutativity: ●
Distributive:
– P ∧ Q = Q ∧ P, or – P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P
∧ R),
– P ∨ Q = Q ∨ P.
– P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P
●
Associativity:
∨ R).
– (P ∧ Q) ∧ R = P ∧ (Q ∧ R), ●
De Morgan’s Law:
– (P ∨ Q) ∨ R = P ∨ (Q ∨ R). – ¬(P ∧ Q) = (¬P) ∨ (¬Q),
●
Identity Element: – ¬(P ∨ Q) = (¬P) ∧ (¬Q).
– P ∧ True = P, ●
Double-negation elimination:
– P ∨ True = True. – ¬(¬P) = P.
24 / 57
Rules of Inference
●
Implication: It is one of the logical connectives which can be
represented as P → Q. It is a Boolean expression.
●
Converse: The converse of implication, which means the right-
hand side proposition goes to the left-hand side and vice-versa.
It can be written 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.
25 / 57
Types of Inference Rules
●
Modus Ponens:
– The Modus Ponens rule is one of the most important rules of
inference, and it states that if P and P → Q are true, then we
can infer that Q will be true.
– Example:
●
Statement-1: ”If I am sleepy then I go to bed” ⇒ P → Q
●
Statement-2: ”I am sleepy” ⇒ P
●
Conclusion: ”I go to bed.” ⇒ Q
– Hence, we can say that, if P → Q is true and P is true, then Q
will be true.
26 / 57
Types of Inference Rules
●
Modus Tollens:
– The Modus Tollens rule states that if P → Q is true and ¬Q is
true, then ¬P will also be true.
– Example:
●
Statement-1: ”If I am sleepy then I go to bed” ⇒ P → Q
●
Statement-2: ”I do not go to bed.” ⇒∼ Q
●
Statement-3: Which infers that ”I am not sleepy” ⇒∼ P
27 / 57
Types of Inference Rules
●
Hypothetical Syllogism:
– The Hypothetical Syllogism rule states that P → R is true
whenever P → Q is true, and Q → R is true.
– Example:
●
Statement-1: ”If you have my home key then you can
unlock my home.” P → Q
●
Statement-2: ”If you can unlock my home then you can
take my money.” Q → R
●
Conclusion: ”If you have my home key then you can take
my money.” P → R
28 / 57
Types of Inference Rules
●
Disjunctive Syllogism:
– The Disjunctive Syllogism rule states that if P ∨ Q is true,
and ¬P is true, then Q will be true.
– Example:
●
Statement-1: ”Today is Sunday or Monday.” ⇒ P ∨ Q
●
Statement-2: ”Today is not Sunday.” ⇒ ¬P
●
Conclusion: ”Today is Monday.” ⇒ Q
29 / 57
Types of Inference Rules
●
Addition:
– The Addition rule is one of the common inference rules, and
it states that if P is true, then P ∨ Q will be true.
– Example:
●
Statement-1: ”I have a vanilla ice-cream.” ⇒ P
●
Statement-2: ”I have chocolate ice-cream.” ⇒ Q
●
Conclusion: ”I have vanilla or chocolate ice-cream.” ⇒ (P
∨ Q)
30 / 57
Types of Inference Rules
●
Simplification:
– The Simplification rule states that if P ∧ Q is true, then Q or
P will also be true.
– Example:
●
Statement: P ∧ Q is true.
●
Conclusion: Q or P will also be true.
31 / 57
Types of Inference Rules
●
Resolution:
– The Resolution rule states that if P ∨ Q and ¬P ∨ R is true,
then Q ∨ R will also be true.
– Example:
●
Statement-1: P ∨ Q is true.
●
Statement-2: ¬P ∨ R is true.
●
Conclusion: Q ∨ R will also be true.
32 / 57
First Order Logic
●
What is First-Order Logic?
– First-order logic is another way of knowledge representation
in artificial intelligence. It is an extension to propositional
logic.
– FOL is sufficiently expressive to represent natural language
statements in a concise way.
– First-order logic is also known as Predicate Logic or First-
order Predicate Logic.
– It is a powerful language that develops information about
objects in an easier way and can also express the
relationships between those objects.
33 / 57
Syntax of First Order Logic
●
Constants: Constant1, 2, A, John, Mumbai, cat.
●
Variables: x, y , z, a, b, . . .
●
Predicates: Brother, Father, >, . . .
●
Functions: sqrt, LeftLegOf, . . .
●
Connectives: ∧, ∨, ¬, ⇒, ⇔
●
Equality: =
●
Quantifiers: ∀, ∃
34 / 57
Syntax of First Order Logic
●
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(term 1 , term 2 , . . . , term n ).
– Example:
●
Ravi and Ajay are brothers: ⇒ Brothers(Ravi, Ajay).
●
Chinky is a cat: ⇒ cat(Chinky).
35 / 57
Syntax of First Order Logic
●
Subject and Predicate:
– Subject is the main part of the statement.
– A predicate can be defined as a relation, which binds two
atoms together in a statement.
– The sentence ”John and his sister are playing in the park”
can be represented as follows:
●
Subject: John and his sister
●
Predicate: are playing in the park
36 / 57
Quantifiers in FOL
●
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 the 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 men drink coffee.
– ∀x man(x) → drink(x, coffee), which is read as, ”For all x
where x is a man who drinks coffee.” 37 / 57
Quantifiers in FOL
●
Existential Quantifier:
– 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 an
inverted E.
– When used with a predicate variable, it is called an
existential quantifier. In Existential quantifier, we always use
the AND or Conjunction symbol (∧).
– If x is a variable, then the existential quantifier will be ∃x or
∃(x). It is read as:
●
There exists an x.
●
For some x.
●
For at least one x.
– Example: Some boys are intelligent.
●
∃x boys(x) ∧ intelligent(x) which is read as ”There 38 / 57
exists some x where x is a boy who is intelligent.”
Examples of FOL using Quantifiers
All birds fly:
∀x bird(x) → fly(x)
Every man respects his parent:
∀x man(x) → respects(x, parent)
Some boys play cricket:
∃x boys(x) → play(x, cricket)
Not all students like both Mathematics and Science:
¬∀x [student(x) → like(x, Mathematics) ∧ like(x, Science)]
39 / 57
Reasoning
●
What is Reasoning?
– The reasoning is the mental process of deriving logical
conclusions and making predictions from available
knowledge, facts, and beliefs.
– It is a general process of thinking rationally to find valid
conclusions.
– In artificial intelligence, reasoning is essential so that the
machine can also think rationally like a human brain and
perform like a human.
40 / 57
Types of Reasoning
●
Deductive Reasoning?
– Deductive reasoning is deducing new information from
logically related known information.
– It is a form of valid reasoning, where the argument’s
conclusion must be true when the premises are true.
– Top-down Reasoning Example:
●
Premise-1: All humans eat veggies.
●
Premise-2: Suresh is human.
●
Conclusion: Suresh eats veggies.
41 / 57
Types of Reasoning
●
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 a series of specific facts or data and reaches a
general statement or conclusion.
– Cause-effect Reasoning (Bottom-up Reasoning) 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.
42 / 57
Types of Reasoning
●
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.
– It is an extension of deductive reasoning, but 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.
43 / 57
Types of Reasoning
●
Common Sense Reasoning:
– Common sense reasoning is an informal form of reasoning,
gained through experiences.
– It simulates the human ability to make presumptions about
events that occur every day.
– It relies on good judgment rather than exact logic and
operates on heuristic knowledge and rules.
– Example:
●
One person can be at one place at a time.
●
If I put my hand in a fire, then it will burn.
44 / 57
Types of Reasoning
●
Monotonic Reasoning:
– In monotonic reasoning, once the conclusion is taken, it
remains the same even if we add new information to the
existing knowledge base.
– The set of propositions derived does not decrease with the
addition of new facts. Monotonic reasoning is not suitable
for real-time systems, as facts may change in real time.
– Example:
●
Earth revolves around the Sun.
●
It is a true fact and remains unchanged even if we add
another sentence to the knowledge base.
45 / 57
Types of Reasoning
●
Non-monotonic Reasoning:
– In non-monotonic reasoning, some conclusions may be
invalidated by adding more information to the knowledge
base.
– It deals with incomplete and uncertain models, and
conclusions may change with additional knowledge.
– Example: Let’s consider the following knowledge base:
●
Birds can fly.
●
Penguins cannot fly.
●
Pitty is a bird.
– Initially, we conclude that Pitty can fly. However, if we add
the sentence
– ”Pitty is a penguin” to the knowledge base, it invalidates the
previous conclusion, and now we conclude that Pitty cannot 46 / 57
fly.
Inference
Inference is the process of deriving new information from
known information.
In the domain of AI, the component of the system that performs
inference is called an inference engine.
47 / 57
Inference within the Framework of
“Logic”
●
Logic Components: Logic, as a language, consists of three
components: syntax, semantics, and proof systems.
– Syntax: Description of valid statements, the expressions
that are legal in that language.
●
The syntax of propositions provides ways to use
propositions, their associated truth values, and logical
connectives for reasoning.
– Semantics: Pertains to what expressions mean.
●
Example: The expression “the cat drove the car” is
syntactically correct but semantically non-sensible.
– Proof Systems:
●
A logic framework comes with a proof system, a way of
manipulating given statements to arrive at new
statements.
●
The idea is to derive ’new’ information from the given 48 / 57
information.
Proof
●
Proof Steps:
– Step 1: Begin with initial statements, called premises of the
proof (or knowledge base).
– Step 2: Use rules, i.e., apply rules to the known information.
– Step 3: Add new statements, based on the rules that match.
– Step 4: Repeat the above steps until you arrive at the
statement you wished to prove.
49 / 57
Resolution Rule
●
Resolution Rule:
– A strategy used to determine the truth of an assertion, using
only one resolution rule.
●
Usage of the Resolution Rule for Proofs:
– To be able to use the resolution rule for proofs, the first step
is to convert all given statements into the conjunctive
normal form.
50 / 57
Conjunctive Normal Form (CNF)
●
Conjunctive Normal Form:
– Resolution requires all sentences to be converted into a
special form called conjunctive normal form (CNF).
– A statement in CNF consists of ANDs of ORs.
●
Structure of a Sentence in CNF:
– The outermost structure is made up of conjunctions.
– Inner units called clauses are made up of disjunctions.
– The components of a statement in CNF are clauses and
literals.
– A clause is the disjunction of many units.
– The units that make up a clause are called literals.
– Literal is either a variable or the negation of a variable.
– Each clause can be seen as a requirement, and each clause
51 / 57
has to be satisfied individually to satisfy the entire
statement.
Conversion to CNF: Example
●
Example:
– Given sentence: (P → Q) ∧ (¬R → Q)
●
Eliminate arrows: (¬P ∨ Q) ∧ (R ∨ Q)
●
The converted CNF form is (¬P ∨ Q) ∧ (R ∨ Q)
52 / 57
Resolution by Refutation: Steps
Write all sentences in CNF.
Negate the desired conclusion.
Apply the resolution rule until you derive a contradiction or
cannot apply the rule anymore.
If we derive a contradiction, then the conclusion follows from
the given axioms.
If we cannot apply anymore, then the conclusion cannot be
proved from the given axioms.
53 / 57
Example
54 / 57
Cont’d
55 / 57
Cont’d
56 / 57
Quiz (10%)
57 / 57