3y ago

113 Views

2 Downloads

2.08 MB

135 Pages

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: