Šī kursa grāmata:
The Description Logic Handbook, edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2007
Tās pirmās nodaļas
D. Nardi, R. J. Brachman. An Introduction to Description Logics (ap 40 lpp.)
elektronisko kopiju var atrast Enrico Franconi (Free University of Bozen-Bolzano asociētā profesora) tīmekļa vietnē. Viņš lasa kursu Description Logic. Ja kopijas adreses beigās skaitlisko daļu maina no nulle-viens līdz viens-seši, tad tā var ielūkoties grāmatas visās sešpadsmit nodaļās.
Pavisam īss ievads un pārskats: Description LogicWikipedia.
Alternatīvas (ļoti labas!) ievadlekcijas: Enrico Franconi, Free University of Bozen-Bolzano, Description Logics, sk, otro moduli (lekcija 1, lekcija 2).
Nopietnāku ievadu - no "augstākām pozīcijām" piedāvā Hector Levesque, University of Toronto, Knowledge Representation and Reasoning (tie ir publiski pieejami lekciju slaidibaksiti uz viņa un R. J. Brachman tāda paša nosaukuma grāmatas).
Matemātiskā orientētiem cilvēkiem, droši vien, būtu patīkamak studēt Stephan Tobies disertācijas tekstu adresē http://citeseer.ist.psu.edu/tobies01complexity.html, sadaļas 1.1-1.4.
Ļoti labas ir arī attiecīgās nodaļas Carlos Areces disertācijā, 2000.
1.2. Zināšanu formalizācija, izmantojot predikātu loģiku
Vispirms mēģināsim nonākt pie aprakstošo loģiku jēdziena, ejot "no augšas".
Par zināšanu bāzēm sk. Deduktīvās datubāzes - gabaliņu no kursa "Datubāzes II".
Visus eksperimentus ar zināšanu bāzēm, ontoloģijām un secinātājiem mēs veiksim, izmantojot rīku Protege, kura autori to pozicionē kā "free, open source ontology editor and knowledge-base framework".
No adreses http://protege.stanford.edu var lejupielādēt versiju Protege 3.4.1 ("vecā" versija, bet toties līdz galam nostrādāta un pārbaudīta) un Protege 4.0 (jaunā versija, vēl nav pabeigta).
Kursā izmantosim Protege 3.4.1, to vajag jau tagad lejupielādēt un instalēt. Visdrošāk ir ņemt pilnu versija ar visu Java mašīnu.
Kā tagad zinām, zināšanu bāzēs predikātu loģiku pilnā apjomā izmantot nevar, jo tad formulu secināšanas uzdevums kļūst algoritmiski neatrisināms.
Aprakstošās loģikas (description logics) ir šobrīd populārākais veids kā, saglabājot tomēr pietiekamu izteiksmes iespēju minimumu, ierobežot predikātu loģiku tā, lai formulu secināšanas uzdevums būtu algoritmiski atrisināms.
Bet tas nav vienīgais iespējamais veids. Par tādām lietām interesējies jau viens no matemātiskās loģikas klasiķiem:
W. Ackermann. Solvable cases of the decision problem. North-Holland, Amsterdam, 1954.
Ļoti vienkāršu un samērā vispārīgu ideju - t.s. guarded fragment (vai guarded logic) piedāvā
H. Andreka, J. van Benthem, I. Nemeti. Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic, 27(3): 217-274, 1998.
Guarded logic atzīst tikai īpašā veidā ierobežotus kvantorus, piemēram (p - jebkura divvietīga predikātu konstante):
Ey(p(x, y)&F(x, y)), jeb (Ey: p(x,y))F(x,y);
Ay(p(x, y)->F(x, y)), jeb (Ay: p(x,y))F(x,y).
Šeit tiek prasīts, lai formulā F(x, y) nebūtu citi brīvi mainīgie kā formulā p(x,y), t.i. tikai x, y. Kvantora darbības apgabals te ir nevis "visa pasaule", bet tikai tie objekti y, kas ir fiksētā veidā (p ir konstante!) saistīti ar tiem objektiem x, par kuriem ir runā formula F(x,y).
Precīzu vispārīgo definīciju sk. Christof Monz, http://www.dcs.qmul.ac.uk/~christof/publications/j50.pdf. Tur minēts arī, ka formulu secināšanas uzdevums guarded logic ir algoritmiski atrisināms - tas ir EXPTIME-complete (fiksētai valodai), t.i. ja iesaistīto formulu kopgarums ir N, tad secināšanas uzdevums prasa laiku 2CN.
ALC ir saīsinājums no "Attribute Logic with Complement".
"Cilvēkiem no loģikas" parasti skaidro tā: ja aplūkojam guarded logic vēl vienkāršāku gadījumu - kad formulā F ir tikai viens brīvs mainīgais y:
Ey(p(x, y)&F(y)),
Ay(p(x, y)->F(y)),
tad mēs nonākam jau pie klasiskās aprakstošās loģikas, t.s. loģikas ALC, kurai (kā vēlāk redzēsim) formulu secināšanas uzdevums ir PSPACE-complete.
Piezīme. Kāpēc te tik liela interese par PSPACE, t.i. par iespēju risināt uzdevumu, izmantojot atmiņu, kuras apjoms nepārsniedz polinomu no ieejas datu garuma? Tāpēc, ka nākošais sarežģītības līmenis ir eksponenciāls atmiņas apjoms. Pie tam atmiņas apjomam (atšķirībā no rēķināšanas laika) ir nejauka īpašība - tas bieži ir vienāds gan "labajos", gan "sliktajos" gadījumos. Tāpēc, ja mēs kādu uzdevumu neprotam risināt polinomiālā atmiņā, tad ir gandrīz droši, ka šis uzdevums būs datoriem "nepaceļams". Tāpēc arī tāda interese par uzdevumiem, kuri pieder sarežģītības klasei PSPACE.
Loģikas ALC elegantākā definīcija
Bet tikko minētais "skaidrojums" liekas pārāk tehnisks, lai noticētu, ka loģika ALC ir kaut kas vairāk nekā šauriem mērķiem domāts izgudrojums.
Manuprāt, esmu atradis daudz elegantāku veidu ALC ievešanai.
"Vīzijas" pamatā, tāpat kā predikātu valodām, ir "apgabals", kas sastāv no "indivīdiem", par kuriem interesējamies.
Piemēri: a) "visi cilvēki"; b) "kursi, pasniedzēji un studenti".
Indivīdiem ir piešķirti vārdi:
Piemēri: a) Jobn, Paris, Peter; b) Algebra, ASmith, BSmith.
Šajā apgabalā mūs interesē dažādas objektu kopas. Sauksim šīs kopas par klasēm, jēdzieniem jeb konceptiem. Dažas no šīm klasēm mums ir definētas jau pašā sākumā kā konstantes p, q, utt. (pamatklases). Un mums ir zināmas indivīdu piederība šīm klasēm.
Piemēri: a) klases: Sieviete -
sievietes, Virietis - vīrieši, Cilveks - visi
cilvēki;
Paris: Sieviete, John: Virietis; Peter: Virietis.
b) Kurss - kursi, Pasniedzejs - pasniedzēji, Students
- studenti.
Algebra: Kurss, ASmith: Pasniedzejs; BSmith: Students.
Kā jau datubāzēs parasts, klašu nosaukumi ir vienskaitlī.
Pārējās klases vajadzēs atvasināt šīm pamatklasēm. Ar kādiem līdzekļiem?
Protams, vispirms prātā nāk tradicionālās Būla operācijas - šķēlums, apvienojums un papildinājums: ja mums jau ir izveidotas klases C, D, tad varam izveidot arī klases C^D, CvD un -C.
Bet starp mūsu objektiem varēs pastāvēt arī divvietīgas asociācijas. Tām jabūt definētām jau pašā sākumā kā konstantēm r, s, utt. (līdzekļus atvasinātu asociāciju veidošanai pagaidām neatļausim). Sauksim tās par lomām - ja objektus x un y saista asociācija r, tad rakstīsīm x r y un teiksim, ka y-am pie x-a ir loma r.
Piemēri: a) loma berns, rakstām: x berns
y (lasām: x-a bērns y).
b) loma maca, rakstām: x maca y (lasām:
[pasn.]x māca [kursu]y);
loma stude, rakstām: x stude y (lasā:
[stud.]x stude [kursu]y.
Lomu vārdus vajag censties izvēlēties tā, lai lasot x r y, sanāktu kas viegli saprotams.
Tātad mūsu apgabals būtībā ir orientēts grafs, kura virsotnes ir objekti x, y, ..., un ja divus objektus x, y saista loma r, tad no x uz y tiek novilkta (orientēta!) šķautne, kurai pierakstīts burts r.
Šādā grafā ir ieraugāms vēl vismaz viens dabisks veids jaunu klašu definēšanai. Ja mums jau ir definēta klase C, tad lomai r mēs varam aplūkot visu to grafa virsotņu kopu, no kurām uz klasi C ved šķautnes ar burtu r.
[Uzzīmējiet bildi, kas šo operāciju demonstrē vizuāli: bērni.] Kopu teorijā šo operāciju pieņemts saukt par inverso attēlu un apzīmēt ar r-1(C). Loģikas valodā:
r-1(C) = {x | Ey(r(x, y) & y in C)}.
Aprakstošo loģiku pasaulē šo operāciju apzīmē ar Er.C - "visi tie objekti, kam eksistē r klasē C".
Piemēri: a) E berns.Sieviete - klase
"visi cilvēki, kam ir meitas".
b) E maca.Kurss - klase "visi [pasniedzēji], kas
māca kādu kursu".
Tad lūk, ja Būla operācijām pievienojam inversā attēla operāciju un aplūkojam visas klases, ko var nodefinēt, kombinējot šīs četras operācijas C^D, CvD, -C, r-1(C) (sākumā mums ir tikai galīgs skaits pamatklašu p, q, utt. un galīgs skaits lomu r, s utt.), tad tā arī ir slavenā aprakstošā loģika ALC! Tik eleganta formulējuma iespējamība liecina, ka aprakstošās loģikas nav tikai tehnisks izgudrojums!
Piemērs. a) Apgabals - visi
cilvēki. Pamatklases: Sieviete, Virietis. Viena loma:
berns. Kādas klases vēl varam nodefinēt:
-Sieviete ("vīrieši", jeb koncepts Virietis),
Sieviete v -Sieviete ("cilvēki", jeb koncepts
Cilveks),
E berns.Sieviete ( "cilvēki, kam ir meitas", jeb
koncepts "cilvēks, kam ir meitas"),
E berns.Cilveks,
Sieviete ^ E berns.Cilveks,
E berns.(E berns.Cilveks).
Piezīme. Klase un koncepts (jēdziens) - kāda ir atšķirība?
Kādu klasi definē izteiksme -Er.-C? Objekts x pieder šai klasei tad un tikai tad, ja
~Ey(r(x, y) & y in -C).
Pārveidojam pēc klasiskās loģikas likumiem:
Ay ~(r(x, y) & y in -C)
Ay(~r(x, y) v y in C)
Ay(r(x, y) -> y in C)
Var arī bez loģikas:
Er.-C nozīmē "visi tie objekti, kam eksistē r ārpus
klases C";
-Er.-C nozīmē "visi tie objekti, kam neeksistē r ārpus
klases C", jeb:
"visi tie objekti, kam visi r ir klasē
C".
Tāpēc aprakstošo loģiku pasaulē konstrukciju -Er.-C pieņemts apzīmēt ar Ar.C - "visi tie objekti, kam visi r ir klasē C".
Piemēri: A berns.Sieviete - "cilvēki, kam visi bērni ir meitas". BET - ievērosim klasiskās loģikas dīvainību - šai klasei pieder arī visi tie cilvēki, kam bērnu nemaz nav! [Pārliecināsimies!]
Rodas dabiski jautājumi:
1. Kāpēc mēs tā "piesējāmies" inversajiem
attēliem r-1(C) = {x | Ey(r(x, y) & y in C)}? Vai
tad "tiešie" attēli ir sliktāki? Runa ir par
operāciju
r(C) = {y | Ex(r(x, y) & x in C)}, t.i. aplūkojam visu to
grafa virsotņu kopu, uz kurām no
klases C ved šķautnes ar burtu r. [Uzzīmējiet
bildi, kas šo operāciju demonstrē vizuāli.] Ja
četrām operācijām C^D, CvD, -C, r-1(C) pievienosim
piekto operāciju r(C), tad iegūsim aprakstošo loģiku, ko
pieņemts apzīmēt ar ALCI (sk. tālāk - arī šo loģiku mēs
nopietni pētīsim). Tas ir viens no loģikas ALC
paplašinājumiem.
2. Kāpēc mēs atļaujam veidot formulas, kas definē atvasinātas klases, bet neļaujam veidot formulas, kas definē atvasinātas lomas? Tiešām, loģikā ALC pie kvantoriem atļauts izmantot tikai "atomāras" lomas r(x ,y), s(x, y) utt. Bet formulas r(x, y) & s(x, y) utt. (jebkuras formulas ar diviem brīviem mainīgiem) taču arī definē lomas? Lomas var kombinēt arī ar t.s.lomu savienošanas (jeb konkatenācijas) palīdzību: r o s = {(x, y) | Ez (r(x, z)&s(z, y))}. Piemēram, izteiksme berns o berns būtībā nozīmē lomu mazberns.[Pārliecināsimies!] Vēl viens populārs jaunu lomu veidošanas līdzeklis ir tranzitīvais slēgums (piemēram, Trans(t v m) - tā no tēva un mātes lomām iegūst senča lomu). Arī tādus loģikas ALC paplašinājumus mēs nopietni pētīsim.
Loģikas ALC definīcija "loģikas cilvēkiem"
a) Pamatā ir predikātu valoda, kurā ir tikai objektu konstantes (indivīdu vārdi), vienvietīgas predikātu konstantes (jēdzieni, koncepti, jeb klases): p(x), q(x), ... un divvietīgas predikātu konstantes (lomas): r(x,y), s(x,y), ...
b) Aplūko tikai formulas ar vienu brīvu mainīgo x. Katra tāda formula definē jēdzienu (jeb klasi). Atomārās ALC formulas ir tikai vienvietīgās predikātu konstantes ar mainīgo x: p(x), q(x), ...
c) Ja F(x), G(x) ir ALC formulas ar vienu brīvo mainīgo x, tad formulas F&G, FvG, F->G, ~F arī ir ALC formulas.
d) Ja F(x) ir ALC formula ar vienu brīvo mainīgo x, un r ir divvietīga predikātu konstante, tad formulas Ey(r(x, y) & F(y)) un Ay(r(x, y) -> F(y)) arī ir ALC formulas ar vienu brīvo mainīgo x. [Pie tam, formulu F(y) varam veidot no F(x), vienkārši apmainot vietām mainīgos x un y.]
e) Ja F(x) ir ALC formula ar vienu brīvo mainīgo x, un r ir divvietīga predikātu konstante, un c, d ir objektu konstantes, tad formulas F(c) un r(c, d) arī ir ALC formulas.
No šīs definīcijas redzams, ka ALC ir apakškopa predikātu loģikai L2 (t.i. loģikai, kuras valodā atļauti tikai divi mainīgie - piemēram, x un y).
Uzdevums. Pārliecināsimies, ka tā ir.
Ir zināms, ka formulu secināšanas uzdevums loģikai L2 ir NEXPTIME-complete (vēlāk redzēsim ka loģikai ALC tas ir PSPACE-complete). Arī ALC paplašinājums ar lomu inversiju un lomu Būla operācijām (sk. tālāk) ir L2 apakškopa. T.i. arī šim paplašinājumam formulu secināšanas uzdevums nav sarežģītāks par NEXPTIME-complete.
[Scott, 1962] - pirmoreiz pierādīja, ka L2 bez vienādības ir atrisināma, [Mortimer, 1975] - ka L2 ar vienādību arī ir atrisināma.
L3 ir neatrisināma jau formulām bez vienādības.
Par šīm lietām sk. Carlos Areces disertācijā, 2000.
Kā pie aprakstošajām loģikām nonāk "no apakšas"?
Semantiskie tīkli un freimi kā pirmie mēģinājumi zināšanu reprezentācijā:
Semantic network, Wikipedia, 1950-tie, 1960-tie, M. Ross Quillian, 1966
Marvin L. Minsky, Frames, June 1974
Aprakstošās loģikas radās, cenšoties pārvarēt semantisko tīklu un freimu semantikas neprecīzitāti. Par izšķirošo soli pieņemts uzskatīt 1985.gadā publicēto rakstu par sistēmu KL-ONE.
R. J. Brachman, J. Schmolze. An Overview of the KL-ONE Knowledge Representation System. Cognitive Sci 9(2), 172-216, 1985. (Sk. arī KL-ONE, Wikipedia.)
Loģiku ALC pirmoreiz noformulēja 1991.gadā:
M. Schmidt-Schauss, G. Smolka. Attributive concept descriptions with complements. Artificial Intelligence, 48, 1-26, 1991.
Par šo vēsturi vislabāk izlasīt Enrico Franconi lekcijās Description Logics, sk. otro moduli (lekcija 2).
Loģikas ALC tradicionālā ("īstā") definīcija
Tāpat kā predikātu loģikām, arī šeit katras konkrētas sistēmas pamatā ir fiksēta valoda. ALC gadījumā valoda ir mazliet neparasta. Mainīgos tajā neizmantojam. Valodas primitīvi ir:
Indivīdu vārdi (piemēram, John, Paris).
Atomārie jēdzieni (jēdzieni, koncepti, klases): p, q, ... (piemēram, Sieviete, Virietis, Bagats).
Lomas: r, s, ... (piemēram, berns, dzivesbiedrs, lomai ir divi gali: x-a berns y, x-a dzivesbiedrs y, bet oficiāli mainīgos te neizmanto).
Atvasināto jēdzienu konstruktori:
a) Būla operācijas: C^D, CvD, -C (piemēram, Virietis^Bagats, -Bagats) (implikāciju C->D reducējam uz -CvD).[Grāmatās par aprakstošajām loģikām, konjukciju pieņemts attēlot kā kvadrātu, kam izņemta apakšējā mala, bet disjunkciju - kā kvadrātu, kam izņemta augšējā mala.]
b) Kvantori: Er.C, Ar.C (piemēram, E berns.Sieviete - cilvēks, kam ir meita; A berns.Sieviete - cilvēks, kam visi bērni ir meitas (t.sk. bērnu var nebūt nemaz); E berns.Cilveks ^ A berns.Sieviete - cilvēks, kam ir bērni un visi ir meitas.
c) Apgalvojumi par indivīdiem:
vards: C, piemēram, Paris: Sieviete;
(vards1, vards2): r - manuprāt, neveiksmīgs pieraksts (bet ar
to būs jādzīvo), piemēram, (John, Paris): berns
(Parisa ir Džona bērns).
Vēl piemēri:
Virietis ^ E berns.(Sieviete ^ A berns.Bagats) - vīrietis, kam ir meita, kurai visi bērni ir bagāti.
Cilveks = Sieviete v Virietis - definē atvasinātu jēdzienu.
Virs = Virietis ^ E dzivesbiedrs.Sieviete - vīrs te tiek definēts kā vīrietis, kas precējies ar sievieti.
John: Virietis^Bagats - Džons ir bagāts vīrietis.
(John, Peter): berns - Pēteris ir Džona bērns (manuprāt, neveiksmīgs pieraksts - bet ar to būs jādzīvo).
(John, Paris): dzivesbiedrs - Parisa ir Džona dzīvesbiedre.
Uzdevums. Šai brīdī būtu ieteicams patrenēties. Veikla ALC formulu lasīšana un rakstīšana atvieglos kursa apgūšanu un padarīs to patīkamu. Izmantojot minētos valodas līdzekļus, uzrakstiet piecus jaunus jēdzienus. Ja vēlaties, varat ievest papildus atomāros jēdzienus un lomas.
Šī definīcija var likties patīkamāka par definīciju "no augšas", bet šādi definētai "loģikas sistēmai" nav tik viegli uzreiz precīzi nodefinēt semantiku. Definīcijai "no augšas" šīs problēmas nav - aiz tās stāv simtgadīga matemātiskās loģikas vēsture - precīzais formālais jēdziens par valodas interpretāciju. Tāpēc dabiskais ceļš uz precīzu "otrās" ALC semantikas definīciju būtu
ALC "īstās" definīcijas translācija uz loģisko definīciju
Šī translācija definē loģikas ALC izteiksmju precīzo semantiku - katrs jēdziens C (atomārs vai atvasināts) tiks translēts par atbilstošās predikātu valodas formulu C(x) ar vienu brīvu mainīgo x. Un predikātu loģikas formulu semantikai eksistē standarta definīcija - jēdziens par valodas interpretāciju.
[Ko vispār nozīmē - definēt formālas valodas semantiku?]
Piemērs. Minētās valodas primitīvi Sieviete,
Virietis, Bagats jātranslē par vienvietīgām predikātu
konstantēm Sieviete(x), Virietis(x), Bagats(x), kur x
vērtību apgabals ir "visi cilvēki". Predikāts Bagats(x)
būs patiess tad un tikai tad, ja x ir bagāts cilvēks. Lomas berns,
dzivesbiedrs jātranslē par divvietīgām predikātu
konstantēm berns(x, y), dzivesbiedrs(x, y), kas
nozīmē: "x-a bērns ir y", "x-a dzīvesbiedrs ir
y" (vai otrādi: "y ir x-a bērns", "y ir x-a
dzīvesbiedrs"). Un konstrukcija
E berns.Sieviete
jātranslē par formulu
Ey(berns(x, y)&Sieviete(y)),
t.i. "x-am ir meita". Bet konstrukcija
A berns.Sieviete
jātranslē par formulu
Ay(berns(x, y)->Sieviete(y)),
t.i. "x-am visi bērni ir meitas" (pat tad, ja x-am
bērnu vispār nav).
Vispārīgais gadījums:
Valodas primitīvi:
a) Indivīdu vārdus translējam par tādām pat objektu konstantēm.
b) Atomāros jēdzienus p, q, ... translējam par vienvietīgām predikātu konstantēm ar mainīgo x: p(x), q(x), ... (tātad jēdziens būtībā nozīmēs objektu klasi).
c) Lomas s, t, ... translējam par divvietīgām predikātu konstantēm ar mainīgajiem x, y: r(x, y), s(x, y), ... (tātad lomas būtībā ir bināras asociācijas).
Konstruktori:
a) Būla operācijas. Ja jēdzieni C, D jau ir translēti par formulām C(x), D(x), tad C^D translējam par C(x)&D(x), CvD - par C(x)vD(x), -C - par ~C(x). Šīs operācijas tātad atbilst klašu šķēlumam, apvienojumam un papildinājumam.
b) Kvantori. Ja jēdziens C jau ir translēts par formulu C(x), un r ir loma, tad Er.C translējam par Ey(r(x, y)&C(y)), bet Ar.C - par formulu Ay(r(x, y)->C(y)). [Pie tam, formulu C(y) varam veidot no C(x), vienkārši apmainot vietām mainīgos x un y.]
Apgalvojumi par indivīdiem:
a) Ja jēdziens C jau ir translēts par formulu C(x), un c ir indivīda vārds, tad c: C translējam par formulu C(c).
b) Ja c, d ir indivīdu vārdi, un r - lomas, tad (c, d): r translējam par formulu r(c, d).
Tā kā predikātu loģikas formulu semantikai eksistē standarta definīcija - jēdziens par valodas interpretāciju, tad līdz ar to varam teikt, ka šī mūsu translācija precīzi definē arī loģikas ALC ''īstās" definīcijas semantiku.
Piezīme. Kā zināms, klasiskajā predikāti loģikā principā varētu iztikt ar vienu kvantoru, piemēram, eksistences kvantoru ExB(x). Universālkvantoru AxB(x) var izteikt kā ~Ex~B(x). Arī loģikā ALC situācija ir līdzīga: mēs jau zinām, ka izteiksme Ar.C nozīmē klasi {x | Ay(r(x,y)->C(y)}, jeb -{x | Ey(r(x,y)&~C(y)}, t.i. -Er.(-C).
Vaicājumi
Šobrīd laikam varam iedomāties 4 veidu vaicājumus, ko var pierakstīt ar loģikas ALC līdzekļiem:
a) Ja c ir indivīds un C - izteiksme (kas, protams, definē klasi), varam vaicāt, vai tiesa, ka c: C?
b) Ja c un d ir indivīdi, un r ir loma, varam vaicāt, vai tiesa, ka (c, d): r?
c) Ja C ir izteiksme, varam palūgt atrast visus indivīdus, kas pieder klasei C.
d) Ja C1 un C2 ir izteiksmes, noskaidrot, vai klase C1 ir C2 apakšklase, t.i. noskaidrot, vai C1<=C2? [Grāmatās klašu iekļautību attēlo ar "uz labo pusi apgāztu U", kam apakšā pievienota pasvītrojuma zīme.]
Uz šādiem vaicājumiem reducējas arī daži citi:
d1) Vai klase C nav tukša? Citiem vārdiem, vai C <= C ^ -C? [Ja vēlamies, varam ievest speciālu apzīmējumu tukšai klasei, piemēram, O, un tad vaicāt: C<=O?]
d2) Vai klases C un D šķeļas? Citiem vārdiem, vai C^D nav tukša klase?
d3) Vai klases C un D nepārklāj visu apgabalu? Citiem vārdiem, vai C v -C <= CvD? [Ja vēlamies, varam ievest speciālu apzīmējumu "pilnajai" klasei, piemēram, T, un tad vaicāt: T<=CvD?]
e) Tikpat labi visus punktā d) minētos vaicājumus var reducēt uz vaicājumu "Vai C ir tukša klase?" (kur C ir jebkura izteiksme). Tiešām, apgalvojums C1<=C2 ir ekvivalents apgalvojumam "C1 ^ -C2 ir tukšā klase". [Pārliecināsimies!]
ALC paplašinājumi
Vai Jums jau ir izveidojies priekšstats, ko ar ALC valodas līdzekļiem var pierakstīt, un ko nevar? Daudzi nav bijuši apmierināti ar ALC iespējām, tāpēc ir mēģinājuši šo loģiku papildināt ar citiem izteiksmes līdzekļiem. Arī šos ALC papildinājumus pieņemts saukt par aprakstošajām loģikām. Lūk, pirmie piemēri.
Skaitliskie ierobežojumi (number restrictions)
Būtībā tie ir eksistences kvantori "ar skaitītājiem":
>=2 berns.Sieviete - kāds, kam ir vismaz 2 meitas,
<=4 dzivesbiedrs.Sieviete - kāds, kam ir ne vairāk par 4 sievām.
[Grāmatās >= un <= attēlo kā matemātikā pierasts attēlot "lielāks vai vienāds" un "mazāks vai vienāds".]
Parastais eksistences kvantors tad, protams, ir rakstāms kā >=1. Piemēram, E berns.Sieviete vietā varam rakstīt >=1 berns.Sieviete. Skaitlisko ierobežojumu pirmsākumi ir ER-modeļos un UML klašu diagrammās - kā asociāciju galu "kardinalitātes" vai "multiplicitātes". Piemēram, lai pateiktu, ka "katrs darbinieks strādā ne vairāk kā vienā departamentā", mums būtu vajadzīga šāda aksioma:
Darbinieks <= (<=1 strada.Departaments).
Šeit pirmais <= apzīmē klašu iekļaušanu (apakšklasi), bet otrais <= nozīmē "mazāks vai vienāds".
Šādi paplašinātu loģiku ALC pieņemt apzīmēt ar ALCQ (Q - qualified number restrictions).
Lomu inversija
Tas būtu vienkāršākais lomu konstruktora gadījums (līdz šīm mums bija tikai klašu konstruktori).
Katrai lomai r(x, y) dabiski atbilst inversā (jeb apgrieztā) loma r-1(y, x). Piemēram, berns(x, y) inverso lomu berns-1(y, x) varētu apzīmēt ar vecaks(y, x). Citiem vārdiem, r-1(y, x) ir patiess tad un tikai tad, ja r(x, y).
Te ir divas iespējas:
a) Katrai lomai r inversās lomas r-1 apzīmējums ir paredzēts jau pašā valodā. Tad mums ir vajadzīgas attiecīgās aksiomas, piemēram, r-1(y, x) <-> r(x, y). Citādi sakaru starp r un r-1 nevarēsim izmantot. Piemēram, ja mums valodā ir gan loma berns, gan loma vecaks, tad ir vajadzīga aksioma vecaks(y, x) <-> berns(x, y), citādi abi jēdzieni nebūs saistīti.
b) (Populārākā versija) Inversija ir operācija, kas jebkurai lomai r piekārto inverso lomu r-1. Tad sakarība starp r un r-1 pieder pie inversijas operācijas semantikas (t.i. r-1(y, x) <-> r(x, y) skaitīsies jau "loģikas aksioma"). Bet tad vecaks vietā visu laiku būs jāraksta berns-1.
Variantu b) - šādi paplašinātu loģiku ALC pieņemt apzīmēt ar ALCI (I - inversion). Ja pieņem abus jau minētos paplašinājumus (skaitliskos ierobežojumus un lomu inversiju), tad iegūstam aprakstošo loģiku ALCIQ.
Lomu savienošana
Tas ir nākošais lomu konstruktora piemērs.
Atbilde uz kolēģa jautājumu - kā ALC var nodefinēt minēto predikātu VECTEVS(x, y)?
Ar ALC var definēt tikai jēdzienus, bet ne to attiecības.
vectevs = Virietis^(E berns.(E berns.Cilveks))
Šeit nodefinēts vectēva jēdziens tā, kā to dažreiz lieto sarunvalodā cilvēka vecuma apzīmēšanai - "kāds, kam jau ir mazbērns(i)". Bet attiecību "x ir y-a vectēvs" ALC nodefinēt nevarēs, jo no ALC viedokļa tā ir loma, nevis jēdziens.
Lai šādu lomu nodefinētu, vajadzētu ievest lomu savienošanas operāciju "berns o berns" - tas būtu viens no iespējamajiem ALC paplašinājumiem. Precīzāk, lomu r un s savienojums r o s nozīmē pāru kopu { (x,y) | Ez (r(x,z)&s(z,y)) }. T.i. berns o berns nozīmē lomu mazberns. Tālāk, mazberns-1 nozīmē lomu vecvecaks. [Kā vēl pietrūkst, lai iegūtu lomu vectevs?]
Būla operācijas ar lomām
Bet principā klašu konstruktoros E loma.jedziens un A
loma.jedziens varētu izmantot arī lomu izteiksmes.
Valodā pieejamo lomu kolekciju var paplašināt ne tikai,
izmantojot inversiju un savienošanu, bet arī, izmantojot,
konjunkciju, disjunkciju un pat negāciju:
r^s jeb r(x, y)&s(x, y),
r v s jeb r(x, y) v s(x, y),
-r jeb ~r(x,y).
Piemēram, lomu berns un students konjunkcija berns^students
saista doto personu (pasniedzēju) ar tām personām, kas
vienlaicīgi ir tās bērni un studenti.
Šādi iegūtos ALC paplašinājumus pieņemts apzīmēt ar ALC(^, v, -), ALC(^, v), ALC(^) utml.
Tāpat kā klašu konstruktori (^, v, -, E, A) dod iespēju veidot izteiksmes, kas definē atvasinātas klases, tā arī lomu savienošanu, inversiju un Būla operācijas var uzskatīt par lomu konstruktoriem, kas dod iespēju veidot izteiksmes, kas definē atvasinātas lomas.
Nomināļi
Atbildot uz Sergeja Rikačova jautājumu: kā nodefinēt jēdzienu "John-a bērni"? Ar šo jautājumu mēs nonākam pie vēl viena loģikas ALC paplašinājuma - jēdzieniem, kas ir definēti vienkārši kā indivīdu kopas (tos sauc par nomināļiem). Piemēram, jēdziens {John} vai jēdziens {John, Paris}. Ja ir ievests šāds valodas līdzeklis, tad jēdzienu "John-a bērni" var uzrakstīt kā E berns-1.{John}. Šo ALC paplašinājumu pieņemts apzīmēt ar ALCO (vai ALCOQ, vai ALCOIQ, utt. ja vienlaicīgi atļauti arī citi palīglīdzekļi).
Expressiveness of language pret tractability of reasoning
Aprakstošo loģiku paplašināšanas "kopējo noskaņu" var labi sajust, paspēlējoties ar Evgeny Zolin, Description Logic Complexity Navigator. Vēlāk mēs šo ainu izpētīsim ļoti detalizēti. Navigators parāda, kā, mainot atļauto loģikas līdzekļu komplektu, mainās secināšanas sarežģītība (tiek aplūkoti divi secināšānas uzdevumi - Concept satisfiability un ABox consistency). Var novērot, piemēram, ka jo vairāk izteiksmes līdzekļu mēs iekļaujam valodā, jo sarežģītāks kļūst attiecīgais secināšanas uzdevutms. Piemēram, ALC un ALCI, un pat ALCIQ(^, v) secināšanas sarežģītība ir PSPACE-complete, bet ALC(^, v, -) un ALCI(^, v, -) - jau NEXPTIME-complete, t.i. iespēja izmantot lomu negācijas "maksā dārgi".
Veidojot reāli lietojamas secinātāju programmas, ir jābalansē starp valodas "izteiksmību" (expressiveness of language) un secināšanas realizējamību (tractability of reasoning). Nebūs reāli lietojama ne pārāk nabadzīga, ne pārāk bagāta valoda, kurai šīs bagātības dēļ būs pārāk grūti risināms secināšanas uzdevums. Šo novērojumu par savu nopelnu uzskata
R. J. Brachman, H. J. Levesque. The tractability of subsumption in frame-based description languages. In AAAI-84, pp. 34-37, 1984.
Ar šādu balansēšanu mēs tagad kādu laiciņu nodabosimies...