Knowledge Base System, Reasoning and

Representation
• To solve complex problems we need:
1. Large amount of knowledge
2. Mechanism for representation and manipulation
of existing knowledge to create new solution.
Two Types of Knowledge:
(i) Procedural (ii) Declarative
Knowledge Representation
– Facts: Things we want to represent. Truth in
some relevant world.
– Representation of facts.
 Representation and Mapping
• Spot is a dog
dog(Spot)

• Every dog has a tail

x: dog(x)  hastail(x)

hastail(Spot)
Spot has a tail
3
Representation and Mapping

No. black squares

= 30

No. white square

= 32

8
 Approaches to KR
1. Simple relational knowledge:
• Provides very weak inferential capabilities.
• May serve as the input to powerful inference engines.
Player Height Weight handed
Peter 6-0 180 right
Ajay 5-10 170 left
John 6-2 215 left
Vickey 6-3 205 right

Fails to infer “which right handed player can best face a

particular bowler” .

10
 Approaches to KR
Inheritable knowledge:
• Objects are organized into classes and classes are
organized in a generalization hierarchy.
• Inheritance is a powerful form of inference, but not
adequate.
• Ex. Property inheritance inference mechanism.

is handed
Adult male a Person Right

instanc
e

Peter Consultancy 11
Works_a
 Approaches to KR

Inferential knowledge:
• Facts represented in a logical form, which facilitates
reasoning.
• An inference engine is required.

ex. 1. “Marcus is a man”

2. “All men are mortal”
Implies:
3. “Marcus is mortal” 12
 Approaches to KR

Procedural knowledge:
• Representation of “how to make it” rather than “what
it is”.
• May have inferential efficiency, but no inferential
adequacy and acquisitional efficiency.
• Ex. Writing Prolog programs

8
 Some General
Representations

1. Logical Representations
2. Production Rules
3. Semantic Networks
• Conceptual graphs, frames
4. Description Logics (see textbook)
Big Ideas

Logic is a great knowledge representation

language for many AI problems
Propositional logic is the simple foundation
and fine for some AI problems
First order logic (FOL) is much more
expressive as a KR language and more
commonly used in AI
Propositional logic

Logical constants: true, false

Propositional symbols: P, Q,... (atomic sentences)
Wrapping parentheses: ( … )
Sentences are combined by connectives:
 and [conjunction]
 or [disjunction]
implies [implication / conditional]
is equivalent[biconditional]
 not [negation]
Literal: atomic sentence or negated atomic sentence
P,  P
Examples of PL sentences

(P  Q)  R
“If it is hot and humid, then it is raining”
QP
“If it is humid, then it is hot”
Q
“It is humid.”
We’re free to choose better symbols, btw:
Ho = “It is hot”
Hu = “It is humid”
R = “It is raining”
 Propositional logic (PL)
Simple language for showing key ideas and definitions
User defines set of propositional symbols, like P and Q
User defines semantics of each propositional symbol:
P means “It is hot”, Q means “It is humid”, etc.
A sentence (well formed formula) is defined as follows:
A symbol is a sentence
If S is a sentence, then S is a sentence
If S is a sentence, then (S) is a sentence
If S and T are sentences, then (S  T), (S  T), (S  T), and (S ↔
T) are sentences
A sentence results from a finite number of applications of the
rules
 Some terms

The meaning or semantics of a sentence

determines its interpretation
Given the truth values of all symbols in a
sentence, it can be “evaluated” to determine its
truth value (True or False)
A model for a KB is a possible world – an
assignment of truth values to propositional
symbols that makes each sentence in the KB True
 Truth tables

• Truth tables are used to define logical connectives

• and to determine when a complex sentence is true
given the values of the symbols in it
Truth tables for the five logical connectives

Example of a truth table used for a complex sentence

Inference rules

Logical inference creates new sentences that

logically follow from a set of sentences (KB)
An inference rule is sound if every sentence X it
produces when operating on a KB logically follows
from the KB
i.e., inference rule creates no contradictions
An inference rule is complete if it can produce
every expression that logically follows from (is
entailed by) the KB.
Note analogy to complete search algorithms
Inference rules:

17
Soundness of modus ponens

A B A→B OK?


True True True


True False False


False True True


False False True
 Resolution

Resolution is a valid inference rule producing a new

clause implied by two clauses containing
complementary literals
A literal is an atomic symbol or its negation, i.e., P, ~P
Amazingly, this is the only interference rule you need to
build a sound and complete theorem prover
Based on proof by contradiction and usually called resolution
refutation
The resolution rule was discovered by Alan Robinson
(CS, U. of Syracuse) in the mid 60s
 Resolution

A KB is actually a set of sentences all of which are true,

i.e., a conjunction of sentences.
To use resolution, put KB into conjunctive normal form
(CNF), where each sentence written as a disjunc- tion of
(one or more) literals
Example Tautologies
• (AB)↔(~AB)
KB: [PQ , QRS]
(A(BC)) ↔(AB)(AC)
• KB in CNF: [~PQ , ~QR , ~QS]
• Resolve KB(1) and KB(2) producing: ~PR (i.e., PR)
• Resolve KB(1) and KB(3) producing: ~PS (i.e., PS)
• New KB: [~PQ , ~Q~R~S , ~PR , ~PS]
 Using Propositional Logic

Representing simple facts

It is raining
RAINING
It is sunny
SUNNY
It is windy
WINDY
If it is
raining,
then it is
not sunny
RAINING
21

