Introduction to AI

Chapter-4 Knowledge Representation and Reasoning

1
Topics

Knowledge Propositional Predicate (First-

Reasoning Logical Agents
Representation Logic Order) Logic

2
3
 Knowledge
Knowledge includes facts about the real world entities and the
relationship between them
• Knowledge-based Systems (KBSs) are useless without the ability to
represent knowledge.
Why Knowledge is important ?
• It enables to:
– Automate reasoning
– Discover new facts.
– Deduce new facts that follow from the KB
– Answer users queries
– Make quality decisions - select courses of actions, etc.
 Knowledge-based Agent (KBA)
• Agents can be seen as knowing about their world, and reasoning about
their possible courses of action.
• KBA begins with some knowledge of the world and of its
actions.
– It uses logical reasoning to maintain a description of the world as
new percepts arrive
– Learn new facts/knowledge that are inferred and unseen by
current percepts
– Deduce a course of actions that will achieve its goals
• One can also design an autonomous agent that
– learns and construct knowledge with less human interventions
 Knowledge engineering (KE)
• KE is the process of building a knowledge base through extracting the
knowledge from the human expert.
• Knowledge engineering is the process of
– Extracting the knowledge from the human expert.
– Choose knowledge representation formalism
– Choose reasoning and problem solving strategy.
• A knowledge engineer is someone who investigates a particular domain,
determines what concepts are important in that domain, and creates a formal
representation of the objects and relations in the domain.
– A KE has to decide what objects and relations are worth representing,
and which relations hold among which objects
 The two main tasks of KE
• Knowledge acquisition: The knowledge engineer interview
the real human experts to be educated about the domain and to
elicit the required knowledge, in a process called knowledge
acquisition
• Knowledge Representation techniques such as logic are a
powerful tool for KR and reasoning. However, such techniques
consists of only the syntax, semantics and proof theory.
– KR techniques do not offer any guidance as to what facts
should be expressed, nor what vocabulary should be used to
express them
• Knowledge base is used to store a set of facts and rules about the
domain expressed in a suitable representation language
– Each individual representation are called sentences
– Sentences are expressed in a (formal) knowledge
representation (KR) language
Knowledge Representation
• How is knowledge represented in the brain?
• How can knowledge be represented?
• Fact knowledge
• Conceptual knowledge
• Procedural knowledge

8
 Reasoning
• Reasoning: is the process of constructing new sentences from
existing facts in the KB.
– Proper reasoning ensures that the new configuration represent facts
that actually follow from the facts in the KB.

Many different types of logic:

• Propositional logic
• First order logic
• Second order logic
Reasoning:
• Deductive reasoning (logical conclusions)
• Inductive reasoning (generalization based on statistics)

9
Deduction
• FROM PREMISES TO LOGICAL AND CERTAIN CONCLUSIONS
• LOGIC: PROPOSITIONAL LOGIC, FIRST ORDER LOGIC, SECOND ORDER
LOGIC

10
Induction
• From strong evidence (e.g. observations, statistically) to
most probable conclusion
• Probabilistic: Bayesian Theory, Evidence Theory

Examples:
• There are 20 balls in a bowl either red or black. We draw 4
balls, 3 of them are red and 1 is black.
• The inductive conclusion is that there are 15 red balls and 5
black balls in the bowl.

• All doves we have observed so far are white Therefore, when

a dove is mentioned we have good reason to believe it is
white.

11
Expert Systems
1. Knowledge base where expert knowledge from one or several experts
is gathered (using knowledge representation)
• Observation, interviews, introspection
2. Inference Engine
• Rules (expert rules) how to use the expert knowledge to derive
conclusions
• Deterministic inference (e.g. logic)
• Probabilistic inference (e.g. Bayesian networks)
3. User interface
• To communicate with the human user

13
make mistakes
Logical Agents

Logic is a formal system for manipulating facts so

that true conclusions may be drawn

Syntax: rules for E.g., x + 2 y is a

constructing valid valid arithmetic
sentences sentence,
x2y + is not
Semantics: “meaning” of
sentences, or relationship Specifically, semantics
defines truth of sentences
between logical sentences E.g., x + 2 y is true in a world
and the real world where x = 5
and y = 7

13
Relation between Knowledge Representation
and the World
Knowledge / Fact
Facts

Learning

• Facts: Sentences we know to be true.

• Possible worlds: all worlds/models which are consistent with the
facts we know (compare with belief state).
• Learning new facts reduces the number of possible worlds.
• Entailment: A sentence logically follows from what we already know.

