Relational Logic SemanticsComputational LogicLecture 6Michael Genesereth Autumn 20022Propositional Logic SemanticsA Propositional logic interpretation is an association betweenthe propositional constants in a propositional language and thetruth values T or F.3Relational Logic SemanticsThe big question: what is a relational logic interpretation?There are no propositional constants, just object constants,function constants, and relation constants. To what do theyrefer?4OutlineModeling the WorldObjects, Functions, RelationsDataModelsSemantics of Relational LogicAtomic SentencesLogical SentencesQuantified SentencesGeneral RemarksOntological PromiscuityRole of Logic5ObjectsAn object is an entity presumed or hypothesized to exist in theworld we are discussing.Primitive: a quarkComposite: an engine, this classReal: Sun, MikeImaginary: a unicorn, Sherlock HolmesPhysical: Earth, Moon, SunAbstract: Justice6Blocks World7Universe of Discourse8Different UniversesBlocks:Stacks:Fragments:9RelationsAn n-ary relation is a property that holds of variouscombinations of n objects.clear - true of a block iff it has no blocks above it.table - true of a block iff it is resting on the table.on - true of 2 blocks iff one is immediately on the other.above - true of 2 blocks iff one is anywhere above the other.below - true of 2 blocks iff one is anywhere below the other.stack - true of 3 blocks iff they form a stack of 3 blocks.10FunctionsAn n-ary function is a relation associating each combination ofn objects in a universe of discourse (called the arguments) witha single object (called the value).Numerical Examples:Unary: sqrt, logBinary: +, -, *, /People Examples:Unary: mother, father11FunctionsFunctions are total and single-valued - one and exactly onevalue for each combination of arguments.Partial - not defined for some combination of argumentsMultivalued - more than one value for some argumentcombinationNB: We ignore partial and multi-valued functions.12Ingredients for a ModelUniverse of Discourse - a set of object constants, one for eachobject under discussion.Functional Basis Set - a set of function constants, one for eachfunction under discussion.Relational Basis Set - a set of relation constants, one for eachrelation under discussion.Note that, in some cases, we need more object constants thanwe can form from 26 letters and 10 digits. We can solve thisproblem by extending our alphabet. However, this won’t benecessary in this course.13DataA datum is a ground, atomic sentence in which all argumentsare object constants.on(a,b)Intuitively, a datum is true if and only if the relation holds of thearguments. It can also be viewed as an instance of a relation.14ModelsA model is an arbitrary set of data.Intuitively, a model is the set of all data that are true in theworld being considered. If a datum is not included in a model, itis assumed to be false in that model.{clear(a),clear(d),table(c),table(d),on(a,b),on(b,c),on(d,e),stack(a,b,c)}15OutlineModeling the WorldObjects, Functions, RelationsDataModelsSemantics of Relational LogicAtomic SentencesLogical SentencesQuantified SentencesGeneral RemarksOntological PromiscuityRole of Logic16Atomic SentencesA ground atomic sentence ϕ is true in a model Γ (written=Γ ϕ ) if and only if ϕ is a member of Γ.Model:True: Not True: clear(a) clear(b) clear(d) clear(c) clear(e){clear(a),clear(d),table(c),table(d),on(a,b),on(b,c),on(d,e),stack(a,b,c)}17Logical SentencesA negation is true if and only if its target is false.A conjunction is true if and only if every conjunct is true.A disjunction is true if and only if some disjunct is true.An implication is true if and only if the antecedent is falseor the consequent is true.A reduction is true if and only if the antecedent is false orthe consequent is true.An equivalence is true if and only if the arguments areeither both false or both true.18InstancesAn instance of a sentence relative to a model is a sentenceobtained by consistently substituting an object constantfrom the model’s universe of discourse for each freevariable in the sentence.p(x,y) ∧ q(x,b,z) → p(a,a) ∧ q(a,b,b)Note that we do not substitute for bound variables (untillater).∃y.∀z.p(x,y,z) → ∃y.∀z.p(a,y,z)19Quantified SentencesA universally quantified sentence is true if and only ifevery instance of the scope is true. An existentiallyquantified sentence is true if and only if some instance ofthe scope is true.Model:True: Not True: ∀x.(on(x,y) ⇒¬on(y,x)) ∀x.on(x,y) ∃x.clear(x) ∃x.(table(x) ∧ clear(x)){clear(a),clear(d),table(c),table(d),on(a,b),on(b,c),on(d,e),stack(a,b,c)}20Open SentencesThe preceding definitions apply to closed sentences, i.e. thosewith no free variables.An open sentence is true in a model if and only if it satisfiesevery instance of the sentence relative to the model.True: Not True: on(x,y) ⇒¬on(y,x) on(x,y)This just formalizes the notion that free variables areuniversally quantified.21Functions and ModelsA functional relation can be notated the same as any otherrelation.{boss(art,art),boss(joe,art)}However, to make explicit the functional character offunctional relations, we often write as equations.{boss(art)=art,boss(joe)=art}22Instances AgainAn instance of a sentence relative to a model is a sentenceobtained by (1) consistently substituting an objectconstant from the model for each free variable in thesentence (2) replacing all ground functional terms by theirvalues in the model.Model:{boss(art)=art,boss(joe)=art}Example:p(x,boss(x)) → p(joe,boss(joe)) → p(joe,art)23NoteThe definition of semantics given here is not the same as thatgiven in the notes or in standard logic textbooks.However, it is equivalent to these other definitions in terms ofits results.Moreover, it is significantly simpler than these otherdefinitions and is more intuitive for people interested inbuilding computer systems.24DefinitionsA sentence is valid if and only if every model satisfies it. Asentence is unsatisfiable if and only if no model satisfies it. Asentence is contingent if and only there is some model thatmakes it true and some model that makes it false.A set of premises ∆ logically entails a conclusion ϕ (written∆= ϕ) if and only if every model that satisfies the premisesalso satisfies the conclusion (i.e.=Γ ∆ implies=Γ ϕ, for all Γ).25OutlineModeling the WorldObjects, Functions, RelationsDataModelsSemantics of Relational LogicAtomic SentencesLogical
View Full Document
Unlocking...