DOC PREVIEW
Stanford CS 157 - Relational Logic Semantics

This preview shows page 1-2-3-20-21-40-41-42 out of 42 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 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 42 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 42 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 42 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 42 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 42 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 42 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 42 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Relational Logic SemanticsPropositional Logic SemanticsSlide 3Universe of DiscourseRelationsArityCardinalityCountingFunctionsTotal and Single-ValuedUnary Functions as Binary RelationsSlide 12Role of LogicInterpretationsExampleGround Value AssignmentsSlide 17Ground Truth AssignmentsRelational SentencesSlide 20Logical SentencesVariable AssignmentsValue AssignmentsTruth AssignmentsSlide 25Slide 26Quantified SentencesVersionsExamplesSlide 30Slide 31Slide 32ModelsClosed SentencesProperties of SentencesSlide 36StructuresSlide 38Elementary EquivalenceSlide 40Lowenheim Skolem Tarski TheoremTransitivity TheoremRelational Logic SemanticsComputational Logic Lecture 6Michael Genesereth Autumn 201001/14/19 2Propositional Logic SemanticsA Propositional logic interpretation is an association between the propositional constants in a propositional language and the truth values T or F.01/14/19 3Relational Logic SemanticsThe big question: what is a relational logic interpretation? There are no proposition constants, just object constants, function constants, and relation constants. To what do they refer?01/14/19 4Universe of DiscourseA Universe of Discourse is a set of objects about which we want to say something.Examples: {1, 2, 3, 4, …} {0, 1, -1, 2, -2, …} Set of real numbers Set of complex numbers {washington, jefferson, … , bush, obama} {, , , , }01/14/19 5RelationsGiven a universe of discourse U, a relation is a set of n-tuples of objects in U each of which manifests a particular property or relationship.Sample Universe of Discourse: {1, 2, 3, 4}Examples of Relations: {1, 3} or, more simply, {1, 3} {1,2, 1,3, 1,4, 2,3, 2,4, 3,4} {1,2,3, 1,3,4, 2,2,4}01/14/19 6ArityEach relation has an arity that determines the number of objects that can participate in an instance of the relation.Arity 1 - unary relation{1, 3}Arity 2 - binary relation{1,2, 1,3, 1,4, 2,3, 2,4, 3,4}Arity 3 - ternary relation{1,2,3, 1,3,4, 2,2,4}01/14/19 7CardinalityThe cardinality of a relation is the number of tuples in the relation.Cardinality 2{1, 3} Cardinality 6{1,2, 1,3, 1,4, 2,3, 2,4, 3,4}Cardinality 3{1,2,3, 1,3,4, 2,2,4}01/14/19 8CountingAssume a universe of discourse with 4 objects.Number of 2-tuples: 42=16Number of binary relations: 216Assume a universe of discourse with n objects.Number of k-tuples: nkNumber of k-ary relations: 2^nkQuestion: How many 0-ary relations are there?01/14/19 9FunctionsGiven a universe of discourse, an n-ary function is a relation associating each combination of n objects in a universe of discourse (called the arguments) with a single object (called the value).Universe of Discourse: {1, 2, 3, 4}Example:1 22 33 44 101/14/19 10Total and Single-ValuedFunctions are total and single-valued - one and exactly one value for each combination of arguments.Partial - not defined for some combination of argumentsMultivalued - more than value for some argument combinationNB: We ignore partial and multi-valued functions.01/14/19 11Unary Functions as Binary RelationsFunction as association:1 22 33 44 1Function as relation:{1,2, 2,3, 3,4, 4,1}Alternative Notation:{1  2, 2  3, 3  4, 4  1}01/14/19 12CountingAssume a universe of discourse with 4 objects.Number of 1-tuples: 4Number of unary functions: 44=256Number of binary relations: 216=65536Assume a universe of discourse with n objects.Number of k-tuples: nkNumber of k-ary functions: n^nk=2^(nk log n)Number of k+1-ary relations: 2^nk+1=2^(nkn)Quiz: How many 0-ary functions are there?01/14/19 13Role of LogicIncomplete Information Block a is on block b or it is on block c. Block a is not on block b.Integrity A block may not be on itself. A block may be on only one block at a time.Definitions A block is under another iff the second is on the first. A block is clear iff there is no block on it. A block is on the table iff there is no block under it.01/14/19 14InterpretationsAn interpretation is a mapping i that assigns “meaning” to the elements of a signature a1, … , ak, f1, … , fm, r1, … , rn in terms of a universe of discourse U.Object Constants:i(aj)UFunction Constants:i(fjn):Un URelation Constants:i(rjn)Un01/14/19 15Example |i|=U={1, 2, 3} i(a) = 1 i(b) = 2 i(c) = 2 i(f) = {12, 23, 33} i(p) = {1} i(q) = {1,2, 1,1, 2,2} i(r) = {1,2,1,2,2,1}01/14/19 16Ground Value AssignmentsA ground value assignment si based on interpretation i is a mapping from the terms of the language into the universe of discourse.si must agree with i on constants; and, for functional terms, it yields the result of applying the interpretation of the function constant to the values assigned to the argument terms.si()=i() si((1,…,n)=i()(si(1),…,si(n))01/14/19 17ExampleInterpretation: i(a) = 1 i(b) = 2 i(f ) = {12, 21} i(r) = {1,2, 2,2}Value Assignment: si(a) = i(a) = 1 si(f(a)) = i(f )(si(a)) = i(f )(1) = 201/14/19 18Ground Truth AssignmentsA ground truth assignment ti based on interpretation i is a mapping from the sentences of the language into {true, false}.ti: sentence  {true, false} The details of the definition are given on the following slides.01/14/19 19Relational SentencesA ground truth assignment satisfies a relational sentence if and only if the tuple of objects denoted by the arguments is a member of the relation denoted by the relation constant. ti((1,…,n)) = true if siv(1),…, siv(1)  i() = false otherwise01/14/19 20ExampleInterpretation: i(a) = 1 i(b) = 2 i(f ) = {12, 21} i(r) = {1,2, 2,2}Example: ti (r(a,b)) = true since 1,2  i(r) ti (r(b,a)) = false since 2,1  i(r)01/14/19 21Logical Sentencestiv() = true iff tiv() = falsetiv( ) = true iff tiv() = true and tiv() = true tiv( ) = true iff tiv() = true or tiv() = true tiv( ) = true iff tiv() = false or tiv() = true tiv( ) = true iff tiv() = true or tiv() = false tiv( ) = true iff tiv() = tiv()01/14/19 22Variable AssignmentsA variable assignment for a universe of


View Full Document

Stanford CS 157 - Relational Logic Semantics

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 Semantics
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 Semantics 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 Semantics 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?