Introduction, Description Logics

3y ago
82 Views
2 Downloads
2.08 MB
135 Pages
Last View : 2d ago
Last Download : 2m ago
Upload by : Macey Ridenour
Transcription

Introduction, Description LogicsPetr Křemenpetr.kremen@fel.cvut.czOctober 5, 2015Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20151 / 118

Our plan1Course Information2Towards Description Logics3Logics4Semantic Networks and Frames5Towards Description Logics6ALC LanguagePetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20152 / 118

Course InformationPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20153 / 118

Course Informationweb 3rzn/startPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20154 / 118

Course Informationweb 3rzn/startthree basic topics: description logics, fuzzy (description) logic,probabilistic modelsPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20154 / 118

Course Informationweb 3rzn/startthree basic topics: description logics, fuzzy (description) logic,probabilistic modelsPlease go through the course web page carefully !!!Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20154 / 118

Technical RoadmapPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20155 / 118

Technical Roadmap (2)Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20156 / 118

Technical Roadmap (3)Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20157 / 118

Towards Description LogicsPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20158 / 118

Semiotic Trianglerefers to modeled by ontologies; you can learn in AE0M33OSWcoursePetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20159 / 118

Semiotic Trianglerefers to modeled by ontologies; you can learn in AE0M33OSWcourserepresents studied by formal knowledge representation languages –this coursePetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 20159 / 118

OntologiesOntologiesin IT are formal informational artifacts explicitely representing sharedconceptualization.basic idea we need to model (and reason) on concepts (i.e.“meanings”) not terms (i.e. “symbols”, “words”, “phrases”). Weneed to know, what our mean.compare words Man vs. Person.but we need to use words to model the concepts .Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201510 / 118

Ontologies (2)Principle of application. A concept satisfies the principle of application ifwe are able to decide, whether an “object” belongs to theconcept or not. E.g. nice vs. red vs. woman.Principle of identity. Each concept is equipped with a principle of identitysaying, what must be fulfilled for an object to belong to theconcept. E.g. an artificial key, birth number vs. particularhuman brainMany concept types – universals vs. individuals, endurants vs. perdurants,etc. and much moreOntologies can be represented formally, in order to exploitautomated reasoning on concepts/meanings.Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201511 / 118

LogicsPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201512 / 118

Formal Ontologiesdeal with proper representation of conceptual knowledge in a domainPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201513 / 118

Formal Ontologiesdeal with proper representation of conceptual knowledge in a domainbackground for many AI techniques, e.g.:Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201513 / 118

Formal Ontologiesdeal with proper representation of conceptual knowledge in a domainbackground for many AI techniques, e.g.:IPetr Křemenknowledge management – search engines, data integrationpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201513 / 118

Formal Ontologiesdeal with proper representation of conceptual knowledge in a domainbackground for many AI techniques, e.g.:IIPetr Křemenknowledge management – search engines, data integrationmultiagent systems – communication between agentspetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201513 / 118

Formal Ontologiesdeal with proper representation of conceptual knowledge in a domainbackground for many AI techniques, e.g.:IIIPetr Křemenknowledge management – search engines, data integrationmultiagent systems – communication between agentsmachine learning – language biaspetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201513 / 118

Formal Ontologiesdeal with proper representation of conceptual knowledge in a domainbackground for many AI techniques, e.g.:IIIknowledge management – search engines, data integrationmultiagent systems – communication between agentsmachine learning – language biasinvolves many graphical/textual languages ranging from informal toformal ones, e.g. relational algebra, Prolog, RDFS, OWL, topic maps,thesauri, conceptual graphsPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201513 / 118

Formal Ontologiesdeal with proper representation of conceptual knowledge in a domainbackground for many AI techniques, e.g.:IIIknowledge management – search engines, data integrationmultiagent systems – communication between agentsmachine learning – language biasinvolves many graphical/textual languages ranging from informal toformal ones, e.g. relational algebra, Prolog, RDFS, OWL, topic maps,thesauri, conceptual graphsMost of them are based on some logical calculus.Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201513 / 118

Logics for Ontologiespropositional logicPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201514 / 118

Logics for Ontologiespropositional logicExample“John is clever.00 “John fails at exam.00Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201514 / 118

Logics for Ontologiespropositional logicExample“John is clever.00 “John fails at exam.00first order predicate logicPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201514 / 118

Logics for Ontologiespropositional logicExample“John is clever.00 “John fails at exam.00first order predicate logicExample( x)(Clever (x) (( y )(Exam(y ) Fails(x, y )))).Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201514 / 118

