Transcript l13 - CE Sharif

Knowledge Representation
and Reasoning
1
Knowledge Representation & Reasoning
• How knowledge about the world can be represented
• What kinds of reasoning can be done with that
knowledge.
• Two different systems that are commonly used to
represent knowledge:
• Propositional calculus
• Predicate calculus
2
Propositional Calculus
In propositional calculus,
• features of the world are represented by
propositions,
• relationships between features (constraints)
are
represented by connectives.
Example:
LECTURE_BORING  TIME_LATE ! SLEEP
3
Propositional Calculus
You see that the language of propositional calculus
can be used to represent aspects of the world.
When there are
• a language, as defined by a syntax,
• inference rules for manipulating sentences in that
language, and
• semantics for associating elements of the
language with elements of the world,
then we have a system called logic.
4
Logic
• When we have too many states, we want a
convenient way of dealing with sets of
states.
• The sentence “It’s raining” stands for all the
states of the world in which it is raining.
• Logic provides a way of manipulating big
collections of sets by manipulating short
descriptions instead.
5
What is a logic?
A formal language:
• Syntax – what expressions are legal
• Semantics – what legal expressions
mean
• Proof system – a way of manipulating
syntactic expressions to get other
syntactic expressions (which will tell
us something new)
6
Propositional Logic
Atoms:
The atoms T and F and all strings that begin with a
capital letter, for instance, P, Q, LECTURE_BORING,
and so on.
Connectives:
•  “or”
•  “and”
• ! “implies” or “if-then”
• $ “equivalence”
•  “not”
7
Propositional Logic
Syntax of well-formed formulas (wffs):
• Any atom is a wff.
• If 1 and 2 are wffs, so are
1  2 (conjunction)
1  2 (disjunction)
1 ! 2 (implication)
1 $ 2 (double implication)
1
(negation)
• There are no other wffs.
8
Propositional Logic
• Atoms and negated atoms are called literals.
• In 1 ! 2 , 1 is called the antecedent, and
2 is called the consequent of the implication.
• Examples of wffs (sentences):
(P  Q) ! P
P ! P
PP!P
(P ! Q) ! (Q ! P)
P
9
:
Æ
Ç
!
$
highest
Precedence
AÇBÆC
A Ç (B Æ C)
AÆB!CÇD
(A Æ B) ! (C Ç D)
A!BÇC$D
(A ! (B Ç C)) $ D
lowest
•
Precedence rules enable “shorthand” form of sentences,
but formally only the fully parenthesized form is legal.
•
Syntactically ambiguous forms allowed in shorthand only
when semantically equivalent: A Æ B Æ C is equivalent to
(A Æ B) Æ C and A Æ (B Æ C)
10
Rules of Inference
We use rules of inference to generate new wffs
from existing ones.
One important rule is called modus ponens or the
law of detachment. It is based on the tautology
(P  (P ! Q)) ! Q. We write it in the following way:
P
P!Q
_____
Q
The two hypotheses P and P ! Q are
written in a column, and the conclusion
below a bar, where  means “therefore”.
11
Rules of Inference
P
______
Addition
 PQ
PQ
_____
P
Simplification
P
Q
______ Conjunction
 PQ
Q
P!Q
_____
 P
Modus tollens
P!Q
Hypothetical
Q!R
_______ syllogism
P!R
PQ
P
_____
Q
Disjunctive
syllogism
12
Predicate Calculus
Proposition’s are simple but weak, so it is a better
idea to use predicates instead of propositions.
This leads us to predicate calculus.
Predicate calculus has symbols called
• object constants,
• relation constants, and
• function constants
These symbols will be used to refer to objects in the
world and to propositions about the world.
13
Syntax of First-Order Logic in BNF
Sentence 
|
|
|
|
AtomicSentence
Sentence Connective Sentence
Quantifier Variable,… Sentence
 Sentence
(Sentence)
AtomicSentence  Predicate(Term,…) | Term= Term
Term  Function(Term,…)
| Constant
| Variable
14
Syntax of First-Order Logic in BNF
Connective
Quantifier
Constant
Variable
Predicate
Function
||||$
|
 A | X1 | John | …
a|v|x|…
 Before | HasColor | Raining | …
 MotherOf | LegOf | …
