Chapter 4

Knowledge and Reasoning

 Knowledge bases

 Knowledge base = set of sentences in a formal language

 Declarative approach to building an agent (or other system):
• Tell it what it needs to know
 Then it can Ask itself what to do - answers should follow from the
KB
 Agents can be viewed at the knowledge level
i.e., what they know, regardless of how implemented
 Or at the implementation level
• i.e., data structures in KB and algorithms that manipulate them

•
 A simple knowledge-based agent

 The agent must be able to:

• Represent states, actions, etc.
• Incorporate new percepts
• Update internal representations of the world
• Deduce hidden properties of the world
• Deduce appropriate actions
 Why KR?
 We understand by "knowledge" all kinds of
facts about the world.
 Knowledge is necessary for intelligent
behavior (human beings, robots).
 What is knowledge? We shall not try to
answer this question!
 Instead, in this course we consider
representations of knowledge and how we
can use it in making intelligent artifacts.
 KR Challenges
 Challenges of KR:
• representation of commonsense knowledge
• the ability of a knowledge-based system to
tradeoff computational efficiency for accuracy
of inferences
• its ability to represent and manipulate
uncertain knowledge and information.
 What is KR?

 A knowledge representation is most

fundamentally a surrogate, a substitute
for the thing itself, used to enable an entity
to determine consequences by reasoning
about the world.
 It is a set of ontological commitments,
i.e., an answer to the question: In what
terms should I think about the world?
 What is KR?
 It is a fragmentary theory of intelligent
reasoning, expressed in terms of three
components:
• the representation's fundamental
conception of intelligent reasoning;
• the set of inferences the representation
sanctions;
• the set of inferences it recommends.
 What is KR?
 It is a medium for pragmatically efficient
computation, i.e., the computational
environment in which reasoning is
accomplished.
• One contribution to this pragmatic efficiency is
supplied by the guidance a representation provides
for organizing information so as to facilitate making
the recommended inferences.

 It is a medium of human expression, i.e., a

language in which we say things about the
world.
 What is KR?
 If A represents B, then A stands for B and
is usually more easily accessible than B.

 We are interested in symbolic

representations

 Symbolic representations of propositions

or statements that are believed by some
agent.
 What is Reasoning?
 Not interested (in the course) in the
philosophical dimension
 Reasoning is the use of symbolic
representations of some statements in
order to derive new ones.

 While statements are abstract objects,

their representations are concrete objects
and can be easily manipulated.
 What is Reasoning?
 Reasoning can be as easy as mechanical
symbol manipulation.

 Reasoning should scale well: we need

efficient reasoning algorithms.
 Formal logic
 Formal logic is the field of study of entailment
relations, formal languages, truth conditions,
semantics, and inference.
 All propositions/statements are represented as
formulae which have a semantics according to
the logic in question.
 Logical system = Formal language +
semantics
 Formal logics gives us a framework to discuss
different kinds of reasoning.
 Logical consequence (entailment)

 Proof centered approach to logical

consequence: the validity of a reasoning
process (argument) amounts to there
being a proof of the conclusions from the
premises.
 Logical consequence (entailment)
 Model centered approach to logical
consequence
 Models are abstract mathematical structures that
provide possible interpretations for each of the
non-logical primitives in a formal language.
 Given a model for a language - define what it is
for a sentence in that language to be true
(according to that model) or not.
 In any model in which the premises are true the
conclusion is true too. (Tarski's definition of logical
consequence from 1936.)
 Properties of logical systems
Important properties of logical systems:
 Consistency - no theorem of the system contradicts
another.
 Soundness - the system's rules of proof will never
allow a false inference from a true premise. If a system
is sound and its axioms are true then its theorems are also guaranteed to be
true.

 Completeness - there are no true sentences in the

system that cannot, at least in principle, be proved
in the system.
 Some logical systems do not have all three properties. Kurt Godel's
incompleteness theorems show that no standard formal system of
arithmetic can be consistent and complete.
How can knowledge be represented ?
 Symbolic methods
• Declarative Languages (Logic)
• Imperative Languages (C, C++, Java, etc.)
• Hybrid Languages (Prolog)
• Rules
• Frames
• Semantic Networks
•…
 Non – symbolic methods
• Neural Networks
• Genetic Algorithms
 Types of Knowledge
 Declarative Knowledge
• Description of notions, facts, and rules of the
world
 E.g.
• For each lecture there is a specific time and
place
• Only one lecture can take place at each time
and place
 Descriptional knowledge, non procedural,
independent of targets and problem solving
 Types of Knowledge
 Procedural Knowledge
• Description of procedures required to achieve targets
• Knowledge of the order in which actions must be
performed
• Heuristic knowledge
 E.g.
• To construct the exams timetable, assign first the
classes of the first year
• To reach Athens faster, take the airplane
It depends on the targets and problems
 Types of Knowledge
 Basic Difference
• declarative knowledge is right or wrong
 Lectures are on Wednesdays
• procedural knowledge can be executed
 the procedure of constructing the exams
timetable
Knowledge Representation
&
Reasoning

 Which of the two interests us ?

• Both of course
 Propositional logic: Syntax
 Atomic sentence:
• A proposition symbol representing a true or false statement
 Negation:
• If P is a sentence, P is a sentence
 Conjunction:
• If P and Q are sentences, P  Q is a sentence
 Disjunction:
• If P and Q are sentences, P  Q is a sentence
 Implication:
• If P and Q are sentences, P  Q is a sentence
 Biconditional:
• If P and Q are sentences, P  Q is a sentence

 , , , ,  are called logical connectives

 Propositional logic: Semantics
 A model specifies the true/false status of each
proposition symbol in the knowledge base
• E.g., P is true, Q is true, R is false
• With three symbols, there are 8 possible models, and they can be
enumerated exhaustively

 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
P  Q is true iff P  Q is true and Q  P is true
 Truth tables
 A truth table specifies the truth value of a
composite sentence for each possible
assignments of truth values to its atoms

 The truth value of a more complex sentence can

be evaluated recursively or compositionally
 Logical equivalence
 Two sentences are logically equivalent iff they are true in
same models
 Universal quantification
 x P(x)

 Example: “Everyone at UNC is smart”

x At(x,UNC)  Smart(x)
Why not x At(x,UNC)  Smart(x)?

 Roughly speaking, equivalent to the conjunction of all

possible instantiations of the variable:
[At(John, UNC)  Smart(John)]  ...
[At(Richard, UNC)  Smart(Richard)]  ...

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

each possible object in the model
 Existential quantification
 x P(x)

 Example: “Someone at UNC is smart”

x At(x,UNC)  Smart(x)
Why not x At(x,UNC)  Smart(x)?

 Roughly speaking, equivalent to the disjunction of all

possible instantiations:
[At(John,UNC)  Smart(John)] 
[At(Richard,UNC)  Smart(Richard)]  …
 x P(x) is true in a model m iff P(x) is true with x being
some possible object in the model
 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
x y Loves(x,y)
“There is a person who loves everyone”
y x Loves(x,y)
“Everyone is loved by at least one person”

 Quantifier duality: each quantifier can be expressed using

the other with the help of negation
x Likes(x,IceCream) x Likes(x,IceCream)
x Likes(x,Broccoli) x Likes(x,Broccoli)