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{〈ab〉,〈ba〉,〈cd〉,〈dc〉,〈ee〉}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