First-Order LogicProblem of Propositional LogicFirst-order logicRelationsModels for FOL: ExampleFOL SyntaxTermsAtomic SentencesComplex SentencesQuantificationQuantifierNested QuantifiersDe Morgan’s Law for QuantifiersCommon mistakes to avoidUsing FOLExamplesSlide 17Knowledge base for the wumpus worldKB For Wumpus WorldDeducing hidden propertiesSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27SummaryFirst-Order LogicChapter 8Problem of Propositional Logic Propositional logic has very limited expressive power–E.g., cannot say "pits cause breezes in adjacent squares“ except by writing one sentence for each square.–We want to be able to say this in one single sentence:“for all squares and pits, pits cause breezes in adjacent squares.–First order logic will provide this flexibility.First-order logic•Propositional logic assumes the world contains facts that are true or false.•First-order logic assumes the world contains–Objects: people, houses, numbers, colors, baseball games, wars, …–Relations between objects: red, round, prime, brother of, bigger than, part of, comes between, …Relations•Some relations are properties: they state some fact about a single object: Round(ball), Prime(7).•n-ary relations state facts about two or more objects: Married(John,Mary), Largerthan(3,2).•Some relations are functions: their value is another object: Plus(2,3), Father(Dan).Models for FOL: ExampleFOL Syntax•Constant symbols objects•Predicate Symbols Relations•Function Symbols Functions•Each symbol needs an interpretation: “Richard” refers to the person Richard. “Brother” refers to the brother relation. “LeftLeg” refers to the mapping objectleftleg.Terms•Terms are logical expressions that refer to an object.•There are 2 kinds of those:–constant symbols: Table, Computer–function symbols: LeftLeg(Pete), Plus(2,3).Atomic Sentences•Sentences in logic state facts that are true or false. •Properties and n-ary relations do just that: LargerThan(2,3) (means 2>3) is false. Brother(Mary,Pete) is false.•Note: Functions do not state facts and form no sentence: Brother(Pete) refers to John (his brother) and is neither true nor false.•Brother(Pete,Brother(Pete)) is True. Binary relationFunctionComplex Sentences•We make complex sentences with connectives (just like in proposition logic).( ( ), ) ( ( ))Brother Lef tLeg Richard J ohn Democrat Bush� �binary relationfunctionpropertyobjectsconnectivesQuantification•Round(ball) is true or false because we give it a single argument (ball).•We can be much more flexible if we allow variables which can take on values in a domain. e.g. reals x, all persons P, etc.•To construct logical sentences we need a quantifier to make it true or false.Quantifier•Is the following true or false?•To make it true or false we use 5,x x R> �and" $2[( 2) ( 3)] ( )[( 1)] ( )x x x x R f alsex x x R f alse" > � > �$ =- �For all real x, x>2 implies x>3.There exists some real x which square is minus 1.Nested Quantifiers•Combinations of universal and existential quantification are possible: ( , ) ( , )( , ) ( , )( , ) ( , )( , ) ( , ), { }x y Father x y y x Father x yx y Father x y y x Father x yx y Father x y y x Father x yx y Father x y y x Father x yx y All people" " �" "$ $ �$ $" $ �$ "$ " �" $�Quiz :which is which: Everyone is the father of someone. Everyone has everyone as a father There is a person who has everyone as a father. There is a person who has a father There is a person who is the father of everyone. Everyone has a father. Binary relation:“x is a father of y”.De Morgan’s Law for Quantifiers( )( )( )( )x P x Px P x Px P x Px P x P" ��$ �$ ��" ��" �$ ��$ �" �( )( )( )( )P Q P QP Q P QP Q P QP Q P Q����ٺ����ں���ٺ����ں�De Morgan’s RuleGeneralized De Morgan’s RuleRule is simple: if you bring a negation inside a disjunction or a conjunction,always switch between them (or and, and or).• Equality symbol: Father(John)=Henry. This relates two objects.Common mistakes to avoid• is the main connective with • is the main connective with , ( ) ( ) { , , }, ( ) ( ), ( ) ( ), ( ) ( )x King x Person x x Pete Mary tablespoonx King x Person xx King x Person xx King x Person x" � =" �$ �$ ��$All of these must be true!King(Pete) AND Person(Pete)King(Mary) AND Person(Mary)King(Tablespoon) AND Person(Tablespoon)One of these should be true!if King(Pete) then Person(Pete)if King(Mary) then Person(Mary)If King(Tablespoon) then Person(Tablespoon)too strongtoo weakUsing FOL•We want to TELL things to the KB, e.g. TELL(KB, )•We also want to ASK things to the KB, ASK(KB, ) •The KB should return the list of x’s for which Person(x) is true: {x/John,x/Richard,...}, ( ) ( )x King x Person x" �, ( )x Person x$ExamplesThe kinship domain:•Brothers are siblingsx,y Brother(x,y) => Sibling(x,y)•One's mother is one's female parentm,c Mother(c) = m (Female(m) Parent(m,c))•“Sibling” is symmetricx,y Sibling(x,y) Sibling(y,x)Some may be considered axioms, others as theorems which can be derived from the axioms.Using FOLThe set domain: s Set(s) (s = {} ) (x,s2 Set(s2) s = {x|s2})x,s {x|s} = {}x,s x s s = {x|s}x,s x s [ y,s2} (s = {y|s2} (x = y x s2))]s1,s2 s1 s2 (x x s1 x s2)s1,s2 (s1 = s2) (s1 s2 s2 s1)x,s1,s2 x (s1 s2) (x s1 x s2)x,s1,s2 x (s1 s2) (x s1 x s2)This constitutes a possible set of axioms for set theoryKnowledge base for the wumpus world•Perceptiont,s,b Percept([s,b,Glitter],t) Glitter(t)•Reflext Glitter(t) BestAction(Grab,t)object (percept)property of time tKB For Wumpus World•Suppose a wumpus-world agent is using an FOL KB and perceives a smell and a breeze (but no glitter) at t=5:Tell(KB,Percept([Smell,Breeze,None],5))Ask(KB,a BestAction(a,5))•I.e., does the KB entail some best action at t=5?•Answer: Yes, {a/Shoot} ← substitution (binding list)relation: smell, breeze, no glitter and t=5 is trueDeducing hidden propertiesx,y,a,b Adjacent([x,y],[a,b]) [a,b] {[x+1,y], [x-1,y],[x,y+1],[x,y-1]} Properties of squares:s,t At(Agent,s,t) Breeze(t) Breezy(s)Squares are
View Full Document
Unlocking...