• Another PL Example:
“I will get wet if it rains and I go out of the house”

Let Propositions be:

W : “I will get wet “
R : “it rains “
S: “I go out of the house”

(S ˄ R)  W

22
First-order logic
First-order logic (FOL) models the world in terms of
Objects, which are things with individual identities
Properties of objects that distinguish them from others
Relations that hold among sets of objects
Functions, which are a subset of relations where there is only
one “value” for any given “input”
Examples:
Objects: Students, lectures, companies, cars ...
Relations: Brother-of, bigger-than, outside, part-of, has-color,
occurs-after, owns, visits, precedes, ...
Properties: blue, oval, even, large, ...
Functions: father-of, best-friend, second-half, more-than ...
User provides

Constant symbols representing individuals in the

world
Mary, 3, green
Function symbols, map individuals to individuals
father_of(Mary) = John
color_of(Sky) = Blue
Predicate symbols, map individuals to truth values
greater(5,3)
green(Grass)
color(Grass, Green)
FOL Provides

Variable symbols
E.g., x, y, foo
Connectives
Same as in propositional logic: not (), and
(), or (), implies (), iff ()
Quantifiers
Universal x or (Ax)
Existential x or (Ex)
 PREDICATE LOGIC

• Can represent objects and quantification

• Theorem proving is semi-decidable

26
 Using Predicate Logic

1. Marcus was a man.

man(Marcus)
2. Marcus was a Pompeian.
Pompeian(Marcus)

27
• Quantifiers:
• 2 types:-

• Universal quantifier ()

• x: means “for all” x

• It is used to represent phrase “ for all”.
• It says that something is true for all possible values of
a variable.

• Ex. “ John loves everyone”

•

28
• Quantifiers:
• 2 types:-

• Universal quantifier ()

• x: means “for all” x

• It is used to represent phrase “ for all”.
• It says that something is true for all possible values of
a variable.

• Ex. “ John loves everyone”

x: loves(John , x)

29
• Existential quantifier (  ):

• Used to represent the fact “ there exists some”

• Ex:
• “some people like reading and hence they gain good
knowledge”

 x: { [person(x)  like (x , reading)] gain(x,

knowledge) }

• “lord Haggins has a crown on his head”

•  x: crown(x)  onhead (x , Haggins)

30
 Nested Quantifiers
• We can use both  and  seperately

• Ex: “ everybody loves somebody ”

x: y:
loves ( x , y)

• Connection between  and 

• “ everyone dislikes garlic”
 x:  like
( x , garlic )
 This can be also said as:
“there does not exists someone who likes garlic” 31
3. All Romans were either loyal to Caesar or hated him.

x: Roman(x)  loyalto (x, Caesar)  hate(x, Caesar)

4. Every one is loyal to someone.

x: y: loyalto(x, y) y: x: loyalto(x, y)
5. People only try to assassinate rulers they are not loyal to.
x: y: person(x)  ruler(y)  tryassassinate(x, y)
 loyalto(x, y)

32
6. “All Pompeians were Romans”
x: Pompeian(x)  Roman(x)

8. Marcus tried to assassinate Caesar.

tryassassinate(Marcus, Caesar)

33
 Some more examples
• “all indoor games are easy”
x: indoor_game( x)  easy(x)

• “Rameez likes only cricket”

Like(Rameez, Cricket)

• “Any person who is respected by every person is a king”

x:y: { person(x)  person(y)  respects (y ,x) king( x)}

34
Semantic Networks
A semantic network is a simple representation scheme that uses a
graph of labeled nodes and labeled, directed arcs to encode
knowledge.
Usually used to represent static, taxonomic, concept
dictionaries
Semantic networks are typically used with a special set of
accessing procedures that perform “reasoning”
e.g., inheritance of values and relationships
The graphical depiction associated with a semantic network is a
significant reason for their popularity.
Nodes and Arcs

Arcs define binary relationships that hold

between objects denoted by the nodes.

mother age
Sue john 5

wi
age fe
father
hu
sba mother(john,sue)
nd
age(john,5)
Max
34 age wife(sue,max)
age(max,34)
...
 Semantic Networks

The ISA (is-a) or AKO (a-kind-

of) relation is often used to link Animal
instances to classes, classes to
superclasses isa
Some links (e.g. hasPart) are hasPart
Bird
inherited along ISA paths.
The semantics of a semantic net isa Wing
can be relatively informal or
Robin
very formal
isa isa
often defined at the
implementation level

Rusty Red
Individuals and Classes
Genus
Many semantic
networks distinguish Animal
nodes representing instance
subclass
individuals and those
hasPart
representing classes Bird
the “subclass” relation subclass Wing
from the “instance-of”
relation Robin

instance instance

Rusty Red
From Semantic Nets to Frames

Semantic networks morphed into Frame

A frame is a lot like the notion of an object in OOP,
but has more meta-data
A frame has a set of slots
A slot represents a relation to another frame (or value)
A slot has one or more facets
A facet represents some aspect of the relation
Facets
A slot in a frame holds more than a value.
Other facets might include:
Value: current fillers
Default: default fillers
Cardinality: minimum and maximum number of fillers
Type: type restriction on fillers (usually expressed as
another frame object)
Proceedures: attached procedures (if-needed, if-added, if-
removed)
Salience: measure on the slot’s importance
Constraints: attached constraints or axioms
In some systems, the slots themselves are instances of
frames.
42