展开查看详情
2 . Propositional logic v. FOPC
❧Propositional calculus deals only with facts
● P : I-love-all-dogs
● facts are either true or they are false
❧Predicate calculus makes a stronger commitment
to what there is (ontology)
● objects: things in the world (no truth value)
● properties & relations of and between objects (truth
value)
❧FOPC breaks facts down into objects & relations
● can be seen as an extension of propositional logic
3 . Predicate calculus
❧Terms refer to objects in the world
● John, Mary, etc.
● functions (one-to-one mapping)
● these terms do not have a truth value assigned to them
❧Predicates [propositions with arguments]
● marriedTo(John, Mary)
❧Quantifiers
● ∀x[valuable(x)]
● ∃x[valuable(x)]
❧Equality: do two terms refer to the same object?
4 .Terms
❧Logical expressions that refer to objects
● Constants (by convention, capitalized)
• e.g., Sue
● Variables (by convention, lower case)
• used with quantifiers
• e.g., x
● Functions
• MotherOf(Sue)
• since functions represent objects, we can nest them
– MotherOf(MotherOf(Ann))
• don’t need explicit names
– LeftFootOf(John)
5 .Sentences
❧Just as in propositional logic, sentences
have a truth-value
❧In FOPC, only relations (predicates) have
truth-values
❧Thus, terms alone are not wffs
❧They must be (part of) an argument to a
predicate
6 .Making sentences
❧Atomic sentences: a single predicate
● married(Sue, FatherOf(Ann))
❧Complex sentences
● just as in propositional logic, we can make
more complicated sentences by combining
predicates using connectives
• or, and, implies, equivalence, not
● quantifiers
● equality
7 .Quantifiers
❧Allows us to express properties of
categories of objects without listing all of
the objects
❧Universal
● ∀x[P(x)] : T if P(x) is true for every object in
our interpretation
● e.g., all men are mortal
❧Existential
● ∃x[P(x)] : T if P(x) is T for some object in our
interpretation
● e.g., I love some dog
8 .Equality
❧An in-fix predicate
● but a predicate all the same [returns true or
false]
● e.g., FatherOf(John) = Henry
❧termA = termB is shorthand for
equal(termA, termB)
● doesn’t have to be in-fix; convenient
❧Will be true if termA & termB refer to the
same object
9 .Backus-Naur form
Sentence → AtomicSentence
| Sentence Connective Sentence
| Quantifier Variable,… Sentence
| ¬ Sentence
| ( Sentence )
Atomic Sentence → Predicate (Term,…)
| Term = Term
10 .BNF (cont.)
Term → Function ( Term,…)
| Constant
| Variable
Connective → ⇒ | ∧ | ∨ | ⇔
Quantifier → ∀ | ∃
11 .BNF (cont.)
Constant → A | X1 | John | . . .
Variable → a | x | s | . . .
Predicate → before | hasColor | raining | . . .
Function → MotherOf | LeftLegOf | . . .
12 .Well Formed Formulas (WFFs)?
❧tall(john)
❧MotherOf(john)
❧mother(john, mary)
❧John = brother(Bill)
● equal(john, brother(Bill))
❧F(p(1) ^ q(2))
13 .English → FOPC
❧“Every rational number is a real number”
❧∀x[rational(x) ⇒ real(x)]
❧What about
● ∀x[rational(x) ∧ real(x)]?
● ∃x[rational(x) ∧ real(x)]?
● ∀x[¬real(x) ∨ rational(x)]?
14 .More English → FOPC
❧There is a prime number greater than 100
● ∃x[prime(x) ∧ greaterThan(x, 100)]
● ∃x[prime(x) ∧ x > 100]
❧There is no largest prime
● no-largest-prime
● ∀x[prime(x) ⇒ ∃y[prime(y) ∧ greaterThan(y,
x)]]
❧Every number has an additive inverse
● ∀x[number(x) ⇒ ∃y[ equal(Plus(x, y), 0)]
15 .Mixing quantifiers
❧Everyone likes a dog
● ∀x[human(x) ⇒ ∃y[dog(y) ^ likes(x, y)]]
❧There’s one dog everyone likes
● ∃y[dog(y) ^ ∀x[human(x) ⇒ likes(x, y)]]
❧Everyone likes a different dog
● ∀x[human(x) ⇒ ∃y[dog(y) ^ likes(x, y) ^
∀z[human(z) ^ likes(z, y)] ⇒ x = z]]
16 .Location of quantifiers
❧Everyone likes a dog
● ∀x[human(x) ⇒ ∃y[dog(y) ∧ likes(x, y)]]
❧What about
● ∀x[∃y[(human(x) ∧ dog(y)) ⇒ likes(x, y)]]
• human(Jim) : T; human(Spot) : F;
• dog(Jim) : F; dog(Spot) : T;
• likes(Jim,Jim) : T; likes(Jim,Spot) : F;
• likes(Spot,Jim) : F; likes(Spot,Spot) : T
❧In general, never use ∃x with ⇒, and don’t
use ∀x with ∧
17 .What is the truth-value of FOPC
wffs? FOPC interpretations
❧The “user” must provide a finite list of
objects in the world
● “universe of discourse”
❧For each function, a mapping from
“parameter setting” to an object in the world
● e.g., Father(John) maps to “Bill”
❧For each predicate, a mapping from each
“parameter setting” to true or false
18 .Determining truth-value of FOPC wff
❧Specify an interpretation, I
❧Obtain truth-values of
● predicates
• look up functions until only constants remain & then look
up the truth value of the predicate
● termA = termB
• look up functions until only constants remain; true if
same constant; false otherwise
● wffA connective wffB
• compute the truth-value of the wffs
• use connective’s truth table to determine the truth-value
of compound wff (same for ¬)
19 .Truth-value for quantifiers
❧∀x wff(x)
● successively replace x by each constant in the
interpretation
● if wff(constant) is true for every case, then
∀x(wff) is true
❧∃x wff(x)
● same as above, but wff(constant) has only to be
true once
❧assume constants list is never empty
20 .Representing change
❧On(BlockA, BlockB)
● this is either T or F
● there is no way to change this fact in “basic”
FOPC
❧Solution: “time stamp” wffs
● add one more parameter to all predicates
indicating when they are true
● On(BlockA, BlockB, S0)
● On(BlockA, BlockC, S1)
• where S0 & S1 are situations or states
21 .Changing the world
❧Acting (operator applications) changes states
(situations) into other states
❧We need a name for the new state
● Use functions!
● In particular, the function Result
• maps an action and a state to a new state
• Result(<action>, <state>) ⇒ <state>
• simply a fancy name for a state, just as FatherOf(---)
is a fancy name for some man
22 .Block-world On(A,C)
Block A
Block C
Block B
Table T On(B,T)
23 .Block-world example
❧ ∀x,y,z,s[block(x) ∧ block(y) ∧ table(z) ∧ state(s)
∧ on(x, z, s) ∧ clear(x, s) ∧ clear(y, s)] ⇒
state(Result(Stack(x, y), s)) ∧
on(x, y, Result(Stack(x, y), s)) ∧
clear(x, Result(Stack(x, y), s)) ∧
¬clear(y, Result(Stack(x, y), s)
❧ Could now almost use deductions to produce plans
(sequences of action)
24 .What’s missing?
❧What do we know about c in the new state?
❧This is a case of the frame problem:
knowing what stays the same as we move
from state to state (like frames in a movie)
❧“Blocks stay clear unless something is
placed on them during stacking”
❧∀u,x,y,s[clear(u, s) ∧ ¬(u = y) ⇒ clear(u,
Result(Stack(x, y), s))
25 . Example
❧Painting a house does not change who owns it
❧∀s,h,p[state(s) ∧ house(h) ∧ human(p) ∧
owns(p, h, s) ⇒ owns(p, h, Result(paint(h), s))]
26 .Alternate approach
❧Say properties stay the same unless a
specific action performed
❧∀u,x,s,a [block(u) ^ state(s) ^ action(a) ^
clear(u, s) ^ ¬(a = Stack(x, u)) ^ ¬(a =
CoverWithBlanket(u)) ^ ¬(a = Smash(u))
=> clear(u, Result(a, s)]
❧This usually leads to fewer rules, but it is
less modular
● when new actions defined, we have to double
check every such rule to see if it needs editing
27 .Problems with formalization
❧Qualification problem
● can we ever really write down all the
“preconditions” for a real-world action?
● E.g., starting a car
❧Ramification problem
● need to represent implicit consequences of
actions
● moving car from A to B also moves its steering
wheel, spare tire, etc.
● can be handled but becomes tedious
28 .Sources
❧Computer Science Lab
❧University of Wisconsin, Madison
热门城市
