Introduction To Description Logic(s) - Unibo.it
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWIntroduction to Description Logic(s)Fedrico ChesaniFebraury 16th, 2010Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWTable of contents1Some considerations2A Description Language DL3Extending DL4Description Logics5Description Logics and SWFedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWSome considerations. . .object naturally fall into categories. . . . . and quite often into multiple categoriescategories can be more general or specific than others. . . . . this is true for simple as well for complex categoriesobjects have parts, sometimes in multiplesthe relationships among an object’s parts is essential toits being considered a member of a categoryFedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWLet’s focus on noun phrases. . . . . broadly: any syntactic element (as a clause, clitic, pronoun, orzero element) with a noun’s function (as the subject of a verb orthe object of a verb or preposition) (Merrian-Webster Dictionary)We would like to represent:individualscategory nounsrelational nounsFedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWLet’s focus on noun phrases. . .IndividualsE.g., john, david, maria, . . .Category nouns, AKA ConceptsUsed to describe basic category classes.E.g., Hunter, Teenager, . . .Relational Nouns, AKA RolesUsed to describe objects that are parts or attributes or propertiesof other objects.E.g., Child, Age, Born, . . .Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWAn ambiguity. . .In natural language many nouns can be used to refer as categoryor relations. E.g., child can be used:as a category: a person of a young ageto indicate a relation: the inverse of parentFedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWWhat else do we desire?Again, we are really interested in the generalization relation. . .we would like to define some generalization relation byourselves. . . . . but we would like also to automatically infer generalizationhierarchies as a consequence of the description we have madeof concepts.we would like to represent complex concepts as the results ofsome ” composition” of simpler conceptswe would like to know if an individual belongs to somecategory or notDescription Logic is a (family of) logic that focus on thedescription of the terms.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWDL vs. FOLFOL focuses on sentencesFOL does not help you on reasoning on complex categories.ExampleWe can say that X is a hunter by a 1-ary predicate Hunter (X );similarly, we can say Gatherer (X ). What if we want to say that Xis both a hunter and a gatherer?We could ad an axiom:Hunter &Gatherer (X ) Hunter (X ) Gatherer (X ).But we should do this for every concept for every possible relationamong them that we want to capture. . .Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWDL vs. FramesIn Frames the generalization relation is all user defined!Roles can have multiple fillers, while slots can’t (at least inbasic Frames systems)Frames provide a procedural solution to the creation andinstantiation of individualsFedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentA simple logic: DLTwo different sets of symbols: logical symbols (with a fixedmeaning) and non-logical symbols (domain-dependent).Logical symbolspunctuation: (,), [, ]positive integersconcept-forming operators: ALL, EXISTS, FILLS, AND.connectives: v, , Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentA simple logic: DLTwo different sets of symbols: logical symbols (with a fixedmeaning) and non-logical symbols (domain-dependent).Non-Logical symbolsAtomic concepts: Person, FatherOfOnlyGirls (camel casing,first letter capital, same as OOP)Roles: :Height, :Age, :FatherOf (same as concepts, butprecede by columns)constants: john, federicoChesani (camel casing, but startingwith uncapitalized letter.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentA simple logic: DLWhat about (complex) concepts?every atomic concept is a concept;if r is a role and d is a concept, then [ALL r d] is a concept;if r is a role and n is a positive integer, then [EXISTS n r] is aconcept;if r is a role and c is a constant, then [FILLS r c] is a concept;if d1 . . . dn are concepts, then [AND d1 . . . dn ] is a concept.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentA simple logic: DLWhat about sentences?if d1 and d2 are concepts, then (d1 v d2 ) is a sentence;.if d1 and d2 are concepts, then (d1 d2 ) is a sentence;if c is a constant and d is a concept, then (c d) is asentence;A KB in a description logic like DL is considered to be anycollection of sentences of this form.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentA simple logic: DLA KB in a description logic like DL is considered to be anycollection of sentences of this form.constants stand for individuals in some application domain;concepts stand for classes or categories of individuals;roles stand for binary relation over those individuals.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentA simple logic: DLIn many research area there is a distinction between:A-Box, Assertion Box: a list of facts about individualsT-Box, Terminological box: a list of sentences (also calledaxioms) that describes the concepts.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming ng operators [EXISTS n r]A desired feature in a description logic is to define complexconcepts in terms of more simpler ones. This is achieved by meansof the so-called concept-forming operators.[EXISTS n r]Stands for the class of individuals in the domain that are related byrelation r to at least n other individuals.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming ng operators [EXISTS n r][EXISTS n r]Stands for the class of individuals in the domain that are related byrelation r to at least n other individuals.[EXISTS 1 :Child] All the individuals (the class of the individuals)that have at least one child;[EXISTS 2 :HasCar] All the individuals that have at least two cars[EXISTS 6 :HasWheels] All the individuals that have at least sixwheels (individual? mind the term!)Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming ng operators [FILLS r c][FILLS r c]Stands for those individuals that are related r -related to theindividual identified by c.[FILLS :Child francescoChesani] All the individuals that have haschild Francesco Chesani;[FILLS :HasCar aa123bb] All the individuals that have the car withplate aa123bb;[FILLS :AreAttendingTheCourse thisCourse] All the individualsthat are attending this course.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming ng operators [ALL r d][ALL r d]Stands for those individuals that are r -related only to individuals ofclass d.[ALL :BeingInThisRoom PHDStudents] All the individuals that arein this room and are students;[ALL :HasChild Male] All the individuals that have zero or morechildren, but all males;[ALL :HaveStudents Male] All the individuals that have only malestudents (o no students at all). In this case with term individualswe could intend universities, schools, courses.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming ng operators [AND d1 . . . dn ][AND d1 . . . dn ]Stands for anything that is described by d1 and . . . dn .[ANDCompany[EXISTS 7 :Director][ALL :Manager [AND Woman [FILLS :Degree phD]]][FILLS :MinSalary 24.00/hour]]Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming ences are expression that are intended to be true or false inthe domain.d1 v d2Concept d1 is subsumed by concept d2 , i.e. every individual thatsatisfies d1 satisfies also d2Example: PhDStudent v StudentEvery phd student is also a student (but not vice-versa).Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentSentences.d1 d2Concept d1 is equivalent to concept d2 , i.e. the individuals thatsatisfy d1 are precisely those that satisfy d2.Example: PhDStudent [AND Student Graduated HasFunding ]A phd student is a student that already graduated, and that hassome funding.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentSentencesc dThe individual denoted by c satisfies the description expressed byconcept d.Example: federico PostDocFederico is a Post Doc.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming nsAn Interpretation is a pair (D, I) where:D is any set of objects, called domain;I is a mapping called the interpretation mapping, from thenon-logical symbols of DL to elements and relations over D:123for every constant c, I[c] D;for every atomic concept a, I[a] D;for every role r , I[r ] D D.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming nsWhat is the interpretation of complex concepts?for the distinguished concept Thing, I[Thing ] D;I[[ALL r d]] {x D for any y, if hx, y i I[r ], theny I[d]};I[[EXISTS n r ]] {x D there are at least n distinct ysuch that hx, y i I[r ]};I[[FILLS r c]] {x D hx, I[c]i I[r ]]};T TI[[AND d1 . . . dn ]] I[d1 ] . . . I[dn ]Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming ns and sentences: the basic notion ofEntailmentGiven an interpretation, when a sentence is true?Given an interpretation (D, I), a sentence α is true ( α),according to the following:123 (c d) iff I[c] I[d]; (d v d 0 ) iff I[d] I[d 0 ];. (d d 0 ) iff I[d] I[d 0 ];There are very good algorithms that compute entailments.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentWhich type of reasoning?In description logic the are two fundamental questions that wewould like to get an automatic answer to. Given a knowledge baseexpressed as a set S of sentences:1does a constant c satisfies concept d?2is a concept d subsumed by a concept d 0 ?Answering to these questions amount to compute the entailment.We would like to answer these questions independently by thespecific domain or interpretation. . .Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentEntailmentA set S logically entails a sentence α (S α), if and only if forevery interpretation , if S then α.1S (c d)?2S (d v d 0 )?Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentClosed- vs. open-world semanticsDifferently by many other formalisms, Description Logics are basedon an Open World Assumption.If a sentence cannot be inferred, then its truthness value isunknown.This means that it is not possible to state that “something doesn’texist until it is explicitly stated that it does not exist”.Note: somehow this characteristics is linked to the idea ofdistributed information in the Web.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentClosed- vs. open-world semanticsOWA Example.(HasOnlyMaleChildren [AND[EXISTS 1 :HasChild][ALL :HasChild Male]]).(federico [[:HasChild francesco]])(francesco Male)Can we infere that federico is an instance of the classHasOnlyMaleChildren ?Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWA simple logic: DLConcept-forming operatorsSentencesSemanticsEntailmentClosed- vs. open-world semanticsOWA Example.(HasOnlyMaleChildren [AND[EXISTS 1 :HasChild][ALL :HasChild Male]]).(federico [[:HasChild francesco]])(francesco Male)We do not know how many children has federico. . . it might bethat federico has also a daughter.The fact is that the knowledege base could be incomplete!!!Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWAdding concept-forming operatorsExtending rolesAdding rulesExtending DLIt is possible to extend the presented description logic in severaldirections:by adding concept-forming operators;by relating roles, and considering also complex roles;by adding rules.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWAdding concept-forming operatorsExtending rolesAdding rulesBounds on the number of roles fillersWe have already the operator EXISTS. We could similarly add theoperator AT-MOST, where [AT-MOST n r ] describes individualsrelated by role r to at most n individuals.Example[AT-MOST 1 :Child] denotes all the parents that have only onechild.This extension could be dangerous. . .What is the meaning of the following concept:[AND [EXISTS 4 r ] [AT-MOST 3 r ]]How do we treat such situation?Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWAdding concept-forming operatorsExtending rolesAdding rulesSets of individualsIt would be nice to specify that a role can be filled only byindividuals belonging to a certain set (without recurring to aconcept). We could add the operator ONE-OF, where [ONE-OFc1 c2 . . . cn ] is a concept satisifed only by ci , used in conjunctionwith ALL would lead to a restriction on the individuals that couldfill a certain role.Example.(Beatles [ALL :BandMember [ONE-OF john paul george ringo]])Implicitly this means that. . . . . there is an AT-MOST restriction limited to 4 on the role:BandMember.Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWAdding concept-forming operatorsExtending rolesAdding rulesQualified Number RestrictionsWhat if we want to describe, e.g., those parents that have at least2 male children?We can add the operator [EXISTS n r d], meaning all theindividuals that are r -related to at least n individuals that areinstances of concept d.Example[EXISTS 2 :Child Male]Unfortunately, this simple extension increase the computationalcomplexity of entailment (subsumption) . . .Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWAdding concept-forming operatorsExtending rolesAdding rulesOther Logic operatorsWe have completely forgot standard usual operators such as:OR: what if we want to describe all the young and the elderpeople, but not the adults? : what if we want to describe all the people that is notinstance of a concept d?What happens to the computational costs?What happen to the decidability?Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWAdding concept-forming operatorsExtending rolesAdding rulesRelating the RolesWhat if we want to relate the fillers of certain roles? Suppose youwant to say that in a small company the CEO and the owner mustbe the same individual. . .We can add the operator [SAME-AS r1 r2 ], which equates fillersof roles r1 and r2 .Example[SAME-AS :CEO :Owner]Unfortunately, also this simple extension increase thecomputational complexity of entailment, and if allowed with rolechains, can lead to undecidability . . .Fedrico ChesaniIntroduction to Description Logic(s)
Some considerationsA Description Language DLExtending DLDescription LogicsDescription Logics and SWAdding concept-forming operatorsExtending rolesAdding rulesComplex RolesUntil now we treated roles ad primitive concepts. . . what if, forexample, we want to consider a role defined as the conjunction ofmore roles?And, more interesting, what if we want to add ideas like theinverse of a role? Saying for example that :Parent is the inverse of:Child? In
Fedrico Chesani Introduction to Description Logic(s) Some considerations A Description Language DL Extending DL Description Logics Description Logics and SW A simple logic: DL Concept-forming operators Sentences Semantics Entailment Sentences d 1: d 2 Concept d 1 is equivalent to concept d 2, i.e. the individuals that satisfy d 1 are precisely those that satisfy d 2 Example: PhDStudent .
Dynamic Logic Dynamic Circuits will be introduced and their performance in terms of power, area, delay, energy and AT2 will be reviewed. We will review the following logic families: Domino logic P-E logic NORA logic 2-phase logic Multiple O/P domino logic Cascode logic
An Introduction to Description Logic IV Relations to rst order logic Marco Cerami Palack y University in Olomouc Department of Computer Science Olomouc, Czech Republic Olomouc, November 6th 2014 Marco Cerami (UP) Description Logic IV 6.11.2014 1 / 25. Preliminaries Preliminaries: First order logic Marco Cerami (UP) Description Logic IV 6.11.2014 2 / 25. Preliminaries Syntax Syntax: signature .
Digital Logic Fundamentals Unit 1 – Introduction to the Circuit Board 2 LOGIC STATES The output logic state (level) of a gate depends on the logic state of the input(s). There are two logic states: logic 1, or high, and logic 0, or low. The output of some gates can also be in a high-Z (high impedance) state, which is neither a high
MOSFET Logic Revised: March 22, 2020 ECE2274 Pre-Lab for MOSFET logic LTspice NAND Logic Gate, NOR Logic Gate, and CMOS Inverter Include CRN # and schematics. 1. NMOS NMOSNAND Logic Gate Use Vdd 10Vdc. For the NMOS NAND LOGIC GATE shown below, use the 2N7000 MOSFET LTspice model that has a gate to source voltage Vgs threshold of 2V (Vto 2.0).File Size: 586KB
categorical and hypothetical syllogism, and modal and inductive logic. It is also associated with the Stoics and their propositional logic, and their work on implication. Syllogistic logic and propositional logic led later to the development of predicate logic (or first order logic, i.e. the foundational logic for mathematics)
An Introduction to Modal Logic 2009 Formosan Summer School on Logic, Language, and Computation 29 June-10 July, 2009 ; 9 9 B . : The Agenda Introduction Basic Modal Logic Normal Systems of Modal Logic Meta-theorems of Normal Systems Variants of Modal Logic Conclusion ; 9 9 B . ; Introduction Let me tell you the story ; 9 9 B . Introduction Historical overview .
The University of Texas at Arlington Sequential Logic - Intro CSE 2340/2140 – Introduction to Digital Logic Dr. Gergely Záruba The Sequential Circuit Model x 1 Combinational z1 x n zm (a) y y Y Y Combinational logic logic x1 z1 x n z m Combinational logic with n inputs and m switching functions: Sequential logic with n inputs, m outputs, r .
2.2 Fuzzy Logic Fuzzy Logic is a form of multi-valued logic derived from fuzzy set theory to deal with reasoning that is approximate rather than precise. Fuzzy logic is not a vague logic system, but a system of logic for dealing with vague concepts. As in fuzzy set theory the set membership values can range (inclusively) between 0 and 1, in
