Declarative language
Before building system
before there can be learning, reasoning, planning, explanation …
need to be able to express knowledge Want a precise declarative language
• declarative: believe P = hold P to be true
cannot believe P without some sense of what it would
mean for the world to satisfy P
• precise: need to know exactly
– what strings of symbols count as sentences
– what it means for a sentence to be true
(but without having to specify which ones are true)
What does it mean to have a language? • syntax
• semantics • pragmatics
Here: language of first-order logic again: not the only choice
KR & R © Brachman & Levesque 2005 FOL 1
Alphabet
• Punctuation: (, ), .
• Connectives: ¬,Ù,Ú,É,o,”,$,=
• Variables: x, x1, x2, …, x’, x”, …, y, …, z, …
Fixed meaning and use
like keywords in a programming language
Non-logical symbols
Logical symbols:
• •
Predicatesymbols(likeDog) Functionsymbols(likebestFriendOf)
Domain-dependent meaning and use
like identifiers in a programming language
Have arity: number of arguments
arity 0 predicates: propositional symbols arity 0 functions: constant symbols
Assume infinite supply of every arity Note: not treating = as a predicate
KR & R
© Brachman & Levesque 2005
FOL 2
Grammar
Expressions: terms and formulas (wffs)
T erms
1. Every variable is a term.
2. If t1, t2, …, tn are terms and f is a function of arity n, then f(t1, t2, …, tn) is a term.
Atomic wffs
1. If t1, t2, …, tn are terms and P is a predicate of arity n,
then P(t1, t2, …, tn) is an atomic wff.
2. If t1 and t2 are terms, then (t1=t2) is an atomic wff.
Wffs
1. Every atomic wff is a wff
2.If a and b are wffs, and v is a variable, then ¬a, (a Ù b), (a Ú b), $v.a, “v.a are wffs.
The propositional subset: No terms
Atomic wffs: only predicates of 0-arity No variables and no quantifiers
(pÙ ¬(qÚr))
KR & R © Brachman & Levesque 2005 FOL 3
Notation
Occasionally add or omit (, ), .
Use[,]and{,} also.
Abbreviations: (aÉb) for (¬aÚb)
(aob) for ((aÉb)Ù(bÉa))
Non-logical symbols:
Predicates: Person, Happy, OlderThan Functions: fatherOf, successor, johnSmith
Lexical scope for variables
P(x) Ù $x[P(x) Ú Q(x)]
free bound occurrences of variables
Sentence: wff with no free variables (closed)
Substitution: a[v/t] means a with all free occurrences of v replaced by term t
(also avt)..
KR & R © Brachman & Levesque 2005 FOL 4
Semantics
How to interpret sentences?
• whatdosentencesclaimabouttheworld? • whatdoesbelievingoneamountto?
Without answers, cannot use sentences to represent knowledge
Problem:
cannot fully specify interpretation of sentences because non- logical symbols reach outside the language
So:
Logical interpretation:
specification of how to understand predicate and function symbols
Can be complex!
DemocraticCountry, IsABetterJudgeOfCharacterThan, favouriteIceCreamFlavourOf, puddleOfWater27
make clear dependence of interpretation on non-logical symbols
KR & R © Brachman & Levesque 2005 FOL 5
Simple case
There are objects
some satisfy predicate P; some do not
Each interpretation settles extension of P borderline cases ruled in separate interpretations
Each interpretation assigns to function f a mapping from objects to objects
functions always well-defined and single-valued
Main assumption:
this is all you need to know about the non-logical symbols to understand which sentences of FOL are true or false
In other words, given a specification of – what objects there are
– which of them satisfy P
– what mapping is denoted by f
it will be possible to say which sentences of FOL are true and which are not
KR & R
© Brachman & Levesque 2005 FOL 6
Interpretations
Two parts: I = áD,Fñ
D is the domain of discourse
can be any set
not just formal / mathematical objects
e.g. people, tables, numbers, sentences, chunks of peanut butter, situations, the universe
F is an interpretation mapping If P is a predicate symbol of arity n,
KR & R
F(P) Í [D ́D ́… ́D]
an n-ary relation over D
Can view interpretation of predicates in terms of characteristic function
F(P) Î [D ́D ́… ́D ® {0, 1}] If f is a function symbol of arity n,
F(f) Î [D ́D ́… ́D ® D] an n-ary function over D
For constants, F(c) Î D © Brachman & Levesque 2005
FOL 7
Denotation
In terms of interpretation I, terms will denote elements of D.
will write element as I||t||
For terms with variables, denotation depends on
the values of variables will write as I,μ||t||
where μ Î [Variables ® D], called a variable assignment
Rules of interpretation:
1. 2.
I,μ ||v|| = μ(v).
I,μ || f(t1, t2, …, tn) || = H(d1, d2, …, dn) where H = F(f)
and di = I,μ||ti||, recursively
KR & R
© Brachman & Levesque 2005
FOL 8
Satisfaction
In terms of I, wffs will be true for some values of the free variables and false for others
will write as I,μ ú= a “a is satisfied by I and μ” where μ Î [Variables ® D], as before
or Iú=a, whena isasentence
or Iú=S, whenS isasetofsentences
(all sentences in S are true in I). Rules of interpretation:
1. I,μ ú= P(t1, t2, …, tn) iff ád1, d2, …, dnñ Î R where R = F(P)
and di = I,μ || ti ||, as on previous slide
2.I,μ ú= (t1 = t2) iff I,μ|| t1 || is the same as I,μ|| t2 || 3.I,μ ú= ¬a iff I,μ ú1 a
4.I,μú= 5.I,μú= 6. I,μ ú= 7. I,μ ú=
(aÙb) iff I,μú=a and I,μú=b
(aÚb) iff I,μú=a or I,μú=b
$v.a iff for some d Î D, I,μ{d;v}ú= a
“v.a iff for all d Î D, I,μ{d;v}ú= a
where μ{d;v} is just like μ, except on v, where μ(v)=d.
For propositional subset:
Iú=p iff F(p) =1 andtherestasabove
KR & R © Brachman & Levesque 2005 FOL 9
Logical consequence
Semantic rules of interpretation tell us how to understand all wffs in terms of specification for non-logical symbols.
But some connections among sentences are independent of non-logical symbols involved.
e.g. If a is true under I, then so is ¬(b Ù ¬a), no matter what I is, why a is true, what b is, …
a function of logical symbols only
S entails a or a is a logical consequence of S:
Inotherwords:fornoI, I|=SÈ{¬a}. Say that S È {¬a} is unsatisfiable
Special case: S is empty
|=a iff forevery I, I|=a. Sayaisvalid.
Note:{a1,a2,…,an}|=a iff |= (a1 Ùa2 Ù…Ùan)Éa finite entailment reduces to validity
S|=a iff forevery I, ifI|=S thenI|=a.
KR & R © Brachman & Levesque 2005 FOL 10
Why do we care?
We do not have access to user-intended interpretation of non-logical symbols
But, with entailment, we know that if S is true in the intended interpretation, then so is a.
If the user’s view has the world satisfying S, then it must also satisfy a.
There may be other sentences true also; but a is logically guaranteed.
So what about:
Dog(fido) => Mammal(fido) ?? Not entailment!
There are logical interpretations where F(Dog) Ë F(Mammal)
Key idea of KR:
include such connections explicitly in S
“x[Dog(x) É Mammal(x)]
Get: S È {Dog(fido)} |= Mammal(fido)
The rest is just the details…
KR & R
© Brachman & Levesque 2005
FOL 11
Knowledge Bases
KB is set of sentences
explicit statement of sentences believed (including assumed connections among non-logical symbols)
KB |= a a is a further consequence of what is believed
• explicitknowledge:KB
• implicit knowledge: { a | KB |= a}
Often non trivial: explicit implicit
Example:
Three blocks stacked.
Top one is green. Bottom one is not green.
green
non-green
A
B
C
Is there a green block directly on top of a non-green block?
KR & R © Brachman & Levesque 2005 FOL 12
A formalization
S = {On(a,b), On(b,c), Green(a), ¬Green(c)} all that is required
a = $x$y[Green(x) Ù ¬Green(y) Ù On(x,y)]
Claim: S |= a
Proof:
Let I be any interpretation such that I |= S.
Case 1: I |= Green(b).
\ I |= Green(b) Ù ¬Green(c) Ù On(b,c). \ I |= a
Case 2: I |1 Green(b).
\ I |= ¬Green(b)
\ I |= Green(a) Ù ¬Green(b) Ù On(a,b). \ I |= a
Eitherway, foranyI, if I|=S then I|=a. So S |= a. QED
KR & R © Brachman & Levesque 2005 FOL 13
Knowledge-based system
Start with (large) KB representing what is explicitly known
e.g. what the system has been told
Want to influence behaviour based on what is implicit in the KB (or as close as possible)
Requires reasoning
deductive inference:
process of calculating entailments of KB
i.e given KB and any a, determine if KB |= a Process is sound if whenever it produces a, then KB |= a
does not allow for plausible assumptions that may be true in intended interpretation
Process is complete if whenever KB |= a, it produces a
does not allow for process to miss some a or be unable
to determine the status of a
KR & R © Brachman & Levesque 2005 FOL 14