KRR: Logiki Deskrypcyjne

Tematem laboratorium są logiki deskrypcyjne (ang. Description Logics). W zakres ćwiczeń wchodzą następujące tematy:

  • DL jako formalizm reprezentacji wiedzy
  • Struktura bazy wiedzy w DL
  • Zadania wnioskowania dla DL
  • Wsparcie narzędziowe

1 Reprezentacja wiedzy z użyciem Logik Deskrypcyjnych

1.1 Wprowadzenie

  • Logiki deskrypcyjne (opisowe) (ang. Description Logics, DL) są rodziną formalizmów reprezentacji wiedzy.
  • Elementami reprezentacji są pojęcia (klasy), role (relacje) i instancje (obiekty 1)).
  • Logiki opisowe są koncepcyjnie powiązane z sieciami semantycznymi (ang. semantic networks) i ramami (ang. frames), jednak w przeciwieństwie do nich, przez swoje powiązanie z logiką pierwszego rzędu, posiadaję formalnie zdefiniowaną semantykę i zapewniają możliwość automatycznego wnioskowania.
  • Intuicyjnie można powiedzieć, że logiki opisowe łączą paradygmat obiektowy (ramy, sieci semantyczne) z logiką (rachunek predykatów, logika 1. rzędu).

Przykład 1: graf obrazujący zbiór obiektów powiązanych relacjami i należących do pewnych klas:

Wybrane fragmenty ww. grafu zapisane w logice opisowej:

  •  Fred : person ,   Tibbs: cat,   (Fred, Tibbs) : has\_pet
  •   man \equiv person \sqcap adult \sqcap male,   cat\_liker \equiv person \sqcap \exists likes.cat
  • (cat\_liker, cat) : likes ,  (sheep, grass) : eats\_only
  •  cat \sqsubseteq animal,   sheep \sqsubseteq animal \sqcap \forall eats.grass

1.2 Co możemy zapisać z użyciem Logik Deskrypcyjnych

W logikach opisowych możemy konstruować zdania o pojęciach i instancjach. Poniżej przedstawiono podstawowe rodzaje wyrażeń w logice opisowej i ich intuicyjne wytłumaczenia:

Instancje (obiekty):

  1. przynależność obiektu do klasy (ang. concept assertions), np:
    • Fred : person - Fred jest osobą
    • Tibbs : cat - Tibbs jest kotem
  2. relacja między dwoma obiektami
    •  (Fred, Tibbs) : has\_pet - Fred ma zwierzę, którym jest Tibbs

Pojęcia

  1. definicje pojęć (warunki konieczne i wystarczające), np.
    •   man \equiv person \sqcap adult \sqcap male - Mężczyzna to dorosła osoba rodzaju męskiego
    •   cat\_liker \equiv person \sqcap \exists likes.cat - Miłośnik kotów to osoba, która lubi (jakiegoś) kota
  2. relacje między pojęciami (klasami)
    •  (cat\_liker, cat) : likes - (każdy) miłośnik kotów lubi (jakiegoś) kota
    •  (sheep, grass) : eats\_only - (każda) owca je tylko trawę
  3. aksjomaty
    •  cat \sqsubseteq animal (każdy) kot jest zwierzęciem (hierarchia pojęć)
    •   sheep \sqsubseteq animal \sqcap \forall eats.grass owce to zwierzęta, które jedzą tylko trawę (warunek konieczny, ale nie wystarczający)

Ćwiczenie 1: Wypisz z grafu z przykładu 1 wszystkie:

  1. pojęcia (klasy),
  2. role (relacje),
  3. instancje (obiekty).

Odpowiedzi: lab_dl_answers

1.3 Podstawowy język DL

  • W języku logiki opisowej tworzymy opisy.
  • Podstawowe elementy języka to: atomicze pojęcia i atomiczne role.
  • Złożone opisy tworzy się indukcyjnie za pomocą konstruktorów.
  • Poszczególne języki DL różnią się między sobą zbiorem dopuszczalnych konstruktorów
  • Najprostszy język to AL (ang. Attributive Language)