Logics for Ontologiespropositional logicExample“John is clever.00 “John fails at exam.00first order predicate logicExample( x)(Clever (x) (( y )(Exam(y ) Fails(x, y )))).(propositional) modal logicPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201514 / 118

Logics for Ontologiespropositional logicExample“John is clever.00 “John fails at exam.00first order predicate logicExample( x)(Clever (x) (( y )(Exam(y ) Fails(x, y )))).(propositional) modal logicExample (( x)(Clever (x) 3 (( y )(Exam(y ) Fails(x, y ))))).Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201514 / 118

Logics for Ontologiespropositional logicExample“John is clever.00 “John fails at exam.00first order predicate logicExample( x)(Clever (x) (( y )(Exam(y ) Fails(x, y )))).(propositional) modal logicExample (( x)(Clever (x) 3 (( y )(Exam(y ) Fails(x, y ))))). what is the meaning of these formulas ?Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201514 / 118

Logics for Ontologies (2)Logics are defined by theirSyntax – to represent concepts (defining symbols)Logics trade-offA logical calculus is always a trade-off between expressiveness andtractability of reasoning.Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201515 / 118

Logics for Ontologies (2)Logics are defined by theirSyntax – to represent concepts (defining symbols)Semantics – to capture meaning of the syntactic constructs (definingconcepts)Logics trade-offA logical calculus is always a trade-off between expressiveness andtractability of reasoning.Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201515 / 118

Logics for Ontologies (2)Logics are defined by theirSyntax – to represent concepts (defining symbols)Semantics – to capture meaning of the syntactic constructs (definingconcepts)Proof Theory – to enforce the semanticsLogics trade-offA logical calculus is always a trade-off between expressiveness andtractability of reasoning.Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201515 / 118

Propositional LogicExampleHow to check satisfiability of the formula A ( (B A) B C ) ?syntax – atomic formulas and , , , Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201516 / 118

Propositional LogicExampleHow to check satisfiability of the formula A ( (B A) B C ) ?syntax – atomic formulas and , , , semantics ( ) – an interpretation assigns true/false to each formula.Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201516 / 118

Propositional LogicExampleHow to check satisfiability of the formula A ( (B A) B C ) ?syntax – atomic formulas and , , , semantics ( ) – an interpretation assigns true/false to each formula.proof theory ( ) – resolution, tableauPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201516 / 118

Propositional LogicExampleHow to check satisfiability of the formula A ( (B A) B C ) ?syntax – atomic formulas and , , , semantics ( ) – an interpretation assigns true/false to each formula.proof theory ( ) – resolution, tableaucomplexity – NP-Complete (Cook theorem)Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201516 / 118

First Order Predicate LogicExampleWhat is the meaning of this sentence ?( x1 )((Student(x1 ) ( x2 )(GraduateCourse(x2 ) isEnrolledTo(x1 , x2 ))) ( x3 )(isEnrolledTo(x1 , x3 ) GraduateCourse(x3 )))Student u isEnrolledTo.GraduateCourse v isEnrolledTo.GraduateCoursePetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201517 / 118

First Order Predicate Logic – quick informal reviewsyntax – constructs involvePetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201518 / 118

First Order Predicate Logic – quick informal reviewsyntax – constructs involveterm (variable x, constant symbol JOHN, functionsymbol applied to terms fatherOf (JOHN))Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201518 / 118

First Order Predicate Logic – quick informal reviewsyntax – constructs involveterm (variable x, constant symbol JOHN, functionsymbol applied to terms fatherOf (JOHN))axiom/formula (predicate symbols applied to termshasFather (x, JOHN), possibly glued togetherwith , , , , , )Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201518 / 118

First Order Predicate Logic – quick informal reviewsyntax – constructs involveterm (variable x, constant symbol JOHN, functionsymbol applied to terms fatherOf (JOHN))axiom/formula (predicate symbols applied to termshasFather (x, JOHN), possibly glued togetherwith , , , , , )universally closed formula formula without free variable(( x)( y )hasFather (x, y ) Person(y ))Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201518 / 118

First Order Predicate Logic – quick informal reviewsyntax – constructs involveterm (variable x, constant symbol JOHN, functionsymbol applied to terms fatherOf (JOHN))axiom/formula (predicate symbols applied to termshasFather (x, JOHN), possibly glued togetherwith , , , , , )universally closed formula formula without free variable(( x)( y )hasFather (x, y ) Person(y ))semantics – an interpretation (with valuation) assigns:Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201518 / 118

