Chapter 2

Foundations of
Knowledge-based Systems

B. Okuku 1
 Recap… Definition of KBS
 A knowledge based system (KBS) is a software system
capable of supporting the explicit representation of
knowledge in some specific competence domain and of
exploiting it through appropriate reasoning mechanisms
in order to provide high-level problem-solving
performance.

 KBS is a specific, dedicated, computer-based problem-

solver, able to face complex problems, which, if solved by
man, would require advanced reasoning capabilities, such
as deduction, abduction, hypothetical reasoning, model-
based reasoning, analogical reasoning, learning, etc.

 Typical problems
 Diagnosis
 Scheduling
 Planning
2
B. Okuku
 Knowledge Representation
 This is the way that knowledge is stored in a
program. This implies that
 There is a systematic way to store the information.
 The knowledge is coded into the program.
 Knowledge representation and reasoning - the
study of formal ways of extracting information
from symbolically represented knowledge
 Existing computer languages can be used and the
knowledge is stored in memory.
 The stored knowledge and facts can be used in
reasoning.

3
B. Okuku
 Knowledge Representation…
 Knowledge can be represented in a variety
of ways.
 The predominant knowledge
representation schemes are
 Frames and production rules.
 Connections and weights.

4
B. Okuku
 Knowledge Representation…
 Some desirable features of any knowledge
representation scheme include:
 Completeness: Should support the acquisition of all
aspects of the knowledge.
 Conciseness: Allow efficient acquisition so that
knowledge is stored compactly and is easily retrieved.
 Computational efficiency: It should be possible to
use the knowledge rapidly and without the need for
excessive computation.
 Transparency: Should be such that it is possible to
understand its behaviour and how it arrives at
conclusions.
 Explicity: The important things should be explicit but
the details suppressed but available in case it is
required in future. 5
B. Okuku
 Why use special tools
 Traditional languages emphasize
 Efficiency
 Maintainability
 Portability
Not representational power
 Traditional language control is
 Primitive
 Implicit in statement ordering
 Pretty much fixed at compile time
 Good for algorithmic work, but knowledge is
implicit not explicit.
6
B. Okuku
 Why use special tools
 There is no single representation scheme that embodies
all the above characteristics.

 Each of the representation schemes is suitable for certain

types of application domain.

7
B. Okuku
 Types of representation schemes
 Some popular representation schemes include
 Rule-based schemes: Information is stored as
abstract rules that have general applicability.
 Learning is explicit.
 Instance based models: Do not operate on explicit
rules. Exhibit rule-like behavior by being exposed to a
series of examples.
 Learning is implicit.

8
B. Okuku
 Logic and other schemes
 Logic: Extensively used in Al programs.
 Main purpose of logic: The soundness or unsoundness of
arguments.
 Typically, an argument consists of statements called
propositions, from which other statement(s) called
conclusion(s) are claimed to follow.
 This is the basis of propositional logic.

9
B. Okuku
 Propositional Logic
 Proposition: A sentence that is either true or
false.
 Example: The following are propositions:
 “Sam is a happy man" (1)
 "All cats are good pets" (2)
 Propositions, because each is either true or false.
 The following phrases are not propositions:
 "Amy's pet" (3)
 "Oh dear me!" (4)
 Statements in propositional logic are usually
expressed symbolically.

10
B. Okuku
 Propositional Logic…
Example:
 The following inference:

 "If Sam is a happy man then Sam is a teacher"

 Could be symbolically expressed as:
 A: Sam is a happy man
 B: Sam is a teacher
 This could be expressed in propositional logic as:
 if A then B
 Logic notation: A  B (meaning proposition A
implies proposition B).

11
B. Okuku
 Propositional Logic…
 This is an example of a rule of inference called modus
ponens.

 This says that if proposition A is true, and the rule of

inference A  B is true, then B will also be true.

 Propositions can be combined using logical connectives

e.g.
 "If I listen to music and the room is warm then I fall asleep“

 Rewriting this symbolically:

 Proposition A: I listen to music
 Proposition B: The room is warm
 Proposition C: I fall asleep