Składnia AL

  • atomiczne pojęcia (A, B, ... )
  • atomiczne role (R, S, ... )
  • opisy (C, D, ... ); mogą nimi być:
    •  A   - pojęcie atomiczne
    • \top - top concept, pojęcie uniwersalne oznaczające „wszystko”
    • \bot - bottom concept, pojęcie puste, oznaczające „nic”
    • \neg A  - negacja
    • C \sqcap D   - koniunkcja
    • \forall R.C - kwantyfikator uniwersalny: „dla każdego”
    • \exists R.\top - kwantyfikator egzystencjalny/szczegółowy: „istnieje”

Semantyka AL

Semantyka zdefiniowana jest poprzez interpretację składającą się z:

  1. dziedziny intepretacji:   \Delta^{\mathcal{I}} - niepustego zbioru, na który mapowane są symbole i relacje
  2. funkcji interpretacji, która przypisuje:
    • każdemu atomicznemu pojęciu zbiór:   A \rightarrow A^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}}
    • każdej atomicznej roli relację binarną:   R^{\mathcal{I}} \rightarrow \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}


Konstruktor Składnia Semantyka
pojęcie atomiczne (atomic concept)   A        A^{\mathcal{I}} = A^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}}
atomiczna rola (atomic role)   R        R^{\mathcal{I}} = R^{\mathcal{I}} \subseteq \Delta^{\mathcal{I}} \times \Delta^{\mathcal{I}}
pojęcie uniwersalne (universal concept)    \top    \top^{\mathcal{I}} = \Delta^{\mathcal{I}}
pojęcie puste (bottom concept)    \bot    \bot^{\mathcal{I}} = \emptyset
(atomic negation)    \neg A   (\neg A)^{\mathcal{I}} = \Delta^{\mathcal{I}} \setminus A^{\mathcal{I}}
koniunkcja/przecięcie (intersection)    C \sqcap D      (C \sqcap D)^{\mathcal{I}} = C^{\mathcal{I}} \cap D^{\mathcal{I}}
ograniczenie wartości (value restriction)    \forall R.C     (\forall R.C)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \forall b, (a,b) \in R^\mathcal{I} \rightarrow b \in C^{\mathcal{I}} \rbrace
ograniczony kwantyfikator egzystencjalny (limited existential quantification)   \exists R.\top    (\exists R.\top)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \exists b, (a,b) \in R^\mathcal{I} } \rbrace

Przykład 2:

  • pojęcia atomiczne: Person, Female, Elephant
    • osoba rodzaju żeńskiego:   Person \sqcap Female
    • słonica:   Elephant \sqcap Female
    • osoba, które nie jest rodzaju żeńskiego:   Person \sqcap \neg Female
  • atomiczna rola: hasChild
    • osoba, która ma (jakieś) dziecko/dzieci:   Person \sqcap \exists hasChild. \top
    • osoba, której wszystkie dzieci są rodzaju zeńskiego   Person \sqcap \forall hasChild.Female
    • osoba bezdzietna   Person \sqcap \forall hasChild. \bot

1.4 Rodzina języków DL

Poszczególne języki DL rozróżniamy poprzez konstruktory, które dopuszczają. Przykładowe konkstruktory:

  •  \mathcal{U} - suma :  (C \sqcup D)^\mathcal{I} = C^\mathcal{I} \cup D^\mathcal{I}
  •  \mathcal{E} - pełny kwantyfikator egzystencjalny :  (\exists R.C)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \vert \exists b, (a,b) \in R^\mathcal{I} \land b \in C^{\mathcal{I}} \rbrace
  •  \mathcal{N} - ograniczenia liczbowe:
    •  (\geq n R)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \arrowvert { \mid\lbrace b \mid (a,b) \in R^\mathcal{I} \rbrace \mid \geq n } \rbrace
    •  (\leq n R)^\mathcal{I} = \lbrace a \in \Delta^\mathcal{I} \arrowvert { \mid\lbrace b \mid (a,b) \in R^\mathcal{I} \rbrace \mid \leq n } \rbrace
  •  \mathcal{C} - negacja :  ( \neg C)^\mathcal{I} = \Delta^\mathcal{I} \setminus C^\mathcal{I}

