DOC PREVIEW
Stanford CS 157 - Relational Logic

This preview shows page 1-2-15-16-31-32 out of 32 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Relational LogicPropositional LogicSlide 3Plan of ActionWordsConstantsArityTermsFunctional TermsSentencesRelational SentencesLogical SentencesQuantified SentencesSyntax TestReminderInfix Syntax for FunctionsInfix Syntax for RelationsOperator PrecedenceMushroomsMore MushroomsInterpersonal RelationsMore Interpersonal RelationsAbelian GroupsOpen Partial OrdersBinary TreesVariable Length ListsSpecial Cases of Relational LogicLimitations of Ground LogicLimitations of Universal LogicExistential and Universal QuantifiersNeed for Explicit QuantifiersExistential Quantifiers and FunctionsRelational LogicComputational Logic Lecture 5Michael Genesereth Autumn 20072Propositional LogicConstants refer to atomic propositions.raining snowing wetCompound sentences capture relationships among propositions.raining  snowing  wet3Relational LogicConstants refer to objects.john maryConstants refer to objects relationships.loves happy Simple sentences express relationships among objects.loves(joe,mary) Compound sentences capture properties of relations.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 PreliminariesResolutionApplicationsStrategies5WordsVariables begin with characters from the end of the alphabet (from u through z).u, v, w, x, y, zConstants begin with digits or letters from the beginning 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 each such word is determined from context.7ArityThe arity of a function constant or a relation constant is the number of arguments it takes.Unary Function constants: father1, motherBinary Function constants: plus2, times2Ternary Function constants: price3Unary Relation constants: person1, happy1Binary Relation constants: parent2, loves2Ternary Relation constants: between3The arity of a function constant or a relation constant is 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 natural language.9Functional TermsA functional term is an expression formed 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 so can be nested.plus2(age1(father1(joe)),age1(mother1(joe)))10SentencesThere are three types of sentences.Relational sentences - analogous to the simple sentences in natural languageLogical sentences - analogous to the compound sentences in natural languageQuantified sentences - sentences that express the significance of variables11Relational SentencesA 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.No! happy1(person1(joe)) No!happy1(joe)person1(joe)12Logical SentencesLogical 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 for Propositional Logic.13Quantified SentencesUniversal sentences assert facts about all objects.x.(person(x)  mammal(x))Existential sentence assert the existence of an object with given properties.x.(person(x)  happy(x))Quantified sentences can be nested within other sentences.x.apple(x)  x.pear(x))x.y.loves(x,y)14Syntax TestObject Constants: art, betty, cathyFunction Constants: father1, mother1, age1, plus2Relation Constants: person1, happy1, reflexive2, parent2, loves2loves(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)15ReminderFunctional 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.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∩ t17Infix 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↑×÷+−∩∪=≠<>≤≥∈∉⊂⊃⊆⊇¬∀ ∃∧∨⇐ ⇔ ⇒19MushroomsUnary 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 and poison.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 poison unless it is purple.If a thing is a mushroom, it is poison unless it is purple.If a thing is a mushroom, it is not poison only if it is purple.x.(mushroom(x)  poison(x)  purple(x))21Interpersonal 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


View Full Document

Stanford CS 157 - Relational Logic

Documents in this Course
Lecture 1

Lecture 1

15 pages

Equality

Equality

32 pages

Lecture 19

Lecture 19

100 pages

Epilog

Epilog

29 pages

Equality

Equality

34 pages

Load more
Download Relational Logic
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Relational Logic and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Relational Logic 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?