12
B. Okuku
 Propositional Logic…
 Then this can be written in logic notation as:
ABC

Connective symbols
 The symbols shown in the table are used to denote some
of the most common connectives used in propositional
logic.

13
B. Okuku
 Propositional Logic…
Symbol Meaning Interpretation
-A Not A Negation. Negation of proposition A
is true if A is false and vice versa
AB A and B Conjunction. A and B only true if A
and B are both true, otherwise false
AB A or B Disjunction. A or B is true if A is
true or B is true.
AB A implies B Implication. If A is true and A
implies B is true, then B is true. If A
is false and A implies B is true then
anything goes. That is, B could be
true or false, since implication says
nothing about case when A is false
14
B. Okuku
 Propositional Logic…
Truth table
 The meanings of the connectives and their results are

summarized in the table

A B A A  B A  B A  B
1 1 0 1 1 1
1 0 0 0 1 0
0 1 1 0 1 1
0 0 1 0 0 1

15
B. Okuku
 Predicate Logic
 Propositional logic is inadequate for solving some
problems because a proposition has to be treated as a
single entity that is either true or false.

 Predicate logic overcomes this by allowing a proposition

to be broken down into two components.
 Arguments
 Predicates.

 It allows the use of variables, in addition to supporting

the rules of inference derived from propositional logic
(i.e. modus ponens etc.).

16
B. Okuku
 Predicate Logic…
Example
 Consider the proposition:

 “Kamau has short hair”.

 This could be written in predicate logic notation
as:
 HAS (Kamau, short hair)
 In the example,
 Predicate: HAS
 Arguments: “Kamau” and “short hair.”

17
B. Okuku
 Predicate Logic…
Quantifiers in predicate logic
 Predicate logic also allows for the use of

quantifiers.
 This means that the language can be extended to
propositions that refer to a range of a variable.
 For example, consider the proposition:
 “Every man loves a woman.”
 This can be expressed in predicate logic using
quantifiers as:

18
B. Okuku
 Predicate Logic…
 x, Man(x)   y, s.t. Woman(y)  Loves(x, y)
 Which reads:
 For any object x in the world if x is a Man, then there exists an
object y, such that y is a woman and x Loves y.

Quantifiers
 : The universal quantifier since it refers to all objects in

the (male) population.

 : The existential quantifier since it refers to at least one

object in the (female) population.

19
B. Okuku
 Predicate Logic…
 Now consider the proposition: every Welshman is a Man.
This would be expressed in formal logic as:
 x, Welshman(x)   Man(x)

 Which reads:
 for any object x, if x is a Welshman, then x is a man.

20
B. Okuku
 Predicate Logic…
 Then from the two facts it can be concluded, using the
rules of inference, that the following fact must be true:
 x, Welshman(x)   y, s.t. Woman(y)  Loves(x, y)

 That is, every Welshman loves a woman.

 The example seems to lead to an obvious conclusion.

However, for other examples such intuitive conclusions
would be less obvious.

21
B. Okuku
 Logic: Validity and Soundness
 Consider the following deductive argument:
 If you are in Chiromo, then you are in Nairobi
 If you are in Nairobi, then you are in Kenya
 Therefore if you are in Chiromo you are in Kenya
 Both premises and conclusion happen to be true
statements, But if you substitute Kampala for Nairobi the
argument will have false premises.
 Therefore, there are arguments that intuitively seem to
be valid in the sense that the conclusions somehow
follow from the premises, but which still have something
missing.

22
B. Okuku
 Logic: Validity and Soundness …
 Validity:
 A deductive argument (or argument form) is valid if
and only if it is impossible for its conclusion to be false
when its premises are true.

 Soundness:
 A deductive argument is sound if it is valid and has
true premises.

23
B. Okuku
 Advantages of formal logic
 There is a set of rules called rules of inference by which
facts that are known to be true can be used to derive
other facts, which must also be true.

 The truth of any new proposition can be checked, in a

well-specified manner, against the facts that are already
known to be true.
 Logical inferences will only guarantee the truth of a conclusion if
the premises leading to the conclusion are also true.

24
B. Okuku