Leírás logika

A leíráslogika [1] ( leíró logika [2] , korai nevek - terminológiai rendszer , fogalmak logikája ) egy tudásreprezentációs nyelv, amely lehetővé teszi a tárgykör fogalmainak egyértelmű, formalizált formában, típus szerint rendszerezve történő leírását. a matematikai logika nyelveiből . A leírási logikák egyrészt gazdag kifejezési lehetőségeket, másrészt olyan jó számítási tulajdonságokat ötvöznek , mint az alapvető logikai problémák eldönthetősége és viszonylag alacsony számítási komplexitása , ami lehetővé teszi azok gyakorlati alkalmazását, kompromisszumot biztosítva az expresszivitás és az alapvető logikai problémák között. eldönthetőség. Az állítmánylogikák eldönthető töredékeinek tekinthetők , de szintaktikailag közel állnak a modális logikához .

A család az 1980-as években kapta modern nevét, ugyanakkor a keretszerkezetek és a szemantikai hálózatok elméletének formális logikai mechanizmusokkal történő kiterjesztéseként tanulmányozták. A 2000-es években a leírási logikákat a szemantikus web koncepció keretében használták , ahol az ontológiák felépítésében javasolták alkalmazásukat . Az OWL web ontológia nyelv OWL-DL és OWL-Lite töredékei szintén leírási logikán alapulnak.

Általános információk

A leíró logikák a "fogalom" és a "szerep" fogalmával működnek, ami a matematikai logika más szakaszaiban megfelel az "egyhelyi predikátum" (vagy halmaz, osztály) és a "kéthelyes predikátum" (vagy bináris reláció) fogalmának. . Intuitív módon a fogalmak bizonyos objektumok osztályainak leírására szolgálnak, például „Emberek”, „Nők”, „Gépek”. A szerepek az objektumok közötti kéthelyes kapcsolatok leírására szolgálnak, például egy emberek halmazán van egy kéthelyes kapcsolat "X is_a_a_arent_of_Y", az emberek és a gépek között pedig egy kéthelyes kapcsolat "X birtokolja_Y", ahol tetszőleges objektumok helyettesíthetők X és Y helyekkel. A leíró logika nyelvezetének segítségével általános állításokat lehet megfogalmazni az osztályokról általában (minden nő férfi, minden gép legfeljebb egy férfi tulajdona) és konkrét állításokat konkrét objektumokról (Mária nő, Iván tulajdonosa). egy gép1).

Az általános formájú vagy terminológiájú állítások ( angol terminológia ) halmazát TBoxnak, egy meghatározott típusú állításhalmazt ( angol állítások ) ABoxnak nevezzük, és ezek együtt alkotják az úgynevezett tudásbázist [3] vagy ontológiát . Számos ontológia épült és épül a legkülönfélébb tantárgyi területeken, mint például a bioinformatika , genetika , orvostudomány , kémia , biológia . Az ontológia felépítése után felvetődik a kérdés, hogy az ontológiában foglalt tudásból hogyan lehet kinyerni a következő tudást, meg lehet-e ezt programozni, és melyek a megfelelő algoritmusok. Mindezeket a kérdéseket elméletileg megoldja a "leíró logika" tudománya, és a gyakorlatban számos szoftverrendszert már megvalósítottak - érvelési mechanizmusokat ( eng. reasoners ), amelyek lehetővé teszik az ontológiákból származó ismeretek automatikus származtatását és más műveletek végrehajtását az ontológiákkal.

Szintaxis

A matematikai logikában minden nyelvet a szintaxisa , vagyis a nyelv kifejezéseinek létrehozásának szabályai és a szemantika jellemez , vagyis az a mód, ahogy ezek a kifejezések valamilyen formális jelentést kapnak, például annak megjelölésével, hogy mely kifejezéseket tekintik igaznak. és hamis.

Bármely leíró logika szintaxisának megfogalmazásához meg kell adni nem üres (és általában véges) szimbólumhalmazokat - az úgynevezett atomi fogalmakat és atomi szerepeket -, amelyekből e logika nyelvének kifejezései épülnek fel. A konkrét logikát konstruktorok halmaza és egy induktív szabály jellemzi, amelyek segítségével az adott logika összetett fogalmai atomi fogalmakból és atomi szerepekből épülnek fel ezen konstruktorok segítségével.

A kompozit fogalmak felépítésére szolgáló tipikus konstruktorok a következők:

a fogalmak metszéspontja (vagy kötőszója ) ; $C\sqcap D$
a fogalmak egyesülése (vagy diszjunkciója ) ; $C\sqcup D$
a fogalom összeadása (vagy tagadása ) ; $\neg C$
a szerepértékek korlátozása (vagy az univerzális kvantor korlátozása), jelölése ; $\forall RC$
egzisztenciális korlátozás (vagy korlátozás az egzisztenciális kvantorral), jelölése: ; $\exists RC$
a szerepértékekre vonatkozó számszerű korlátozások, például: , , és mások. $({\le}n\,R)$ $({\ge}n\,RC)$

A leíró logikákban a konjunkciót és a diszjunkciót általában másképpen jelölik, hogy hangsúlyozzák a különbséget a többi logikától. Léteznek olyan leírási logikák, amelyekben egyszerű szerepekből, műveleteket használó összetett szerepek is vannak: inverzió, metszés, egyesülés, összeadás, szerepek összeállítása, tranzitív lezárás és egyebek [4] .

ALC

A leírási logikát (az angol attributív nyelvből kiegészítéssel ) 1991-ben fejlesztették ki [5] , és egyike azoknak az alaprendszereknek, amelyekre sok más leírási logika épül. Adjuk meg az atomi fogalmak és atomi szerepek nem üres véges halmazait. Ezután a következő induktív definíciója a logika összetett fogalmainak (fogalmaknak): $\mathcal{ALC}$ $\mathcal{ALC}$

