DOC PREVIEW
Stanford CS 157 - Relational Logic Semantics

This preview shows page 1-2-21-22 out of 22 pages.

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

Unformatted text preview:

1Relational Logic SemanticsComputational Logic Lecture 6Michael Genesereth Autumn 200610/19/06 2Propositional Logic SemanticsA Propositional logic interpretation is an associationbetween the propositional constants in a propositionallanguage and the truth values T or F.210/19/06 3Relational Logic SemanticsThe big question: what is a relational logicinterpretation? There are no propositional constants,just object constants, function constants, and relationconstants. To what do they refer?10/19/06 4Universe of DiscourseThe Universe of Discourse is the set of all objectsabout which we want to say something.Primitive: a quarkComposite: an engine, this classReal: Sun, MikeImaginary: a unicorn, Sherlock HolmesPhysical: Earth, Moon, SunAbstract: Justice310/19/06 5Blocks World10/19/06 6Universe of Discourse410/19/06 7RelationsA relation is a set of objects or tuples of objects each ofwhich manifest a particular property or relationship.clear - set of all blocks with no blocks on top.table - set of all blocks on the table.on - set of pairs of blocks in which first is on the second.above - all pairs in which first block is above the second.below - all pairs in which first is below the second.stack - set of triples of blocks arranged in a stack.10/19/06 8ArityEach relation has an arity that determines thenumber of objects that can participate in aninstance of the relation.1-ary (unary): clear2-ary (binary): on3-ary (ternary): stack510/19/06 9Relations as Tablesonclearstacka bb cd ea b cad10/19/06 10Set Representation of RelationsEach row in a table with n columns can berepresented as a single n-tuple. The table can berepresented as the set of such tuples.a bb cd ea b cad{〈a,b〉, 〈b,c〉, 〈d,e〉}{〈a〉, 〈d〉} or {a,d}{〈a,b,c〉}610/19/06 11CountingAssume a universe of discourse with 5 objects.Number of 2-tuples: 52=25Number of binary tables: 225Assume a universe of discourse with n objects.Number of k-tuples: nkNumber of k-ary tables: 2^nk10/19/06 12FunctionsAn n-ary function is a relation associating eachcombination of n objects in a universe of discourse(called the arguments) with a single object (called thevalue).Numerical Examples:Unary: sqrt, logBinary: +, -, *, /Symbolic Examples:Unary: mother, fatherBinary: grade710/19/06 13FunctionsFunctions are total and single-valued - one andexactly one value for each combination of arguments.Partial - not defined for some combination ofargumentsMultivalued - more than value for some argumentcombinationNB: We ignore partial and multi-valued functions.10/19/06 14Unary Functiona → bb → ac → dd → ce → e810/19/06 15Binary Functiona a → ba b → aa c → cb a → cb b → bb c → ac a → bc b → bc c → b10/19/06 16Unary Functions as Binary RelationsAn n-ary function can always be viewed as an n+1-aryrelation.a → bb → ac → dd → ce → ea bb ac dd ce e910/19/06 17Binary Functions as Ternary Relationsa a → ba b → aa c → cb a → cb b → bb c → ac a → bc b → bc c → ba a ba b aa c cb a cb b bb c ac a bc b bc c b10/19/06 18Set Representation of FunctionsA function can be represented as a set of associationsof arguments and values.Same as representation of tables except for the use ofarrows as a reminder that the table is a function.a bb ac dd ce e{〈ab〉,〈ba〉,〈cd〉,〈dc〉,〈ee〉}1010/19/06 19CountingAssume a universe of discourse with 5 objects.Number of 1-tuples: 5Number of unary functions: 55=3125Number of binary relations: 225=33554432Assume 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)10/19/06 20Role 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.1110/19/06 21Our World 10/19/06 22ConceptualizationUniverse of Discourse - a set U of objects.{, }Functional Basis Set - set {f1,…,fm} of functions on U.fi: Uk → URelational Basis Set - set {r1,…,rn} of relations on U.ri ⊆ Uk1210/19/06 23InterpretationsAn interpretation is a mapping from the constantsof a language into elements of aconceptualization 〈U,F,R〉.i: objconst → Ui: funconst → Fi: relconst → RThe arity of the function and relation constantsmust match the arity of their interpretations.10/19/06 24Example |i|=U={, } i(a) =  i(b) =  i(c) =  i(f1) = {→, →} i(q1) = {〈〉} i(r2) = {〈, 〉, 〈, 〉, 〈, 〉} i(s3) = {〈, , 〉,〈, , 〉}1310/19/06 25Ground Value AssignmentsA ground value assignment si based oninterpretation i is a mapping from the groundterms of the language into the universe ofdiscourse that agrees with i on constants and that,for functional terms, yields the result of applyingthe interpretation of the functional constant to thevalues assigned to the argument terms. si(σ) = i(σ) si(π(τ1,…,τn)) = i(π)(si(τ1),…, si(τn))10/19/06 26ExampleInterpretation: i(a) =  i(b) =  i(f ) = {→, →} i(r) = {〈, 〉, 〈, 〉}Ground Value Assignment: si(a) = i(a) =  si(f(a)) = i(f )(si(a)) = i(f )() = 1410/19/06 27Ground Truth AssignmentsA ground truth assignment ti based oninterpretation i is a mapping from the groundsentences of the language into {true, false}.ti: ground sentences → {true, false}The details of the definition are given on thefollowing slides.10/19/06 28Relational SentencesA ground truth assignment satisfies a groundrelational sentence if and only if the tuple ofobjects denoted by the arguments is a member ofthe relation denoted by the relation constant. ti(ρ(τ1,…,τn)) = true if 〈i(τ1),…, i(τ1)〉 ∈ i(ρ) = false otherwise1510/19/06 29ExampleInterpretation: i(a) =  i(b) =  i(f ) = {→, →} i(r) = {〈, 〉, 〈, 〉}Example: tiv(r(a,b)) = true since 〈, 〉 ∈ i(r) tiv(r(b,a)) = false since 〈, 〉 ∉ i(r)10/19/06 30Logical Sentencesti(¬ϕ) = true iff ti(ϕ) = falseti(ϕ ∧ψ) = true iff ti(ϕ) = true and ti(ψ) = trueti(ϕ ∨ψ) = true iff ti(ϕ) = true or ti(ψ) = trueti(ϕ ⇒ψ) = true iff ti(ϕ)


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?