First Order Predicate Logic – quick informal reviewsyntax – constructs involveterm (variable x, constant symbol JOHN, functionsymbol applied to terms fatherOf (JOHN))axiom/formula (predicate symbols applied to termshasFather (x, JOHN), possibly glued togetherwith , , , , , )universally closed formula formula without free variable(( x)( y )hasFather (x, y ) Person(y ))semantics – an interpretation (with valuation) assigns:domain element to each termPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201518 / 118

First Order Predicate Logic – quick informal reviewsyntax – constructs involveterm (variable x, constant symbol JOHN, functionsymbol applied to terms fatherOf (JOHN))axiom/formula (predicate symbols applied to termshasFather (x, JOHN), possibly glued togetherwith , , , , , )universally closed formula formula without free variable(( x)( y )hasFather (x, y ) Person(y ))semantics – an interpretation (with valuation) assigns:domain element to each termtrue/false to each closed formulaPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201518 / 118

First Order Predicate Logic – quick informal reviewsyntax – constructs involveterm (variable x, constant symbol JOHN, functionsymbol applied to terms fatherOf (JOHN))axiom/formula (predicate symbols applied to termshasFather (x, JOHN), possibly glued togetherwith , , , , , )universally closed formula formula without free variable(( x)( y )hasFather (x, y ) Person(y ))semantics – an interpretation (with valuation) assigns:domain element to each termtrue/false to each closed formulaproof theory – resolution; Deduction Theorem, Soundness Theorem,Completeness TheoremPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201518 / 118

First Order Predicate Logic – quick informal reviewsyntax – constructs involveterm (variable x, constant symbol JOHN, functionsymbol applied to terms fatherOf (JOHN))axiom/formula (predicate symbols applied to termshasFather (x, JOHN), possibly glued togetherwith , , , , , )universally closed formula formula without free variable(( x)( y )hasFather (x, y ) Person(y ))semantics – an interpretation (with valuation) assigns:domain element to each termtrue/false to each closed formulaproof theory – resolution; Deduction Theorem, Soundness Theorem,Completeness Theoremcomplexity – undecidable (Goedel)Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201518 / 118

Open World AssumptionOWAFOPL accepts Open World Assumption, i.e. whatever is not known is notnecessarily false.As a result, FOPL is monotonic, i.e.monotonicityNo conclusion can be invalidated by adding extra knowledge.This is in contrary to relational databases, or Prolog that accept ClosedWorld Assumption.Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201519 / 118

Semantic Networks and FramesPetr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201520 / 118

Semantic NetworksNodes entities (individuals, classes),( c wikipedia.org)Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201521 / 118

Semantic NetworksNodes entities (individuals, classes),Edges binary relations( c wikipedia.org)Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201521 / 118

Semantic NetworksNodes entities (individuals, classes),Edges binary relationsThe only possible inference isinheritance by means of is arelationship.( c wikipedia.org)Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201521 / 118

Semantic NetworksNodes entities (individuals, classes),Edges binary relationsThe only possible inference isinheritance by means of is arelationship.Example( c wikipedia.org)Petr Křemenpetr.kremen@fel.cvut.czEach Cat hasa Vertebrate, sinceeach Cat isa Mammal.Introduction, Description LogicsOctober 5, 201521 / 118

Semantic Networks (2)However, this does not allowdistinguishing individuals (instances)and groups (classes).Petr Křemenpetr.kremen@fel.cvut.czTo solve this, a new relationship type“is a kind of” ako can be introducedand used for inheritance, while is arelationships would be restricted toexpressing individual-grouprelationships.Introduction, Description LogicsOctober 5, 201522 / 118

Semantic Networks (3), are simple – from the point of logics they are not much more than abinary structure ako and is a relationships with the followingsemantics:Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201523 / 118

Semantic Networks (3), are simple – from the point of logics they are not much more than abinary structure ako and is a relationships with the followingsemantics:relation(X , Y ) ako(Z , X ) relation(Z , Y ).isa(X , Y ) ako(Y , Z ) isa(X , Z ).ako(X , Y ) ako(Y , Z ) ako(X , Z ).Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201523 / 118

Semantic Networks (3), are simple – from the point of logics they are not much more than abinary structure ako and is a relationships with the followingsemantics:relation(X , Y ) ako(Z , X ) relation(Z , Y ).isa(X , Y ) ako(Y , Z ) isa(X , Z ).ako(X , Y ) ako(Y , Z ) ako(X , Z )./ no way to express non-monotonous knowledge (like FOL).Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201523 / 118