15
Components
Object constants:
Strings of alphanumeric characters beginning with
either a capital letter or a numeral.
Examples: XY, George, 154, H1B
Function constants:
Strings of alphanumeric characters beginning with a
lowercase letter and (sometimes) superscripted by
their “arity”:
Examples: fatherOf1, distanceBetween2
16
Components
Relation constants:
Strings of alphanumeric characters beginning with a
capital letter and (sometimes) superscripted by their
“arity”:
Examples: BeatsUp2, Tired1
Other symbols:
Propositional connectives , , !, $ , and , delimiters
(, ), [, ].
17
Terms
• An object constant is a term.
• A function constant of arity n, followed by n terms in
parentheses and separated by commas, is a term.
Examples: fatherOf(George), times(3, minus(5, 2))
18
Wffs
Atoms:
• A relation constant of arity n followed by n terms in
parentheses and separated by commas is an atom.
An atom is a wff.
• Examples: Tired(John), OlderThan(Hans, Peter)
Propositional wffs:
• Any expression formed out of predicate-calculus
wffs in the same way that the propositional calculus
forms wffs out of other wffs is a propositional wff.
• Example: OlderThan(John, Peter) 
OlderThan(Peter, Jennifer)
19
Quantification
Introducing the universal quantifier  and the existential
quantifier  facilitates the translation of world knowledge into
predicate calculus.
Examples:
Paul hates all professors who fail him.
x(Professor(x)  Fails(x, Paul) ! Hates(Paul, x))
There is at least one intelligent Sharif professor.
x(SharifProf(x)  Intelligent(x))
20
Rules of Inference
x
P(x)
__________
 P(c) if cU
Universal
instantiation
P(c)
for an arbitrary cU
___________________
 x P(x)
Universal
generalization
x
P(x)
______________________
 P(c) for some element cU
Existential
instantiation
P(c)
for
some
element
cU
____________________
 x P(x)
Existential
generalization
21
Quantifiers
Properties of quantifiers:
– x y is the same as y x
– x y is the same as y x
– note: x y can be written as x,y likewise with 
Example?
– x y Likes(x,y) is active voice:
Everyone likes everyone.
– y x Likes(x,y) is passive voice:
Everyone is liked by everyone.
22
Quantifiers
Properties of quantifiers:
– x y is not the same as y x
– x y is not the same as y x
Example?
– x y Likes(x,y) is active voice:
Everyone likes someone.
– y x Likes(x,y) is passive voice:
Someone is liked by everyone.
23
Quantifiers
Properties of quantifiers:
– x P(x) is the same as x P(x)
– x P(x) is the same as x P(x)
Example?
– x Likes(x,IceCream)
Everyone likes ice cream.
– x Likes(x,IceCream)
No one doesn't like ice cream.
It's a double negative!
24
Quantifiers
Properties of quantifiers:
– x P(x) when negated is x P(x)
– x P(x) when negated is x P(x)
Example?
– x Likes(x,IceCream)
Everyone likes ice cream.
– x Likes(x,IceCream)
Someone doesn't like ice cream.
– This is from the application of de Morgan's law
to the fully instantiated sentence.
25
Basics
A free variable is a variable that
isn't bound by a quantifier.
– y Likes(x,y)
x is free, y is bound
A well-formed formula is a sentence where
all variables are quantified.
26
Summary
Term: Constant, variable, or Function(term1, …, termn)
denotes an object in the world
Ground Term has no variables
Atom: Predicate(term1, …, termn), term1 = term2
is smallest expression assigned a truth value
Sentence:
atom, quantified sentence with variables or
complex sentence using connectives
is assigned a truth value
Well-Formed Formula (wff):
sentence where all variables are quantified
27
An example of E.I.
b1
b2
T1
1.
2.
3.
4.
b3
b1
b2
b3
T2
x(Bottle(x,T1)  Upturned(x, T2))
xy(Upturned(x, y)  Empty(x, y))
x(Full(x, T1) & Empty(x, T2)  Wet(Floor))
x (Bottle(x, T1) & Full(x, T1))
28
An example of E.I.
5.
Bottle(b1, T1) & Full(b1, T1))
6.
Bottle(b1, T1)
7.
Full(b1, T1)
8.
Upturned (b1, T2)
9.
Empty(b1, T2)
10.
Full(b1, T1) & Empty (b1, T2)
11.
Wet(Floor)
Wet(Floor)
- EI assumption
-&,5
-&,5
-,1,-,6
-,2,-,7
+ & , 7, 9
-  , 3, -  , 10
- EI conclusion
29