005-first order predicate calculus

This chapter is mainly about first order predicate calculus, which mainly includes propositional logic,predicate calculus,terms,sentences,making sentences,quantifiers,equality,backus-naur form,well formed formulas,location of quantifiers and so on.


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