2
Contents I
Fogalmi h´ att´ er
9
1 Bevezet´ es
11
2 Mesters´ eges Intelligencia h´ att´ er 2.1 Intelligencia ´es intelligens viselked´es . . . . . . . 2.2 Turing teszt . . . . . . . . . . . . . . . . . . . . 2.3 Az emberi probl´emamegold´o gondolkod´as . . . . 2.4 A szakmai fejl˝od´es l´epcs˝ofokai . . . . . . . . . . 2.5 Mesters´eges intelligencia . . . . . . . . . . . . . 2.6 Algoritmikus megk¨ozel´ıt´es . . . . . . . . . . . . 2.6.1 Algoritmikusan megoldhat´o probl´em´ak . 2.6.2 Nem algoritmikus megoldhat´o probl´em´ak 2.7 Az MI ´es a klasszikus informatika . . . . . . . . 2.7.1 Alkalmaz´asi ter¨ uletek . . . . . . . . . . . 2.7.2 Az adatok term´eszete . . . . . . . . . . . 2.7.3 Az adatok pontoss´aga . . . . . . . . . . 2.7.4 A felmer¨ ult probl´ema megold´asa . . . . .
. . . . . . . . . . . . .
15 15 16 17 17 18 19 19 20 22 22 22 23 23
. . . . .
25 25 25 25 26 26
3 Fogalmi rendszerez´ es 3.1 Adat, inform´aci´o, ismeret fogalma 3.1.1 Adat . . . . . . . . . . . . 3.1.2 Inform´aci´o . . . . . . . . . 3.1.3 Tud´as vagy ismeret . . . . 3.2 A szak´ert˝o rendszer fogalma . . . 3
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . . . . . . . . . .
. . . . .
. . . . . . . . . . . . .
. . . . .
. . . . . . . . . . . . .
. . . . .
. . . . . . . . . . . . .
. . . . .
4
II
CONTENTS
Tud´ asalap´ u, szak´ ert˝ o rendszerek
4 Az 4.1 4.2 4.3 4.4 4.5 4.6
27
ismeretalap´ u rendszerek Az ismeretalap´ u rendszerek jellemz˝oi . . . . . . . . Az emberi tud´as ´es a szak´ert˝o rendszer o¨sszevet´ese . A szak´ert˝o rendszer el˝onyei . . . . . . . . . . . . . . A szak´ert˝o rendszer h´atr´anyai . . . . . . . . . . . . A szak´ert˝o rendszer tud´asszintje . . . . . . . . . . . Az ismeretalap´ u rendszerek fel´ep´ıt´ese . . . . . . . . 4.6.1 Ismeretb´azis . . . . . . . . . . . . . . . . . 4.6.2 K¨ovetkeztet˝og´ep . . . . . . . . . . . . . . . 4.6.3 Magyar´az´o alrendszer . . . . . . . . . . . . . 4.6.4 Ismeretb´azis fejleszt˝o alrendszer . . . . . . . 4.6.5 Felhaszn´al´oi fel¨ ulet . . . . . . . . . . . . . .
5 Ismeretszerz´ es 5.1 Ismeretszerz´es c´elja . . . . . . 5.2 Az ismeretszerz´es r´eszter¨ uletei 5.2.1 Szerepl˝ok . . . . . . . 5.3 Az ismeretszerz´es neh´ezs´egei . 5.4 A tud´asmegszerz´es m´odszerei
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
6 Ismeret´ abr´ azol´ as 6.1 Szab´alyalap´ u ismeretreprezent´aci´o . . . . . . . . 6.1.1 K¨ovetkeztet´esi strat´egi´ak . . . . . . . . . 6.1.2 Szab´alyalap´ u rendszerek ´ert´ekel´ese . . . 6.2 Szemantikus (asszociat´ıv) h´al´ok . . . . . . . . . 6.2.1 El˝ony¨ok . . . . . . . . . . . . . . . . . . 6.3 Keretalap´ u ismeretreprezent´aci´o . . . . . . . . . ¨ 6.3.1 Or¨okl˝od´es . . . . . . . . . . . . . . . . . 6.3.2 D´emonok . . . . . . . . . . . . . . . . . 6.3.3 A keretalap´ u ismeret´abr´azol´as el˝onyei . . 6.3.4 A keretalap´ u ismeret´abr´azol´as h´atr´anyai 6.3.5 P´elda . . . . . . . . . . . . . . . . . . . . 6.3.6 A hierarchikus strukt´ ur´ar´ol . . . . . . . 6.3.7 P´elda d´emon alkalmaz´as´ara . . . . . . .
. . . . .
. . . . . . . . . . . . .
. . . . .
. . . . . . . . . . . . .
. . . . . . . . . . .
. . . . .
. . . . . . . . . . . . .
. . . . . . . . . . .
. . . . .
. . . . . . . . . . . . .
. . . . . . . . . . .
29 29 30 30 31 31 32 32 32 32 34 34
. . . . .
37 37 37 38 38 39
. . . . . . . . . . . . .
41 42 43 48 52 55 57 60 61 62 62 62 64 67
CONTENTS
5
7 Le´ır´ o logik´ ak 7.1 Bevezet´es . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 A le´ır´o logik´ak kialakul´as´anak t¨ort´enete . . . . . . . . . 7.3 A le´ır´o nyelvek szintaxisa ´es szemantik´aja . . . . . . . . 7.3.1 A le´ır´o nyelvek szintaxisa . . . . . . . . . . . . . 7.3.2 P´eld´ak . . . . . . . . . . . . . . . . . . . . . . . 7.3.3 A le´ır´o nyelvek szemantik´aja . . . . . . . . . . . 7.3.4 Az ALCN R nyelv szemantik´aja . . . . . . . . . 7.4 Hierarchia a fogalmak ´es a szerepek k¨or´eben . . . . . . 7.4.1 Egyszer˝ u p´eld´ak al´arendel´esre . . . . . . . . . . 7.5 Az SHIQ nyelvcsal´ad . . . . . . . . . . . . . . . . . . 7.5.1 Az SHIQ . . . . . . . . . . . . . . . . . . . . 7.5.2 Az SHIQ nyelv szemantik´aja . . . . . . . . . . 7.6 A le´ır´o ismeretb´azis fogalma . . . . . . . . . . . . . . . 7.6.1 P´elda le´ır´o ismeretb´azisra . . . . . . . . . . . . 7.7 K¨ovetkeztet´esi elj´ar´asok egy le´ır´o ismeretb´azisban . . . 7.7.1 P´elda az egyedes´ıt´esre . . . . . . . . . . . . . . 7.8 Ny´ıltvil´ag ´es z´art vil´ag szemantika . . . . . . . . . . . . 7.9 A le´ır´o logika, a klasszikus logika ´es az objektum alap´ u ismeret´abr´azol´as . . . . . . . . . . . . . . . . . . . . . . 7.10 Alkalmaz´asok . . . . . . . . . . . . . . . . . . . . . . . 8 Az oszt´ alyoz´ as fogalm´ anak h´ al´ o alap´ u 8.1 Bevezet´es . . . . . . . . . . . . . . . 8.2 H´al´oelm´eleti alapfogalmak . . . . . . 8.2.1 A h´al´o fogalma . . . . . . . . 8.2.2 P´eld´ak . . . . . . . . . . . . . 8.2.3 A h´al´ok tulajdons´agai . . . . 8.2.4 Modul´aris h´al´ok . . . . . . . . 8.2.5 Disztribut´ıv h´al´ok . . . . . . . 8.2.6 Boole-algebra . . . . . . . . . 8.3 Fogalmi hierarchia . . . . . . . . . . 8.4 Az oszt´alyoz´asi elj´ar´as . . . . . . . . 8.4.1 Egy klasszifik´aci´os algoritmus 8.4.2 P´eld´ak . . . . . . . . . . . . . ¨ 8.5 Osszegz´ es . . . . . . . . . . . . . . .
bevezet´ ese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
69 69 71 72 72 73 75 75 78 79 79 79 80 81 82 84 84 86
. 87 . 89
. . . . . . . . . . . . .
87 87 88 88 89 90 92 92 93 94 95 96 97 98
6
CONTENTS
9 Bizonytalans´ agkezel´ es 103 9.1 Bevezet´es . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.2 A bizonytalans´agkezel´es m´odszereinek, modelljeinek oszt´alyoz´asa103 9.3 Numerikus modellek, a Bayes-t´etelen alapul´o m´odszer . . 105 9.3.1 K´ıs´erlet, esem´eny ´es ellentett esem´eny . . . . . . 105 9.3.2 M˝ uveletek esem´enyekkel, teljes esem´enyrendszer . 106 9.3.3 Val´osz´ın˝ us´egi m´ert´ek, felt´eteles val´osz´ın˝ us´eg, Bayes t´etele . . . . . . . . . . . . . . . . . . . . . . . . . 107 9.3.4 P´elda a Bayes m´odszer alkalmaz´as´ara . . . . . . . 108 9.4 Fuzzy logika . . . . . . . . . . . . . . . . . . . . . . . . . 111 9.4.1 Bevezet´es . . . . . . . . . . . . . . . . . . . . . . 111 9.4.2 Fuzzy halmazelm´elet . . . . . . . . . . . . . . . . 112 9.4.3 Lukasiewicz fuzzy logik´aja . . . . . . . . . . . . . 113 9.4.4 G¨odel fuzzy logik´aja . . . . . . . . . . . . . . . . 116 9.4.5 A fuzzy rendszerek ´ert´ekel´ese . . . . . . . . . . . 117 9.5 A Bayes m´odszer, a fuzzy modell ´es a heurisztikus modellek118 10 K¨ ovetkeztet˝ o rendszerek 119 10.1 K¨ovetkeztet´esi m´odok . . . . . . . . . . . . . . . . . . . . 119 10.1.1 Form´alis k¨ovetkeztet´es . . . . . . . . . . . . . . . 119 10.1.2 Procedur´alis k¨ovetkeztet´es . . . . . . . . . . . . . 119 10.1.3 Anal´ogi´an alapul´o k¨ovetkeztet´es . . . . . . . . . . 120 ´ 10.1.4 Altal´ anos´ıt´ason ´es absztrakci´on alapul´o k¨ovetkeztet´es120 10.1.5 Eset-alap´ u k¨ovetkeztet´es . . . . . . . . . . . . . . 120 10.1.6 K¨ozel´ıt˝o k¨ovetkeztet´es . . . . . . . . . . . . . . . 120 10.1.7 Hipotetikus k¨ovetkeztet´es . . . . . . . . . . . . . 120 10.1.8 Alap´ertelmez´esen alapul´o . . . . . . . . . . . . . . 120 10.1.9 Kvalitat´ıv k¨ovetkeztet´es . . . . . . . . . . . . . . 120 10.2 Hasonl´os´agon alapul´o k¨ovetkeztet´es . . . . . . . . . . . . 121 10.3 Eset alap´ u k¨ovetkeztet´es . . . . . . . . . . . . . . . . . . 122 10.3.1 A CBR ´eletciklusa . . . . . . . . . . . . . . . . . 124 10.4 CBR az OOKBR-ben . . . . . . . . . . . . . . . . . . . . 125 10.4.1 Objektum alap´ u ismeret´abr´azol´as . . . . . . . . . 126 10.4.2 Az esetek hierarchikus szervez´ese . . . . . . . . . 126 10.4.3 P´elda . . . . . . . . . . . . . . . . . . . . . . . . . 127 10.5 Eset visszakeres´es, adapt´aci´o . . . . . . . . . . . . . . . . 128 10.5.1 Eset visszakeres´es . . . . . . . . . . . . . . . . . . 128
CONTENTS 10.5.2 10.5.3 10.5.4 10.5.5 10.5.6
III
7 P´elda eset visszakeres´esre Adapt´aci´o . . . . . . . . . P´elda adapt´aci´ora . . . . . Gyenge oszt´alyoz´as . . . . P´elda gyenge oszt´alyoz´asra
Tud´ askezel´ esi technol´ ogi´ ak
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
129 130 130 130 131
135
´ 11 Agensek 137 11.1 Bevezet´es . . . . . . . . . . . . . . . . . . . . . . . . . . 137 11.2 Az a´gens sz´o eredete . . . . . . . . . . . . . . . . . . . . 138 11.3 Az a´gens ´altal´anos jelent´ese . . . . . . . . . . . . . . . . 138 ´ 11.4 Agens defin´ıci´ok . . . . . . . . . . . . . . . . . . . . . . . 139 11.5 Az a´gensek csoportos´´asa . . . . . . . . . . . . . . . . . 140 11.5.1 K¨olcs¨onhat´o ´agensek . . . . . . . . . . . . . . . . 140 ´ AGENSEK ´ 11.5.2 ADAPT´IV, TANULO . . . . . . . . . 140 ´ ´ ´ ´ REND11.6 AGENSEK ALKALMAZASA INFORMACIOS SZEREKBEN . . . . . . . . . . . . . . . . . . . . . . . . 144 ´ OI ´ MODELLEZES ´ AGENS ´ 11.6.1 FELHASZNAL RENDSZEREKBEN . . . . . . . . . . . . . . . . . . . . 145 ´ WWW-AGENSEK ´ 11.6.2 INTERNET ES . . . . . . . . 146 ´ 11.6.3 AGENSEK AZ ELEKTRONIKUS KERESKEDELEMBEN . . . . . . . . . . . . . . . . . . . . . . . . . 146 ´ ´ 11.6.4 INTERFESZ AGENSEK . . . . . . . . . . . . . . 147 11.6.5 ASSZISZTENSEK . . . . . . . . . . . . . . . . . 147 ´ AGENSEK ´ 11.6.6 OKTATO . . . . . . . . . . . . . . . 148 ´ 11.6.7 MOBIL AGENSEK . . . . . . . . . . . . . . . . . 148 ´ ´ AI ´ . . 152 11.6.8 A MOBIL ALKALMAZASOK PROBLEM ´ 11.6.9 TIPIKUS ALKALMAZASOK . . . . . . . . . . . 155 11.7 Strukt´ ur´ak ´es r´eszben-strukt´ ur´alt adatok . . . . . . . . . 156 11.7.1 R´eszben-strukt´ ur´alt adatok . . . . . . . . . . . . 156 11.8 Szemantikus web . . . . . . . . . . . . . . . . . . . . . . 162 11.8.1 A g´epekhez besz´el˝o Web . . . . . . . . . . . . . . 163 11.8.2 Alkalmaz´asok . . . . . . . . . . . . . . . . . . . . 165
8
CONTENTS
Part I Fogalmi h´ att´ er
9
68
Chapter 7 Le´ır´ o logik´ ak 7.1
Bevezet´ es
A le´ır´o logik´ak egy ismeret´abr´azol´asi nyelvcsal´adot alkotnak. A formalizmusukban a fogalom, individuum (egyed) ´es szerep fogalmak jelennek meg. A fogalom individuumok halmaz´anak reprezent´al´as´ara szolg´al, m´ıg a szerep az individuumok k¨oz¨otti bin´aris rel´aci´ot a´br´azolja. A fogalom az alkalmaz´asi ter¨ ulet egy a´ltal´anos, gener´al´o egys´ege, az individuum speci´alis, a fogalom megjelen´esi form´aja, annak tulajdons´agait viseli. A fogalom, szerep ´es individuum a k¨ovetkez˝o alapelveknek felelnek meg: • A fogalom ´es a szerep struktur´alis le´ır´as´aban konstruktorok vesznek r´eszt. A fogalom ´es a szerep le´ır´as´ahoz egy szemantika kapcsol´odik az interpret´aci´on kereszt¨ ul. A k¨ ul¨onb¨oz˝o m˝ uveleteket ezen szemantik´aval o¨sszhangban hajtjuk v´egre. • Az ismereteket k¨ ul¨onb¨oz˝o szinteken vessz¨ uk figyelembe. A fogalmak, szerepek a´br´azol´asa ´es m˝ uveleteik a terminol´ogia szintj´en, az individuumok le´ır´asa ´es m˝ uveleteik a t´enyek ´es a hozz´arendel´esek szintj´en jelennek meg. A szakirodalomban a terminol´ogia szintj´et TBox-nak, a t´enyek ´es a hozz´arendel´esek szintj´et ABoxnak nevezik. 69
70
´ LOGIKAK ´ CHAPTER 7. LE´IRO • A fogalmakat (´es esetenk´ent a szerepeket) hierarchi´aba rendezhetj¨ uk a rajtuk ´ertelmezett al´arendel´es (subsumption) rel´aci´o alapj´an. Azt mondhatjuk, hogy egy C fogalom al´arendeli a D fogalmat, ha C a´ltal´anosabb, mint D abban az ´ertelemben, hogy a D a´ltal reprezent´alt individuumok halmaz´at C tartalmazza. • A le´ır´o logik´ak k¨ovetkeztet˝orendszer´eben k´et m˝ uvelet jelenik meg: az oszt´alyoz´as (classification) ´es az egyedes´ıt´es (instanciation). Az oszt´alyoz´ast a fogalmakra ´es a szerepekre alkalmazzuk. Lehet˝ov´e teszi, hogy egy adott fogalom, vagy szerep hely´et meghat´arozzuk a hierarchi´aban. Az egyedes´ıt´es lehet˝ov´e teszi, hogy megtal´aljuk azt a fogalmat, amelynek egy adott individuum a megjelen´esi form´aja lehet. Ez a fogalom elt´er az objektum-orient´alt nyelvekben szok´asos egyedes´ıt´es fogalm´at´ol, hiszen ott egy adott oszt´alyb´ol hozunk l´etre egyedeket.
Adjunk n´eh´any kezdeti p´eld´at a le´ır´o logik´ak haszn´alat´anak bemutat´as´ara. Legyen EMBER egy fogalom-n´ev ´es van-gyereke egy szerep-n´ev. Ekkor a sz¨ ul˝o fogalmat a k¨ovetkez˝o kifejez´essel ´ırhatjuk le: EMBER u ∃ van-gyereke.EMBER ¨ O ˝ le´ır´oval hivatkozunk, ahol A k´es˝obbiekben erre a fogalomra a SZUL sz¨ ul˝onek nevez¨ unk egyedeknek olyan halmaz´at, akik emberek ´es le˝ fogalomgal´abb egy gyerek¨ uk van. Amennyiben bevevezetj¨ uk a NO nevet, az anya ´es apa fogalmakat a k¨ovetkez˝ok´eppen ´ırhatjuk le: ˝ u ∃ van-gyereke.EMBER EMBER u NO ˝ u ∃ van-gyereke.EMBER EMBER u ¬ NO K¨onnyen bel´athat´o, hogy a fogalomnevek un´aris, a szerepek bin´aris predik´atummal, a fogalom defini´al´o kifejez´esek egyv´altoz´os els˝orend˝ u formul´aval ´ırhat´ok le a klasszikus logik´aban. P´eld´aul, a sz¨ ul˝o fogalmat els˝orend˝ u formul´aval megadva: ember(x) ∧ ∃ y(van-gyereke(x,y) ∧ ember(y), ahol x szabad v´altoz´o. Egy adott interpret´aci´oban a sz¨ ul˝o jelent´es´et form´alisan u ´gy specifik´alhatjuk, mint egyedek egy halmaz´at, amely kiel´eg´ıti a megfelel˝o els˝orend˝ u formul´at a szabad v´altoz´oja helyettes´ıt´esekor. A le´ır´o logik´akon alapul´o ismeret´abr´azol´asi rendszerek f˝o jellemz˝oje az a k¨ovetkeztet˝o rendszer, amely az ismeretb´azisban t´arolt ismeretekb˝ol
´ LOGIKAK ´ KIALAKULAS ´ ANAK ´ ¨ ENETE ´ 7.2. A LE´IRO TORT
71
u ´jabb ismeretet vezet le. Tipikusan ez a k¨ovetkeztet˝orendszer egyr´eszt az al´arendel´es m´asr´eszt az egyedes´ıt´es rel´aci´okon alapul. Az el˝obbi p´eld´ankban a sz¨ ul˝o fogalom al´arendeli az anya ´es apa fogal¨ O ˝ ´es APA v SZUL ¨ O). ˝ makat (ANYA v SZUL A le´ır´o logik´an alapul´o rendszerek automatikusan ´eszlelik az al´arendel´esi rel´aci´okat ´es ennek megfelel˝oen a fogalmakat al´arendel´esi hierarchi´aban helyezik el.
7.2
A le´ır´ o logik´ ak kialakul´ as´ anak t¨ ort´ enete
A le´ır´o logik´ak t¨ort´enetileg a keretek ´es szemantikus h´al´ok ismeret´abr´azol´asi formalizmus´aban gy¨okereznek. Minthogy a keretek ´es a szemantikus h´al´ok nem rendelkeznek form´alis szemantik´aval, ez´ert a pontos ´ertelmez´es¨ uk az ˝oket implement´al´o programoz´ok feladata. P´eld´aul a sz´ıne B´eka
−→
Z¨old
szemantikus h´al´o ´ertelmez´ese k´erd´eses. Jelent´ese lehet: • Minden b´eka z¨old. • Minden b´eka r´eszben z¨old. • Vannak z¨old b´ek´ak. • A b´ek´ak tipikusan z¨oldek, de lehetnek kiv´etelek. Az al´abbi keret alap´ u ismeretr´eszletben is felmer¨ ulhetnek eld¨ontetlen k´erd´esek. Frame Ember endframe. Frame Magas-fi´ u-apja is-a Ember van-gyereke Magas endframe.
´ LOGIKAK ´ CHAPTER 7. LE´IRO
72 Frame Magas endframe. Frame Peter instance-of Magas-fi´ u-apja endframe.
Ebb˝ol az a´br´azol´asb´ol nem der¨ ul ki, hogy Magas-fi´ u-apja minden p´eld´any´anak az ¨osszes gyereke magas, vagy hogy minden ap´anak ebben az oszt´alyban van legal´abb egy magas gyereke. Ez a szemantikai hi´anyoss´ag ind´ıtott t¨obb kutat´ot is u ´jabb reprezent´aci´os ´ m´odszerek kialak´ıt´as´ara. Igy, Brachmann (1977)-ben ”struktur´alt ¨or¨okl´esi h´al´o” n´even u ´j grafikus reprezent´aci´os m´odszert dolgozott ki, s ennek a formalizmusnak az implement´aci´ojak´ent elk´esz´ıtette a KL-ONE rendszert, amelyet az els˝o le´ır´o logikai rendszernek tekinthet¨ unk. Az eredeti KL-ONE rendszert sz´amos tov´abbi k¨ovette, k¨oz¨ ul¨ uk kiemelked˝o jelent˝os´eg˝ u a LOOM (1991) ´es a CLASSIC (1991).
7.3 7.3.1
A le´ır´ o nyelvek szintaxisa ´ es szemantik´ aja A le´ır´ o nyelvek szintaxisa
Fogalmon az a´br´azoland´o vil´ag elemeit jelent˝o individuumok halmaz´at ´ertj¨ uk. Szerepen az individuumok k¨oz¨otti bin´aris rel´aci´ot ´ertj¨ uk. Le´ır´o nyelvnek nevezz¨ uk a (fogalom-nevek, individuum-nevek, szerep-nevek, konstruktorok) n´egyest, ahol a fogalom-nevek k¨ ul¨onb¨oz˝o fogalmakat, az individuumnevek individuumokat, a szerep-nevek pedig szerepeket szimboliz´alnak. A konstruktorok a k¨ovetkez˝ok lehetnek: konjunkci´o (u), diszjunkci´o (t), neg´aci´o (¬), univerz´alis kvantor (∀), egzisztenci´alis kvantor (∃), sz´amoss´ag-korl´atoz´as (≥n, ≤n). Az egyes konstruktorok a megfelel˝o defin´ıci´o szerint fogalom- ´es szerepneveket k¨otnek o¨ssze, ´es ´ıgy fogalom- ´es szerep-kifejez´esek j¨onnek l´etre. A fogalom-nevek o¨nmagukban fogalom-kifejez´esek. Ha C ´es D fogalom-
´ NYELVEK SZINTAXISA ES ´ SZEMANTIKAJA ´ 7.3. A LE´IRO
73
kifejez´es, akkor C∗D ´es ?C is fogalom-kifejez´esek, ahol ∗ valamely bin´aris, ? valamely un´aris konstruktor. A tov´abbiakban a fogalomneveket A, B, a szerep-neveket P, az individuumok nev´et a, b, o, a fogalom-kifejez´eseket C, D, a szerep-kifejez´eseket Q, R jel¨oli. A top (>) ´es bottom (⊥) speci´alis fogalmak; a top a leg´altal´anosabb, m´ıg a bottom a legink´abb specifikus fogalmat jel¨oli. A k¨ ul¨onb¨oz˝o le´ır´o nyelveket a megengedett konstruktorok hat´arozz´ak meg. Az alapnyelv az FL (frame-based description language), amely konjunkci´o, univerz´alis kvantor ´es a nem min˝os´ıtett egzisztenci´alis kvantor konstruktorokat tartalmaz. Ezen alapul a leg´altal´anosabban vizsg´alt AL nyelv, amely az el˝obbieken k´ıv¨ ul (azaz az FL-b˝ol sz´armaztatva) tartalmazza a top, bottom fogalmakat, valamint a fogalom-n´ev neg´aci´ot (azaz fogalom-n´ev neg´alhat´o, de fogalom-kifejez´es nem). Form´alisan AL={>, ⊥, ¬A, CuD, ∀R.C, ∃R}. Az AL nyelvcsal´adot a megengedett konstruktorokkal kieg´esz´ıtve kapjuk az AL[U][C][E][N ][R] nyelveket, ahol, U a diszjunkci´o, C a neg´aci´o, E az egzisztenci´alis kvantor, N a sz´amoss´ag-korl´atoz´as, R a szerep konjunkci´o konstruktorokat jel¨oli.
7.3.2
P´ eld´ ak
Ojektumok, oszt´ alyok Fejezz¨ uk ki Hallgat´o Szem´ely n´ev c´ım felvette
az al´abbi p´eld´at
: sztring : sztring : kurzus
klasszikus logikai formul´aval {x | hallgat´o(x)}={x | szem´ely(x) ∧ (∃yn´ev(x,y) ∧ string(y)) ∧ (∃zc´ım(x,z) ∧ string(z)) ∧ (∃wfelvette(x,w) ∧ kurzus(w))} le´ır´o logik´aban fogalom defin´ıci´oval ´ = SZEMELY ´ HALLGATO u ∃n´ev.STRING u ∃c´ım.STRING u ∃felvette.KURZUS
´ LOGIKAK ´ CHAPTER 7. LE´IRO
74 Ojektumok, egyedek
Fejezz¨ uk ki az al´abbi p´eld´at s1 : Hallgat´o n´ev : ”Jani” c´ım : ”Ak´acfa utca” felvette : I3102 le´ır´o logik´aban egyedhozz´arendel´essel ´ HALLGATO(s1) n´ev(s1,”Jani”) c´ım(s1, ”Ak´acfa utca”) felvette(s1, I3102) Szemantikus h´ al´ o Fejezz¨ uk ki az al´abbi p´eld´at felvette Hallgat´o Kurzus −→ -
tan´ıt ←− %
Oktat´o
Demonstr´ator le´ır´o logik´aban al´arendel´essel ´ v ∃ felvette.KURZUS HALLGATO ´ v ∃ tan´ıt.KURZUS OKTATO ´ ´ DEMONSTRATOR v HALLGATO ´ ´ DEMONSTRATOR v OKTATO
Nem pontosan defini´ alt szemantikus h´ al´ o Az al´abbi szemantikus h´al´o sz´ıne B´eka
Z¨old −→ k¨ ul¨onb¨oz˝o lehets´eges v´altozatai le´ır´o logik´aban:
´ ¨ • BEKA v ∃sz´ıne.ZOLD Minden b´eka r´eszben z¨old
´ NYELVEK SZINTAXISA ES ´ SZEMANTIKAJA ´ 7.3. A LE´IRO
75
´ ¨ • BEKA v ∀sz´ıne.ZOLD Minden b´eka z¨old ´ ¨ • BEKA(x), sz´ıne(x,y), ZOLD(y) Vannak z¨old b´ek´ak
7.3.3
A le´ır´ o nyelvek szemantik´ aja
A fogalmat az interpret´aci´os alaphalmaz r´eszhalmazak´ent, m´ıg a szerepet az alaphalmaz o¨nmag´aval alkotott Descartes szorzat´anak r´eszhalmazak´ent interpret´aljuk. • Az interpret´aci´os alaphalmaz (O) r¨ogz´ıt´es´evel az a individuum interpret´aci´oja aI ∈ O. • Az A fogalom-n´ev interpret´aci´oja AI ⊆ O. • A C fogalom C I interpret´aci´oja a C fogalmat alkot´o individuumok interpret´aci´oib´ol a´ll´o halmaz, azaz ha C={ci }, ahol i∈ indexhalmaz, akkor C I ={cIi }, teh´at C I ⊆ O. • A ∆I az ¨osszes C I halmaza, azaz az interpret´aci´os alaphalmaz (O) hatv´anyhalmaza. • Az R szerep interpret´aci´oja RI ⊆ O × O.
7.3.4
Az ALCN R nyelv szemantik´ aja
Egy I=(∆I , .I ) interpret´aci´o egy interpret´aci´os alaphalmaz ´es egy interpret´aci´os f¨ uggv´eny egy¨ uttese, ahol az .I interpret´aci´os f¨ uggv´eny I egy fogalomat hozz´arendel a ∆ egy r´eszhalmaz´ahoz ´es egy szerepet a ∆I × ∆I egy r´eszhalmaz´ahoz u ´gy, hogy a k¨ovetkez˝o azonoss´agok fenn´alljanak.
´ LOGIKAK ´ CHAPTER 7. LE´IRO
76 >I ⊥I (C u D)I (C t D)I (¬C)I (∀R.C)I (∃R.C)I (≥ nR)I (≤ nR)I (R1 u ...u Rn )I
= = = = = = = = = =
∆I 60 CI ∩ DI CI ∪ DI ∆I \ CI { a ∈ O | ∀ b : (a,b) ∈ RI → b ∈ C I } {a ∈ O | ∃ b : (a,b) ∈ RI ∧ b ∈ C I } {a ∈ O | {b ∈ O | (a,b) ∈ RI }|≥ n} {a ∈ O | {b ∈ O | (a,b) ∈ RI }|≤ n} RI1 ∩ ...∩ RIn
• A ∀ konstruktor korl´atoz´ast id´ez el˝o egy attrib´ utum ´ert´ekein. A (∀R.C) fogalom interpret´aci´oja olyan egyedek halmaza, mellyel minden R rel´aci´oban lev˝o egyed a C fogalomhoz tartozik. (∀gyereke.ORVOS) Megfelel egy fogalomnak, amelynek minden gyereke orvos. Ezzel a m´odszerrel egy keretben egy slot ´ert´ek´ere ´ırhatunk el˝o korl´atoz´ast. • A (∃R.C) fogalom interpret´aci´oja egy olyan (x,y) egym´assal R rel´aci´oban lev˝o, elemp´ar l´etez´es´et mondja ki, ahol y a C fogalom ´ egyede. P´eld´aul a (∃gyereke.ZENESZ) fogalom interpret´aci´oja azon egyedek halmaza, akiknek van zen´esz gyereke (ahol a gyerek(x,y) szerep jelent´ese y gyereke x-nek). Ezen az u ´ton vezethet¨ unk be egy slotot a keretbe. • A (≥ n R) fogalom interpret´aci´oja az R szerephez kapcsol´od´o egyedek halmaz´anak sz´amoss´ag´at korl´atozza. P´eld´aul a (≥ 3 gyerek) interpret´aci´oja jelenti azon egyedekb˝ol ´all´o halmazt, amelyben minden elemnek legal´abb 3 egyeddel van a gyerek szerepen kereszt¨ ul kapcsolata (azaz akiknek legal´abb 3 gyereke van). K´et fogalmat (C, D) ekvivalensnek nevez¨ unk (C ≡ D), ha CI = DI minden I interpret´aci´oban. Az egzisztenci´alis kvantornak (∃R.C) egy speci´alis esete a nem min˝os´ıtett egzisztenci´alis kvantor (∃R), amikor C ≡ >. Interpret´aci´oja: (∃R)I = {a ∈ O | ∃ b ∈ O : (a,b) ∈ RI }.
´ NYELVEK SZINTAXISA ES ´ SZEMANTIKAJA ´ 7.3. A LE´IRO Alapfogalmak fogalom-n´ev top bottom individuum-nevek (∆I ) szerep-n´ev
Szintaxis A > ⊥ {a1 , a2 , ..., an } P
77
Szemantika AI ⊆ ∆I ∆I 60 I I {a1 , a2 , ..., aIn } PI ⊆ ∆I × ∆I
Table 7.1: Le´ır´o logik´ak alapfogalmai Konstruktorok Szintaxis Szemantika konjunkci´o CuD CI ∩ DI diszjunkci´o (U) CtD CI ∪ DI neg´aci´o (C) ¬C ∆I \ CI univerz´alis kvantor ∀R.C {a1 | ∀a2 : (a1 , a2 ) ∈ RI → a2 ∈ CI } egzisztenci´alis kvantor (E) ∃R.C {a1 | ∃a2 : (a1 , a2 ) ∈ RI ∧ a2 ∈ CI } nem min˝os´ıtett ∃R {a1 | ∃a2 : (a1 , a2 ) ∈ RI ∧ a2 ∈ O} egzisztenci´alis kvantor sz´amoss´ag-korl´atoz´as (N ) (≥ n R) {a1 | {a2 | (a1 , a2 ) ∈ RI } ≥n} (≤ n R) {a1 | {a2 | (a1 , a2 ) ∈ RI } ≤n} Szerep konjunkci´o (R) QuR QI ∩ RI Table 7.2: Fogalom- ´es szerep-form´al´o konstruktorok Az 1. ´es 2. t´abl´azatok ¨osszefoglal´o k´epet adnak az alapfogalmak ´es konstruktorok jel¨ol´es-rendszer´er˝ol ´es ´ertelmez´es´er˝ol.
Sz´ amoss´ agkorl´ atoz´ asok A (≥ n R) ´es (≤ n R) sz´amoss´agkorl´atoz´asok jelent´ese azon egyedekb˝ol a´ll´o halmaz, amelyek mindegyik´ehez legal´abb n, illetve legfeljebb n k¨ ul¨onb¨oz˝o, vele R-kapcsolatban lev˝o egyed tal´alhat´o. Teh´at (≥ 1 R) sz´amoss´agkorl´atoz´as ekvivalens a (∃R.>) egyszer˝ u exisztenci´alis kvantor korl´atoz´assal. Azt is ´eszrevehetj¨ uk, hogy ezek a sz´amoss´agkorl´atoz´asok nem teszik lehet˝ov´e, hogy valamely fogalomhoz tartoz´o egyedek darabsz´am´ara tegy¨ unk korl´atoz´ast, azaz nem besz´elhet¨ unk a ”legal´abb 3 k´ekszem˝ u
´ LOGIKAK ´ CHAPTER 7. LE´IRO
78
gyerekkel b´ır´o” egyedek halmaz´ar´ol.
7.4
Hierarchia a fogalmak ´ es a szerepek k¨ or´ eben
Egy C fogalom al´arendeltje a D fogalomnak, (jel¨ol´esben: C v D), ha tetsz˝oleges I interpret´aci´o eset´en CI ⊆ DI . Az al´arendel´es rel´aci´o reflex´ıv, tranzit´ıv ´es antiszimmetrikus, teh´at egy parci´alis rendez´esi rel´aci´o, amely a fogalmakat egy hierarchi´aba szervezi. Ebben a hierarchi´aban a fogalmakat egyr´eszt saj´at lok´alis le´ır´ojuk jellemzi, m´asr´eszt az al´arendeltjeikkel megosztott le´ır´asuk (mint ahogyan az objektum-orient´alt nyelvekben az al´a- ´es f¨ol´erendelt oszt´alyokn´al szok´asos). Az ´ıgy kialakult hierarchi´aban van egy ”maxim´alis” elem, a top fogalom, amelynek minden m´as fogalom al´arendeltje, ´es egy ”minim´alis” elem, a bottom, amely valamennyi fogalomnak al´arendeltje. Mivel ∆I az al´arendel´es m˝ uvelet´ere n´ezve h´al´o; a fogalmak konjunkci´oja ´es diszjunkci´oja tulajdonk´eppen halmaz metszet ´es u ´ni´o, amelyekre teljes¨ ulnek a h´al´oaxi´om´ak: • AuA≡A ´es AtA≡A (idempotencia) • AuB≡BuA ´es AtB≡BtA (kommutativit´as) • Au(BuC)≡(AuB)uC ´es At(BtC)≡(AtB)tC (asszociativit´as) • Au(AtB)≡A ´es At(AuB)≡A (elnyel´es) Tov´abbi tulajdons´agok: • Ha DvC ´es DvE, akkor DvCuE • Ha DvC ´es EvC, akkor DtEvC • Ha DvC, akkor DuXvC, ahol X tetsz˝oleges fogalom
´ 7.5. AZ SHIQ NYELVCSALAD
79
• Ha DvC, akkor DvCtX, ahol X tetsz˝oleges fogalom. Az ALCN nyelv h´al´ot alkot az al´arendel´es m˝ uvelet´et tekintve, ahol a C ´es D fogalmak legkisebb fels˝o korl´atja CuD, legnagyobb als´o korl´atja pedig CtD.
7.4.1
Egyszer˝ u p´ eld´ ak al´ arendel´ esre
˝ ´ ˝ (FELNOTT u FERFI) v FELNOTT ˝ ´ ˝ ´ (FELNOTT u FERFI u GAZDAG) v (FELNOTT u FERFI) ˝ ´ ˝ (∀gyereke.(FELNOTT u FERFI)) v (∀gyereke.FELNOTT) ˝ ˝ ((∀gyereke.FELNOTT)u(∃gyereke)) v (∀gyereke.FELNOTT) (≥ 2 gyerek) v (≥ 3 gyerek)
7.5 7.5.1
Az SHIQ nyelvcsal´ ad Az SHIQ
Az SHIQ nyelv a mai gyakorlatban ´altal´anosan alkalmazott le´ır´o logikai nyelvek k¨oz¨ ul a legnagyobb kifejez˝oerej˝ u, amelyhez hat´ekony k¨ovetkeztet´esi algoritmus is rendelkez´esre a´ll. Az SHIQ nyelv az ALCN nyelv kiterjeszt´esek´ent t¨obbek k¨oz¨ott megengedi a szerephierarchi´ak megad´as´at, tranzit´ıv ´es inverz szerepek haszn´alat´at. Az S nyelvkiterjeszt´ esek Az SHIQ nyelvcsal´ad legegyszer˝ ubb tagja az S nyelv, amelyet az ALC nyelvb˝ol sz´armaztatjuk, u ´gy hogy megengedj¨ uk a tranztit´ıv szerepek haszn´alat´at. P´eld´aul kijelenthetj¨ uk, hogy a r´esze, ˝ose, lesz´armazottja szerepek tranzitvak. Szerephierarchi´ ak - a H nyelvkiterjeszt´ es A H nyelvkiterjeszt´es a szerephierarchia bevezet´ese, azaz le´ırhatjuk, hogy egy szerep a´ltal´anosabb, mint egy m´asik. P´eld´aul kijelenthetj¨ uk,
80
´ LOGIKAK ´ CHAPTER 7. LE´IRO
hogy a bar´atja kapcsolatn´al a´ltal´anosabb az ismer˝ose (bar´atja v ismer˝ose). Inverz szerepek - az I nyelvkiterjeszt´ es Az I nyelvkiterjeszt´es az inverz szerepek haszn´alat´at engedi meg. Jel¨ol´esben az R szerep inverze Inv(R). P´eld´aul Inv(gyereke)= sz¨ ul˝oje. Az inverz szerepek j´ol alkalmazhat´oak a r´esz-eg´esz kapcsolatok mindk´et ir´any´ u megnevez´es´ere. P´eld´aul Inv(r´esze)=tartalmaz´oja szerepek eset´en mondhatjuk, hogy a r´esze(aut´o, motor) eset´en tartalmaz´oja(motor, aut´o) kapcsolatok is fenn´allnak. Min˝ os´ıtett sz´ amoss´ agkorl´ atoz´ as - a Q nyelvkiterjeszt´ es A min˝os´ıtett sz´amoss´agkorl´atoz´as az N nyelvkiterjeszt´es, azaz (≥ n R) ´es (≤ n R) min˝os´ıtetlen sz´amoss´agkorl´atoz´asok a´ltal´anos´ıt´asa, azzal a megszor´ıt´assal, hogy az R szerep nem lehet tranzit´ıv. Megjegyezz¨ uk, hogy a k¨ ul¨onb¨oz˝o nyelvkiterjeszt´esek megv´alaszt´asakor k´et egym´asnak ellentmond´o szempontot kell figyelembe venni: az ismeretreprezent´aci´o kifejez˝oerej´enek n¨ovel´ese szempontj´ab´ol egyre er˝osebb nyelveket k´ıv´anunk, ugyanakkor a hat´ekonys´agi k¨ovetelm´enyek korl´atozz´ak az o¨sszetett nyelvi elemek bevezet´es´et. Ha a min˝os´ıtett sz´amoss´agkorl´atoz´asban megengedn´enk a tranzit´ıv szerepek haszn´alat´at, akkor az ´ıgy el˝oa´ll´o logika m´ar nem lenne eld¨onthet˝o. A min˝os´ıtetlen sz´amoss´agkorl´atoz´asok a Q nyelvkiterjeszt´es (≥ n R.C) ´es (≤ n R.C) speci´alis esetei, ahol C ≡ >. A Q nyelvkiterjeszt´es seg´ıts´eg´evel le´ırhatjuk p´eld´aul a ”legal´abb h´arom iskol´as gyerek˝ u sz¨ ul˝o” fogalm´at (≥ 3 gyereke.iskol´as). Az egyed-kapcsolaton alapul´o modellez´esi eszk¨oz¨okben fontos szerepet kap a rel´aci´ok multiplicit´as´anak megad´asa, amikor p´eld´aul egy egyed pontosan egy, vagy legal´abb egy tulajdons´aggal rendelkezik.
7.5.2
Az SHIQ nyelv szemantik´ aja
Az SHIQ nyelv szemantik´aj´at az ALCN R nyelv szemantik´aj´ahoz hasonl´oan defini´aljuk. Egy I=(∆I , .I ) interpret´aci´o egy interpret´aci´os alaphalmaz ´es egy interpret´aci´os f¨ uggv´eny egy¨ uttese, ahol az .I interpret´aci´os f¨ uggv´eny egy fogalomat hozz´arendel a ∆I egy r´eszhalmaz´ahoz ´es egy szerepet a ∆I × ∆I egy r´eszhalmaz´ahoz u ´gy, hogy a k¨ovetkez˝o
´ ISMERETBAZIS ´ 7.6. A LE´IRO FOGALMA
81
azonoss´agok fenn´alljanak. >I ⊥I (C u D)I (C t D)I (¬C)I (∀R.C)I (∃R.C)I (≥ nR.C)I (≤ nR.C)I (Inv(R))I
7.6
= = = = = = = = = =
∆I 60 CI ∩ DI CI ∪ DI ∆I \ CI {a ∈ O | ∀b: (a, b) ∈ RI → b ∈ C I } {a ∈ O | ∃b: (a, b) ∈ RI ∧ b ∈ C I } {a ∈ O | {b∈ O |(a,b)∈ RI ∧ b ∈ C I }|≥ n} {a ∈ O | {b∈ O |(a,b)∈ RI ∧ b ∈ C I }|≤ n} {(b,a) ∈ ∆I ×∆I | (a,b)∈ RI }
A le´ır´ o ismeretb´ azis fogalma
A le´ır´o nyelvekben az ismeret´ abr´ azol´as k´et szinten val´osul meg. A terminol´ogia szintj´en vezetj¨ uk be a fogalmakat, a szerepeket ´es az adott ALCN R le´ır´o nyelvnek megfelel˝ oen az al´ arendel´esi rel´aci´okat. A fogalmak ´es szerepek lehetnek primit´ıvek (atomiak) vagy ¨osszetettek (defini´altak). A primit´ıv fogalmakat (szerepeket) al´ arendel´esi rel´aci´oval adjuk meg, az ¨osszetett fo. galmakat (szerepeket) pedig konstruktorok seg´ıts´eg´evel (jel¨ol´esben: =). A t´enyek ´es a hozz´ arendel´esek szintj´en az egyes fogalmakhoz tartoz´o individuumokat ´es az egyes szerepekhez tartoz´o individuum p´arokat mint t´enyeket soroljuk fel. Jel¨ol´esben a hozz´ arendel´esek C(a) ´es R(a,b) alak´ uak. A hozz´arendel´eseket ´altal´anosan α hozz´ arendel´esnek jel¨ olj¨ uk a tov´abbi defin´ıci´okban. Az ALCN R nyelvben le´ır´ o ismeretb´azisnak nevezz¨ uk (jel¨ol´esben: Σ = (T , A)) a (T , A) p´ arost, ahol T a fogalmak ´es szerepek le´ır´asa a nyelv eszk¨ozeivel, A pedig a t´enyek ´es egyed-hozz´arendel´esek megad´asa C(a) vagy R(a,b) alakban. Azt mondjuk, hogy az I interpret´ aci´o modellje a C fogalomnak, ha CI 6=6 0. Azt mondjuk, hogy egy C fogalom kiel´eg´ıthet˝o, ha l´etezik modellje. Legyen I = (∆I , .I ) egy interpret´aci´o. A C(a) hozz´arendel´est kiel´eg´ıti az I interpret´ aci´ o, ha aI ∈ CI ; az R(a,b) hozz´arendel´est kiel´eg´ıti az I interpret´aci´o, ha (aI ,bI )∈ RI . Egy I interpret´ aci´ o modellje a Σ = (T , A) le´ır´o ismeretb´azisnak, ha I kiel´eg´ıti A minden hozz´ arendel´es´et. A Σ = (T , A) le´ır´ o ismeretb´ azis kiel´eg´ıthet˝o, ha l´etezik modellje.
82
´ LOGIKAK ´ CHAPTER 7. LE´IRO
Az α hozz´ arendel´es logikai k¨ovetkezm´enye a Σ = (T , A) le´ır´o ismeretb´azisnak, ha Σ minden modellje kiel´eg´ıti α-t. Jel¨ol´esben: Σ |= α.
7.6.1
P´ elda le´ır´ o ismeretb´ azisra
Az al´ abbi p´eld´ aban a T Tbox n´egy fogalmat vezet be.
t1 Egy kurzus oktat´oja vagy professzor vagy egyetemi diplom´aval rendelkez˝ o di´ ak (PhD hallgat´o).
t2 A professzorok doktori diplom´aval rendelkez˝o szem´elyek.
t3 Ha valakinek doktori diplom´aja van, akkor biztosan van egyetemi diplom´ aja is.
t4 A doktori ´es egyetemi diplom´ak k¨ ul¨onb¨oz˝oek.
Az A Abox hozz´ arendel´esek k¨oz¨ ul a2 azt mutatja, hogy J´anos nem lehet professzor, hiszen legfeljebb egy diplom´aja van, s ez a1 ´es a3 miatt, azaz mert J´ anos tan´ıtja a Prog kurzust, felt´etlen¨ ul egyetemi diploma.
´ ISMERETBAZIS ´ 7.6. A LE´IRO FOGALMA
83
Legyen Σ = (T , A) ahol T ={ ´ SZEMELY v> ´ PROFESSZOR v SZEMELY ´ v SZEMELY ´ DIAK KURZUS v > FOKOZAT v > EGYETEMI v FOKOZAT DOKTORI v FOKOZAT tan´ıt´ o v toprole diploma v toprole (∃tan´ıt´ o.KURZUS) v ´ u (∃diploma.EGYETEMI))) (PROFESSZOR t (DIAK PROFESSZOR v (∃diploma.DOKTORI) (∃diploma.DOKTORI) v (∃diploma.EGYETEMI) (DOKTORI u EGYETEMI) v ⊥ } A={ tan´ıt´ o(J´ anos, Prog kurzus) (≤ 1 diploma)(J´ anos) KURZUS(Prog kurzus) }
A k¨ovetkez˝ o interpret´ aci´ o egy modellje az el˝obbi Σ = (T , A) le´ır´o ismeretb´azisnak, ahol az interpret´ aci´os alaphalmaz O = {Jani, Programoz´ as, Jani egyetemi diploma}. Ekkor a J´anosI = Jani Prog kurzusI = Programoz´ as I ´ DIAK = {Jani} PROFESSZORI = 6 0 KURZUSI = {Programoz´ as} EGYETEMII = {Jani egyetemi diploma} DOKTORII = 6 0 tan´ıt´oI = {(Jani, Programoz´ as)} diplomaI = {(Jani, Jani egyetemi diploma} interpret´ aci´ o kil´eg´ıti A minden hozz´arendel´es´et.
t1 t2 t3 t4
a1 a2 a3
´ LOGIKAK ´ CHAPTER 7. LE´IRO
84
7.7
K¨ ovetkeztet´ esi elj´ ar´ asok egy le´ır´ o ismeretb´ azisban
Egy le´ır´ o ismeretb´ azisban az al´abbi k¨ovetkeztet´esi elj´ar´asok alkalmazhat´ok: • Al´ arendel´esek ellen˝orz´ese. Ezen elj´ar´as seg´ıts´eg´evel eld¨onthetj¨ uk, hogy egy C fogalom al´arendeli-e a D fogalmat vagy sem. Ez az alapja az oszt´ alyoz´ asi m˝ uveletnek, ami meghat´arozza egy fogalom k¨ozvetlen lesz´ armazottait. • Egy fogalom kiel´eg´ıthet˝os´eg´enek ellen˝orz´ese. Ennek sor´an eld¨onthetj¨ uk, hogy egy fogalomnak l´etezik-e modellje, azaz vannak-e egyedei valamely interpret´aci´oban. • Egy le´ır´ o ismeretb´azis kiel´eg´ıthet˝os´eg´enek vizsg´alata. Itt ellen˝orizz¨ uk, hogy l´etezik-e modellje. • Egyedes´ıt´es. Ezen elj´ar´as sor´an ellen˝orizz¨ uk, hogy egy b individuum egyede-e a C fogalomnak a Σ le´ır´o ismeretb´azisban, azaz Σ |= C(b) teljes¨ ul-e. Pontosabban ez az elj´ar´as azon fogalmakat keresi meg, amelyeknek a b individuum egyede, ´es amelyek ugyanakkor a legink´abb specifikusak az al´arendel´esi hierarchi´aban.
7.7.1
P´ elda az egyedes´ıt´ esre
A T Tboxban primit´ıv ´es defini´alt fogalmakra l´athatunk p´eld´at. A szem´ely ´es halmaz primit´ıv fogalmak, amelyeket a v jel vezet be, ´es a > (top fogalom) mint a leg´ altal´ anosabb fogalom al´arendeltjei. A > tekinthet˝o a fogalmak hierarchi´ aj´ aban a gy¨ ok´erelemnek. A u (konjunkci´ o) konstruktor jelzi, hogy egy fogalmat t¨obb m´as fogalom konjunkci´ ojak´ent hozunk l´etre, amelyek az ´ıgy defini´alt fogalom k¨ozvetlen osei. A ∀ konstruktor a tag szerep ´erv´enyess´egi tartom´any´at pontos´ıtja. ˝ A ¬ konstruktor neg´aci´ot fejez ki, amit az AL nyelvben csak primit´ıv fogalomra alkalmazunk. A ≤ ´es ≥ konstruktorok a tag szerep ´erv´enyess´egi tartom´ any´ aban val´ o el˝ofordul´as sz´amoss´ag´at korl´atozz´ak. Legyen T ={ ´ SZEMELY v> HALMAZ v > ´ ´ FERFI v SZEMELY
¨ ´ ELJAR ´ ASOK ´ ´ ISMERETBAZISBAN85 ´ 7.7. KOVETKEZTET ESI EGY LE´IRO ˝ v (SZEMELY ´ ´ NO u (¬ FERFI)) tag v toprole f˝on¨ok v tag . ´ CSAPAT = (HALMAZ u (∀tag.SZEMELY) u (≥ 2 tag)) . KISCSAPAT = (CSAPAT u (≤ 5 tag)) . MODERNCSAPAT = (CSAPAT u (≤ 4 tag) u (≥ 1 f˝on¨ok) ˝ u (∀f˝ on¨ ok.NO)) } A={ MODERNCSAPAT(Trio) ´ FERFI(Antal) ´ SZEMELY(Erzsi) tag(Trio, Antal) tag(Trio, P´eter) f˝on¨ok(Trio, Erzsi) (≤ 3 tag)(Trio) }
• Defini´ aljon az (≤ nD RD ) ´es (≤ nC RC ) sz´amoss´ag-korl´atoz´as k´et fogalmat. Bizony´ıthat´ o al´ arendel´esi szab´aly: ha nD ≤ nC ´es RC v RD akkor (≤ nD RD ) v (≤ nC RC ). Ebb˝ ol ad´ odik, hogy MODERNCSAPAT al´arendeltje a KISCSAPATNAK. (4≤5 ´es R=tag mindk´et esetben.) • Bizony´ıthat´ o al´ arendel´esi szab´aly: ha az o egyede a C fogalomnak ´es C al´ arendeltje a D fogalomnak, akkor o egyede a D fogalomnak is. Ebb˝ ol ad´ odik, hogy a Trio egyede a KISCSAPAT-nak, hiszen a Trio a MODERNCSAPAT fogalom egy egyede ´es a MODERNCSAPAT al´arendeltje a KISCSAPATNAK. • Bizony´ıthat´ o al´ arendel´esi szab´aly: ha D1 (o) ´es D2 (o) hozz´arendel´esek, valamint a C fogalomnak nem al´arendeltje sem D1 sem D2 , de al´arendeltje D1 u D2 , akkor ebb˝ ol k¨ovetkezik a C(o) hozz´arendel´es. • Bizony´ıthat´ o al´ arendel´esi szab´aly: ha adva van egy szerep-hozz´arendel´es R(o,b) ´es o egy egyede egy (∀R.C) alak´ u fogalomnak, akkor C(b) k¨ovetkezik, azaz b egyede C-nek. Ebben a p´eld´ aban, P´eter ´es Antal tag rel´aci´oban vannak a Trio-val ´es Trio egyede a MODERNCSAPAT-nak. Mivel MODERNCSAPAT
86
´ LOGIKAK ´ CHAPTER 7. LE´IRO al´ arendeltje a CSAPAT-nak, k¨ovetkez´esk´eppen a Trio egyede a CSAPAT´ nak. A CSAPAT (∀tag.SZEMELY) defin´ıci´oj´ab´ol ad´odik, hogy P´eter ´ ´es Antal egyede a SZEMELY fogalomnak. Hasonl´ oan levezethet˝o, hogy Erzsi egyede a N˝o fogalomnak a f˝ on¨ ok(Trio, Erzsi) ´es MODERNCSAPAT(Trio) hozz´arendel´esekb˝ol, ˝ alak´ valamint a MODERNCSAPAT (∀f˝on¨ok.NO) u defin´ıci´oj´ab´ol.
7.8
Ny´ıltvil´ ag ´ es z´ art vil´ ag szemantika
A le´ır´ o logik´ ak ismeretb´azis´at megfigyelve, hasonl´os´agot tapasztalhatunk az adatb´ azisokkal. Hangs´ ulyozzuk azonban az adatb´azis ´es ismeretb´azis k¨oz¨otti relev´ ans elt´er´est: a ny´ıltvil´ag ´es z´artvil´ag szemantika k¨oz¨otti k¨ ul¨onbs´eget. Egy adott adatb´ azis mindig egyetlen interpret´aci´ot k´epvisel, azt amelyben az adott egyedek k¨oz¨otti rel´aci´ok fenn´allnak. Az adatb´azis lek´erdez´esek erre az egyetlen interpret´aci´ora vonatkoznak. Ebben a z´artvil´ag szemantik´ aban csak az az ´all´ıt´as igaz, amely k¨ozvetlen¨ ul megjelenik az adatb´azis rekordjai k¨ oz¨ ott. Ezzel szemben a le´ır´o logik´ak Abox ismeretei ny´ıltvil´ag szemantik´ an alapulnak. Az Aboxr´ol csak olyan ´all´ıt´asokat mondhatunk ki, amelyek minden interpret´aci´oban igazak. Ez azt jelenti, hogy az adatb´azis lek´erdez´eshez k´epest a le´ır´o logikai egyedes´ıt´es ¨osszetettebb feladat, amelynek megold´ as´ ahoz esetsz´etv´alaszt´ason kereszt¨ ul vezet az u ´t. Tekints¨ uk az al´ abbi p´eld´ at: gyereke(IOKASZTE, OIDIPUSZ) gyereke(OIDIPUSZ, POLUNEIKESZ) gyereke(IOKASZTE, POLUNEIKESZ) gyereke(POLUNEIKESZ, THERSZANDROSZ) Apagyilkos(OIDIPUSZ) ¬Apagyilkos(THERSZANDROSZ) K´erd´es, van-e Iokaszt´enek olyan gyereke, aki apagyilkos, ´es akinek van nem apagyilkos gyereke. azaz Σ |=(∃ gyereke.(Apagyilkosu∃ gyereke.¬Apagyilkos))(IOKASZTE) Ennek a k´erd´esnek a vizsg´alatakor az adatb´azisok vil´ag´aban a ”gyereke” rel´ aci´ o adatt´ abl´ aj´ anak n´egy sora van, az Apagyilkos rel´aci´oba csak egy ´all´ıt´ as tartozik, az hogy Oidipusz apagyilkos. Poluneikeszr˝ol nincs arra vonatkoz´ o all´ıt´ ´ as, hogy apagyilkos lenne, teh´at Apagyilkos(POLUNEIKESZ) ´all´ıt´ast hamisnak kell tekinten¨ unk. Azaz a feltett k´erd´esre(van-e Iokaszt´enek olyan gyereke, aki apagyilkos, ´es akinek van nem apagyilkos gyereke) adand´o v´alasz,
´ LOGIKA, A KLASSZIKUS LOGIKA ES ´ AZ OBJEKTUM ALAPU ´ ISMERETABR ´ A ´ 7.9. A LE´IRO igen, Poluneik´esz. A ny´ılt vil´ ag szemantik´ aban az Apagyilkos(POLUNEIKESZ) ´all´ıt´as nem defini´alt volta miatt lehet igaz is, ez´ert az esetsz´etv´alaszt´as technik´aj´at alkalmazva: 1. abban az interpret´ aci´ oban, amelyben POLUNEIKESZ apagyilkos, a feltett k´erd´esre a v´ alasz igen, mivel Iokaszt´enak van apagyilkos gyermeke Poluneik´esz, akinek van nem apagyilkos gyermeke Therszandrosz. 2. abban az interpret´ aci´ oban, amelyben POLUNEIKESZ nem apagyilkos, a feltett k´erd´esre szint´en igen a v´alasz, mivel Iokaszt´e apagyilkos gyermeke Oidipusz, akinek van nem apagyilkos gyermeke Pol¨ uneik´esz. Teh´at az el˝ obbi Abox minden modellj´eben a k´erd´esre adand´o v´alasz igen, an´elk¨ ul, hogy Pol¨ uneik´eszr˝ ol megfogalmazn´ank az apagyilkos/nem apagyilkos ´all´ıt´ ast.
7.9
A le´ır´ o logika, a klasszikus logika ´ es az objektum alap´ u ismeret´ abr´ azol´ as
A le´ır´o logik´ ak f˝ o jellemz˝ oi a fogalmakat ´es szerepeket le´ır´o nyelv, a nyelvhez kapcsol´ od´ o interpret´ aci´ o, valamint az al´arendel´esi rel´aci´o. Term´eszetes m´odon ad´ odik teh´ at a kapcsolat a klasszikus form´alis logik´aval, ami a formul´akon, az azokhoz kapcsol´ od´ o interpret´aci´on ´es a levezet´esi szab´alyokon alapul. A le´ır´ o logik´ ak fogalmait tekinthetj¨ uk un´aris, a szerepeket bin´aris predik´atumoknak, az al´ arendel´est pedig levezet´esi szab´alynak. A p´arhuzamoss´agot szeml´elteti, hogy a fogalom-kifejez´esek ´es a hozz´arendel´esek l´enyeg´eben speci´ alis els˝ orend˝ u logikai formul´ak. P´eld´aul legyen adott a . ˝ ´ C = ∃gyereke.NOu∀gyereke.SZEM ELY fogalom. Ez megfeleltethet˝ o az al´ abbi formul´anak: ˝ ´ φ(x) = ∃y(gyereke(x, y)∧NO(y)) ∧ ∀z(gyereke(x, z) →SZEMELY(z)) A φ(x) formula modellje egyben modellje a C fogalomnak ´es megford´ıtva. A le´ır´o logik´ ak kifejez˝ oereje az els˝orend˝ u predik´atumkalkulussal szemben ´ ha a predik´ gyenge. Am atumkalkulusban csak un´aris ´es bin´aris predik´atumokat ´es legfeljebb 2 szabad v´ altoz´ ot enged¨ unk meg, akkor kifejez˝oereje megegyezik az ALCN nyelv´evel. A kifejez˝oer˝o gyenges´eg´e´ert k´arp´otol benn¨ unket a k¨ovetkeztet´esi feladatokra val´ o j´ o alkalmazhat´os´aga. Bebizony´ıtott´ak, hogy
88
´ LOGIKAK ´ CHAPTER 7. LE´IRO
az al´ arendel´es vizsg´alata teljes, ´es polinomi´alis id˝oben megval´os´ıthat´o az ALCN nyelvekben.
A le´ır´ o logik´ ak bizonyos hasonl´os´agot mutatnak az objektum alap´ u ismeret´br´ a azol´ assal is. Egy objektum alap´ u ismeret´abr´azol´asi rendszer ´allapotot ´es viselked´est bez´ ar´ o oszt´alyokat tekint ismeretnek. Az ´allapotot ´es a viselked´est funkcion´ alis, valamint le´ır´o tulajdons´agok hat´arozz´ak meg. A le´ır´o tulajdons´ agokhoz (attrib´ utumokhoz) t´ıpust, ´ert´eket ´es d´emonokat rendelhet¨ unk. A funkcion´ alis tulajdons´agok (met´odusok) u ¨zenetk¨ uld´es u ´tj´an aktiv´alhat´o elj´ ar´ asok vagy f¨ uggv´enyek. Az oszt´alyok ¨or¨okl˝od´esi hierarchi´aba rendezettek. Az oszt´ alyok egyedes´ıthet˝oek, s az ´ıgy keletkezett objektumokkal v´egezhetnek m˝ uveletet az alkalmaz´asok. Az objektum alap´ u ismeret´abr´azol´asi rendszerekben a k¨ ovetkeztet´es megval´os´ıthat´o ¨or¨okl˝od´essel (egy tulajdons´ag ´ert´eke az oszt´ alyok k¨ oz¨otti ¨or¨okl˝od´esi rel´aci´ob´ol vezethet˝o le), oszt´alyoz´assal (egy oszt´ alynak az o¨r¨okl˝od´esi hierarchi´aba val´o beilleszt´ese, vagy egy egyednek egy oszt´ alyhoz rendel´ese u ´tj´an) vagy sz˝ ur´essel (egy bizonyos sz˝ ur˝onek megfelel˝ o objektumok kiv´alaszt´asa r´ev´en). A fogalom ¨ osszevethet˝o az oszt´alyfogalommal, a szerep az oszt´aly attrib´ utumaival. Ugyanakkor a le´ır´o logik´akn´al teljesen hi´anyzik a procedur´alis jelleg, ami alapvet˝ oen megk¨ ul¨onb¨ozteti ˝oket az objektum alap´ u ismeret´abr´azol´ast´ol. Ebb˝ ol a szempontb´ ol tekinthetj¨ uk az objektum alap´ u ismeret´abr´azol´ast procedur´ alisnak, m´ıg a le´ır´o logik´akat deklarat´ıvnak. Egy m´ asik ¨ osszehasonl´ıt´asi szempont lehet az oszt´alyoz´as, amikor az objektum alap´ u ismeret´ abr´azol´as szabad kezet ad a programoz´onak egy oszt´aly elhelyez´es´ere az ¨ or¨ okl˝od´esi hierarchi´aba. A le´ır´o logik´ak eset´en egy u ´j fogalom f fni´ al´ asakor az oszt´alyoz´asi elj´ar´as megadja a fogalom elhelyez´es´et a hierarchi´ aba az al´ arendel´esi szab´alynak megfelel˝oen. Tov´ abbi k¨ ul¨ onbs´eg, hogy az objektum alap´ u ismeret´abr´azol´as eset´en az oszt´ alyhoz rendelt tulajdons´ agok le´ır´o jelleg˝ uek, azaz sz¨ uks´eges, de nem el´egs´eges felt´etelt jelentenek. Azaz, ha egy o objektum egy C oszt´aly egyede, akkor ez azt jelenti, hogy ily m´ odon defini´altuk, ´es rendelkezik a C oszt´aly tulajdons´agaival. Ellenben, ha o rendelkezik a C oszt´aly tulajdons´agaival, ebb˝ol nem k¨ovetkeztethet¨ unk arra, hogy o val´oban egyede is C-nek. A le´ır´o logik´akban az oszt´ alyoz´ asi mechanizmus defin´ıci´os szemantik´an nyugszik, ahol a hierarchi´ aba rendez´esnek sz¨ uks´eges felt´etelei egyben el´egs´eges felt´etelek is. Ugyanakkor a kiv´etelkezel´es teljes eg´esz´eben hi´anyzik a le´ır´o logik´akb´ol, hiszen az al´ arendel´esi rel´aci´o ezt nem engedi meg.
´ 7.10. ALKALMAZASOK
7.10
89
Alkalmaz´ asok
A le´ır´o logik´ akat sikerrel alkalmazt´ ak a fogalmi modellez´es, az inform´aci´o integr´al´as, a tervez˝ o ´es konfigur´ al´ o rendszerek, a term´eszetes nyelvek meg´ert´ese ter¨ ulet´en. A KL-ONE (1977) az els˝ ok k¨ oz¨ ott volt, amelynek ismeret´abr´azol´asa a le´ır´o logik´akon alapult. Az elm´elet terjed´es´evel sz´amos m´as rendszer, KRYPTON (1983), KANDOR (1984) MESON (1988) k¨ovette. Ma is k´esz¨ ulnek alkalmaz´sok a CLASSIC, LOOM, BACK nyelveken, amelyeket tekinthet¨ unk a le´ır´o logik´ ak referenci´ ainak is. A tud´asalap´ u technol´ ogi´ ak szempontj´ab´ol fontos alkalmaz´asi ter¨ ulet az OWL ontol´ogianyelvek (az OWL Full, OWL DL ´es OWL Lite) k¨ovetkeztet˝orendszereinek haszn´alata. Az OWL DL az SHOIN (D), m´ıg az OWL Lite az SHIF(D) le´ır´o logik´ anak feleltethet˝ o meg.
134
´ LOGIKAK ´ CHAPTER 7. LE´IRO
Part III Tud´ askezel´ esi technol´ ogi´ ak
135
180
List of Figures 6.1 6.2
c´elvez´relt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . adatvez´erelt . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1 8.2 8.3 8.4 8.5 8.6 8.7
P´eld´ ak h´ al´ o strukt´ ur´ ara . . . . P´eld´ ak nem h´ al´ o strukt´ ur´ ara . P´elda nem disztribut´ıv h´ al´ora . Sz´ amp´elda . . . . . . . . . . . . Sz´ amp´elda elem besz´ ur´ as ut´an Sz´ op´elda . . . . . . . . . . . . . Sz´ op´elda elem besz´ ur´ as ut´an .
181
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
46 47 90 91 94 100 100 101 101
182
LIST OF FIGURES
List of Tables 2.1
A hagyom´ anyos ´es az MI alap´ u rendszerek ¨osszehasonl´ıt´asa .
24
4.1
Az ismeretalap´ u rendszerek fel´ep´ıt´ese . . . . . . . . . . . . . .
33
6.1 6.2
A c´elvez´erelt ´es adatvez´erelt technik´ak lehet˝os´egeinek ¨osszevet´ese 49 A slot oszt´ aly attrib´ utumai . . . . . . . . . . . . . . . . . . . 59
7.1 7.2
Le´ır´ o logik´ ak alapfogalmai . . . . . . . . . . . . . . . . . . . . Fogalom- ´es szerep-form´ al´ o konstruktorok . . . . . . . . . . .
9.1
A bizonytalans´ ag n´eh´ any lehets´eges oka . . . . . . . . . . . . 104
183
77 77
