Chapter Four

Knowledge Representation(NR) and Reasoning

1
Contents will be covered
§ Knowledge
§ What????
§ Why?????
§ KBA
§ KE
§ KR
§ KR
§ KR using Logic
§ Why???? 2
 Data, Information, and Knowledge
• What is Data and Information? Are they different from
Knowledge?

ü data!=information!=knowledge

D
• :- Unorganized and unprocessed facts; static; a set of
discrete facts about events

• :- Aggregation of data that makes decision making easier

• : - i s der i ved f r om i nf or mat i on i n t he same way

K
information is derived from data; it is a person’s range of
3

information.
 Con't…
ü Data are raw facts and figures that on their own have no
meaning. Involves facts, observations, numbers, symbols,
characters and image or opinions with out r/ship.
ü Unorganized /unprocessed/and evaluated facts and figures
about the real world.
ü It is unorganized facts that needs to be processed. That means
data is useless unless it is processed or has been made into
something.
ü It has no meaning when it has not been interpreted. Data does
not depend upon information but information depend upon data.
ü Information- is derived from data. Refers to data has been
given meaning by way of relational connection. It is a
4
processed, structured ,presented in the given context to make
 Con’t…
When data is processed, organized , structured in a given context
so as to make it useful=information
ü Basically information is the data + the meaning of what the data was
collected for.
vKnowledge- is derived from information. That means k/ge is
appropriate collection of information.
ü Information and skills acquired through experience or
education, theoretical and practical understanding.
- It is the sort of information that people use to solve problems.
- May be general or specific.
- If information is interpreted and evaluated it gives k/ge
• If k/ge is understanding principles it gives wisdom.
- Information answer who, what, where, and when
5
- Knowledge answer how where as Wisdom answer why?
 Knowledge: What and Why?
• 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. If k/ge is understanding
principles it gives wisdom.
Why Knowledge is important ?
• We are living in complex environment.
• Hence, there is a need to represent knowledge to ease the
development of an intelligent system.
• It enables to:
–Automate reasoning , Discover new facts, Deduce new
facts that follow from the KB, and Answer users queries 6
–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 from experience and construct knowledge with less
human interventions 7
 Knowledge-based Agent (KBA)…
We can describe a knowledge-
based agent at three levels:
I. Knowledge Level
The most abstract level: describe
agent by saying what it knows
about the world and what its goals
II. Logical Level. are.
The level at which the knowledge is encoded into sentences
of some logical language.
III. Implementation Level.
This is the level where sentences are implemented. This level
runs on the agent architecture.
8
 Knowledge engineering (KE)
• KE is the process of building a knowledge base through extracting
knowledge from the human expert.
• Knowledge engineering is the process of
–Extracting 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
Knowledge Goal
Knowledge
acquisition Representation Knowledge Base
(Extract knowledge (choose KR Method &
9
of Human Expert) reasoning strategy)
 The two main tasks of KE
• Knowledge acquisition: The KE 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
–S ent ences ar e expr es s ed i n a ( f or mal ) know l edge
10
representation (KR) language
 Knowledge Representation & Reasoning
•Knowledge Representation (KR): express knowledge explicitly
in a computer-tractable way such that the agent can reason out.
•Parts of KR language:
–Syntax of a language: describes the possible configuration to
form sentences. E.g.: if x & y denote numbers, then x > y is a
sentence about numbers
–Semantics: determines the facts in the world to which the
sentences refer. E.g.: x > y
–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.
11
 Logic
• Formal language – is an abstraction general characteristics
programming languages. A formal language consists of a
set of symbols and some rules of formation by w/c these
symbols can be combined into entities called sentences.
• Is the set of all strings permitted by the rules of formation.
• A Logic is a formal language in which knowledge can be
represented such that conclusions can easily be drawn. It is
a declarative language to assert sentences and deduce from
sentences.
• If we have a set of assumptions {A1, A2, . . . , An}, and
from those assumptions we are able to derive a conclusion,
C, then we say that we have deduced C from the
assumptions, which is written {A1, A2, . . . ,An} |---C12
 Cont.….