minden atomfogalom fogalom;
kifejezések és fogalmak; $\top$ $\bot$
ha van fogalom, akkor annak kiegészítése fogalom; $C$ $\neg C$
ha vannak fogalmak, akkor metszéspontjuk és egyesülésük fogalmak; $C$ $D$ $C\sqcap D$ $C\sqcup D$
ha van fogalom és van szerep, akkor a kifejezések fogalmak . $C$ $R$ $\forall RC$ $\exists RC$

Szigorúan véve ez nem egy logika, hanem egy logikák családja, ahol ennek a családnak minden egyes logikáját az atomi fogalmak és szerepek meghatározott halmazai határozzák meg. Ez hasonló egy elsőrendű elmélet aláírásának meghatározásához. Ezt a megkülönböztetést azonban általában figyelmen kívül hagyják. $\mathcal{ALC}$

Szemantika

A leírási logika szemantikáját az adja, hogy atomi fogalmait objektumok halmazaként („egyedek”), amelyeket valamilyen rögzített halmazból („domain”), az atomi szerepeket pedig egyedpárok halmazaként értelmezzük, vagyis a tartomány bináris relációit . .

Formálisan az értelmezés egy nem üres halmazból (tartományból) és egy értelmező függvényből áll, amely minden atomfogalomhoz leképez egy részhalmazt , és minden egyes atomi szerepkört a részhalmazára képez le . Ha egy egyedpár tartozik valamilyen szerep értelmezéséhez , akkor az egyént az egyén követőjének mondjuk . $\mathcal{I}$ $\Delta^\mathcal{I}$ $A$ ${A^\mathcal{I}\subseteq\Delta^\mathcal{I}}$ $R$ ${R^\mathcal{I}\subseteq\Delta^\mathcal{I}\times\Delta^\mathcal{I}}$ $R$ $(e,d)\in R^\mathcal{I}$ $d$ $R$ $e$

Továbbá az értelmezési funkció az összetett fogalmakra és szerepekre is kiterjed. Mivel az utóbbiak minden DL-ben eltérőek, példaként tekintsük a fent leírt logika szemantikáját . $\mathcal{ALC}$

Például az ALC esetében az értelmező funkciót kiterjesztjük a logika összetett fogalmaira a következő szabályok szerint: $\mathcal{ALC}$

$\top$ a teljes tartományként értelmezve: $\top^\mathcal{I}=\Delta^\mathcal{I}$
$\bot$ üres halmazként értelmezve: $\bot^\mathcal{I}=\varnothing$
a fogalom komplementerét a halmaz komplementereként értelmezzük: $(\neg C)^\mathcal{I}=\Delta^\mathcal{I}\setminus C^\mathcal{I}$
a fogalmak metszetét halmazok metszéspontjaként értelmezzük: $(C\sqcap D)^\mathcal{I}=C^\mathcal{I}\cap D^\mathcal{I}$
a fogalmak unióját halmazok uniójaként értelmezzük: $(C\sqcup D)^\mathcal{I}=C^\mathcal{I}\cup D^\mathcal{I}$
a kifejezést azoknak az egyéneknek a halmazaként értelmezzük, amelyekben minden -követő a fogalom értelmezéséhez tartozik . Formálisan: $\forall RC$ $R$ $C$

(\forall RC)^\mathcal{I} = \{\,e\in\Delta^\mathcal{I} \mid \forall d\in\Delta^\mathcal{I}:\ (e,d)\ in R^\mathcal{I} \Jobbra d\in C^\mathcal{I} \,\}

a kifejezést azon személyek halmazaként értelmezzük, akiknek a fogalom értelmezéséhez tartozó -követőjük van . Formálisan: $\exists RC$ $R$ $C$

(\exists RC)^\mathcal{I} = \{\,e\in\Delta^\mathcal{I} \mid \exists d\in\Delta^\mathcal{I}: (e,d)\in R^\mathcal{I} \land d\in C^\mathcal{I} \,\}

Példa: ha az értelmezési tartomány minden emberből áll, akkor az atomfogalom férfiemberek halmazaként értelmeződik, a szerep pedig relációként „szülő”. Ekkor a fogalom olyan emberek halmazaként lesz értelmezve, akiknek minden fiúgyermeke van, a fogalmat pedig az „apák” halmazaként, vagyis olyan férfiakként, akiknek legalább egy gyermekük van. $\Delta^\mathcal{I}$ $M$ $R$ $\forall RM$ $M\sqcap\exists R.\top$

Kapcsolat a modális logikával

1991-ben [6] megállapították, hogy a logika nem más, mint más jelöléssel írt , független modalitásokkal rendelkező modális logika . Ugyanis, ha a -ban vannak atomi fogalmak és atomi szerepek , akkor a logikák közötti megfeleltetés a következőképpen történik: $\mathcal{ALC}$ $\mathbf{K}_n$ $n$ $\mathcal{ALC}$ $A_1,\ldots,A_m$ $R_1,\ldots,R_n$

az atomi fogalmak átmennek a modális logika propozíciós változóiba ; $A_{i}$ $p_{i}$
a fogalmak metszéspontja , egyesülése és összeadása Boole-féle konnektívumokká alakul konjunkció , diszjunkció és tagadás ; $\sqcap$ $\sqcup$ $\neg$ $\föld$ $\lor$ $\neg$
kifejezés megy és kifejezés megy . $\forall R_j$ $\Box_j$ $\exists R_j$ $\Diamond_j$