14
 Knowledge-based agents

Knowledge
base Domain-specific content

Inference engine Domain-independent algorithms

• Knowledge base (KB) = set of sentences in a formal language

(knowledgerepresentation) that are known to be true = set of facts
• Declarative approach to building an agent: Define what it needs to know
• Distinction between data (knowledge) and program (inference)
• Fullest realization of this philosophy was in the field of expert systems or
knowledge-based systems in the 1970s and 1980s

15
 Generic Knowledge-based Agent
Memorize percept
at time t

Ask for logical

action

Record action
taken at time t

KB= set of sentences in a formal language The agent must be able to:
Declarative approach to building an agent (or • Represent states, actions, etc.
other system): • Incorporate new percepts
• TELL it what it needs to know • Update internal representations of the world
• Then it can ASK itself what to do • Deduce hidden properties of the world
• Answers are consequences of the KB • Deduce appropriate actions
16
Propositional Logic
23
Propositional logic: Syntax

= Symbols

Negation
Conjunction
Disjunction
Implication
Biconditiona
l

24
 Propositional logic
• A simple language useful for showing key ideas and
definitions
• Syntax: PL allows facts about the world to be represented
as sentences formed from:
✓ Logical constants: True, False
✓ Proposition symbols (P, Q, R, …) are used to
represent facts about the world: e.g.: P = "It is hot“,
Q = "It is humid“, R = "It is raining“
✓ Logical connectives: not (), and (), or (),
implies (→), is equivalent, if and only if ().
➢Precedence order from highest to lowest is: ,
,,→, 
e.g. The sentence P v Q  R → S is equivalent to [(P)
v (Q  R)] → S
➢Parenthesis ( ): Used for grouping sentences
and to specify order of precedence
We have 3 possible worlds for 𝑃 ⇒ 𝑄 = 𝑡𝑟𝑢𝑒 25
 Propositional logic (PL) sentences
• A sentence is made by linking prepositional symbols together
using logical connectives.
– There are atomic and complex sentences.
– Atomic sentences consist of propositional symbol (e.g. P, Q,
TRUE, FALSE)
– Complex sentences are combined by using connectives or
parenthesis:
– while S and T are atomic sentences, S  T, (S  T), (S  T), (S
→ T), and (S  T) are complex sentences.
Examples: Given the following sentences about the “weather
problem” convert them into PL sentences:
• “It is humid.”: Q
• “If it is humid, then it is hot” : Q → P
We have 3 possible worlds for 𝑃 ⇒ 𝑄 = 𝑡𝑟𝑢𝑒 26
 • “If it is hot and humid, then it is raining”: (P  Q) → R

Exercise
Examples: Convert the following English sentences to
Propositional logic
Let A = Lectures are active and R = Text is readable, P =
Kebede will pass the exam, then represent the following:
• the lectures are not active: 
• the lectures are active and the text is readable: A  R
• either the lectures are active or the text is readable: A V R
• if the lectures are active, then the text is not readable: A →  R
• the lectures are active if and only if the text is readable: A  R
• if the lectures are active, then if the text is not readable,
Kebede will not pass the exam:
A → (R → P )

We have 3 possible worlds for 𝑃 ⇒ 𝑄 = 𝑡𝑟𝑢𝑒 27

 Validity and Satisfiability
• Valid sentence: A sentence is valid sentence or tautology if and
only if it is True under all possible interpretations in all possible worlds.
Example: “It’s raining or it’s not raining.” (R  R).
• Satisfiable: A sentence is satisfiable if and only if there is some
interpretations in some world for which the sentence is True.
Example: “It is raining or it is humid”. R v Q, R
• Unsatisfiable: A sentence is unsatisfiable (inconsistent sentence or
self- contradiction) if and only if it is not satisfiable, i.e. a sentence
that is False under all interpretations. The world is never like what it
describes.
Example: “It’s raining and it's not raining.” R  R
• Entailment: mirrors the relation of one fact following from another.
– New sentences are generated that are necessarily true, given that
the old sentences are true.
– KB entails α (KB |= α) if and only if the conclusion α is true in

We have 3 possible worlds for 𝑃 ⇒ 𝑄 = 𝑡𝑟𝑢𝑒 28

 every logically possible worlds in which all the premises in KB are
true.

Possible Worlds, Models and Truth Tables

