1Relational LogicComputational Logic Lecture 5Michael Genesereth Autumn 20082Propositional LogicProposition constants refer to atomic propositions.raining snowing wetCompound sentences capture relationships amongpropositions.raining ∨ snowing ⇒ wet23Relational LogicObject constants refer to objects.john maryRelation constants refer to relationships.loves happySentences express information about objects and theirrelationships.loves(joe,mary)loves(x,y) ⇒ loves(y,x) loves(x,y) ∧ loves(y,x) ⇒ happy(x)4Plan of ActionRelational Logic Syntax and Informal SemanticsFormal SemanticsHerbrand MethodRelational ProofsResolution PreliminariesResolutionApplicationsStrategies35WordsVariables begin with characters from the end of thealphabet (from u through z).!u, v, w, x, y, zConstants begin with digits or letters from thebeginning of the alphabet (from a through t).a, b, c, arthur, betty, cathy, 1, 2, ...6ConstantsObject constants refer to objects.joe, stanford, usa, 2345Function constants denote functions.father, mother, age, plus, timesRelation constants refer to relations.person, happy, parent, lovesThere is no syntactic distinction between object,function, and relation constants. The type of eachsuch word is determined from context.47ArityThe arity of a function constant or a relation constantis the number of arguments it takes.Unary Function constants: father, motherBinary Function constants: plus, timesTernary Function constants: priceUnary Relation constants: person, happyBinary Relation constants: parent, lovesTernary Relation constants: betweenThe arity of a function constant or a relation constantis optionally notated as a subscript on the constant.8TermsA term is either a variable, an object constant, ora functional term.Terms refer to items in the universe of discourse.Terms are analogous to noun phrases in naturallanguage.59Functional TermsA functional term is an expression formed froman n-ary function constant and n terms enclosedin parentheses and separated by commas.father(joe)age(joe)plus(x,2)Functional terms are terms and so can be nested.plus(age(father(joe)),age(mother(joe)))10SentencesThere are three types of sentences.Relational sentences - analogous to the simplesentences in natural languageLogical sentences - analogous to the compoundsentences in natural languageQuantified sentences - sentences that express thesignificance of variables611Relational SentencesA relational sentence is an expression formed froman n-ary relation constant and n terms enclosed inparentheses and separated by commas.happy(art)loves(art,cathy)Relational sentences are not terms and cannot benested in terms or relational sentences.!No! happy(person(joe)) No!happy(joe)person(joe)12Logical SentencesLogical sentences in Relational Logic are analogousto 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 forPropositional Logic.713Quantified SentencesUniversal sentences assert facts about all objects.∀x.(person(x) ⇒ mammal(x))Existential sentence assert the existence of an objectwith given properties.∃x.(person(x) ∧ happy(x))Quantified sentences can be nested within othersentences.∀x.apple(x) ∨ ∃x.pear(x))∀x.∃y.loves(x,y)14Syntax TestObject Constants: art, betty, cathyUnary Function Constants: father, mother, ageBinary Function Constant: plusUnary Relation Constants: person, happyBinary Relation Constants: reflexive, parent, lovesloves(father(art),mother(art))plus(father(art),betty)happy(person(cathy))∀x.∀y.(loves(x,y) ⇒ loves(y,x))loves(x,y) ⇒ loves(y,x)∀x.∀y.loves(art,cathy)∀z.∀x.reflexive(z) ⇒ z(x,x)815ReminderFunctional terms and relational sentences looksimilar. However, they are not the same.Functional terms may be used within otherfunctional terms. Functional terms may be usedwithin relational sentences.Relational sentences may not be used in functionalterms. Relational sentences may not be used inrelational sentences.16Infix Syntax for Functionsplus(2, 3) ↔ 2 + 3minus(2, 3) ↔ 2 − 3times(2, 3) ↔ 2 × 3quotient(2, 3) ↔ 2 ÷ 3expt(2, 3) ↔ 2 ↑ 3union(s,t) ↔ s ∪ tintersection(s,t) ↔ s ∩ t917Infix Syntax for Relationseq(2, 3) ↔ 2 = 3nq(2, 3) ↔ 2 ≠ 3lt(2, 3) ↔ 2 < 3gt (2, 3) ↔ 2 > 3leq(2, 3) ↔ 2 ≤ 3geq(2, 3) ↔ 2 ≥ 3member(s,t) ↔ s ∈tsubset(s,t) ↔ s ⊂ tsubseteq(s,t) ↔ s ⊆ t18Operator Precedence↑× ÷+ −∩∪= ≠ < > ≤ ≥∈∉⊂ ⊃ ⊆ ⊇¬ ∀ ∃∧∨⇐ ⇔ ⇒1019MushroomsUnary relation constants: mushroom, purple, poisonPurple mushrooms are poison.If a thing is a purple mushroom, then it is poison.If a thing is mushroom and it is purple, then it is poison.∀x.(mushroom(x) ∧ purple(x) ⇒ poison(x))No purple mushroom is poison.There is nothing that is a mushroom and purple andpoison.¬∃x.(mushroom(x) ∧ purple(x) ∧ poisonous(x))20More MushroomsUnary relation constants: mushroom, purple, poisonA mushroom is poison only if it is purple.If a thing is a mushroom, it is poison only if it is purple.If a thing is a mushroom and it is poison, then it is purple.∀x.(mushroom(x) ∧ poison(x) ⇒ purple(x))A mushroom is not poison unless it is purple.If a thing is a mushroom, it is not poison unless it is purple.If a thing is a mushroom and it is not purple, then it is notpoison.∀x.(mushroom(x) ∧ ¬purple(x) ⇒ ¬poison(x))1121Interpersonal RelationsObject constants: mike, maureenBinary relation constant: lovesEverybody 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))22More Interpersonal RelationsObject constants: mike, maureenBinary relation constant: lovesEverybody loves somebody.∀x.∃y.loves(x,y)There is somebody whom everybody loves.∃y.∀x.loves(x,y)1223Abelian GroupsAssociativity AxiomCommutativity AxiomIdentity AxiomsInverse Axioms(x + y) + z = x + (y + z)x + y = y + x0 + y = yy + 0 = yx + inv(x) = 0inv(x) + x = 024Open Partial OrdersNon-reflexivity¬x<xAsymmetryx<y ⇒ ¬y<xTransitivityx<y ∧ y<z ⇒ x<z1325Binary Trees!Representation as a term:pair(pair(a,b), pair(c,d))Membership axioms:in(x,x)in(x,pair(y,z)) ⇐ in(x,y) ∨ in(x,z)a b c
View Full Document
Unlocking...