Például egy fogalom egy modális képletbe kerül . Egy ilyen transzformációval a logika bármely összetett fogalma a modális logika jól kialakított formulájává válik , és bármely modális formula valamilyen fogalom fordítása (tehát ez ugyanaz a nyelv, csak két különböző jelölési rendszerben van írva). Ráadásul ez az átalakítás összhangban van egyrészt a logika fentebb leírt szemantikájával, másrészt a modális logika Kripke-féle szemantikájával . $\exists R_1.(A_1\sqcup\forall R_2.\neg A_2)$ $\Diamond_1(p_1\lor\Box_2p_2)$ $\mathcal{ALC}$ $\mathbf{K}_n$ $\mathcal{ALC}$

Ez a technika, mind a két leírt logikára, mind azok különféle kiterjesztésére alkalmazva lehetővé teszi, hogy a leírási logikák területére a modális logikákkal kapcsolatos számos ismert tényt átvigyünk, például eldönthetőségükről , számítási összetettségükről , feloldási eljárásokról és egyéb fontos tulajdonságaikról. (a modellek végessége, faszerűségi modellek stb.).

A predikátumlogikához való viszony

Számos leíró logika, köztük a , a predikátumok logikájának töredékének tekinthető a fogalmak „természetes” predikátumképletekre történő fordításában. Ha vannak atomi fogalmak és atomi szerepek , akkor az egyhelyű állítmány szimbólumokat és a kéthelyes állítmány szimbólumokat vezetjük be a fordításhoz , és magát a fordítást induktív módon adjuk meg a következőképpen: $\mathcal{ALC}$ $\mathcal{ALC}$ $A_1,\ldots,A_m$ $R_1,\ldots,R_n$ $P_1,\ldots,P_m$ $S_1,\ldots,S_n$

