1Relational Logic SemanticsComputational Logic Lecture 6Michael Genesereth Autumn 201110/13/11 2Propositional Logic SemanticsA Propositional logic interpretation is an associationbetween the propositional constants in a propositionallanguage and the truth values T or F.210/13/11 3Relational Logic SemanticsThe big question: what is a relational logicinterpretation? There are no proposition constants,just object constants, function constants, and relationconstants. To what do they refer?10/13/11 4Universe of DiscourseA Universe of Discourse is a set of objects aboutwhich 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} {, , , , }310/13/11 5RelationsGiven a universe of discourse U, a relation is a set ofn-tuples of objects in U each of which manifests aparticular property or relationship.Sample Universe of Discourse: {1, 2, 3, 4}Example of a 2-ary (binary) relation:{〈1,2〉, 〈1,3〉, 〈1,4〉, 〈2,3〉, 〈2,4〉 , 〈3,4〉}132443423241312110/13/11 6ArityEach relation has an arity that determines thenumber of objects that can participate in aninstance of the relation.Arity 1 - unary relation{〈1〉, 〈3〉} or, more simply, {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〉}410/13/11 7CardinalityThe cardinality of a relation is the number oftuples 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〉}10/13/11 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?510/13/11 9FunctionsGiven a universe of discourse, an n-ary function is arelation associating each combination of n objects in auniverse of discourse (called the arguments) with asingle object (called the value).Universe of Discourse: {1, 2, 3, 4}Example:1 22 33 44 110/13/11 10Total and Single-ValuedFunctions 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.610/13/11 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〉}10/13/11 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?710/13/11 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.10/13/11 14InterpretationsAn interpretation is a mapping i that assigns“meaning” to the elements of a signature〈a1, … , ak, f1, … , fm, r1, … , rn〉 in terms of auniverse of discourse U.Object Constants:i(aj)∈UFunction Constants:i(fjn):Un →URelation Constants:i(rjn)⊆Un810/13/11 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〉}10/13/11 16Ground Value AssignmentsA ground value assignment si based oninterpretation i is a mapping from the terms of thelanguage into the universe of discourse.si must agree with i on constants; and, forfunctional terms, it yields the result of applyingthe interpretation of the function constant to thevalues assigned to the argument terms.si(σ)=i(σ) si(π(τ1,…,τn)=i(π)(si(τ1),…,si(τn))910/13/11 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) = 210/13/11 18Ground Truth AssignmentsA ground truth assignment ti based oninterpretation i is a mapping from the sentencesof the language into {true, false}.ti: sentence → {true, false}The details of the definition are given on thefollowing slides.1010/13/11 19Relational SentencesA ground truth assignment satisfies a relationalsentence if and only if the tuple of objects denotedby the arguments is a member of the relationdenoted by the relation constant. ti(ρ(τ1,…,τn)) = true if 〈siv(τ1),…, siv(τ1)〉 ∈ i(ρ) = false otherwise10/13/11 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)1110/13/11 21Logical Sentencestiv(¬ϕ) = true iff tiv(ϕ) = falsetiv(ϕ ∧ψ) = true iff tiv(ϕ) = true and tiv(ψ) = truetiv(ϕ ∨ψ) = true iff tiv(ϕ) = true or tiv(ψ) = truetiv(ϕ ⇒ψ) = true iff tiv(ϕ) = false or tiv(ψ) = truetiv(ϕ ⇐ψ) = true iff tiv(ϕ) = true or tiv(ψ) = falsetiv(ϕ ⇔ψ) = true iff tiv(ϕ) = tiv(ψ)10/13/11 22Variable AssignmentsA variable assignment for a universe of discourseU is a function assigning variables to objects in U.v: Variable → UUniverse of Discourse: U = {1, 2, 3}Example: Example: v(x) = 1 v(x) = 2 v(y) = 2 v(y) = 2 v(z) = 3 v(z) = 21210/13/11 23Value AssignmentsA value assignment siv based on interpretation iand variable assignment v is a mapping from theterms of the language into the universe ofdiscourse.siv must agree with i on constants it must agreewith v on variables; and, for functional terms, ityields the result of applying the interpretation ofthe function constant to the values assigned to theargument terms.siv(σ)=i(σ)siv(υ)=w(υ) siv(π(τ1,…,τn)=i(π)(siv(τ1),…,siv(τn))10/13/11 24Truth AssignmentsA truth assignment tiv based on interpretation iand variable
View Full Document
Unlocking...