Unit 7. Representation with Logic Nov 2, 2011 Video 7.1. Introduction AI manages complexity and uncertainty search dicovers sequences of actions to solve problems probability can represent and reason with uncertainty machine learning can be used to learn and improve pushing complexity in three directions: Agent design, from simple Reflex to Goal and Utility based agents. Environment compleity, from simple to Partial Observable, Stochastic Actions, Multiple Agents, so on. Representation, the agents model of the world becomes increasingly complex. The tools of Logic can be used by an agent to better model the world. Video 7.2. Propositional Logic Alarm problem: B E A M J burglarly, etal, each, true false unknown Alarm is True whenever Earthquake or Burglarly is true: (E V B) => A Equake is true OR Burg is true IMPLIES (THEN) Alarm is true John and Mary call when the Alarm is true: A => (J /\ M) Alarm IMPLIES John AND Mary Double arrow for EQUIVALENCE <=> John calls IF and ONLY IF Mary calls: J <=> M John is EQUAVALENT to Mary, when one is true the other is true NOT sign for Negation ~ (actually the stupid square side bracket) J <=> ~M John is EQUAVALENT to NOT Mary, when one is true the other is false A propositional sentence if true or false with respect to a model of the world. Where a model is a set of values for the propositional symbols. A model might be the set {B:true, E:false, ... } Video 7.3. Truth Tables see image: 07class_TruthTables.jpg ~P (NOT) is true when P is false and vv P /\ Q (AND) is true only when both P,Q are true P V Q (OR) is true when either or both P,Q are true (inclusive OR) P => Q (IMPLIES) is false _only_ when P is true and Q is false <--! ...always true if P is false... Quiz: O -- 5 is an odd number P -- Paris is the capital of france is O => P true or false? true because of truth table, scope doesn't matter E -- 5 is an even number M -- Moscow is the capital of france is E => M true or false? true because of truth table, both false equals TRUE P <=> Q (EQUIVALENT) is true when both true or both false ...a tautology is true when both sides are the same... See AIMA page 246 for truth tables and 249 for statement transformations... Video 7.4. Question P /\ (P => Q) -- P is true AND (P IMPLIES Q) is true only when P AND Q are true because P=>Q is false when P=true and Q=false ~( ~P V ~Q ) -- NOT ( NOT-P OR NOT-Q) only when P AND Q are true because ~P OR ~Q is false _only_ when both are true ~(~P OR ~Q ) == (P AND Q) <---!!! A <=> B (above) -- Are the two statements above equivalent ALWAYS because they are each true for same values of P,Q Video 7.5. Question These sentences are true: (E V B) => A -- E OR B IMPLIES A A => (J /\ M) -- A IMPLIES J AND M B -- B is true are these symbols true false or unknown: E -- unknown, can be either and still satisfy sentences B -- true by definition A -- true by (E OR B) where (B is true) J -- true by A M -- true by A Video 7.6. Terminology Valid sentence is true in every model or combination of symbol values Satisfiable sentence is true in some, not necessiarily all, models (Un-satisfiable is false for all models) are these sentences valid, satisfiable, or unsatisfiable P V ~P -- (OR) valid, one or the other is always true P /\ ~P -- (AND) unsatis, both can't be true P V Q V (P => Q) -- valid, true when P or Q, when both false: P=>Q is true (P => Q) V (Q => P) -- valid, => only false when predicate is true one or the other x=>y must be true ((Food=>Party) V (Drinks=>Party)) => ((Food /\ Drinks) => Party) -- ((F=>P) OR (D=>P)) => ((F AND D) => P) -- valid both sides work out to: NOT Food OR NOT Drinks OR Party so P => P -- if they are EQUIVALENT, IMPLIES holds as well ...I don't get the last one... Video 7.7. Propositional Logic Limitations Can only handle true/false. No uncertainty Can't handle objects that have properties like size or weight, nor the relations between objects No shortcuts to suscinctly talk about things happening, can't have a single sentence that specifies 1000 things that are the same. First Order logic addresses the last two. Video 7.8. First Order Logic Ontological Committment of the logic is what they say about the world. Epistomological Commitment is what type of belief's agenst can have. World Beliefs First Order relations, objects, functions true, false, unknown Propositional facts, variables true, false, unknown Probability facts, variables real numbers 0-1 Representations can be atomic -- just an individual state with no pieces inside used for search and problem solving A -> B states transition to each other but we can only say if they are the same or a goal factored -- factored into several variables, true/false for Propostional or could be multi-valued for Probability structured -- includes relationships between objects, not just variables and values individual states can include branching structure, etc programming languages are example First Order Logic is structured Video 7.9. Models In Propositional Logic the model is the values for variables First Order Logic model has sets of * objects that may have constant names which refer to them can have multiple constants refer to same object or objects with no constant names * functions that map from objects to objects e.g. for the scrabble tiles: NumberOf() maps letter to score * relations that describe relationships of objects e.g.: Above() { [A,B], [C,D] } (binary relation) Vowel() { [A] } (uniary relation) Rainy() { } (not raining) or { [ ] } raining since the "aridy" of rainy is 0 there are no objects in either set Video 7.10. Syntax Sentences describe facts that are true or false atomic sentences are predicates wheich describe relations Vowel(A) or Above(A,B) equality relation like 2 = 2 -- in every model can combine sentences with the Propositional Logic operators: AND OR NOT IMPLIES EQUIVALENT Parens Terms which describe or refer to objects contants: A, B, 2 variables: x, y (usually lower case) functions: NumberOf(A) -- another name that refers to same object as "1" in the scrabble model above Quantifiers (complex sentences that make First Order logic unique) for All (upside down A): Ax -- for all x there Exists (backwards E): Ex -- there exists an x (...if the quantifier is missing, just assume it is there...) e.g.: Ax Vowel(x) => NumberOf(x) = 1 for all x if x is a vowel then numberof x is equal to 1 Ex NumberOf(x) = 2 there exists an x such that the numberof x is equal to 2 says such an object exists but doesn't specify what it is for All A tends to go with a conditional to talk abut a sub-set of objects in the domain there Exists E is usually not conditional, just one object Video 7.11. Vacuum World Representing the world in First Order Logic see image: 04week_HW_Q4_7.jpg -- states of the world model can have: locations: A -- right, B -- left, V -- vacuum D1 -- dirt right, D2 -- dirt left relations: Loc -- true for each location Vacuum -- true for vacuum location Dirt -- true for dirt at location At(o,l) -- true for object and location can say: The vacuum is at location A: At(V,A) There is no dirt at any location (sussinct expression for all locations): Ad Al Dirt(d) /\ Loc(l) => ~At(d,l) for all dirt AND for all locations, Dirt(d) AND Loc(l) IMPLIES NOT At(d,l) The Vacuum is in a location with dirt, but location not specified El Ed Dirt(d) /\ Loc(l) /\ At(v,l) /\ At(d,l) there exists an location and dirt such that there is Dirt(d) AND Loc(l) AND At(v,l) AND At(d,l) (there is dirt and location and vacuum at location and dirt at location) For First Order Logic the relations are on Objects but not on other relations, Higher Order Logics can describe transitive relations like this: Ar Transitive(r) <=> ( Aa,b,c) R(a,b) /\ R(b,c) => R(a,c) ) for All "r", Transitive(r) is EQUIVALENT to for All "a,b,c" variables, r(a,b) AND r(b,c) IMPLIES r(a,c) Video 7.12. Question Are these sentences Valid, Satisfiable, Un-satis Ex,y x = y -- Valid, a tautology: every model has at least one object and we can have more than one identifier for the object so it must be able to be equal to itself there exists an x and a y such that x equals y (Ex x = x) => (Ay Ez y = z) -- Valid: x always equals x so left is true y can be set to z so right is true so this is always true there Exists an x such that x equals x IMPLIES that for All y there Exists a z such that y = z Ax P(x) V ~P(x) -- Valid, tautology: everything has to either in or out of relation for P() for All x P(x) OR NOT-P(x) Ex P(x) -- Satisfiable, some models have x in P and some not there Exists an x such that P(x) Video 7.13. Question Sentences in First Order Logic, correctly or incorrectly represent the English? "Sam has two jobs" Ex,y Job(Sam,x) /\ Job(Sam,y) /\ ~(x=y) -- yes there Exists x,y such that Job of Sam,x AND Job of Sam,y AND NOT-(x = y) there are x and y, both are jobs of Sam, and "crutially" they are not equal to each other Assuming I've defined the action of adding a member to a set can I define set membership with these two axioms? -- no Ax,s Member(x, Add(x,s)) for All x,s x is a member of the result of Adding x to any set s Ax,s Member(x, s) => ( Ay Member(x, Add(y,s) ) for All x,s x is a member of s IMPLIES that for ALL y x is a member of the set you get when you Add y to s NO. Does a good job of telling you what is a member: If x is a member of a set you can add other y members but doesn't tell what x is not a member of... For the notion of horizontal and vertical adjacency for squares on a checkerboard? -- no Ax,y Adj( Sq(x,y), Sq(plus(x,1), y) ) /\ Adj( Sq(x,y), Sq(x, plus(y,1)) ) for All x,y the Square x,y is Adjacent to the Square plus(x,1),y AND the Square x,y is Adjacent to the Square x,plus y,1) Does tell you that 1,1 is adj to 2,1 and 1,2 but doesn't tell the opposite 2,1 is adj to 1,1 because only goes positive, nor that 8,9 is not adjacent to 1,1 --(wha?) There is no way to prove the negative. The moral is when you are trying to make a definition what you usually want to do is have a sentence with the EQUIVALENT <=> or "bi-conditional" sign to say this is true IF and ONLY IF, rather than just have an assertion or an implication in only one direction.