Używające powyższych konstruktorów języki nazywają się odpowiednio:

  •   \mathcal{ALU}
  •   \mathcal{ALE}
  •   \mathcal{ALN}
  •   \mathcal{ALC} → odpowiada podzbiorowi logiki pierwszego rzędu ograniczonemu do formuł z dwoma zmiennymi

Ćwiczenie 2

Rozważmy interpretację: I = (∆, ·I ), gdzie

  • \Delta I = \{John,Suzan,Max,Helen,Natalie,Nick\},
  • Human^I = \{John,Suzan,Helen,Natalie,Nick\},
  • Male^I	= \{John, Max, Nick\},
  • Dog^I	= \{Max\},
  • Doctor^I	= \{John, Helen\},
  • areFriends^I = \{(Suzan,Helen),(Helen,Suzan),(Natalie,Helen),(Helen,Natalie),  (Suzan, Natalie), (Natalie, Suzan), (Natalie, Nick), (Nick, Natalie) \} ,
  • areMarried^I	= \{(Suzan, John), (John, Suzan)\},
  • hasPet^I	= \{(Suzan, Max), (John, Max)\}.
  1. Przedstaw powyższą interpretację w postaci grafu.
  2. Zapisz następujące opisy w logice deskrypcyjnej:
    1. Ci którzy są w związku małżeńskim z doktorem i posiadający psa jako zwierzę domowe.
    2. Ci którzy nie są w związku małżeńskim, a wszyscy ich przyjaciele są albo kobietami albo mężczyznami w związkach małżeńskich.
    3. Wyznacz rozszerzenie powyższych pojęć w interpretacji I (sprawdź czy/kto w podanej interpretacji zalicza się do tych grup).
  3. Zapisz następujące pojęcia w postaci aksjomatów (postaci A \sqsubseteq B) języka ALC:
    1. Ci, którzy nie mają męskich przyjaciół, nie mają zwierząt domowych.
    2. Wszyscy mężczyźni są albo w związku małżeńskim albo mają nie-męskiego przyjaciela.
    3. Czy te aksjomaty są prawdziwe w danej interpretacji?

Odpowiedzi: reprezentacja_-_zadanie

1.5 Powiązanie z innymi rachunkami (logicznymi)

  • Większość logik opisowych jest podzbiorem logiki pierwszego rzędu
    • nazwy pojęć ⇔ predykaty unarne
    • relacje (atomiczne) ⇔ predykaty binarne
    • pojęcia ⇔ formuły z jedną wolną zmienną
  • Formuły logiki opisowej można intuicyjnie interpretować poprzez analogię do algebry zbiorów
Przykład użycia Składnia DL Składnia FOL Algebra zbiorów
Mężczyzna to dorosły i osoba i rodzaju męskiego  C_{1} \sqcap ... \sqcap C_{n}  C_{1}(x) \land ... \land C_{n}(x)  C_{1} \cap ... \cap C_{n}
Gazeta to dziennik lub czasopismo  C_{1} \sqcup ... \sqcup C_{n}  C_{1}(x) \lor ... \lor C_{n}(x)  C_{1} \cup ... \cup C_{n}
Wszystko, co jedzą wegetarianie to nie mięso   \neg C   \neg C(x)  C^c (dopełnienie zbioru)
Kraje UE to: Niemcy, Francje, …, Polska   \lbrace x_{1} \rbrace \sqcup ... \sqcup \lbrace x_{n} \rbrace   x=x_{1} \lor ... \lor x=x_{n}   \lbrace x_{1} \rbrace \cup ... \cup \lbrace x_{n} \rbrace
Każde zwierzę, które ma starsza pani to kot   \forall P.C   \forall y.P(x,y) \rightarrow C(y)  \pi_Y(P) \subseteq C
Właściciel psa ma jakiegoś psa   \exists P.C   \exists y.P(x,y) \land C(y) \pi_Y(P) \cap C \neq \emptyset (Π - projekcja)
Rozsądny mężczyzna spotyka się z maksymalnie 1 kobietą równocześnie ;-)   \leq nP   \exists^{\leq n}y.P(x,y)  card(P)\leq n (card - liczność zbioru)
Miłośnik zwierzą ma minimum 3 ziwerzaki   \geq nP   \exists^{\geq n}y.P(x,y)   card(P) \geq n
Dziecko to to samo co młoda osoba   C \equiv D   \forall x.C(x) \leftrightarrow D(x)   C \equiv D
Każda foka jest zwierzęciem   C \sqsubseteq D   \forall x.C(x) \rightarrow D(x)  C \subseteq D