Components of a logic include syntax, semantics,
reasoning and inference mechanism.
üSyntax: what expressions/structures are allowed in the language.
It describes how to make sentences.
E.g. AVB is valid represantetion but VAB is invalide
üSemantics: express what sentences mean, in terms of a
mapping to real world.
§ The meaning of a sentence is not intrinsic to that sentence.
Semantics relate sentences to reality.
E.g. AVB if A is true the resulet is true.
üProof Theory: It is a means of carrying our reasoning using a
set of rules. It helps to draw new conclusions from existing statements in
the logic. 13
 Propositional logic
Ø It is branch of formal logic that studys a sentences and their
connectivity, Is a way of representing k/ge.
Ø 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 14
of precedence
 Proposition/Statement
ØThe main concern of propositional logic is study
about proposition. It is define as the a declarative
sentences (that is, a sentence that declares a fact)that
can either True or False but not both.
Examples
ü Bahirdar is the capital of the Amhara region
ü Debre markos is the capital of west gojjam.
ü 1 + 1 = 2.
ü 2+2=3
ü What time is it?
ü Read this carefully. 15
ü x + 1 = 2. 4. x + y = z.
 Truth table
ØA truth table shows whether a propositional formula is
true or false for each possible truth assignment.
ØIf we know how the five basic logical connectives
work, it is easy (in principle) to construct a truth table

X Y X XvY XY XY X Y

T T F T F T T
T F F T F F F
F T T T T T F
F F T F F T T

16
 Cont…
Ø Let p be a proposition. The negation of p, denoted by ¬p
(also denoted by p’) is the statement “It is not the case that
p.” The proposition ¬p is read “not p.” The truth value of the
negation of p, ¬p, is the opposite of the truth value of p.
Ø Let p and q be propositions. The conjunction of p and q,
denoted by p ∧ q, is the proposition “p and q.” The
conjunction p ∧ q is true when both p and q are true and is
false otherwise.
Ø Let p and q be propositions. The disjunction of p and q,
denoted by p ∨ q, is the proposition “p or q.” T he
disjunction p ∨ q is false when both p and q are false and is
true otherwise.
17
 Cont…
ØLet p and q be propositions. The conditional statement
p → q is the proposition “if p, then q.” The conditional
statement p → q is false when p is true and q is false,
and true otherwise. In the conditional statement p →
q, p is called the hypothesis (or antecedent or premise)
and q is called the conclusion (or consequence). p →
q can be expressed as follow

18
 Cont…
Ø The proposition q → p is called the converse of p → q. The
contrapositive of p → q is the proposition ¬q → ¬p. The
proposition ¬p → ¬q is called the inverse of p → q.
Ø Let p and q be propositions. The biconditional statement p ↔
q is the proposition “p if and only if q.” The biconditional
statement p ↔ q is true when p and q have the same truth
values, and is false otherwise. Biconditional statements are
also called bi-implications. There are some other common
ways to express p ↔ q: “p is necessary and sufficient for q”
“if p then q, and conversely” “p iff q.
Ø The application of propositional logic and its rules can be
used to design computer circuits, to construct computer
programs, to verify the correctness of programs, and to build
19
expert systems.
 Propositional logic (PL) sentences
ØA sentence is made by linking prepositional symbols
together using logical connectives.
v 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
– “If it is hot and humid, then it is raining”: (P  Q)  R 20
Syntax of Propositional logic (PL)

Symbol P|Q| R
|…

21
 Exercise
Examples: Convert the following English sentences to
Propositional logic
Let A = Lectures are active and R = Text is readable, P =
Aleazar will pass the exam, then represent the following:
• The lectures are not active: A

• 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 the text is not readable and
Aleazar will not pass the exam:
A  (R  P ) 22
 Proposition equivalence
Ø A compound proposition that is always true, no matter
what the truth values of the propositional variables that
occur in it, is called a tautology.
Ø A compound proposition that is always false is called a
contradiction.
Ø A compound proposition that is neither a tautology nor a
contradiction is called a contingency.
Ø The compound propositions p and q are called logically
equivalent if p ↔ q is a tautology. The notation p ≡ q
denotes that p and q are logically equivalent.
Ø Remark: The symbol ≡ is not a logical connective, and p ≡ q is not a
compound proposition but rather is the statement that p ↔ q is a
tautology. The symbol ⇔ is sometimes used instead of ≡ to denote
logical equivalence. 23
 Terminology
•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).

•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
•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
24
 Proof: Inference Rules
•Inference is used to create new sentences that logically
follow from a given set of sentences in the KB.
–It captures patterns of inferences that occur over &
over again.
–Once a rule is established, it can be used to make
inferences without going through the tedious process
of building truth tables
•Given set of inference rules (I) and set of sentences
(KB); Inference is the process of applying successive
inference rules from the KB, each rule inferring new
facts and adding its conclusion to KB
–There are different inference rules (including logical
equivalence) that can be used for proofing and
reasoning purpose. 25
 Logical equivalence
•Two sentences are logically equivalent iff they are true in same
models
p ν q ≡ qνp Commutativity of disjunction
pΛ q≡q Λp Commutativity of conjunction
(p Λ q) Λ r ≡ p Λ (q Λ r) Associativity of conjunction
(p ν q) ν r ≡ p ν (q ν r) Associativity of disjunction
( ( p) ≡ p Double Negation elimination
p  q≡ q   p contraposition
p  q≡ p ν q implication elimination
(p ν q) ≡ ( p Λ q) De-Morgan
(p Λ q) ≡ ( p ν  q) De-Morgan
(p  q) ≡ (p q) Λ (q  p) Biconditional elimination
p Λ (q ν r) ≡ (p Λ q) ν (p Λ r) Distributive of Λ over ν
26
p ν (q Λ r) ≡ (p ν q) Λ (p ν r) Distributive of ν over Λ
 Inference Rules
Rule Premises Conclusion
Modus Ponens A, A  B B
And Elimination AB A
B
And Introduction A, B AB
Or Introduction A A1  A2 …  An
Double Negation  A A
Elimination
Hypothetical Syllogism PQ, P R
QR
In the case of modus ponens, if A is true and A  B is true, then
we know that B is true. 27
 Example
• E.g. Given the following facts and relationship
between facts; What can we say about the weather
condition?
– It is humid:
– If it is humid, then it is hot :
– If it is hot and humid, then it is raining:
1.Q
2.Q  P
3.(P  Q)  R
4. (using Modes Ponens on 1 & 2) P
5.(using AND introduction on 1 & 4) P  Q

28
 Propositional logic is a weak language
• PL cannot handle even a domain with small worlds. The
problem is that there are just too many propositions to handle
since it only has one representational device: the proposition
• In PL world consists of just facts. It is hard to :
–Identify individuals: E.g., Mary, 3
–Describe properties of (or relations between) individuals. E.g.
Belete is taller than Gelaw
–Generalize for a given universe. E.g., all triangles have 3
sides

• Example: Prove that “my dog Fido is Nice, given that “all dogs
are Nice.”
–This requires to get at the structure and meanings of
statements (where FOL is useful).
29
 First Order Logic
•First-Order Logic (FOL) is expressive enough to
concisely represent any kind of situation that are
expressed in natural language.
–FOL represents objects and relations between
objects, variables, and quantifiers in addition to
propositions

–Also know as predicate logic.

–Predicate is some thing that show the property of
an object

30
 Components of FOL
• Constants symbol
–names (like yonas, kebede, …), numbers (like 1, 2, … n), ...
• Predicates:
–Predicates used to relate one object with another. E.g. Brother,
>, ,...
Eg Greater(5,3)
• Functions: Returns value (Sqrt, mother-of, color-of,...) eg father-
of(Mary) = John
• Variables: X, Y, A, B,...
–Important to increase generalization capability of KB
• Connectives:
–retains connectives used in PL (, , , , )
• Quantifiers:
–Quantifiers specify whether all or some objects satisfy
properties or relations between objects
–Two standard quantifiers: Universal (" for all, for every) 31and
Existential (“there exists, some”)
 Components of FOL…
• Quantifiers
– Each quantifier defines a variable for the duration of the
following expression, and indicates the truth of the
expression.
– It is “an operator that limits the variables of a proposition”
v Universal quantifier “for all” :- (x)P(x) means that P holds
for all values of x in the domain associated with that variable
– The expression is true for every possible value of the
variable
–  is the main connective with 
Every elephant is gray:
 x (elephant(x)  gray(x))
v Existential quantifier “there exists” :- ( x)P(x) means that P
holds for some value of x in the domain associated with that
variable
– The expression is true for at least one value of the variable 32

– is the main connective with 

 Existential quantifiers
• Represented by an bacwards E: 
• The existential quantification of P (x) is the proposition
“There exists an element x in the domain such that P (x).”
• W e use t he not at i on ∃xP (x) for t he exi st ent i al
quantification of P (x). Here ∃ is called the existential
quantifier.
– Let P(x) = x+1 > x
• We can state the following:
– English translation: “there exists (a value of) x such that
P(x) is true”
– English translation: “for at least one value of x, x+1>x
is true”
• Let P(x) = x+1 < x
33
– There is no numerical value x for which x+1<x
 Cont…
Let P(x) = x+1 > x
There is a numerical value for which x+1>x
In fact, it’s true for all of the values of x!
Thus, x P(x) is true
üIn order to show an existential quantification is true, you
only have to find ONE value
üIn order to show an existential quantification is false,
you have to show it’s false for ALL values
Ø Given some propositional function P(x) and values in
the universe x1 .. xn. The existential quantification x
P(x) implies: P(x1)  P(x2)  …  P(xn)

34
 Existential quantification
•Makes statements about some objects in the universe
<variables> <sentence >
- There is a student who is smart
(x) student(x)  smart(x)
–Someone at BC is smart:
x At(x,BC)  Smart(x)
•x sentence P is true iff P is true with x being some possible objects in
the universe.
•Common mistake to avoid
–Typically,  is the main connective with 
–Common mistake: using  as the main connective with :
x At(x,BC)  Smart(x) is true if there is anyone who is not at BC

35
 Universal quantifier
Ø Represented by an upside-down A: 
Ø The universal quantification of P (x) is the statement “P (x) for all
values of x in the domain.”
Ø The notation ∀xP (x) denotes the universal quantification of P (x).
Here ∀ is called the universal quantifier.
Ø We read ∀xP (x) as “for all xP (x)” or “for every xP (x).” An
element for which P (x) is false is called a counterexample of ∀xP
(x).
ü English translation: “for all values of x, P(x) is true”
ü English translation: “for all values of x, x+1>x is true”
Ø In order to prove that a universal quantification is true, it must be
shown for ALL cases
Ø In order to prove that a universal quantification is false, it must be
shown to be false for only ONE case
Ø Given some propositional function P(x) and values in the universe36
x1 .. xn. The universal quantification x P(x) implies:
 Universal quantification
• Universal Quantifiers: makes statements about every object
<variables> <sentence>
–All cats are mammals:
x cat(x)  mammal(x)
–Everyone at BC is smart:
x At(x,BC)  Smart(x)
• x sentence P is true iff P is true with x being each possible object in the
given universe
• A common mistake to avoid
–Typically,  is the main connective with 
–Common mistake: the use of  as the main connective with :
x At(x, BC)  Smart(x) is true if “Everyone is at BC & everyone is
smart”

37
Statemen When True?
Cont…When False?
t
∀xP (x) P (x) is true for every x There is an x for which P (x) is
∃xP (x) There is an x for which P (x) is false.
true. P (x) is false for every x.

Example Let P (x) be the statement “x + 1 > x.” What is the truth value of
the quantification ∀xP (x), where the domain consists of all real
numbers?
Solution: Because P (x) is true for all real numbers x, the quantification
∀xP (x) is true.
∀x Besides “for all” and “for every,” universal quantification can be
expressed in many other ways, including “all of,” “for each,” “given any,”
“for arbitrary,” “for each,” and “for any.
∃x Besides the phrase “there exists,” we can also express existential
quantification in many other ways, such as by using the words “for some,”
“for at least one,” or “there is.” 38
 Nested quantifiers
•x,y parent(x,y)  child(y,x)
–for all x and y, if x is the parent of y then y is the child of x.
•x y Loves(x,y)
–There is a person who loves everyone in the given world
•y x Loves(x,y)
–Everyone in the given universe is loved by at least one person
Properties of quantifiers
–x y is the same as y x
–x y is the same as y x
–x y is not the same as y x

•Quantifier duality: each can be expressed using the other, using negation
()
x Likes(x,icecream) x Likes(x,icecream)
– Everyone likes ice cream means that there is nobody who dislikes ice
cream x Likes(x,cake)
x Likes(x,cake) 39

–There is someone who likes cake means that there is no one who