Computational Logic Lecture 5 Relational Logic Michael Genesereth Autumn 2002 Propositional Logic Constants refer to atomic propositions raining snowing wet Compound sentences capture relationships among propositions raining snowing wet 2 Relational Logic Constants refer to objects and relationships joe mary loves happy Simple sentences express relationships among objects loves joe mary Compound sentences capture relationships among relations loves x y loves y x loves x y loves y x happy x 3 Plan of Action Relational Logic Syntax and Inf ormal Semantics Formal Semantics Herbrand Method Relational Proof s Unif ication Relational Resolution Applications Strategies Model Elimination Epilog Equality 4 Words Variables begin with characters from the end of the alphabet from u through z u v w x y z Constants begin with digits or letters from the beginning of the alphabet from a through t a b c arthur betty cathy 1 2 5 Constants Object constants refer to objects in the universe of discourse Function constants denote functions father mother age plus times Relation constants refer to relations person happy parent loves There is no syntactic distinction between object constants function constants and relation constants The type of each such word is determined from context 6 Arity The arity of a function constant or a relation constant is the number of arguments it takes Unary Function constants father1 mother Binary Function constants plus2 times2 Ternary Function constants price3 Unary Relation constants person1 happy1 Binary Relation constants parent2 loves2 Ternary Relation constants between3 The arity of a function constant or a relation constant is optionally notated as a subscript on the constant 7 Terms A term is either a variable an object constant or a functional term Terms ref er to items in the universe of discourse Terms are analogous to noun phrases in natural language 8 Functional Terms A functional term is an expression f ormed from an n ary function constant and n terms enclosed in parentheses and separated by commas father1 joe age1 joe plus2 x 2 Functional terms are terms and as such can be nested plus2 age1 father1 joe age1 mother1 joe 9 Sentences There are three types of sentences Relational sentences analogous to the simple sentences in natural language Logical sentences analogous to the compound sentences in natural language Quantified sentences sentences that express the significance of variables 10 Relational Sentences A relational sentence is an expression formed from an n ary relation constant and n terms enclosed in parentheses and separated by commas happy1 art loves2 art cathy Relational sentences are not terms and cannot be nested in terms or relational sentences happy1 person1 joe happy1 joe person1 joe 11 Logical Sentences Logical sentences in Relational Logic are analogous to those in Propositional Logic loves art cathy loves art betty loves betty art loves art betty loves art cathy loves x y loves y x loves x y loves y x loves x y loves y x Parenthesization rules are the same as f or Propositional Logic 12 Quantified Sentences Quantified sentences can be nested within other sentences x apple x x pear x x y loves x y 13 Syntax Test Object Constants art betty cathy 1 2 Function Constants father1 mother1 age1 plus2 times2 Relation Constants person1 happy1 reflexive2 parent2 loves2 lt2 lt father art mother betty plus father art betty happy person cathy loves x y loves y x reflexive z z x x 14 Reminder Functional terms and relational sentences look similar However they are not the same Functional terms may be used within other functional terms Functional terms may be used within relational sentences Relational sentences may not be used in functional terms Relational sentences may not be used in relational sentences 15 Infix Syntax for Functions 2 3 2 3 2 3 2 3 2 3 union s t intersection s t s t s t plus 2 3 minus 2 3 times 2 3 quotient 2 3 expt 2 3 16 Infix Syntax for Relations 2 3 2 3 2 3 2 3 2 3 2 3 member s t subset s t subseteq s t s t s t s t eq 2 3 nq 2 3 lt 2 3 gt 2 3 leq 2 3 geq 2 3 17 Operator Precedence 18 Mushrooms Unary relation constants mushroom purple poisonous Purple mushrooms are poisonous If a thing is a purple mushroom then it is poisonous If a thing is mushroom and it is purple then it is poisonous x mushroom x purple x poisonous x No purple mushroom is poisonous There is no thing that is a mushroom and purple and poisonous x mushroom x purple x poisonous x 19 More Mushrooms Unary relation constants mushroom purple poisonous A mushroom is poisonous only if it is purple If a thing is a mushroom it is poisonous only if it is purple If a thing is a mushroom and it is poisonous then it is purple x mushroom x poisonous x purple x A mushroom is not poisonous unless it is purple If a thing is a mushroom it is not poisonous if it is not purple If a thing is a mushroom and it is poisonous then it is purple x mushroom x poisonous x purple x 20 Interpersonal Relations Object constants mike maureen Binary relation constant loves Everybody loves Maureen x loves x maureen Maureen loves everyone who loves her x loves x maureen loves maureen x Nobody loves Mike x loves x mike Nobody who loves Maureen loves Mike x loves x maureen loves x mike 21 More Interpersonal Relations Object constants mike maureen Binary relation constant loves Everybody loves somebody x y loves x y There is somebody whom everybody loves y x loves x y 22 Abelian Groups Associativity Axiom x y z x y z Commutativity Axiom x y y x Identity Axioms Inverse Axioms 0 y y y 0 y x inv x 0 inv x x 0 23 Open Partial Orders Non reflexivity x x Asymmetry Transitivity x y y x x y y z x z 24 Binary Trees Representation as a term pair pair a b pair c d a b c d Membership axioms in x x in x pair y z in x y in x z 25 Variable Length Lists Example a b c d a b c d Representation as Term cons a cons b cons c cons d nil Language Objconst nil Funconst cons Relconst member Membership axioms member x cons x y member x cons y z member x z 26 Special Cases of Relational Logic Ground Logic no variables no functions no quantif iers Universal Logic no functions no quantif iers free variables implicitly universally quantified Existential Logic no functions Functional Logic no quantifiers 27 Limitations of Ground Logic Everybody loves somebody loves joe mary or loves joe sally or loves mary joe or loves mary bill or The sum of two natural numbers is greater than either number 1 1 1 1 2 1 1 2 2 What about facts about
View Full Document
Unlocking...