Ćwiczenie 3 (na podstawie http://pages.cs.wisc.edu/~dyer/cs540/notes/fopc.html Poniższe zdania przełożono z języka naturalnego na formuły rachunku pierwszego rzędu. Dopisz odpowiadające im zdania w logice deskrypcyjnej tam gdzie jest to możliwe.

  1. Każdy ogrodnik lubi słońce. / Every gardener likes the sun.
    1. (Ax) gardener(x) ⇒ likes(x,Sun)
  2. Niektórych ludzi możesz nabrać zawsze. / You can fool some of the people all of the time.
    1. (Ex) (person(x) ^ (At)(time(t) ⇒ can-fool(x,t)))
  3. Czasami możesz nabrać wszystkich ludzi. / You can fool all of the people some of the time.
    1. (Ax) (person(x) ⇒ (Et) (time(t) ^ can-fool(x,t)))
  4. Wszystkie fioletowe grzyby są trujące. / All purple mushrooms are poisonous.
    1. (Ax) (mushroom(x) ^ purple(x)) ⇒ poisonous(x)
  5. Żadne fioletowe grzyby nie są trujące. / No purple mushroom is poisonous.
    1. ~(Ex) purple(x) ^ mushroom(x) ^ poisonous(x)
    2. (Ax) (mushroom(x) ^ purple(x)) ⇒ ~poisonous(x)
  6. Deb nie jest wysoka. / Deb is not tall.
    1. ~tall(Deb)

Odpowiedzi: lab_dl_answers

* Rozszerzenia języków DL

Podstawowym językiem jest ALC (≈ALUE). Dodatkowe litery oznaczają następujące rozszerzenia:

  • dotyczące konstruktorów pojęć:
    •  \mathcal{F} ograniczenia funkcyjne (np. ≤1hasMother)
    •  \mathcal{N} ograniczenia liczbowe (np. ≥2hasChild, ≤3hasChild)
    •  \mathcal{Q} warunkowe ograniczenia liczbowe (np. ≥2hasChild.Doctor))
    •  \mathcal{O} z użyciem instancji (e.g., {Italy})
  • dotyczące konstruktorów ról:
    • koniunkcja ról: R∩S, suma ról: R∪S, role dopełniające: ¬R, łańcuchy (kompozycja) ról: R o S
    •  \mathcal{I} role odwrotne (np.  isChildOf \equiv hasChild^{–})
  • dodatkowe aksjomaty dot. ról:
    •  \mathcal{S} przechodniość relacji
    •  \mathcal{H} hierarchia relacji (e.g.,  hasDaughter \sqsubseteq hasChild)
    •  \mathcal{R} zawieranie się relacji: RoS ⊆ R, RoS ⊆
  • inne:
    •   ^{(\mathcal{D})} użycie typów danych w obrębie języka

Przykłady: Język ontologii

  1. OWL DL jest równoważny SHOIN(D)
  2. OWL Lite jest uproszczonym podzbiorem OWL DL i odpowiada SHIF(D)
  3. OWL2 - ekspresywny język ontologii równoważny SROIQ(D)

BONUS:

  • Złożoność obliczeniowa wnioskowania w poszczególnych językach DL zależy od ich siły ekspresji: zobacz przewodnik po językach DL

2 Struktura bazy wiedzy opartej na logice opisowej

