1Relational LogicComputational Logic Lecture 5Michael Genesereth Autumn 20092Propositional 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 SemanticsRelational Logic SemanticsRelational ProofsProperties of Relational LogicResolution PreliminariesResolutionApplicationsStrategies35WordsConstants begin with digits or letters from thebeginning of the alphabet (from a through t).a, b, c, arthur, betty, cathy, 1, 2, ...Variables begin with characters from the end of thealphabet (from u through z).!u, v, w, x, y, z6ConstantsObject 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.8Relational LanguagesA relational signature is a set/sequence of constants.Given a relational signature and an arity function, arelational sentence is a compound expression formedfrom members of the signature in a way that respectsthe arity function. (Details to follow.)A relational language is the set of all relationalsentences that can be formed from a relationalsignature and an arity function.59TermsA 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.10Functional 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)))611SentencesThere 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 variables12Relational 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)713Logical 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.14Quantified 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)815Syntax 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)16ReminderFunctional 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.917Infix 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 ∩ t18Infix 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 ⊆ t1019Parenthesis RemovalDropping Parentheses is good:(p(x) ∧ q(x)) → p(x) ∧ q(x)But it can lead to ambiguities:((p(x) ∨ q(x)) ∧ r(x)) → p(x) ∧ q(x) ∨ r(x)(p(x) ∨ (q(x) ∧ r(x))) → p(x) ∧ q(x) ∨ r(x)20Operator Precedence↑× ÷+ −∩∪= ≠ < > ≤ ≥∈∉⊂ ⊃ ⊆ ⊇¬ ∀ ∃∧∨⇐ ⇔ ⇒1121MushroomsUnary 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))22More 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))1223Interpersonal 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
View Full Document
Unlocking...