KR Module Exam
What is knowledge representation?
branch of AI concerned with the techniques for representing and reasoning about knowledge.
What is the long term goal of KR?
Make programs, systems, interfaces and agents behave intelligently.
What are the characteristics of intelligent entities?
They can reason, make decisions/plans, learn, communicate, take commands/queries/requests/preferences, act/return answers/plans/decisions/control commands
What is reasoning?
The process of making inferences. Make implicit knowledge explicit, correctness, and completeness
What do we need to reason with
How can a reasoning task be expressed?
Knowledge base to conclusion or asserted knowledge to inferred knowledge
How is entailment or inference defined?
Based on the concept of implication. Premise to conclusion, if ==>then, sometimes called rule.
All men are mortal
If something is a man, then it is mortal
If something is not mortal, then it can't be a man
If something is not a man, then ???
It is not mortal
What is deduction? Provide an example
Premise to conclusion
Socrates is a man. All men are mortal.
So, Socrates must be mortal, too
What is abduction? Provide an example
Conclusion to premise
All men are mortal. Socrates is mortal.
So, (it's possible that) Socrates is a man
What is induction? Provide an example
Premise/conclusion to implication
Socrates is a man and is mortal.
Aristoteles is a man and is mortal.
So, (it's likely that) all men are mortal
What are some KB search strategies?
What is forward chaining
-Start from known facts
– Make inferences to derive new facts
– Stop when goal has been derived
What is backward chaining
-Start from goal
– See under which premises the goal can be entailed
– Replace goal with premises
– Stop when current goal is a known fact
How is knowledge encoded in a suitable format
In declarativeness, what is how?
Exact step by step instructions
In declarativeness what is what
A high level directive or request whose detailed implementation is left up to the intelligent entity.
The more ____ level the directives and requests an entity can handle, the more ____ it is
What is appropriate knowledge representation
can be consumed by a “standard” reasoning process
“Implemented” by an “intelligent” being
What is language
Syntax and Semantics
What is the fundamental issue of KR
Need appropriate languages to be able to
Given KB to conclusion, we need
– (how to write) KB and Conclusion.
– (meaning) for ‘’.
– Semantics ~ “Enumerating the ‘models’ of KB”
What should KB be?
Incremental, should be easy to add and revise knowledge.
What is (non) monotonicity
KB ==> Conclusion
KB + New Knowledge==> not Conclusion
Provide an example of default language
I don't know this, but given that normally this...
Provide an example of episthemic language
I believe that you know this
Provide an example of modal language
This is possibly while that is necessarily
Provide an example of deontic language
This is obligatory, while that is prohibited
Provide an example of defeasible language
This would be true except that
Provide an example of temporal language
This is true now
Rule Based Inference example
Inclusion: gender, female, pregnant, gestational age...
Exclusion: chorioamnionitis, non-reasuring fetal testing
ancestor(X,Y) ancestor(X,Z), parent(Z,Y).
parent( alex, bob ).
parent( bob, carlos ).
parent( bob, diana ).
parent( fiona, alex ).
Can you derive the full ancestry knowledge inherent here
(ie, all the facts that can be derived from the given facts)?
What must we do in KR (need a way to write? assign meaning to?)
We need a way to write (syntax) and assign meaning
– Facts (previous knowledge)
– Rules (conditions) + allow learning
– Questions (queries)
so a computer can process them and reach reasonable
conclusions (answers, plans, new knowledge).
Applications of reasoning?
Reasoning with incomplete information, default
– Reasoning with preferences and priorities, inheritance
What is featured in declarative problem solving
Planning, job shift scheduling.
– Explanation generation, diagnosis.
– Combinatorial graph problems.
Further applications of KR
Causal modeling, medical decision support systems
What is of fundamental importance in building intelligent entities
Representing knowledge and reasoning with it is of fundamental
building intelligent entities.
What are specific languages used for in KR
Specific languages are used to express (represent) this knowledge and
knowledge from it (reason).
What are logics
formal languages for representing information such that conclusions can be drawn
What is syntax
defines the sentences in the language
What are semantics
define the "meaning" of sentences
What is a model
“worlds” with respect to which truth can be evaluated
What is entailment
expresses the notion that a sentence logically follows (can be derived from) another. Used to carry out logical inference.
What is logical inference
the process derivation of all sentences that logically follow another
What are the two parts of interpretation
Domain and interpretation mapping
What is the domain of discourse
can be any non-empty set, not just formal/mathematical object (i.e. people, tables, numbers, unicorns, chunks of PB, the universe)
What is an interpretation mapping
If P is a predicate symbol of arity, an n-aray relation over D for propositional symbols....etc...
What are the assumptions of first order logic
Assumes the world contains objects, relations, and functions
What are objects
Protein, people, house, numbers
What are relations
activates, red, round, prime,
brother, part of, comes between, … any
assertion of the form R(x),
What are functions
>, <, one more than, plus, … any
f(x) applied to an object x (or a set of objects).
Basic elements of first order logic
Constants: john, 2, asu,...
• Predicates: brother, active,...
• Functions: sqrt, leftLegOf,...
• Variables: X, Y, A, B, Test, …
• Connectives: Ø, Þ , Ù, Ú, Û
• Equality: =
• Quantifiers: ", $
What is an atomic sentece
: predicate (term1,...,termn)
| term1 = term2
where a term is defined as follows:
: function (term1,...,termn)
What are complex sentences. Provide an example
Complex sentences are made from atomic
sentences using connectives
ØS, S1 Ù S2, S1 Ú S2, S1 Þ S2, S1 Û S2,
– Sibling(x,y) Þ Sibling(y,x)
– greater(x,y) Ú lessOrEqual(x,y)
– >(x,y) Ù Ø >(x,y)
When are sentences true
Sentences are true with respect to a model and an
What does a model contain
A model contains objects (domain elements) and
relations among them
What does an interpretation specify referent for
constant symbols → objects
predicate symbols → relations
function symbols → functional relation
When is an atomic sentence predicate true
An atomic sentence predicate(term1,...,termn) is true
if the objects referred to by term1,...,termn
are in the relation referred to by predicate
What are complex sentences
What are complex sentences based on
Based on the truth value of each atom
– Combined using the operators' “truth tables”
OR y Øy
x T T
Øx T F
AND y Øy
x T F
Øx F F
Write universal quantification for: Everyone at ASU is smart
"vX : at(X,asu) → smart(X)
Vx what is stand for
P is true in a model m iff P is true for all possible
objects x in the model
Roughly speaking, equivalent to the conjunction
instantiations of P
at(jian,asu) → smart(jian)
Ù at(richard,asu) → smart(richard)
Ù at(asu,asu) → smart(asu)
Ù at(abc129,asu) → smart(abc129)
Typically, ==> is the main connective used
Common mistake: using ^ as the main
VX: at(X,asu) ^ Smart(X) means?
“Everyone is at ASU and everyone is smart”
Existential quantification for: Someone at ASU is smart:
EX: at(X,asu) ^Smart(X)
Ex P is true in a model m if
P is true with x being some possible object (at least one) in the model
Existential quantification is equivalent to?
Roughly speaking, equivalent to the disjunction
instantiations of P
Vx Vy is the same as
Ex Ey is the same as
Ex Vy is not the same as
Ex Vy loves(X,Y) stands for
There is a person who loves everyone in the world”
Vy Ex loves(X,Y)
“Everyone in the world is loved by at least one person”
What is a quantifier duality
each can be expressed using the other
Two sentences are logically equivalent if
true in same model
term1 = term2 is true under
a given interpretation if and only if term1 and term2 refer to the same object
John is Mark's brother
John has a brother
brother( john, theBrotherOf(john) )
– or -
EX : brother(john, X)
John is a man
– or –
VX,Y: brother(X,Y) ==> Sibling(X,Y)
Brothers are siblings
VM,C mother(C) = M <==>
(female(M) ^ Parent(M,C))
One's mother is one's female parent
“Sibling” is symmetric
VX,Y: Sibling(X,Y) <==> Sibling(Y,X)
Definition of Sibling in terms of Parent:
VX,Y : sibling(X,Y)
“Any two individuals are siblings iff”
John is a patient
patient( john )
John suffers from diabetes
suffersFrom( john, diabetes )
John is taking some drug for diabetes
E D: drug(D) ^ takes(john, D) ^ treats(D, diabetes)
(All) drugs treat some disease
VD: drug(D) ==> E X : disease(X) ^ treats(D,X)
(All) drugs treat (all) diseases
VD,X: drug(D) ^ disease(X) ==> treats(D,X)
Try defining “uncle” and “aunt”
in terms of “brother” / “sister” and “parent
VX,Y : uncle(X,Y)
EF: parent(F,Y) ^ brother(X,F)
• VX,Y : uncle(X,Y)
^ Ø (X = F)
What can first order logic represent
FOL can represent knowledge about a simple
What can logical reasoning do
Logical reasoning can discover new facts using