Baza wiedzy w logice opisowej składa się z:

  1. Terminologii, tzw. TBox (ang. terminology box), zawierającej aksjomaty dot. pojęć, w tym definicje
  2. Zbioru twierdzeń , tzw. ABox (ang. assertion box) - zawierającego twierdzenia o pojedynczych obiektach

2.1 Terminologia (TBox)

Składnia:

  • TBox to skończony zbiór aksjomatów terminologicznych postaci:
    •   C \sqsubseteq D
    •   R \sqsubseteq S
    •  C \equiv D
    •  R \equiv S
  • Definicje to równości, które po lewej stronie mają pojęcie atomiczne

Semantyka:

  • funkcja interpretacji  \mathcal{I} mapuje każde pojecie na podzbiór dziedziny
  • interpretacja spełnia aksjomat   C \sqsubseteq D jeżeli:   C^{\mathcal{I}} \subseteq D^{\mathcal{I}} ; analogicznie w przypadku relacji  R \sqsubseteq S
  • interpretacja I spełnia definicję  C \equiv D jeżeli:   C^{\mathcal{I}} = D^{\mathcal{I}} ; analogicznie w przypadku relacji  R \equiv S
  • interpretacja spełnia terminologię (TBox) jeżeli spełnia wszystkie jej aksjomaty. Mówimy wtedy, że I jest modelem T.

Ćwiczenie 4: Używając pojęć: „Przedmiot”, „Wykładowca”, „Mgr” i „Inż” oraz ról „prowadzi” i „maTytuł” przedstaw poniższą wiedzą w postaci TBoxa:

  1. Każdy kto prowadzi przedmiot musi mieć albo stopień magistra albo być wykładową.
  2. Każdy wykładowca ma tytuł inżyniera.
  3. Każdy wykładowca prowadzi jakiś przedmiot.
  4. Każdy posiadający tytuł magistra ma też tytuł inżyniera.

Odpowiedzi: tbox

2.2 Opis świata (ABox)

Składnia: ABox zawiera wiedzę o instancjach (obiektach występujących w opisywanym świecie), w tym:

  • stwierdzenia o przynależności do klasy tzw. concept assertions np. a : C
  • stwierdzenia o relacjach między obiektami tzw. role assertions np. (b,c) : R

Semantyka:

  • funkcja interpretacji mapuje każdą nazwę na element dziedziny.
  • interpretacja spełnia (względem terminologii T):
    • a : C wtw gdy  a^{\mathcal{I}} \in C^{\mathcal{I}}
    • (b,c) : R wtw gdy  (b^{\mathcal{I}}, c^{\mathcal{I}}) \in R^{\mathcal{I}}
    • ABox wtw gdy spełnia wszystkie jego stwierdzenia. Mówimy wtedy, że I jest modelem A.

Ćwiczenie 5 Dany jest następujący opis świata (ABox):

  • (john,susan): friend
  • (john,andrea): friend
  • (susan,andrea): loves
  • (andrea,bill): loves
  • susan: Female
  • bill: ¬Female
  1. Wypisz relacje, klasy i obiekty.
  2. Przedstaw ww. ABox w postaci grafu.
  3. Zapisz następujące stwierdzenie: „John ma przyjaciółkę (przyjaciela rodzaju żeńskiego), które jest zakochana w mężczyźnie (osobie niebędącej rodzaju żeńskiego)” w postaci john : X, gdzie X jest odpowiednim opisem.

Odpowiedzi: abox

3 Wnioskowanie w logikach deskrypcyjnych

  • Logiki opisowe, dzięki formalnemu ugruntowaniu w logice, umożliwiają automatyczne wnioskowanie.
  • Osobne zadania wnioskowania definiuje się dla TBoxa i ABoxa.
  • W logikach opisowych stosuje sią Założenie o otwartości świata.
  • Podstawowymi algorytmami dla DL są:
    • algorytmy strukturalne (Structural subsumption algorithms)
    • algorytmy tableau (Tableau algorithms)
  • Złożoność obliczeniona poszczególnyc zadań wnioskowania zależy od siły ekspresji języka DL