az atomfogalmak képletekre mennek át ; $A_{i}$ $P_{i}(x)$
a fogalmak metszéspontja , egyesülése és összeadása Boole-féle konnektívumokká alakul konjunkció , diszjunkció és tagadás ; $\sqcap$ $\sqcup$ $\neg$ $\föld$ $\lor$ $\neg$
kifejezés megy ; $\forall R_j.C$ $\forall y (S_j(x,y)\Jobbra C'(y))$
kifejezésre megy . $\exists R_j.C$ $\exists y (S_j(x,y)\land C'(y))$

Az utolsó két bekezdésben a változó friss (korábban nem találkoztunk vele), de a fogalom fordítása (amelyet az indukciós feltételezés szerint már felépítettünk). $y$ $C'$ $C$

Egy ilyen fordítás összhangban van a leíró logika szemantikájával, vagyis bármely értelmezésben, ha az atomi fogalmakat és atomi szerepeket ugyanúgy értelmezzük, mint a megfelelő predikátumokat és , akkor bármely összetett fogalmat ugyanaz a halmaz értelmez, mint a megfelelőt. predikátum formula egy változóból. Azt is meg kell jegyezni, hogy nem minden predikátumlogika formulája valamilyen fogalom fordítása; például a képlet nem. $A_{i}$ ${\displaystyle R_{j))$ $P_{i}$ $S_j$ $\forall x P_1(x)$

Ez a fordítás csak két változóval boldogul [7] , és így (valamint számos kiterjesztése) egy kétváltozós predikátumlogika töredékének tekinthető, amelyről ismert, hogy eldönthető [8] . Ez a fordítás lehetővé teszi számunkra, hogy a megoldhatóságra, a számítási bonyolultságra, a feloldó algoritmusokra stb. vonatkozó eredményeket átvigyük az predikátum logika tartományából a leírási logikák tartományába. $\mathcal{ALC}$

Tudásbázis

A leírási logika fogalmai nem annyira önmagukban érdekesek, hanem mint eszköz a leírt tárgykörrel kapcsolatos ismeretek rögzítésére . Ez az ismeret a fogalmakkal és kapcsolataikkal kapcsolatos általános ismeretekre ( intenzionális tudás) és az egyes objektumokról, azok tulajdonságairól és más objektumokkal való kapcsolatairól ( extenzionális tudás) vonatkozó ismeretekre oszlik . Az előbbiek stabilabbak és állandóbbak, míg az utóbbiak jobban módosulnak.

Ennek a felosztásnak megfelelően a leírási logikák nyelvén rögzített tudás a következőkre oszlik:

terminológiai axiómák halmaza vagy és $TBox{\mathcal {T}}$
egyénekre vonatkozó állítások halmaza vagy . $ABox{\mathcal {A}}$

Az axiómák és állítások együttese alkotja az úgynevezett tudásbázist . $\mathcal{K}=\mathcal{T}\cup\mathcal{A}$

Terminológiai axiómák

A beágyazó axióma a forma kifejezése, a fogalom ekvivalencia axióma pedig a forma kifejezése , ahol és tetszőleges fogalmak. Hasonlóképpen, a szerepbeágyazási axióma a forma kifejezése, a szerepekvivalencia axióma pedig a forma kifejezése , ahol és tetszőleges szerepek. Itt van egy fészkelő szimbólum. $C\sqsubseteq D$ $C\equiv D$ $C$ $D$ $R\sqsubseteq S$ $R\equiv S$ $R$ $S$ $\sqsubseteq$

A terminológia vagy terminológiai axiómák halmaza a felsorolt típusú axiómák véges halmaza. Néha a szerepekre vonatkozó axiómákat külön halmazba osztják, és szerephierarchiának vagy . A felsorolt axiómatípusokon kívül más axiómák (például a szerepek tranzitivitása) is megengedettek a terminológiában. $TBox$ $RBox$

A terminológia szemantikája természetes módon meghatározott. Adjunk egy értelmezést . Az axióma teljesül az értelmezésben , ha ; ebben az esetben is axiómamodellnek mondják . Hasonlóan más típusú axiómákhoz is. A terminológia az értelmezésben történik , és az értelmezést terminológiai modellnek nevezzük, ha az összes benne szereplő axióma modellje. $\mathcal{I}$ $C\sqsubseteq D$ $\mathcal{I}$ $C^\mathcal{I}\subseteq D^\mathcal{I}$ $\mathcal{I}$ $C\sqsubseteq D$ $\mathcal{T}$ $\mathcal{I}$ $\mathcal{I}$ $\mathcal{T}$ $\mathcal{I}$ $\mathcal{T}$

Például a következő gyűjtemény terminológia (vagy TBox) a logika nyelvén : $\mathcal{ALC}$

\mathsf{Nő}\equiv\mathsf{Személy}\sqcap\mathsf{Nő}

\mathsf{Anya}\equiv\mathsf{Woman}\sqcap\exists\mathsf{hasChild}.\top

\forall {\mathsf {hasChild}}.{\mathsf {Person}}\sqsubseteq {\mathsf {Személy}}

\mathsf{Doktor}\sqsubseteq\mathsf{Személy}

Intuitív módon (vagyis a „természetes” értelmezés szerint, amikor a fogalom az összes ember halmazának, a szerep a „gyermeke van” kapcsolatnak stb.) azt mondják, hogy nőnek lenni pontosan azt jelenti, embernek és nőnek lenni; anyának lenni pontosan annyit jelent, mint nőnek lenni és gyereket szülni; minden ember számára minden gyermek egyben személy is; minden orvos ember. Az első két axióma együtt példát ad az úgynevezett aciklikus terminológiára . $\mathsf{személy}$ $\mathsf{hasChild}$

Nyilatkozatok egyénekről

A terminológiák lehetővé teszik a fogalmakról és szerepekről szóló általános ismeretek rögzítését. Ezen túlmenően azonban általában megkövetelik az egyes személyekről szóló ismeretek rögzítését is: milyen osztályba (fogalomba) tartoznak, milyen kapcsolatokat (szerepeket) kapcsolnak egymáshoz. Ez a DL tudásbázis azon részében történik, amelyet hívnak (vagy az egyénekre vonatkozó állítások halmazában). $ABox$

Ennek érdekében az atomfogalmak és atomi szerepek, azaz az osztály- és relációnevek mellett egy véges névhalmazt is bevezetnek az egyénekre. Az egyénekre vonatkozó kijelentések kétféleek:

kijelentés az egyénnek egy fogalomhoz való tartozásáról - vagy ként van írva ; $a$ $C$ $C(a)$ $a\colon C$
két személy és egy szerep kapcsolatára vonatkozó kijelentés - vagy vagy -ként van írva . $a$ $b$ $R$ $R(a,b)$ $(a,b)\colon R$ $a\,R\,b$

Végül az egyénekre vonatkozó állítások halmaza vagy (az angol assertional boxból ) e két típusú állítások végső halmaza. $ABox$

Egyes leírási logikák lehetővé teszik az űrlap utasításait is . $\neg R(a,b)$ $ABox$

Az ABox szemantikájának megadásához ki kell terjeszteni az értelmezését , mégpedig minden egyes névre, hogy a tartomány valamely elemét hozzárendeljük . Ekkor a vagy állítás teljesül az értelmezésben , ha vagy történik , ill. Azt mondják, hogy egy ABox egy értelmezésben hajtódik végre , és az értelmezés ennek az ABoxnak a modellje, ha az összes állítása teljesül az értelmezésben. $\mathcal{I}$ $a$ $a^\mathcal{I}\in\Delta^\mathcal{I}$ $C(a)$ $R(a,b)$ $\mathcal{I}$ $a^\mathcal{I}\in C^\mathcal{I}$ $(a^\mathcal{I},b^\mathcal{I})\in R^\mathcal{I}$ $\mathcal{I}$ $\mathcal{I}$

Például a következő gyűjtemény az egyénekre (vagy ABoxra) vonatkozó állítások halmaza a logika nyelvén : $\mathcal{ALC}$

\mathsf{Mária}\colon\mathsf{Woman}\sqcap\neg\mathsf{Doktor}

\mathsf{Mária}\colon\exists\mathsf{hasChild}.\mathsf{Nő}

\mathsf{Mária}\,\mathsf{hasChild}\,\mathsf{Péter}

\mathsf{Péter}\colon\mathsf{Doctor}\sqcap\forall\mathsf{hasChild}.\bot

Itt Mária és Péter egyének nevei. Intuitív módon ezek a kijelentések azt jelentik, hogy Mária nő, de nem orvos, van egy leánygyermeke, Péter is Mary gyermeke, Péter pedig orvos, és nincs gyereke.

Gyakran csak azokat az értelmezéseket veszik figyelembe, amelyek megfelelnek a nevek egyediségi konvenciójának . Ez azt jelenti, hogy az értelmezésnek a tartomány különböző elemeit kell társítania az egyének különböző neveihez. Az OWL nyelv alapértelmezés szerint nem rendelkezik ezzel a konvencióval, de vannak olyan konstrukciói, amelyek lehetővé teszik, hogy kifejezetten meghatározza, mely egyedi nevek azonosak vagy eltérőek.

Különbség az adatbázisoktól

Amellett, hogy a tudásbázisok kissé eltérő nyelven fogalmazódnak meg, mint az adatbázisok , fő különbségük abban rejlik, hogy a DL-ben a logikai levezetésben az úgynevezett nyitott világ feltételezést használják , míg az adatbázisokban a világ zárt . Ez utóbbi azt jelenti, hogy ha egy bizonyos állítás nem igaz, akkor azt feltételezzük, hogy hamis. A világ nyitottságának feltételezése ebben az esetben egy ilyen állítást nem tekint sem igaznak, sem hamisnak. Ez alapvetően befolyásolja, hogy egy adott tudásbázisból milyen tényeket tekintünk logikailag következőnek, és ebből adódóan magát a logikai következmény fogalmát is a DL-ben.

Kifejező leíró logikák

A logikának számos kiterjesztése van további konstruktorokkal a fogalmak, szerepek, valamint további axiómatípusok létrehozásához a -ban . Az eredményül kapott logikákhoz informális elnevezési konvenció tartozik, általában úgy, hogy a logika nevéhez betűket adnak, amelyek megfelelnek a nyelvhez hozzáadott konstruktoroknak. A leghíresebb kiterjesztések a [4] : $\mathcal{ALC}$ $TBox$

${\mathcal {F}}$	A szerepek funkcionalitása: a forma fogalmai , jelentése: legfeljebb egy -követő van $({\le}1\,R)$ $R$

$\mathcal{N}$	A szerepkör kardinalitási korlátai: a fajta fogalmak , jelentése: Nincs több követő $({\le}n\,R)$ $n$ $R$

$\mathcal{Q}$	A szerepek számosságának minőségi megszorításai: a forma fogalmai , jelentése: legfeljebb -követők vannak $({\le}n\,RC)$ $n$ $R$ $C$

$\mathcal{I}$	Fordított szerepek: ha van szerep, akkor az is szerep, vagyis egy bináris reláció megfordítása $R$ $R^{-}$

$\mathcal{O}$	Megnevezések: ha van egy egyed neve, akkor van egy egyelemű halmazt jelentő fogalom $a$ $\{a\}$

${\mathcal {H}}$	Szerephierarchia: A TBoxban engedélyezett szerepek egymásba ágyazási axiómái $R\sqsubseteq S$

$\mathcal{S}$	Tranzitív szerepek: A TBox lehetővé teszi az alak tranzitivitási axiómáit $\mathsf{Tr}(R)$

$\mathcal{R}$	A TBox-ban ( , ) szereplő szerepbeágyazás összetett axiómái aciklicitási feltétellel, ahol van szerepek összetétele $R\circ S\sqsubseteq R$ $R\circ S\sqsubseteq S$ $R\circ S$

${\megjelenítési stílus (D)}$	A nyelv kiterjesztése meghatározott domainekkel (adattípusokkal)

Például az inverz szerepekkel, felekezetekkel és szerepszám-korlátozásokkal kibővített logikát a következővel jelöljük . $\mathcal{ALC}$ $\mathcal{ALCIOQ}$

A betű nem adódik hozzá a logika nevéhez, hanem helyettesíti a benne lévő betűket . Így például az inverz szerepekkel (betű ), a szerepek számosságának minőségi korlátozásával (betű ), tranzitív szerepekkel (betű ) és szerephierarchiával (betűvel ) kibővített logikának a neve . Minden betű eredete világosan kiderül a kivitelezők angol nevéből; a betűt azért választottuk, mert a kapott DL szorosan kapcsolódik a modális logikához [6] (bár ez utóbbiban az S betű egyszerűen rendszert jelent, a 4 -es szám különbözteti meg magát a logikát a többi modális logikától ). $\mathcal{S}$ $\mathcal{ALC}$ $\mathcal{ALC}$ $\mathcal{I}$ $\mathcal{Q}$ $\mathcal{S}$ ${\mathcal {H}}$ $\mathcal{SHIQ}$ $\mathcal{S}$ $\mathbf {S4}$ $\mathbf {S4}$

Ha a logika a , és a vagy vagy betűket tartalmazza , akkor a fogalmak felépítésének szabálya további megszorítást jelent: az űrlap fogalmaiban nem használhatók olyan szerepek , amelyek (az RBox axiómák szempontjából) tranzitív al- szerepeket. Ha ezeket a korlátozásokat nem szabják meg, akkor a logika eldönthetetlenné válik . [9] $\mathcal{S}$ ${\mathcal {H}}$ $\mathcal{Q}$ $\mathcal{N}$ $({\le}n\,RC)$ $R$

A leíró logikákat is figyelembe veszik, amelyekben lehetőség van összetett szerepek felépítésére az egyesülés, metszés, összeadás, inverzió, kompozíció, tranzitív lezárás és egyebek segítségével. Ezen túlmenően a többhelyes (n-áris relációt jelölő) szerepkörrel rendelkező DL-eket vizsgálják. [négy]

Logikai elemzés

A leírási logikák nyelvén megfogalmazott tudásbázisok nem csak a tárgykörrel kapcsolatos ismeretek reprezentálására szolgálnak, hanem a tudás logikai elemzésére ( angol érvelés ) is, például ellentmondásmentesség ellenőrzésére, új ismeretek levezetésére a meglévőkből, tudásbázisok kérésének biztosítása (az adatbázisok lekérdezéseivel analóg módon). Tekintettel arra, hogy a DL tudásbázisok formalizált formában vannak megírva, szigorú logikai következtetés vonható le. És mivel a leírási logikák szintaxisa és szemantikája úgy van felépítve, hogy a fő logikai problémák megoldhatók legyenek, az új ismeretek levezetése számítógépes eszközökkel - speciális programokkal ( gondolkodókkal ) valósítható meg.

A logikai elemzés néhány definíciója:

ennek a logikának a fogalma végrehajtódik az értelmezésben , ha ; $C$ $\mathcal{I}$ $C^\mathcal{I}\ne\varnothing$
egy fogalmat kielégítőnek nevezünk, ha van olyan értelmezés, amelyben teljesül; $C$
a fogalom be van ágyazva a fogalomba (vagy benne van; az eng.-t a ) foglalja magában, ha bármely értelmezésben igaz . $C$ $D$ $\mathcal{I}$ $C^\mathcal{I}\subseteq D^\mathcal{I}$

Hasonló fogalmak bevezethetők néhány adott TBox esetében, az adott TBox modelljére korlátozva. Például egy koncepciót kielégítőnek mondunk egy TBox vonatkozásában, ha van egy olyan értelmezés, amely ennek a TBoxnak a modellje, amelyben a koncepció végrehajtásra kerül. $\mathcal{T}$ $C$ $\mathcal{T}$

Ha nem csak a TBox van megadva , hanem az ABox is , ami azt jelenti, hogy van tudásbázis , akkor egy másik fogalom merül fel: $\mathcal{T}$ $\mathcal{A}$ $\mathcal{K}=\mathcal{T}\cup\mathcal{A}$

az egyén a fogalom egy példánya a tudásbázis tekintetében, ha jelen van a tudásbázis bármely modelljében . $a$ $C$ $\mathcal{K}$ $\mathcal{I}$ $\mathcal{K}$ $a^\mathcal{I}\in C^\mathcal{I}$

A következő fogalmak formalizálják az adott leíró logikához kapcsolódó kulcsfontosságú algoritmikus problémákat:

koncepció kielégíthetőség: kielégíthető-e az adott koncepció az adott TBox vonatkozásában?
fogalmak egymásba ágyazása: igaz, hogy egy adott fogalom egy másikba van beágyazva egy adott TBoxhoz képest?
TBox kompatibilitás: Van egy adott TBoxnak legalább egy modellje?
tudásbázis kompatibilitás: az adott párnak (TBox, ABox) van legalább egy modellje?

A -t tartalmazó logikákban a fogalombeágyazási probléma a fogalom kielégíthetőségére redukálódik. [4] A nem szabványos algoritmikus problémák nagy gyakorlati jelentőséggel bírnak, különösen: $\mathcal{ALC}$

terminológia osztályozása: egy adott terminológiához (azaz TBoxhoz) építsen fel taxonómiát vagy fogalomhierarchiát, azaz rendezze az összes atomi fogalmat egymásba ágyazás szempontjából (egy adott TBoxhoz viszonyítva), és adja vissza a megfelelő részben rendezett halmazt ;
fogalompéldányok kinyerése: egy adott fogalom összes példányának megkeresése adott tudásbázishoz viszonyítva;
a legszűkebb fogalom egyedre vonatkozóan: keresse meg a legkisebb (beágyazással) fogalmat, amelynek egy példánya egy adott egyed egy adott tudásbázishoz képest;
válasz egy lekérdezésre a tudásbázisnak: az egyedek összes olyan halmazát adja vissza, amely az adott tudásbázishoz képest kielégíti az adott lekérdezést . Jelenleg mélyrehatóan tanulmányozták a leírási logikák tudásbázisainak ún. konjunktív lekérdezéseit (valamint azok diszjunkcióit), amelyek hasonlóak az adatbázisok területéről származó hasonló lekérdezésekhez ; általánosabb formájú lekérdezések esetén a probléma gyorsan nagy számítási komplexitásra tesz szert, vagy akár megoldhatatlanná is válik [10] [11] .

Tulajdonságok

Egy adott leíró logika alapvető jellemzői a következők:

feloldhatóság : általában figyelembe veszi a koncepció megvalósíthatósági problémáinak megoldhatóságát (TBox tekintetében), tudásbázis kompatibilitást, konjunktív lekérdezésekre adott választ;
számítási komplexitás : a fenti algoritmikus problémák számítási bonyolultságát a bemeneti adatok (fogalom, TBox, ABox) méretére vonatkozóan tanulmányozzuk. Külön kiemelik a koncepció megvalósíthatósági problémájának összetettségét fix TBox esetén, a tudásbázis megvalósíthatósági problémájának összetettségét vagy a kérések fix TBox-szal és változó ABox-szal történő megválaszolásának problémáját (az ún. adatkomplexitás ) .
modell végességi tulajdonsága (teljesség a véges modellekre vonatkozóan): azt a kérdést vizsgáljuk, hogy vajon mindig igaz-e, hogy ha egy koncepció megvalósítható (TBox tekintetében), akkor valamilyen véges modellen is megvalósítható (adott TBox) ; ennek a tulajdonságnak egy adott logikában való jelenlétéből általában az következik, hogy könnyebb feloldó eljárást építeni rá, például eredménytábla algoritmust ;
famodell tulajdonság (teljesség a famodellek tekintetében, angol famodell tulajdonság ): hasonló kérdés, de nem véges, hanem „fa” modellekkel kapcsolatban, míg a hagyományos fakoncepciótól némileg eltérő szerkezetek jöhetnek szóba. faszerű itt ; például hurkok (egy csúcsból ugyanabba a csúcsba vezető élek), több élek (több különböző "típusú" él, amely egyik csúcsból a másikba vezet), tranzitív fák (struktúrák, amelyek a közönséges fák tranzitív lezárását jelentik), mint pl. valamint ezek kombinációi is megengedhetők ; Az ezzel a tulajdonsággal rendelkező logikák általában alacsonyabb számítási bonyolultságúak, különösen a feloldó eredménytábla algoritmus egyszerűbb felépítésű .

A különféle leírási logikák ezen tulajdonságaival kapcsolatban számos eredmény született [12] .

Kapcsolat az OWL-lel

Az OWL web ontológia nyelvét olyan nyelvként fejlesztik, amelyen úgynevezett hálózati ontológiák fogalmazhatók meg és publikálhatók a weben – formálisan megírt kijelentések egy bizonyos témakör fogalmairól és tárgyairól. Az ilyen ontológiákkal szemben támasztott egyik követelmény, hogy a bennük található tudás „elérhető” legyen a gépi feldolgozáshoz, különösen a meglévőkből új ismeretek automatikus következtetéséhez. Ez megköveteli, hogy a nyelv, amelyen az ontológiákat megfogalmazzák, pontos szemantikával rendelkezzen, és a megfelelő logikai problémák megoldhatók legyenek (és gyakorlatilag elfogadható számítási összetettséggel rendelkezzenek). Ezenkívül kívánatos, hogy egy ilyen nyelv meglehetősen nagy kifejezőerővel rendelkezzen, amely alkalmas gyakorlatilag jelentős tények megfogalmazására.

A leírási logikák rendelkeznek ezekkel a tulajdonságokkal, ezért választottuk őket az OWL web ontológia nyelv logikai alapjául. Ez utóbbi egy XML -formátumú nyelv , így az OWL-ről elmondható, hogy néhány DL újrafogalmazása XML szintaxist használva. Mivel sok DL létezik, amelyek mind kifejezőerőben, mind számítási bonyolultságban változnak, ez több változathoz vezetett az OWL-ben.

Az OWL leírási logikáiban elérhető „fogalom”, „szerep”, „egyén” és „tudásbázis” fogalmak megfelelnek az „osztály”, „tulajdon”, „objektum” és „ontológia” fogalmának.

A hivatalos W3C 2004. február 10- i ajánlás az OWL 1.0 . Ez az OWL nyelvi specifikáció a következő változatokra oszlik:

OWL-Lite - megfelel a leírási logikának ; $\mathcal{SHIF}(D)$
OWL-DL - megfelel a leírási logikának ; $\mathcal{SHOIN}(D)$
OWL-Full - nem felel meg semmilyen leíró logikának, ráadásul eldönthetetlen.

Az OWL 1.1 nyelv új verziója, amely a munkatervezet stádiumában van, lefedi a leírási logikát , amely magában foglalja a logikát , a TBox-ban lévő szerepek egymásba ágyazásának összetett axiómáit ( a logika nevében lévő betűt), valamint mint a szerepek diszjunktásának, reflexivitásának, irreflexivitásának és aszimmetriájának axiómái, az univerzális szerep (értelmezése szerint ) , a fogalom megalkotója ( önmaguk -követőinek halmazaként értelmezve) és megengedi az állításokat az ABoxban [13] . $s\mathcal{ROIQ}(D)$ $\mathcal{SHOIQ}(D)$ $\mathcal{R}$ $\Delta^\mathcal{I}\times\Delta^\mathcal{I}$ $\exists R.\mathsf{Self}$ $R$ $\neg R(a,b)$

Ezzel párhuzamosan készül az OWL 2.0 nyelv következő verziója, amely a fentieken túl lehetővé teszi az ontológiák megfogalmazását a leíró logikának megfelelő nyelven (amelynek előnye, hogy polinomiális számítási képességgel rendelkezik). bonyolultság); szintaktikai fejlesztéseket fog hozni, amelyek megkönnyítik a tudásbázisok lekérdezését és az azokra adott válaszok kiadását; és tartalmazni fogja a következtetési szabályok megfogalmazására szolgáló mechanizmusokat is [14] . $\mathcal{EL}$

Kimeneti motorok és szerkesztők

Számos szoftverrendszer ( következtető motor ) lehetővé teszi a logikai elemzés végrehajtását a leírási logikákban (az ontológia konzisztenciájának ellenőrzése, taxonómiák felépítése, a fogalmak megvalósíthatóságának és egymásba ágyazásának ellenőrzése, tudásbázisok lekérdezése stb.). Az ilyen rendszerek különböznek a támogatott leírási logikákban, a bennük megvalósított engedélyezési eljárás típusában (például eredménytábla algoritmus , felbontás stb.), a támogatott adatformátumokban, a programozási nyelvben, amelyen implementálják őket, és egyéb paraméterek. Néhány jól ismert lehetséges rendszer [15] :

CEL - támogatja a polinomiális komplexitású logikát, Lisp [16] -ban írva ; $\mathcal{EL}+$
FaCT++ - támogatja a logikát , valamint az OWL 2.0-t, egy eredménytábla algoritmust valósít meg, C++ nyelven írva [17] ; $s\mathcal{ROIQ}(D)$
Kaon2 - támogatja a speciális következtetési szabályokkal bővített logikát , felbontás alapú algoritmust valósít meg, Java nyelven írva [18] ; $\mathcal{SHIQ}$
Pellet - támogatja a logikát , valamint az OWL 1.1-et, egy eredménytábla algoritmust valósít meg, Java nyelven írva [19] ; $s\mathcal{ROIQ}(D)$
RacerPro - támogatja a logikát , egy eredménytábla algoritmust valósít meg, Lisp [20] nyelven írva . $\mathcal{SHIQ}(D)$

Léteznek olyan ontológiaszerkesztők is, amelyek lehetővé teszik ontológiák létrehozását, különféle formátumokban történő elmentését, némelyikük lehetővé teszi egy érvelő blokk csatlakoztatását és az ontológia logikai elemzésének elvégzését. Az egyik leghíresebb a Protégé ontológiaszerkesztő , amely lehetővé teszi az OWL Full nyelvű ontológiákkal való munkát.

Jegyzetek

↑ Lapshin V. A., Ontológiák számítógépes rendszerekben. RSDN Magazin, 2009. 4 . Hozzáférés dátuma: 2012. október 21. Az eredetiből archiválva : 2013. február 26. (határozatlan)
↑ Russell, Norvig, 2006 , p. 482.
↑ Leíró logikai kézikönyv, 2003 , Alapvető leírási logikák, pp. 43-95.
↑ 1 2 3 4 Baader, F.; Calvanese, D.; McGuinness, D.L.; Nardi, D.; Patel-Schneider, PF, szerk. The Description Logic Handbook (neopr.) . - New York: Cambridge University Press , 2003. - ISBN 0-521-78176-0 .
↑ Schmidt-Schauß, M.; Smolka, G. Attributív fogalomleírások kiegészítésekkel (neopr.) // Mesterséges intelligencia. - 1991. - T. 48 . - S. 1-26 .
↑ 1 2 Schild, K. Egy korrespondenciaelmélet a terminológiai logikákhoz: Előzetes jelentés // In Proc. 12. Int. Közös Konf. a mesterséges intelligenciáról (IJCAI'91). : folyóirat. - 1991. - P. 466-471 .
↑ Lutz, C.; Sattler, U.; Wolter, F. A modális logikák és a kétváltozós töredék (neopr.) // Az Európai Számítástudományi Logikai Szövetség éves konferenciájában (CSL'2001). – 2001.
↑ Grädel, E.; Ottó, M.; Rosen, E. Kétváltozós logika számlálással eldönthető (határozatlan) // In Proc. a 12. IEEE Symp. a logikáról a számítástechnikában (LICS'97). - 1997. - S. 306-317 . .
↑ Horrocks, I.; Sattler, U.; Tobies, S. Gyakorlati érvelés az expresszív leírási logikákhoz // In Proc. 6. Int. Programozási logika és automatizált érvelés (LPAR'99) konferencia: folyóirat. - 1999. - P. 161-180 .
↑ Tessaris, S. Kérdések és válaszok: Érvelés és lekérdezés a leíráslogikában (PhD tézis ) . – Manchesteri Egyetem, 2001.
↑ Glimm, B.; Horrocks, I.; Lutz, C.; Sattler, U. Konjunktív lekérdezés válaszol a SHIQ leírási logikára // In Proc. 20. Int. Közös Konf. a mesterséges intelligenciáról (IJCAI 2007). : folyóirat. - 2007. - Vol. 31 . - P. 151-198 .
↑ Leírás Logic Complexity Navigator
↑ OWL 1.1 fejlesztői webhely . Letöltve: 2009. június 17. Az eredetiből archiválva : 2008. február 16.. (határozatlan)
↑ Új szolgáltatások az OWL 2.0-ban . Letöltve: 2009. június 17. Az eredetiből archiválva : 2009. június 26.. (határozatlan)
↑ DL-kimeneti gépek listája . Letöltve: 2017. május 4. Az eredetiből archiválva : 2015. október 27.. (határozatlan)
↑ C.E.L. _ Letöltve: 2009. június 17. Az eredetiből archiválva : 2009. szeptember 1.. (határozatlan)
↑ FaCT++ . Letöltve: 2009. június 17. Az eredetiből archiválva : 2009. június 6.. (határozatlan)
↑ Kaon2 . Letöltve: 2009. június 17. Az eredetiből archiválva : 2006. január 6.. (határozatlan)
↑ Pellet
↑ RacerPro . Letöltve: 2009. június 17. Az eredetiből archiválva : 2009. június 7.. (határozatlan)

Irodalom

Russell S., Norvig P. Mesterséges intelligencia: modern megközelítés. - M . : "Williams" kiadó, 2006. - 1408 p. — ISBN 5-8459-0887-6 .
Franz Baader és Diego Calvanese és eborah L. McGuinness és Daniele Nardi és Peter F. Patel-Schneider. A Leírólogikai kézikönyv: elmélet, megvalósítás és alkalmazások . - Cambridge University Press, 2003. - ISBN 0-521-78176-0 .

Linkek

Szótárak és enciklopédiák	nagy kínai

szemantikus web
Alapok	A világháló Internet Hipertext Adatbázis Szemantikus hálózatok Ontológiák Leírás logika
alszakaszok	Kapcsolt adatok adatháló Hiperadatok Üzleti szabály-végrehajtási kiszolgáló Adatterek
Alkalmazások	Szemantikus Wiki Szemantikus publikálás Szemantikus keresés Szemantikus számítástechnika szemantikus reklámozás Szemantikus érvelési mechanizmus szemantikai illesztés szemantikai leképező szemantikai bróker szemantikai elemzés szemantikus szolgáltatásorientált architektúra
Kapcsolódó témák	Folksonomia Könyvtár 2.0 Web 2.0 Linkek Információs architektúra Tudásmenedzsment kollektív intelligencia Tematikus térképek Gondolattérképezés metaadatokat Geocímkézés webtudomány
Szabványok	Szintaxis : RDF RDF/XML 3. jelölés Teknősbéka N-hármas JSON-LD SPARQL URI HTTP XML Sémák, ontológiák : RDFS BAGOLY Szabálycsere formátuma Szemantikus webszabály nyelve közös logika Schema.org Szemantikai megjegyzés : RDFa erDF GRDDL Mikroformátumok Mikroadatok Szótárak : DOAP FOAF SIOC Dublin mag SKOS ERNYŐVIRÁGZAT Előzmények : Egyszerű régi szemantikus HTML DAML+OLAJ

Logikák

Filozófia • Szemantika • Szintaxis • Történelem

Logikai csoportok

klasszikus logika	Arisztotelészi logika propozíciós logika Elsőrendű logika Másodrendű logika magasabb rendű logika
matematikai logika	halmazelmélet Modellelmélet Kiszámíthatóság elmélet Bizonyításelmélet és konstruktív matematika Lineáris logika formális rendszer természetes következtetés Sorozatszámítás Logikai algebra Releváns logika Deontikus logika intuicionista logika Lambek kalkulus
Nem klasszikus logika	intuicionizmus zavaros logika Szubstrukturális logika logika Leírás logika Többértékű logika Logikai szintézis Kötési logika Időbeli logika Modális logika ( Hibrid logika ) episztemikus logika
Filozófiai logika	Kritikus gondolkodás informális logika deduktív érvelés

Alkatrészek

Logikai szimbólumok listája