Semantic Networks (3), are simple – from the point of logics they are not much more than abinary structure ako and is a relationships with the followingsemantics:relation(X , Y ) ako(Z , X ) relation(Z , Y ).isa(X , Y ) ako(Y , Z ) isa(X , Z ).ako(X , Y ) ako(Y , Z ) ako(X , Z )./ no way to express non-monotonous knowledge (like FOL)./ no easy way to express n-ary relationships (reification needed).Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201523 / 118

Semantic Networks (3), are simple – from the point of logics they are not much more than abinary structure ako and is a relationships with the followingsemantics:relation(X , Y ) ako(Z , X ) relation(Z , Y ).isa(X , Y ) ako(Y , Z ) isa(X , Z ).ako(X , Y ) ako(Y , Z ) ako(X , Z )./ no way to express non-monotonous knowledge (like FOL)./ no easy way to express n-ary relationships (reification needed)./ no way to express binary relationships characteristics – transitivity,functionality, reflexivity, etc., or their hierarchies “to be a fathermeans to be a parent”, etc.,Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201523 / 118

Semantic Networks (3), are simple – from the point of logics they are not much more than abinary structure ako and is a relationships with the followingsemantics:relation(X , Y ) ako(Z , X ) relation(Z , Y ).isa(X , Y ) ako(Y , Z ) isa(X , Z ).ako(X , Y ) ako(Y , Z ) ako(X , Z )./ no way to express non-monotonous knowledge (like FOL)./ no easy way to express n-ary relationships (reification needed)./ no way to express binary relationships characteristics – transitivity,functionality, reflexivity, etc., or their hierarchies “to be a fathermeans to be a parent”, etc.,/ no way to express more complex constructs, like cardinalityrestrictions: “Each person has at most two legs.”Petr Křemenpetr.kremen@fel.cvut.czIntroduction, Description LogicsOctober 5, 201523 / 118

Semantic Networks (3), are simple – from the point of logics they are not much more than abinary structure ako and is a relationships with the followingsemantics:relation(X , Y ) ako(Z , X ) relation(Z , Y ).isa(X , Y ) ako(Y , Z ) isa(X , Z ).ako(

Introduction, Description Logics Petr K remen petr.kremen@fel.cvut.cz October 5, 2015 Petr K remen petr.kremen@fel.cvut.cz Introduction, Description Logics October 5, 2015 1 / 118. Our plan 1 Course Information 2 Towards Description Logics 3 Logics 4 Semantic Networks and Frames 5 Towards Description Logics 6 ALCLanguage Petr K remen petr.kremen@fel.cvut.cz Introduction, Description Logics .

Related Documents:

Description Logic Reasoning Research Challenges Reasoning with Expressive Description Logics – p. 2/40. Talk Outline Introduction to Description Logics The Semantic Web: Killer App for (DL) Reasoning? Web Ontology Languages DAML OIL Language Reasoning with DAML OIL OilEd Demo Description Logic Reasoning Research Challenges Reasoning with Expressive Description Logics – p. 2/40. Talk .

Basic Description Logics Franz Baader Werner Nutt Abstract This chapter provides an introduction to Description Logics as a formal language for representing knowledge and reasoning about it. It first gives a short overview of the ideas underlying Description Logics. Then it introduces syntax and semantics, covering the basic constructors that are used in systems or have been introduced in the .

An Introduction to Description Logics Daniele Nardi Ronald J. Brachman Abstract This introduction presents the main motivations for the development of Description Logics (DL) as a formalism for representing knowledge, as well as some important basic notions underlying all systems that have been created in the DL tradition. In addition, we provide the reader with an overview of the entire book .

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 .

system. HSR-OD-1-LD: Intelligent one-button table adjustment. HSU-OD-F2-LD: Simple Flex Memory handset, without display. HSU-MDF-4F2-LD: Flex Memory handset with 4 memory keys and display. IRR-DSK-SET: Infrared remote control with 2 sets of up and down keys and memory keys. ACS-ADAP-MOUSE: Computer mouse control adapter.

Department of Computer Science, University of Link oping, Sweden . 9.3 How to Develop a Modal Logic for an Application . . . . . . . . 70 . the classical propositional and predicate calculus modal logics, including logics of programs and temporal logics

For many applications natural choices would be various more expressive logics, including the predicate logic or various modal logics. These logics, however, lack the kind of efficient and scalable algorithms that are available for the classical propositional logic. The existence of high performance algorithms for reasoning with propositional

(ii) is an aboveground storage tank with a capacity of more than 2200 litres, installed at or in use at a bulk petroleum sales outlet or a retail outlet, or (iii) is part of a field-erected aboveground storage tank system that falls within the requirements of API standard API 650, Welded Steel Tanks for Oil Storage, Twelfth Edition, Includes