3.1 Zadania wnioskowania dla TBoxa

  1. Spełnialność (ang. satisfiability)
    • Pojęcie C jest spełnialne względem terminologii T jeżeli istnieje model (interpretacja) I taki że  C^{\mathcal{I}} jest niepusty.
  2. Subsumcja 2) (ang. subsumption)
    • Pojęcie C jest włączone w pojęcie D wzg. T jeżeli  C^{\mathcal{I}} \subseteq D^{\mathcal{I}} dla każdego modelu I terminologii T.
  3. Równoważność (ang. equivalence)
    • Dwa pojęcia C i D są sobie równoważne wzg. T jeżeli  C^{\mathcal{I}} = D^{\mathcal{I}} dla każdego modelu I terminologii T.
  4. Rozłączność (ang. disjointness)
    • Dwa pojęcia C i D są rozłączne wzg. T. jeżeli  C^{\mathcal{I}} \cap D^{\mathcal{I}} = \emptyset dla każdego modelu I terminologii T.

Ćwiczenie 6

  1. Wiedząc, że:
    • Vegetarian \equiv (\forall eats.(\neg (\exists partOf.Animal))) \sqcap (\forall eats.(\neg Animal)) \sqcap Animal
    • Cow \sqsubseteq Vegetarian
    • MadCow \equiv \exists eats.(\exists partOf.Sheep \sqcap Brain) \sqcap Cow
      Odpowiedz na pytanie:
    1. Jakiemu pojęciu jest równoważne pojęcie MadCow?
  2. Wykorzystując bazę wiedzy z sekcji terminologia_tbox odpowiedz na pytanie:
    1. Czy zdanie„ „Każdy kto prowadzi przedmiot musi mieć tytuł inżyniera” jest logiczną konsekwencją tej bazy wiedzy? Odpowiedź uzasadnij.

3.2 Zadania wnioskowania dla ABoxa

  1. Sprawdzenie spójności (ang. consistency checking)
    • ABox A jest spójny wzg. terminologii T, jeżeli istnieje nterpretacja I będąca jednocześnie modelem A i T.
  2. Sprawdzanie instancji (ang. instance checking)
    •  A \models \alpha iff każda interpretacja spełniająca A spełnia również α.
  3. Poszukiwanie najbardziej szegółowego pojęcia dla danej instancji (ang. realization).
  4. Poszukiwanie instancji danego pojęcia (ang. retrieval).

Uwaga:

  • wszystkie zadania TBox mogą być zredukowane do zadania subsumcji lub spełnialności
    • C i D są rozłączne ⇔  C \sqcap D zawiera się w ⊥
    • np. C zawiera się D ⇔  C \sqcap \neg D nie jest spełnialne (na tej obserwacji opierają się algorytmy tableau)
  • wszystkie zadania wnioskowania mogą być sprowadzone do sprawdzenia spójności bazy wiedzy.

Ćwiczenie 7:

  1. Wiedząc, że:
    •  OldLady \equiv Elderly \sqcap Female \sqcap Person
    •  OldLady \sqsubseteq  \exists hasPet.Animal  \sqcap  \forall hasPet. Cat
    •  hasPet(Minnie,Tom),  Elderly(Minnie),  Female(Minnie)
      Odpowiedz na pytania:
    1. Czy każda starsza pani musi mieć kota? Dlaczego?
    2. Do jakiej klasy należy obiekt Minnie?
    3. Do jakiej klasy należy obiekt Tom?
  2. Rozważ opis świata z sekcji abox i odpowiedz na pytanie:
    • Czy John należy do klasy: ∃friend.(Female ⊓ ∃loves.¬Female)?
    • Podpowiedź:
      • Zwizualizuj w postaci grafu ten ABox, zaobserwuj, do jakich klas należą poszczególne obiekty.
      • Rozważ dwa przypadki: andrea : Female i andrea : ¬Female

Odpowiedzi: wnioskowanie

3.3 Założenie o otwartości świata

  • Analogia bazy wiedzy DL i relacyjnej bazy danych:
    • schemat bazy danych ↔ TBox
    • instancje danych ↔ ABox
  • W przeciwieństwie do relacyjnych baz danych, brak w ABox oznacza brak wiedzy, nie zaś negatywnąinformację
  • ABox reprezentuje potencjalnie nieskończenie wiele interpretacji.
  • Semantyka otwartego świata wymaga nietrywialnych mechanizmów wnioskowania, a realizaja zapytań jest bardziej skomplikowana.