A model specifies a “possible world” with the true/false
status of each proposition symbol in the knowledge base
• E.g., P is true and Q is true
• With two symbols, there are 22 = 4 possible worlds/models, and they can
be enumerated exhaustively using:
A truth table specifies the truth value of a composite sentence for each
possible assignments of truth values to its atoms. Each row is a model.

We have 3 possible worlds for 𝑃 ⇒ 𝑄 = 𝑡𝑟𝑢𝑒 29

Propositional logic: Semantics

Rules for evaluating truth with respect to a model:

• P is true iff P is false

•P Q is true iff P is true and Q is true
•P Q is true iff P is true or Q is true
•P Q is true iff P is false or Q is true

Sentence Model

30
Logical equivalence

Two sentences are logically equivalent iff (read if, and only if)
they are true in same models

31
Entailment

• Entailment means that a sentence follows from the

premises contained in the knowledge base:
KB ╞ α
• The knowledge base KB entails sentence α iff α is
true in all models where KB is true
• E.g., KB with x = 0 entails sentence x * y = 0
• Tests for entailment
• KB ╞ α iff (KB α) is valid
• KB ╞ α iff (KB α) is unsatisfiable

32
Inference

• Logical inference: a procedure for generating

sentences that follow from a knowledge base KB

• An inference procedure is sound if it derives a

sentence α iff KB╞ α. i.e, it only derives true
sentences.

• An inference procedure is complete if it can derive

all α for which KB╞ α.

33
Inference
• How can we check whether a sentence α is entailed by KB?

• How about we enumerate all possible models of the

KB (truth assignments of all its symbols), and check that
α is true in every model in which KB is true?
• Is this sound (if an answer is produced, it is correct)?
• Is this complete (guaranteed to produce the correct
answer)?
• Problem: if KB contains n symbols, the truth table will be of size 2n

• Better idea: use inference rules, or sound procedures to

generate new sentences or conclusions given the premises
in the KB

34
Summary

• Logical agents apply inference to a knowledge base to derive

new information and make decisions
• Basic concepts of logic:
• syntax: formal structure of sentences
• semantics: truth of sentences in models
• entailment: necessary truth of one sentence given another
• inference: deriving sentences from other sentences
• soundness: derivations produce only entailed sentences
• completeness: derivations can produce all entailed sentences
• Resolution is complete for propositional logic
• Algorithms use forward, backward chaining, are linear in
time, and complete for special clauses (definite clauses).

37
First-Order Logic (FOL)
36
First-order logic
Whereas propositional logic assumes world contains
facts, first-order logic (like natural language) assumes
the world contains
• Objects: people, houses, numbers, theories,
colors, baseball games, wars, centuries . . .
• Relations: red, round, bogus, prime, multistoried
. . ., brother of, bigger than, inside, part of, has
color, occurred after, owns, comes between, . . .
• Functions: father of, best friend, third round of,
one more than, end of . . .

37
Other Languages to represent Knowledge

• First-order Logic adds objects and relations.

38
Syntax of FOL

Objects

Relations. Predicate
is/returns True or False

Function returns an object

39
Universal quantification
• x P(x)

• Example: “Everyone at WKU is smart”

x At(x,WKU) Smart(x)
Why not x At(x,WKU) Smart(x)?

• Roughly speaking, equivalent to the conjunction of all

possible instantiations of the variable:
[At(Abebe, WKU) Smart(Abebe)] ...
[At(Kebede, SMU) Smart(Kebede)]
...

• x P(x) is true in a model m iff P(x) is true with x being

eachpossible object in the model

40
Existential quantification

• x P(x)

• Example: “Someone at WKU is smart”

x At(x,WKU) Smart(x)
Why not x At(x,WKU) Smart(x)?

• Roughly speaking, equivalent to the disjunction of all

possible instantiations:
[At(Abebe,WKU) Smart(Abebe)]
[At(Kebede,WKU) Smart(Kebede)] …

• x P(x) is true in a model m iff P(x) is true with x being some

possible object in the model

41
Inference in FOL
• Inference is complicated.

1. Reduction to propositional logic and then use propositional

logic inference.

2. Directly do inference on FOL (or a subset like definite clauses)

• Unification: Combine two sentences into one.
• Forward Chaining for FOL
• Backward Chaining for FOL
• Logical programming (e.g., Prolog)

49
Limitations of Logic
• What if we cannot collect enough knowledge to make a decision
e.g., the environment if only partially observable
• What about facts about the future?
grade(Abebe, AI, this_semester)

50