BONUS:

3.4 Algorytmy wnioskowania

Strukturalne

Porównują strukturę składniową pojęć. Są efektywne, ale odpowiednie tylko do prostych języków, np. nie działają dla języków z negacją i dysjunkcją

Tableau

Opierają swoje działanie na obserwacji, że: C \sqsubseteq D wtw. gdy wyrażenie C \sqcap \neg D jest niespełnialne. Schemat działania:

  1. Start od faktów (aksjomatów ABox)
  2. Dekompozycja składniowa z użyciem odpowiednich reguł tzw. tableaux expansion rules
    • reguły odpowiadają poszczególnymkonstruktorom ( \sqcap, \sqcup, ...)
    • niektóre reguły są niedeterministyczne (np.   \sqcup, \leq ) (w praktyce prowadzi to do przeszukiwania)
  3. Wnioskowanie o ograniczeniach na elementach modelu
  4. Stop, kiedy nie można zastosować więcej reguł lub wystąpiła sprzeczność

Ćwiczenie 8 (dla chętnych):

Sprawdź czy poniższe pojęcia są spełnialne:

  1. A ⊓ ∃R.C ⊓ ∀R.D
  2. ∃R.C ⊓ ∀R.¬(C ⊓ D)
  3. A⊓∃R.C⊓∀R.D⊓∀R.¬(C⊓D)
  4. ∃R.(A ⊓ ∃R.C) ⊓ ∀R.¬C
  5. ∃R.(A ⊓ ∃R.C) ⊓ ∀R.∀R.¬C
  6. ¬C ⊓ ∃R.C ⊓ ∀R.(¬C ⊔ ∃R.C)
  7. A ⊓ ∀R.A ⊓ ∀R.¬∃P.A ⊓ ∃R.∃P.A

Przykładowe rozwiązania z użyciem algorytmu tableau: tutaj.

3.5 Wsparcie narzędziowe

Istnieje wiele implementacji silników wnioskujących dla logik deskrypcyjnych. Niektóre z nich są zoptymalizowane pod kątem konkretnych języków DL (np. takich na których opierają się warianty języka ontologii OWL ).

Lista dostępnych silników wnioskujących dostępna jest na stronie: Prof. U. Sattler. Popularne narzędzia to m.in:

Najczęściej silniki wnioskujące zintegrowane są z innymi narzędziami, np. edytorami ontologii (pełnią one wówczas rolę pomocniczą, np. do sprawdzania spójności ontologii itp.).

Ćwiczenie 9:

  1. Pobierz silnik wnioskujący Pellet.
    1. :!: Na borgu powinien być w /usr/local/pellet.
  2. Uruchom go wpisując w konsoli pellet.sh help i zapoznaj się z dostępnymi opcjami. (/usr/local/pellet/pellet.sh)
  3. Uruchom pellet.sh consistency <ontology> gdzie <ontology> jest bazą wiedzy people+pets.owl umieszczoną w katalogu examples/data.
  4. Jakie są rezultaty?
  5. Uruchom pellet.sh classify <ontology> dla powyższej ontologii peopl+pets.owl
  6. Jakie są rezultaty?

Materiały

Wykłady, prezentacje

Kursy

Narzędzia

1)
Nazwy w nawiasach używane są zwykle w ontologiach zapisanych w języku OWL, opartym na formalizmie DL
2)
subsumcja (sub- + sumere ‘brać’) log. proces wynajdowania dla danego pojęcia innego pojęcia, bardziej ogólnego. Wg. „Słownik Wyrazów Obcych” Wydawnictwa Europa, pod redakcją naukową prof. Ireny Kamińskiej-Szmaj, autorzy: Mirosław Jarosz i zespół. ISBN 83-87977-08-X. Rok wydania 2001.
pl/dydaktyka/krr/lab_dl.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0