Logika

BME Informatikai K¨ozpont Axelero Internet Rt.

Az inform´ aci´ o´ abr´ azol´ as matematikai m´ odszerei Verzi´osz´am: 1.02

Kardkov´acs Zsolt Tivadar

k´esz´ıtette

A szavak h´ al´ oj´ aban (NKFP-2/0019/2002) projekt keret´eben

Az SQL domesztik´aci´o elm´eleti el˝ok´esz´ıt´ese t´em´aban

2003. ´aprilis 8.

Az inform´ aci´ o´ abr´azol´as matematikai m´odszerei

i

Tartalomjegyz´ ek 1. Bevezet˝ o

1

2. A matematikai fogalmakr´ ol

2

3. Az extenzion´ alis logika

4

3.1. Az ´all´ıt´ aslogika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

3.2. Az els˝ orend˝ u logika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

3.3. A magasabb rend˝ u logik´ akr´ ol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.4. A t¨obb´ert´ek˝ u logika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

4. A le´ır´ o logika

8

5. Az intenzion´ alis logika

9

5.1. Mod´alis logika

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

6. Helyzetk´ epelm´ elet

10

7. Logikai modellek az inform´ aci´ o-visszakeres´ esben

11

¨ 8. Osszefoglal´ o

12

NKFP-2/0019/2002

Az inform´ aci´ o´ abr´azol´as matematikai m´odszerei

1

Az inform´ aci´ o´ abr´ azol´ as matematikai m´ odszerei Kardkov´acs Zsolt Tivadar BME Informatikai K¨ozpont Axelero Internet Rt.

1.

Bevezet˝ o Ha ´altal´aban logik´ ar´ ol besz´el¨ unk, akkor egyfel˝ol ´erthet¨ unk alatta logikus gondolkod´ast, amelyben

´ervek ment´en ´ all´ıt´ asokat fogalmazunk meg; ´erthet¨ unk filoz´ofi´at, amely a vil´ag valamely le´ır´as´at, modellez´es´et pr´ ob´ alja megragadni; de ´erthet¨ unk ´epp´ ugy (term´eszetes) nyelvi k¨ovetkeztet´eseket – gondoljunk csak a szillogizmusokra –, mint matematikai keretrendszert, amelyre l´enyeg´eben a ma haszn´alatos matematikai eszk¨ ozt´ arunkat fel´ep´ıtett¨ uk.

Az inform´aci´o-visszakeres´esben a filoz´ofia, a

nyelvtudom´any ´es a matematikai eszk¨ oz¨ ok azonos s´ ullyal kapnak szerepet. A nyelvtudom´any seg´ıts´eg´evel egy-egy term´eszetes nyelvi mondat vagy inform´aci´o feldolgoz´as´at, jelent´es´enek helyes ´ertelmez´es´et, a nyelv szab´alyszer˝ us´egeinek meghat´ aroz´ as´ at k¨olcs¨on¨ozz¨ uk. A filoz´ofia gondoskodik sz´amunkra arr´ol, hogy az emberi l´at´asm´ odnak legink´ abb megfelel˝ o, vagy ahhoz k¨ozel´all´o, a gondolkod´asunkban hasonl´o g´epi rendszereket, modelleket szerkessz¨ unk ´es val´os´ıtsunk meg. A matematika pedig felder´ıti sz´amunkra, hogy milyen hat´ekonys´ aggal ´es milyen korl´atok k¨oz¨ott vagyunk k´epesek automatiz´alni term´eszetes nyelvi mondatok g´epi meg´ert´es´et” ´es megfelel˝ o elhelyez´es´et. ” Az inform´aci´ o-visszakeres´es logikai fel´ep´ıt´ese teh´at sz¨ uks´egszer˝ uen a term´eszetes nyelvekb˝ol indul ki, ehhez egy megfelel˝ o filoz´ ofiai vil´ agmodellt pr´ob´alunk meg t´ars´ıtani – ami rendszerint t´emater¨ ulet vagy szakmaf¨ ugg˝o – ´es v´eg¨ ul megpr´ ob´ aljuk megtal´alni hozz´a azt a matematikai logikai modellt, amely a lehet˝o legt¨obb inform´aci´ ot k´epes megragadni ´es a lehet˝o legt¨obbet k´epes visszakeresni megfelel˝o v´alaszid˝on bel¨ ul. Egy inform´aci´ ot visszakeres˝ o rendszer j´ os´ aga a matematikai logikai modellj´en kereszt¨ ul ¨osszem´erhet˝o az eml´ıtett h´arom tulajdons´ ag alapj´ an. A l´enyeges k´erd´esek teh´at: • Mely term´eszetes nyelvi form´ ak ´ abr´ azolhat´ok vagy fogalmazhat´ok meg az adott matematikai logikai modellben? Mekkora lehet az egy´ertelm˝ us´eg ´es az ´atfed´es? • Mely inform´ aci´ ok kereshet˝ oek vissza ´es melyek nem, azaz milyen k´erd´esekre kaphatunk helyes v´alaszt az adott matematikai logikai modellben? A kutat´ asi jelent´ es az Axelero Internet Rt. ´ es a BME Informatikai K¨ ozpont tulajdona. A kutat´ ast a Magyar K¨ ozt´ arsas´ ag t´ amogatta az NKFP-2/0019/2002 p´ aly´ azati projekt keret´ eben.

Kutat´ asi jelent´ es, 1. f´ azis, 2003. janu´ ar 31.

NKFP-2/0019/2002

2

Zs. T. Kardkov´acs • Milyen hat´ekonys´ aggal, sz´am´ıt´ asid˝ ovel kereshet˝oek vissza a (helyesen) visszakereshet˝o inform´aci´ok az adott matematikai logikai modellben? A tov´abbiakban az inform´ aci´o-visszakeres´esben ma haszn´alatos matematikai logikai modelleket fogjuk

bemutatni, a h´arom k´erd´esre adand´ o v´ alaszt vizsg´alva. Az egyszer˝ us´eg kedv´e´ert a tov´abbiakban elhagyjuk a matematikai” jelz˝ ot a logikai modellekre vonatkoz´oan, amennyiben ez nem f´elre´erthet˝o. ” A logikai modellek szeml´elet¨ ukben jelent˝os k¨ ul¨onbs´egeket mutatnak ´es ez alapj´an csoportos´ıtani is lehet ˝oket. A logik´ ak egy r´esze kiz´ arja a bizonytalan t´enyez˝ok megjelen´es´et, minden logikai elem az adott elm´eletben pontosan annyit jelent, amennyit az adott szimb´olum ´abr´azolni k´epes - f¨ uggetlen¨ ul att´ol, hogy milyen k¨ ornyezetben fordul el˝ o. Az ilyen logik´akat extenzion´alis logik´anak nevezz¨ uk. Vannak azonban olyan logik´ ak is, amelyekben bizonyos logikai elemek jelent´esm´odosul´ast eredm´enyeznek valamely logikai elem(ek)re vonatkoz´ oan – az ilyen tulajdons´ag´ u logik´akat ¨osszefoglal´oan intenzion´alis logik´aknak nevezz¨ uk. A fejezet tov´ abbi r´esz´eben mindenekel˝ott ¨osszefoglaljuk a l´enyegesebb matematikai fogalmakat, amelyekkel dolgozni fogunk. A fogalmainkb´ ol kiindulva bemutatjuk az extenzion´alis logika legismertebb tagj´at, az els˝orend˝ u matematikai logik´ at – elemezz¨ uk k´epess´egeit ´es hi´anyoss´agait egyar´ant, tov´abb´a megmutatjuk, milyen b˝ ov´ıt´esekkel ´elhet¨ unk m´eg az extenzion´alis logika keretein bel¨ ul, milyen kiterjeszt´esei lehetnek m´eg az els˝ orend˝ u logik´anak. Az extenzion´alis logika fogalmi hi´anyoss´againak, t¨obb´ertelm˝ us´eg´enek felold´ as´ ara alkott´ ak meg az u ´n. le´ır´o logik´at, amely tulajdonk´eppen ´atmenetet k´epez az extenzion´alis ´es az intenzion´ alis vil´ ag k¨ oz¨ott. A le´ır´o logik´ak ut´an az intenzion´alis logik´ak adotts´agait vizsg´aljuk meg, ezen bel¨ ul is hangs´ ulyt fektetve a k¨ ul¨onb¨oz˝o mod´alis logik´ak alkalmazhat´os´ag´ara. A logikai rendszerek megismer´ese ut´ an sz´ amos inform´aci´o-visszakeres´esi elm´eletet ´es modellt mutatunk be, mintegy illusztr´ aland´ o, hogy mik´eppen lehet (vagy hogyan szok´as) a t´argyalt matematikai eszk¨ozt´arakat k¨ozvetlen¨ ul felhaszn´ alni az adott k¨ ornyezetben.

2.

A matematikai fogalmakr´ ol Ahogy a bevezet˝ oben is eml´ıtett¨ uk, a matematikai logika fel´ep´ıt´es´et a term´eszetes nyelvek fel˝ol ´erdemes

– az inform´aci´ o-visszakeres´es vil´ ag´ aban pedig sz¨ uks´eges – megk¨ozel´ıteni. Mindenekel˝ott r¨ogz´ıts¨ uk le, hogy ´all´ıt´asok, ´ all´ıt´ o mondatok logik´ aj´ aval fogunk ebben a k¨ornyezetben foglalkozni, b´ar a tudom´anyban ismeretes a k´erd´eslogika elemz´ese is. Mondat alatt teh´at a tov´abbiakban egy kijelent˝o (vagy ´all´ıt´o) mondatot ´ert¨ unk.

A mondat a legnagyobb logikai egys´eg.

A logik´aban feltessz¨ uk, egy ´all´ıt´ashoz

rendelhet¨ unk valamilyen ´ıt´eletet – amely vagy igaz, vagy hamis. Term´eszetesen el˝ ofordulhat, hogy az a ´ll´ıt´as” val´oj´aban egy tagad´o mondat, valaminek a l´etez´es´et ” c´afolja – ´es mag´ aban az ´ all´ıt´ as. Mondataink sok esetben kisebb egys´egekb˝ol, tagmondatokb´ol ´allnak ¨ossze. A tagmondatok is lehetnek sok esetben ¨on´all´o mondatok – m´as k¨ornyezetben, gondoljunk csak a mondatok mell´erendel˝ o viszony´ ara. A tagmondatokat k¨ot˝oszavakkal illesztj¨ uk ¨ossze, amilyen p´eld´aul az ´es” a vagy”, de ide sorolhat´ o a ha . . . , akkor . . . ” szerkezet is. A tagad´asok megfelel˝o szavainak, ” ” ” tov´abb´a a mondatokat ¨ osszek¨ ot˝o szavaknak a logikai megfelel˝oit logikai oper´atoroknak vagy m´ask´eppen mondatfunktoroknak nevezz¨ uk. Mondataink a vil´ ag egyedeir˝ol fogalmaznak meg valamilyen ´all´ıt´ast. A vil´ag egyedeinek tekint¨ unk mindent, amelynek valamely konkr´et el˝ ofordul´as´at ¨on´all´o n´evvel azonos´ıtani tudunk. Ezeket h´ıvjuk individuumoknak vagy konstansoknak – tipikusan ilyenek a f˝ onevek ´es a sz´amnevek. Az individuumok

A szavak h´al´oj´aban

Az inform´ aci´ o´ abr´azol´as matematikai m´odszerei

3

egy halmaz´at is jel¨ olhetj¨ uk valamilyen ¨ on´ all´o n´evvel – ezeket v´altoz´oknak nevezz¨ uk. A v´altoz´o ´ert´ek´en pedig az individuum halmaz valamely elem´et ´ertj¨ uk. A konstansokat ´es v´altoz´okat ¨osszefoglal´oan (logikai) neveknek nevezz¨ uk. A nevek a logika atomi egys´egei. El˝ofordulhat, hogy ugyanannak az individuumnak t¨obbf´ele megnevez´ese is l´etezik, de olyan is, hogy csak egy, amely m´ as nevekb˝ ol k´epezhet˝ o. Ilyenre p´elda lehet a Mikl´os anyja” kifejez´es – b´arki legyen is ” az a konkr´et szem´ely, de ilyen az aritmetik´aban p´eld´aul az ¨osszead´as is: a 4 mint sz´am fel´ırhat´o 3 + 1, 2 + 2 alakokban is. A nevekb˝ ol nevet el˝ o´ all´ıt´o m˝ uveleteket” n´evfunktoroknak h´ıvjuk, de legt¨obbsz¨or ” csak funktork´ent emlegetj¨ uk. A p´eld´ ankban az anyja” ´es +” kifejez´es egy-egy funktor. Egy-egy funktor ” ” argumentumsz´ ama tetsz˝ olegesen nagy lehet, de az argumentumok sorrendje mindig r¨ogz´ıtett – gondoljunk csak az oszt´as m˝ uvelet´ere. A nevek k¨ oz¨ ott ´ertelmezhet¨ unk valamilyen kapcsolatot, rel´aci´ot – valamilyen elemi ´all´ıt´ast.

A

logikai rel´aci´ora lehet p´elda a Mikl´ os anyja M´aria” ´all´ıt´as, vagy az aritmetik´at illet˝oen p´eld´aul az ” 3 < 4” is – a hagyom´ anyos ´ertelmez´essel. A logikai rel´aci´okat predik´atumoknak nevezz¨ uk, amelyek ” teh´at a legegyszer˝ ubb, atomi mondatok. A predik´atumok tetsz˝olegesen sok argumentummal rendelkez˝o mondats´em´ak. A f¨ uggv´enyekhez hasonl´ oan az argumentumok sorrendje r¨ogz´ıtett, sorrendt˝ol f¨ ugg a jelent´ese, azaz sorrendhelyesen ´ertelmezend˝o – hiszen vil´agos k¨ ul¨onbs´eg van, ´es kell legyen a k¨oz¨ott, hogy Mikl´os anyja M´ aria” vagy M´ aria anyja Mikl´os”. ” ” Predik´atumok nevek k¨ oz¨otti viszonyt jeleznek meghat´aroz´asunk szerint, ugyanakkor a nevekbe ¨ all´o beletartoznak a v´ altoz´ ok is, ilyen m´ odon individuumok halmaz´ar´ol is tehet¨ unk ´all´ıt´asokat. On´ jelent´essel azonban a v´ altoz´ o nem b´ır, csak valamely ´ert´eke – ´ıgy c´elszer˝ unek l´atszik meghat´arozni, hogy konkr´etan milyen ´ert´ekre ´ertelmezz¨ uk az ´all´ıt´ast. Az ´ert´ekk´eszletre vonatkoz´o megszor´ıt´o ´all´ıt´asokat kvantoroknak nevezz¨ uk. Ilyenek a term´eszetes nyelvben a minden”, a van olyan”, de m´eg az az, aki” ” ” ” t´ıpus´ u szerkezetek is. Ha egy mondatban minden v´altoz´o legal´abb egy kvantor korl´atoz´o hat´alya al´a esik, akkor z´art mondatr´ ol, ellenkez˝ o esetben ny´ılt mondatr´ol besz´el¨ unk. Ny´ılt mondatokr´ol az inform´aci´ ovisszakeres´es t´emak¨ or´eben, vagy a term´eszetes nyelvi le´ır´asok kapcs´an a tov´abbiakban nem esik sz´o, nem tartjuk l´enyegesnek r´eszletes t´ argyal´ as´ at. ¨ Osszefoglal´ oan:

bemenet/kimenet

n´ ev

mondat

´ ert´ ekkorl´ atoz´ as

nevekb˝ol

funtorok

predik´atumok

kvantorok1

mondatokb´ ol

kvantorok

mondatfunktorok

A logikai le´ır´ asunk c´elja az, hogy a term´eszetes nyelvet univerz´alisan, g´epi meg´ert´esre alkalmasan formaliz´alja.

A formaliz´ al´ as egy nyelvtan vagy grammatika megteremt´ese, amelyben adott szavak

vannak ´es benne mondatk´epz´esi szab´ alyokat defini´alunk. A formaliz´alt alak nyelvf¨ uggetlen kell legyen, de nem lesz ´ertelmes,

besz´edes” – teh´ at csak az eredetileg lek´epzend˝o mondat ismeret´eben tudjuk ” pontosan megmondani, mit jelent az adott logikai kifejez´es. Viselked´ese, igazs´agtartalma azonban az eredetivel azonos kell legyen – err˝ ol nyelvtanhoz tartoz´o (ki)´ert´ekel´esi szab´alyrendszer (m´odszer), azaz

egy interpret´aci´ o vagy strukt´ ura gondoskodik. K¨ovetkez´esk´eppen a g´epi k¨ovetkeztet´es ´es meg´ert´es” ” sz¨ uks´egszer˝ uen nem felfog´ as” vagy ´erz´ekel´es, hanem hasonl´o tulajdons´agokb´ol levont kiz´ar´olag nyelvi ” 1 Els˝ osorban

neveken ´ ertelmezz¨ uk, de a magasabb rend˝ u logik´ ak eset´ eben v´ altoz´ oszimb´ olum jel¨ olhet predik´ atumot is –

´ıgy ´ ertelmezhet˝ ok r´ a a kvantorok.

NKFP-2/0019/2002

4

Zs. T. Kardkov´acs

k¨ovetkeztet´es, azonos helyzetekben, azonos ´ert´ekel´esi form´akkal.

Ennek megfelel˝oen a b´armely

inform´aci´ot visszakeres˝ o rendszer helyes matematikai modellje logikus, t¨orv´enyszer˝ u eredm´enyeket fog szolg´altatni, de nem v´ arhat´ o el t˝ ole az ´esszer˝ us´eg.2 A jel¨ol´eseket illet˝ oen az individuumok jel¨ol´es´ere haszn´alt u ´n. konstansszimb´olumokat kisbet˝ uvel ´ırjuk,

m´ıg a v´ altoz´ oszimb´ olumokat nagybet˝ uvel.

A predik´atumokat ´es funktorokat jel¨ol˝o

predik´atumszimb´ olumokat ´es f¨ uggv´enyszimb´olumokat szint´en kisbet˝ uvel ´ırjuk, argumentumait vessz˝ovel v´alasztjuk el ´es z´ ar´ ojelek k¨ oz´e ´ırjuk. A f¨ uggv´eny- ´es predik´atumszimb´olumokat a logikai szerkezetben meghat´arozott hely¨ uk egy´ertelm˝ uen azonos´ıtja, nem ¨osszekeverhet˝oek.

3.

Az extenzion´ alis logika Az extenzion´ alis logik´ aban minden szimb´olum pontosan ugyanazt jelenti b´armely el˝ofordul´as´aban,

teh´at semmif´ele bizonytalans´ agi t´enyez˝ ot nem kell erre vonatkoz´oan figyelembe venn¨ unk. Ez egyben azt is jelenti, hogy kiz´ ar´ olag olyan ´ all´ıt´ asokkal dolgozunk, amelyek t´enyek, bizonyosan eld¨onthet˝oek ismereteinkb˝ol.

3.1.

Az ´ all´ıt´ aslogika

A legegyszer˝ ubb extenzion´ alis logika az ´all´ıt´aslogika.

Az ´all´ıt´aslogik´aban a nevek csak

konstansszimb´olumokb´ ol ´ allnak, teh´ at nincsenek benne v´altoz´ok - ennek megfelel˝oen a kvantorok sem ´ertelmezettek. Az ´ all´ıt´ aslogik´ aban ´ertelmezz¨ uk a mondatfunktorok k¨oz¨ ul a tagad´ast ´es az ”´es” kapcsolatot - az ¨ osszes t¨ obbi l´enyegesebb mondatfunktor kifejezhet˝o e kett˝o seg´ıts´eg´evel. A f¨ uggv´enyek ´es a predik´atumok sz´ ama tetsz˝ oleges lehet - egy-egy ´all´ıt´aslogikai nyelvet csak ezek alapj´an tudunk megk¨ ul¨onb¨oztetni. Az ´ all´ıt´ aslogika nagyon j´ol alkalmazhat´ o az adatt´arol´as ter¨ ulet´en, de egyszer˝ u logikai k¨ovetkeztet´esek ellen˝ orz´es´ere is. A legt¨ obb adatb´azis-kezel˝o adatdefin´ıci´os nyelve ´all´ıt´aslogik´an alapszik. Az ´all´ıt´aslogika azonban ¨ onmag´ aban nem alkalmas visszakeres´esre, ehhez sz¨ uks´eg¨ unk lenne m´ar az individuumok halmaz´ anak ´ abr´ azol´ as´ ara - a v´altoz´okra ´es a kvantorokra is.

3.2.

Az els˝ orend˝ u logika

Az els˝orend˝ u logika n´evter´eben az individuumokat jel¨ol˝o konstansszimb´olumok valamilyen, nem felt´etlen¨ ul v´eges ´es a v´ altoz´ oszimb´ olumok v´egtelen halmaza tal´alhat´o. Az els˝orend˝ u logika nyelvtan´aban n´evfunktorok is vannak. A konstansszimb´ olumok ´es a v´altoz´ok mindegyik´et termnek nevezz¨ uk, tov´abb´a ha f egy n-v´altoz´ os n´evfunktor megval´ osul´ asa – azaz f egy f¨ uggv´enyszimb´olum –, ´es t1 , t2 , . . . , tn termek, akkor f (t1 , t2 , . . . , tn ) is egy term. Legyen a nyelv¨ unkben ´ertelmezve az ´es” k¨ot˝osz´onak megfelel˝o ∧”, a ” ” tagad´asnak – azaz a nem” sz´ onak – megfelel˝o ¬”, a vagy” k¨ot˝osz´onak megfelel˝o ∨”, a ha . . . , akkor ” ” ” ” ” . . . ” nyelvtani szerkezetnek megfelel˝ o ⇒” szimb´olum; tov´abb´a a kvantorok k¨oz¨ ul a minden” kifejez´esnek ” ” megfelel˝o ∀”,a l´etezik olyan” kifejez´esnek megfelel˝o ∃” szimb´olum, ´es v´eg¨ ul a predik´atumszimb´olumok ” ” ” valamely v´eges halmaza. A mondatk´epz´esi szab´alyaink pedig legyenek a k¨ovetkez˝ok: 1. Ha p egy predik´ atumszimb´ olum ´es t1 , t2 , . . ., tn termek, akkor p(t1 , t2 , . . . , tn ) egy formula (mondat). 2 Isaac

Asimov nyom´ an.

A szavak h´al´oj´aban

Az inform´ aci´ o´ abr´azol´as matematikai m´odszerei

5

2. Ha ϕ egy formula, akkor ¬ϕ is egy formula. 3. Ha ϕ1 ´es ϕ2 egy-egy formula, akkor ϕ1 ∧ ϕ2 , ϕ1 ∨ ϕ2 , ϕ1 ⇒ ϕ2 is egy-egy formula. 4. Ha ϕ egy formula ´es X egy v´ altoz´ o, akkor ∀Xϕ ´es ∃Xϕ egyar´ant formul´ak. Hasonl´oan a termek defin´ıci´ oj´ ahoz a formul´ak – azaz a mondatok – meghat´aroz´asa is rekurz´ıv. A nyelvtan seg´ıts´eg´evel most m´ ar tetsz˝ oleges els˝orend˝ u logikai mondatot el˝o tudunk ´all´ıtani. A mondataink igazs´agtartalm´ at azonban m´eg nem tudjuk ´abr´azolni.

Hasonl´oan a val´os´aghoz, bizonyos ´all´ıt´asok,

amelyek egyetemlegesen igazak ´es vannak bizonyos ´all´ıt´asok, amelyek csak egy-egy helyzetben vagy n´ez˝opontban igazak. Ezeket a bizonyos n´ez˝opontokat nevezz¨ uk interpret´aci´onak vagy strukt´ ur´anak; az olyan ´all´ıt´asokat, amelyen minden strukt´ ur´ an igazak, azokat pedig logikai igazs´agoknak. Hogyan lehet matematikailag megragadni a strukt´ ur´at? A strukt´ ura alatt ´erts¨ uk az individuumok egy U halmaz´anak ´es egy olyan φ f¨ uggv´eny p´aros´at, amely valamilyen ´ert´ekeket rendel a nyelv termjeihez ´es predik´atumaihoz, az al´ abbiak szerint: • Ha c egy konstansszimb´ olum, akkor φ(c) ∈ U . • Ha p egy 0-argumentum´ u predik´ atum, akkor φ(p) a 0, 1 (hamis, igaz) igazs´ag´ert´ekek egyike. • Ha p egy n-argumentum´ u predik´ atum, ahol n ≥ 1, akkor φ(p) az U elemeib˝ol k´epzett rendezett n-esek egy halmaza. Vezess¨ unk be a nyelvtani elemek ´ert´ekel´es´ere” egy ν-f¨ uggv´enyt. Ahogy kor´abban eml´ıtett¨ uk, ” formul´aink z´artak, azaz minden v´ altoz´ oszimb´olum valamely kvantor hat´ask¨or´eben ´all. A mondatok egy ν ´ert´ekel´es´er˝ol teh´ at a k¨ ovetkez˝ot mondhatjuk el: 1. Ha c egy konstansszimb´ olum, akkor ν(c) = φ(c). 2. Ha p egy 0-argumentum´ u predik´ atum, akkor ν(p) = φ(p). 3. Ha p egy n-argumentum´ u predik´ atum, ahol n

≥

1, t1 , t2 , . . . , tn termek, akkor

ν(p(t1 , t2 , . . . , tn )) akkor igaz – azaz egyenl˝o 1-gyel –, ha < ν(t1 ), ν(t1 ), . . . , ν(tn ) >∈ φ(p), ahol < ν(t1 ), ν(t1 ), . . . , ν(tn ) > egy rendezett n-es. 4. Ha ϕ egy formula, akkor ν(ϕ) = 1 − ν(ϕ) 5. Ha ϕ1 ´es ϕ2 egy-egy formula, akkor ν(ϕ1 ∧ ϕ2 ) = 1, ha ν(ϕ1 ) = ν(ϕ2 ) = 1, 0 m´ask¨ ul¨onben. 6. Ha ϕ1 ´es ϕ2 egy-egy formula, akkor ν(ϕ1 ∨ ϕ2 ) = 0, ha ν(ϕ1 ) = ν(ϕ2 ) = 0, 1 m´ask¨ ul¨onben. 7. Ha ϕ1 ´es ϕ2 egy-egy formula, akkor ν(ϕ1 ⇒ ϕ2 ) = 0, ha ν(ϕ1 ) = 1 ´es ν(ϕ2 ) = 0, 1 m´ask¨ ul¨onben. 8. Ha ϕ egy formula ´es X egy v´ altoz´ o, akkor ∀Xϕ = 0, ha van olyan u ∈ U , amelyre ν(ϕ(X = u)) = 0, ahol ϕ(X = u) azt jelenti, hogy X minden ϕ-beli el˝ofordul´as´anak hely´ebe u-t ´ırunk. 9. Ha ϕ egy formula ´es X egy v´ altoz´ o, akkor ∃Xϕ = 1, ha van olyan u ∈ U , amelyre ν(ϕ(X = u)) = 1, ahol ϕ(X = u) azt jelenti, hogy X minden ϕ-beli el˝ofordul´as´anak hely´ebe u-t ´ırunk.

NKFP-2/0019/2002

6

Zs. T. Kardkov´acs Ha vessz¨ uk a nyelv formul´ ainak valamely Σ halmaz´at, akkor a Σ halmazt kiel´eg´ıthet˝onek nevezz¨ uk,

´es azt mondjuk, hogy van modellje, amennyiben van olyan strukt´ ura ´es ´ert´ekel´es, azaz egy modell, amelyben a Σ halmaz minden eleme igazz´ a tehet˝o, azaz 1-gyel egyenl˝o. Egy formulahalmaz szemantikus k¨ovetkezm´eny´enek nevezz¨ uk a ϕ formul´ at, amennyiben az adott Σ ∪ {¬ϕ} halmaz nem kiel´eg´ıthet˝o. Ha Σ formulahalmaz u ¨res, akkor logikai igazs´agokr´ol besz´el¨ unk.

A szemantikai k¨ovetkezm´enyek

meg´allap´ıt´as´ahoz teh´ at mindenk´eppen sz¨ uks´eg¨ unk van a modell teljes k¨or˝ u – ´ıgy valamennyi, az egyes predik´atumokat ´es formul´ akat kiel´eg´ıt˝o ´ert´ekek – ismeret´ere is. A megk¨ozel´ıt´es ez´ert nevezik modellelm´eleti fel´ep´ıt´esnek. Az els˝orend˝ u logika fel´ep´ıt´es´et azonban m´as megk¨ozel´ıt´esben is elk´epzelhetj¨ uk. Az elk´epzel´es alapelve szerint a nyelvtani szab´ alyokb´ ol k´epezhet˝ ok olyan s´em´ak, amelyeket ak´armilyen formul´aval t¨olten´enk is ki, minden esetben igaz ´ all´ıt´ ast eredm´enyezn´enek.

Ezeknek egy minim´alis halmaz´at nevezz¨ uk

alaps´em´aknak vagy axi´ omarendszernek. Az alaps´em´akba, vagy azok egym´asba ´agyaz´as´aval nyert s´em´akba behelyettes´ıtett formul´ ak (illetve azok ∀” kvantorral vett lez´artjaik) az alapformul´ak. Term´eszetesen ” minden alapformula logikai igazs´ ag – a defin´ıci´o szerint. Ha Σ egy formulahalmaz, ´es ϕ pedig egy tetsz˝oleges formula, akkor a Σ formulahalmaz szintaktikus k¨ovetkezm´enyek mondjuk a ϕ formul´at, amennyiben: 1. alapformula, vagy 2. ϕ ∈ Σ, vagy 3. ha ϕ0 ⇒ ϕ ´es ϕ0 egyar´ ant szintaktikus k¨ovetkezm´enyei Σ formulahalmaznak. A 3. pontban le´ırt szab´ aly a modus ponens. A szintaktikus k¨ovetkezm´eny mint fogalom csak a nyelvtani szerkezettel foglalkozik, bizonyos ismeretek fenn´all´as´ab´ol kiindulva. L´enyeg´eben teh´at igaz ´all´ıt´asokb´ol ´all´ıt el˝ o (´ ujabb, esetleg m´eg nem ismert) igaz ´all´ıt´asokat az alaps´em´ak ´es a modus ponens alapj´an; azaz bizony´ıt´ ast v´egez. A megk¨ ozel´ıt´est ez´ert nevezik bizony´ıt´aselm´eleti fel´ep´ıt´esnek. Ismert t´eny, hogy a bizony´ıt´ aselm´eleti ´es a modellelm´eleti megk¨ozel´ıt´es megfeleltethet˝ok egym´asnak, teh´at szemantikai k¨ ovetkezm´eny,

szemantikai igazs´ag el˝o´all´ıthat´o algoritmussal,

a szintaktikai

saj´atoss´agok felhaszn´ al´ as´ aval. Ezt a t´enyt u ´gy fejezz¨ uk ki, hogy azt mondjuk, az els˝orend˝ u logika teljes. A teljess´eg a g´epi feldolgoz´ asn´ al fontos, b´ar nem elengedhetetlen k¨ovetelm´eny. Fontos, mert a bevitt adatokn´al, inform´aci´ okn´ al sok esetben t¨ obbet szeretn´enk el˝o´all´ıtani – ´es arra t¨oreksz¨ unk, hogy valamennyi (nem ismert) igaz ´ all´ıt´ as el˝ o´ all´ıthat´ o legyen. Ugyanakkor nem elengedhetetlen, mivel a min˝os´eg ´es a hat´ekonys´ag sokszor fontosabb tulajdons´ ag a mindenhat´os´agn´al” – ´altal´aban pedig k¨olcs¨on¨osen kiz´arj´ak ” egym´ast. Az els˝orend˝ u logikai rendszerek teljess´eg´ere vonatkoz´oan k´et negat´ıv t´ezist is ismer¨ unk. Az egyik az u ´n. G¨odel-f´ele inkompletts´egi t´etel, amely szerint kell˝oen nagy kifejez˝oerej˝ u, ellentmond´asmentes ´es z´art rendszerek eset´eben nem adhat´o meg v´eges axi´omarendszer. A m´asik ennek egyfajta k¨ovetkezm´enye, amit Church t´ezis´enek nevez¨ unk; ha v´eges axi´omarendszer meg is adhat´o egy kell˝oen nagy kifejez˝oerej˝ u, ellentmond´asmentes ´es z´ art rendszerhez, akkor sem eld¨onthet˝o egy ilyen modell, azaz nincs semmilyen garancia arra, hogy egy sz´ am´ıt´ og´ep, pontosabban egy u ´n. Turing-g´ep mindenk´eppen befejezi a fut´as´at bizonyos probl´em´ ak megold´ as´ anak keres´esekor.

Mivel az ellentmond´as-mentess´eg n´elk¨ ul¨ozhetetlen

tulajdons´ag, a v´eges axi´ omarendszer legt¨ obbsz¨or a hat´ekonys´ag z´aloga, a z´arts´ag elhagy´asa pedig komoly ´abr´azol´asi neh´ezs´egeket vetne fel, ´ıgy a kifejez˝oer˝ob˝ol c´elszer˝ u ´esszer˝ u keretek k¨oz¨ott engedni. Ennek megfelel˝oen a legt¨ obb esetben az els˝ orend˝ u logikai modellek valamilyen r´eszhalmaz´ara, korl´atoz´as´ara szor´ıtkozunk.

A szavak h´al´oj´aban

Az inform´ aci´ o´ abr´azol´as matematikai m´odszerei 3.3.

7

A magasabb rend˝ u logik´ akr´ ol

Az els˝orend˝ u logika kifejez˝ oereje b´ ar meglep˝oen sok esetben kiel´eg´ıt˝onek bizonyult, azonban sz´amos alkalommal sz¨ uks´eg van valamilyen kiterjeszt´es´ere is – leggyakrabban a rekurz´ıv, vagy ¨or¨okl˝od˝o tulajdons´agok logikai megfogalmaz´ asakor. Vizsg´aljuk meg p´eld´aul, hogy hogyan defini´aln´ank az emberek k¨oz¨otti o˝se” kapcsolatot matematikai formul´aval! Vil´agos, hogy X szem´ely akkor ˝ose Y szem´elynek, ha ” ” X k¨ozvetlen sz¨ ul˝ oje, vagy Y valamely sz¨ ul˝ oj´enek sz¨ ul˝oje, vagy Y valamely sz¨ ul˝oj´enek sz¨ ul˝oinek a sz¨ ul˝oje, . . . ” A megfogalmaz´ as korl´ atlan hossz´ u logikai vagy” kapcsolatot ig´enyelne. Hogy v´eges hossz´ u alakban ” fel´ırhassuk pr´ob´ aljuk meg a r´esztulajdons´ agokat, az ¨or¨okl˝od˝o tulajdons´agokat megragadni. Az olyan tulajdons´ agokat, amelyek sz¨ ul˝ or˝ol gyermek´ere ¨or¨okl˝odnek foglaljuk az o¨r¨okl˝od˝o” (inherited) ” predik´atumszimb´ olumba, majd ennek seg´ıts´eg´evel ´ırjuk fel a az ˝ose” (ancestor) kapcsolatot: ” def

∀X∀Y

def

∀p inherited(p) ⇒ (p(X) ⇒ p(Y ))

inherited(p) ⇐⇒ ancestor(X, Y ) ⇐⇒

p(X) ∧ parent(X, Y ) ⇒ p(Y )

Behelyettes´ıtve a o ¨r¨ okl˝ od˝ o” (inherited) predik´atumot a meghat´aroz´as´aval, z´art formul´at kapunk. ” Azonban a formul´ aban olyan v´ altoz´ ot helyezt¨ unk kvantor hat´ask¨or´ebe, amely val´oj´aban nem individuumok egy halmaz´ at, hanem predik´atumok egy halmaz´at jel¨oli. A m´asodrend˝ u logika voltak´eppen az els˝orend˝ u logikai olyan kiterjeszt´ese, amelyben a v´altoz´ok jel¨olhetnek predik´ atumok vagy n´evfunktorok egy-egy csoportj´at. az els˝orend˝ u logik´ aval.

Minden m´ast tekintve azonos

A m´ asodrend˝ u logik´aban azonban m´ar elvi ´ertelemben sem lehet olyan

bizony´ıt´aselm´eleti megk¨ ozel´ıt´est adni, amely a modellelm´eleti t´ars´anak kifejez˝oerej´et megk¨ozel´ıten´e, emiatt igen neh´ez k¨ ovetkeztet´es u ´tj´ an b´armif´ele u ´j, az inform´aci´os rendszerbe el˝ozetesen be nem vitt megismer´esre szert tenni a m´ asodrend˝ u logika seg´ıts´eg´evel. Term´eszetesen, a m´asodrend˝ u logika kiterjeszthet˝o magasabb rend˝ u logik´ av´ a, egyre ¨osszetettebb fogalmak le´ır´as´ara alkalmass´a t´eve azt. Ilyen fogalom lehet p´eld´ aul a valamely di´ ak”, minden orvos”, a felv´eteliz˝ok t¨obbs´ege”, n´egy musk´et´as” stb. ” ” ” ” A magasabb rend˝ u logik´ akra vonatkoz´ oan szint´en nem adhat´o olyan bizony´ıt´aselm´eleti eszk¨oz, amely a modellelm´eleti megk¨ ozel´ıt´essel azonos kifejez˝oerej˝ u lenne, hiszen m´ar a m´asodrend˝ u logik´aban sem lehets´eges ez, amely r´eszhalmaz´ at k´epezi a magasabb rend˝ u logik´aknak.

3.4.

A t¨ obb´ ert´ ek˝ u logika

Az els˝orend˝ u logik´ aban k´etf´ele igazs´ ag´ert´eket k¨ ul¨onb¨oztett¨ unk meg; az igaz ´es a hamis ´ert´ekeket, amelyeket rendre 1 ´es 0 sz´ amjegyek szimboliz´altak. Nyilv´anval´oan, ami nem volt igaz, azt sz¨ uks´egszer˝ uen hamisnak tekintett¨ uk. A besz´elt nyelvben azonban a tagad´as sokszor nem jelenik meg ilyen ´elesen. Gondoljunk csak a h´ıres mond´ asra, miszerint aki nem vel¨ unk van, az ellen¨ unk”. Az ´all´ıt´as sark´ıtott, ” mondjuk azt, hogy nem igaz, hiszen sz´ o sincs arr´ol, hogy csak ez a k´et lehet˝os´eg ´allna fenn – az, hogy valaki nem vel¨ unk tart, m´eg nem sz¨ uks´egszer˝ uen van ellen¨ unk, lehet k¨oz¨omb¨os r´esztvev˝oje is az esem´enyeknek. De hasonl´oan j´ ol ismert, hogy ha a bar´ at ´es ellens´eg fentiekben ´elesen meg´allap´ıtott modellj´et venn´enk, akkor a bar´at bar´ atja ´es az ellens´eg ellens´ege sem biztos, hogy bar´at vagy ´eppen ellens´eg. Megfigyelhet˝ o, hogy az igazs´ ag´ert´ekek az´ert nem egym´as ellent´etei a fenti p´eld´akban, mert egy adott ´all´ıt´ast k¨ozvetve, ´ all´ıt´ assal tagadtunk, nem pedig a m´ar j´ ol ismert nem” tagad´osz´oval. A t¨obb´ert´ek˝ u ” logik´ak eredm´enyei javar´eszt az u ´n. mod´ alis logik´aban jelentek meg teljes form´ajukban – r´eszletes tov´abbi t´argyal´as´at ehely¨ utt nem folytatjuk.

NKFP-2/0019/2002

8

Zs. T. Kardkov´acs

4.

A le´ır´ o logika Az extenzion´ alis logik´ ak eset´eben felmer¨ ulhet valamif´ele hi´anyoss´ag bizonyos individuumok

megnevez´esekor. Milyen hi´ anyoss´ agokr´ ol lehet sz´o? Vegy¨ unk egy ´all´ıt´ast, amely szerint Az u ¨gyn¨ok, ” aki Am´alk´at alkalmazta, csak k´epzett titk´ arn˝oket alkalmazott”. Logikus lenne arra k¨ovetkeztetni, hogy Am´alka k´epzett titk´ arn˝ o. De hogyan lehetne ezt bizony´ıtani? B´armilyen form´alis fel´ır´ast is tenn´enk az u ¨gyn¨ok szem´ely´enek meghat´ aroz´ as´ aban, bizonytalans´agot tapasztalhatunk, hiszen nem tudjuk, hogy pontosan kir˝ol van sz´ o, csak azt, hogy egy´ertelm˝ uen meghat´arozott a szem´elye. Tal´an a leg¨otletesebb a mondat ´abr´azol´ as´ ara az al´ abbi implik´ aci´ o fel´ır´asa: ∀X(c = u ¨gyn¨ ok, aki Am´ alk´ at alkalmazta) ∧ alkalmazta(c, X) ⇒k´epzett titkarn˝o(X) Ez az az, aki” vagy az, ami” egy logikai oper´ator – amely teh´at (nyitott) mondatokb´ol k´epez ” ” nevekre. Ilyen tulajdons´ ag´ u logikai elem¨ unk az extenzion´ alis logik´aban nem volt – sz¨ uks´egszer˝ uen nem lehet n´evfunktor, sem konstansszimb´ olum, se predik´atum. Jobb h´ıj´an kvantornak tekintj¨ uk ´es le´ır´onak vagy deskriptornak nevezz¨ uk, ´es I-vel jel¨ olj¨ uk. A fenti p´eld´aban a c meghat´aroz´asa a k¨ovetkez˝ok´eppen n´ezhet ki: IY

u ¨gyn¨ ok(Y ) ∧ alkalmazta(Y, Am´alka)

Szemantikai ´ertelemben a le´ır´ onak csak abban az esetben van ´ertelme, ha az egyetlen individuumot jel¨ol.

Mindent ¨ osszevetve a le´ır´ o logika voltak´eppen extenzion´alis logika, ugyanakkor valamilyen

bizonytalans´ag m´ ar megjelent a form´ alis megfogalmaz´asban, nem felt´etlen¨ ul vagyunk teljes m´ert´ekben tiszt´aban azzal, hogy kir˝ ol ´ all´ıtunk valamit mondatainkban.

Ilyen ´ertelemben a le´ır´o logik´at az

extenzion´alis ´es az intenzion´ alis logika k¨ oz¨ otti valamif´ele ´atmenetnek tekintj¨ uk. Felvet˝odik a k´erd´es, hogy mi t¨ ort´enik a le´ır´onkkal abban az esetben, ha a le´ır´as” egyetlen egyet ” sem, vagy egyn´el t¨ obb individuumot jel¨ ol. A nyelvtanilag j´ol k´epzett mondatainkban ilyenkor ´ert´ekr´es keletkezhet. P´eld´ aul az a n´ev, amelyet a B´alint testv´ere” kifejez´es jel¨ol voltak´eppen lehet nem l´etez˝o ” szem´ely is bizonyos strukt´ ur´ akban, de lehet egyn´el t¨obb szem´ely meghat´aroz´asa is. Nincs garancia, hogy egyetlen szem´elyr˝ ol besz´el¨ unk – ez´ert hallgat´olagosan ezt mindenk´eppen feltessz¨ uk. A helyzet kicsit bonyol´ odik, amennyiben az ilyen formul´akat ´ert´ekeln¨ unk. Vegy¨ uk p´eld´aul a jelenlegi ” francia kir´aly kopasz” ´ all´ıt´ ast. Egyfel˝ ol jelenleg Franciaorsz´agnak nincs kir´alya, k¨ovetkez´esk´eppen az ´all´ıt´as lehetne hamis, ha logikai ´es” kapcsolatot tenn´enk fel a kopaszs´agra vonatkoz´o ´all´ıt´as ´es a jelenlegi ” ” francia kir´aly” meghat´ aroz´ as k¨ oz¨ ott. Ha a ha . . . , akkor . . . ” szerkezetben gondolkodunk, akkor az ” ´all´ıt´ast tekinthetj¨ uk igaznak. De ebben az esetben az ´all´ıt´as tagad´asa, miszerint nem kopasz ill. nem a jelenlegi francia kir´ aly kopasz igaz ill. hamis kellene legyen – holott ez sem (felt´etlen¨ ul) van ´ıgy. Az ilyen jelleg˝ u probl´em´ ak felold´ as´ ara fogalmak, le´ır´asok ¨osszevon´as´at eszk¨oz¨olt´ek. Ez annyit tesz, hogy az azonos individuumok le´ır´ o´ abr´ azol´ as´ at egyetlen fogalomba t¨om¨or´ıtik, amely a tov´abbiakban m´ar val´oban egyetlen t´enyleges ´ertekkel, ´ abr´ azol´ assal b´ır, f¨ uggetlen¨ ul att´ol, hogy a fogalom t´enylegesen h´any lehets´eges le´ır´ast foglal mag´ aba. A le´ır´o logika teljes – azaz a modellelm´eleti ´es a bizony´ıt´aselm´eleti fel´ep´ıt´ese k¨olcs¨on¨osen megfeleltethet˝ oek egym´ asnak. Az u ´jabb kutat´asok nagy hangs´ ulyt fektetnek arra – f˝oleg a tud´asb´azisok tervez˝oi eset´eben –, hogy a le´ır´ o logika megfelel˝o bizony´ıt´aselm´eleti algoritmusai milyen hat´ekonys´aggal val´os´ıthat´ok meg. Az els˝ orend˝ u logik´ ahoz hasonl´oan itt is elmondhat´o, hogy egy minden helyes v´alaszt el˝o´all´ıt´o, ma ismert legjobb algoritmus eset´eben az eld¨onthet˝os´egnek elvi akad´alya nincs – csak a v´alaszid˝o irre´alisan nagy.

A szavak h´al´oj´aban

Az inform´ aci´ o´ abr´azol´as matematikai m´odszerei

9

A le´ır´o logika alkalmaz´ asa az inform´ aci´os rendszerek ter¨ ulet´en m´eg mindig t¨oretlen fejl˝od´est mutat. Legink´abb u ´n. ontol´ ogi´ ak le´ır´ as´ ara alkalmazz´ak. Erre vonatkoz´oan l´asd m´eg a DAML+OIL ontol´ogia le´ır´o nyelvvel foglalkoz´ o r´eszeket a szemantikus h´al´o t´emak¨or´eben.

5.

Az intenzion´ alis logika Az intenzion´ alis logik´ aban megjelenik egy olyan oper´ator, amely valamely ´all´ıt´as igazs´ag´ert´ek´et

m´odos´ıtja, ´ıgy egy-egy ´ all´ıt´ as ´ert´ekel´ese nem lehets´eges ¨onmag´ aban, a k¨ornyezet´eb˝ol r´eszben vagy eg´eszen kiragadva. Az oper´ ator teh´ at sz¨ uks´egszer˝ uen mondatfunktor a meghat´aroz´as szerint. Milyen nyelvtani szerkezetek b´ırnak ilyen tulajdons´ aggal? P´eld´aul: a brit minisztereln¨ok lehetne munk´asp´arti”, a halak ” ” sz¨ uks´egszer˝ uen kopolty´ usak”, a mohamed´anok lehetnek t¨obbnej˝ uek”, mindig tudtam, hogy egyed¨ ul ” ” leszek”, B´ela azt hiszi, Andr´ as j´ art Csill´ an´ al”. Az intenzion´alis logik´ak k¨oz¨ ul a legr´egibbel, egyszersmind ” a legegyszer˝ ubbel; az u ´n. mod´ alis logik´ aval ismerked¨ unk meg.

5.1. A

Mod´ alis logika mod´alis

logik´ aban

mind¨ ossze

n´eh´any

egyargumentum´ u

intenzion´alis

mondatfunktort

k¨ ul¨onb¨oztet¨ unk meg az els˝ orend˝ u logika kiterjeszt´esek´ent. Ezek rendre a lehets´eges”, a lehetetlen”, ” ” ´ a sz¨ uks´egszer˝ u” ´es az esetleges” szavak megfelel˝oi. Altal´ aban k´et mondatfunktor is elegend˝o a fentiek ” ” kifejez´es´ere. Az els˝ o ilyen egyargumentum´ u mondatfunktort olvassuk ki sz¨ uks´egszer˝ u, hogy” form´aban ´es ” jel¨olj¨ uk 2” szimb´ olummal. Mivel a mod´ alis logika az els˝orend˝ u logika kiterjeszt´ese, ´ıgy r¨ogt¨on ´elhet¨ unk ” egy t¨orv´ennyel, miszerint ha egy ϕ ´ all´ıt´ as logikai igazs´ag, akkor 2ϕ is az. Tov´abb´a az is igaz, hogy ha 2(ϕ1 ⇒ ϕ2 ) ⇒ (2ϕ1 ⇒ 2ϕ2 ) Vezess¨ uk be ezek ut´ an a logikai

nem” seg´ıts´eg´evel a lehets´eges, hogy” egyargumentum´ u ” ” mondatfunktort is, amelyet a 3” szimb´ olum fog jel¨olni: ” 3ϕ = ¬2¬ϕ azaz a ϕ lehets´eges, amennyiben a tagad´ asa nem sz¨ uks´egszer˝ uen igaz. Vil´agos, hogy a k´et mondatfunktor nem lehet extenzion´ alis, hiszen a ϕ ´ all´ıt´as valamilyen igazs´ag´ert´ekel´es´eb˝ol nem k¨ovetkezik sem a sz¨ uks´egszer˝ uen, sem a lehets´egesen igaz ill. hamis ´all´ıt´as. Bizonyos tekintetben teh´at f¨ uggetlen az ´all´ıt´as ´ert´ekel´ese az u ´j mondatfunktorok haszn´ alat´anak bevezet´es´evel nyert ´all´ıt´as ´ert´ekel´es´et˝ol. B´ar a defin´ıci´ okban a mod´ alis logika szak´ert˝oi megegyeznek – l´atsz´olag meglehet˝osen egyszer˝ uek is – jelent´estartalm´ an azonban m´ ar k¨ ozel sincsenek azonos ´all´asponton. Gondoljuk csak v´egig, hogy ha azt ´all´ıtan´ ank, hogy Magyarorsz´ ag f˝ ov´arosa Budapest” az sz¨ uks´egszer˝ u vagy lehets´eges ´all´ıt´asnak ” ´ tekinten´enk-e. Altal´ aban fogalmazzuk meg u ´gy, hogy akkor tekint¨ unk valamit sz¨ uks´egszer˝ uen igaz ´all´ıt´asnak, ha a vil´ ag ´ allapota alapvet˝ oen megrend¨ ulne, ha hamis lenne. V´eletlenszer˝ uen pedig akkor igaz, ha lehetne hamis is an´elk¨ ul, hogy a vil´ag ´allapota l´enyeg´eben megrend¨ ulne. Ennek megfelel˝oen a Magyarorsz´ ag f˝ ov´ arosa Budapest” ´ all´ıt´ ast lehets´egesen igaznak tekintj¨ uk, hab´ar a konkr´et haszn´alat ” m´eg ebben az esetben is kiss´e hom´ alyos. ´ Az elk´epzel´est finom´ıtsuk tov´ abb. Altal´ aban, ha egy ´all´ıt´ast c´afolni szeretn´enk, akkor azt elj´ar´ast szoktuk k¨ovetni, hogy vessz¨ uk a felt´etelek teljes halmaz´at, amelyek egy adott vil´agban teljes¨ ulnek – ´es

NKFP-2/0019/2002

10

Zs. T. Kardkov´acs

megmutatjuk, hogy a konkl´ uzi´ o nem ´ allja meg a hely´et ebben a vil´agban. Sok esetben nem is kell, hogy l´etez˝o vil´ag legyen, amit le´ırunk, csak lehets´eges”. Ezt a m´odszert pr´ob´aljuk meg alkalmazni a mod´alis ” logik´ara vonatkoz´ oan. Tekints¨ uk a lehets´eges vil´agok egy teljes rendszer´et, ´es tegy¨ uk fel, hogy egy-egy lehets´eges vil´ag egy gr´ af valamelyik cs´ ucspontja, megfelel˝ o c´ımk´evel ell´atva. Tov´abb´a tegy¨ uk fel, hogy egy-egy gr´af pontb´ ol ir´ any´ıtott ´elt h´ uzunk egy m´asik fel´e, ha az hasonl´o hozz´a, bizonyos ´ertelemben alternat´ıv´aja – azaz minden t¨ orv´enyszer˝ us´eg ugyanaz benne, ha egyes ´all´ıt´asok m´as ´ert´ekel´eseket is kaphatnak. Ilyen t¨ orv´enyszer˝ us´egek lehetnek p´eld´aul a fizikai t¨orv´enyszer˝ us´egek, ak´arh´any elk´epzelhet˝o f¨oldi vil´agban. Ir´any´ıtott gr´ afot kaptunk, teh´ at az ´elek olyan rel´aci´ot jelk´epeznek, amelyek nem sz¨ uks´egszer˝ uen szimmetrikusak, se nem felt´etlen¨ ul tranzit´ıvek. Ezek alapj´an azt mondjuk, hogy egy ´all´ıt´as sz¨ uks´egszer˝ uen igaz, ha minden hasonl´ o vil´ agban az ´ all´ıt´ as igaz. A lehets´egesen igaz ´all´ıt´as meghat´aroz´asa a fentebbi ´ defin´ıci´okb´ol m´ ar el˝ o´ all. Erdekess´egk´eppen megeml´ıtj¨ uk, hogy ez a szerkezet lehet˝ov´e teszi az intenzion´alis mondatfunktorok halmoz´ as´ at, amely ¨ on´ all´ o jelent´essel ´es igazs´ag´ert´ekel´essel b´ırnak. A mod´alis logik´ ahoz – a lehets´eges vil´agok elm´elet´et figyelembe v´eve – szerkeszthet˝o olyan bizony´ıt´aselm´eleti megk¨ ozel´ıt´es, amely helyes ´es teljes a modellelm´eleti fel´ep´ıt´es´ere n´ezve. A megold´as bonyolults´ag ´es a fejezet m´ as ir´ any´ u ind´ıttat´asa miatt ennek r´eszletes t´argyal´as´at´ol eltekint¨ unk. Megjegyezz¨ uk azonban, hogy a mod´ alis logika alkalmaz´asa az inform´aci´o-visszakeres´esben f˝oleg a fogalmi h´al´ok ´es a t´emat´erk´epek ter¨ ulet´en bevett gyakorlat.

6.

Helyzetk´ epelm´ elet A helyzetk´epelm´elet egy teljesen u ´j kezdem´enyez´es, els˝osorban Fred I. Dretske u ´j, filoz´ofiai

n´ez˝opontj´ara alapozva. Els˝ o matematikai formaliz´al´as´anak le´ır´asa 1983-b´ol val´o, Jon Barwise ´es John Perry nev´ehez f˝ uz˝ odik. Dretske szerint az ´erz´ekel´es, felfog´as ´es ´ertelmez´es – legal´abbis, amit ´altal´aban ennek nevez¨ unk – egy anal´og” folyamat (k´ep, sz¨oveg, hang, mimika stb.) r´esze, mik¨ozben a konkr´et ” elemi, formaliz´ alhat´ o inform´ aci´ ok sz¨ uks´egszer˝ uen digit´alis” (diszkr´et) mennyis´egek. ” Logikai alapegys´ege az infon. Az infon tetsz˝oleges elemi ´all´ıt´as lehet, ami ugyanannak a val´os´agr´eszletnek t¨ obbf´ele le´ır´ as´ aban is azonos alakot kell, hogy jelentsen.

P´eld´anak ok´a´ert Anita ” sz´ep kuty´aval aj´ and´ekozta meg Bulcs´ ut” (mondja Csenge), a sz´ep kuty´at aj´and´ekoztam Bulcs´ unak” ” (mondja Anna) ´es a sz´ep kuty´ at kaptam aj´and´ekba Anit´at´ol” (mondja Bulcs´ u) ugyanazon infon ” t¨obbf´ele megfogalmaz´ asa. Az infon elemei teh´at ´allnak egyfel˝ol individuumokb´ol, amelyekr˝ol feltessz¨ uk, hogy minden k¨ or¨ ulm´enyek k¨ oz¨ ott invari´ ansak ´es megk¨ ul¨onb¨oztethet˝oek. Az individuumok k¨oz¨ott pedig valamilyen tulajdons´ ag vagy kapcsolat ´ all fenn, amely megfeleltethet˝o egy megfelel˝o argumentum´ u predik´atumnak.

Az infon formaliz´ alt alakj´aban v´egeredm´enyben pontosan olyan predik´atumhoz

juthatunk, mint p´eld´ aul az ´ all´ıt´ aslogika eset´eben – azzal a k¨ ul¨onbs´eggel, hogy az ´all´ıt´as ´es a tagad´ as t´enye szorosan kapcsol´ odik az infonhoz, azaz nem tekintj¨ uk a tagad´ast mondatfunktornak, tov´abb´a nem vizsg´aljuk, ha u ´gy tetszik nincs igazs´ ag´ert´ekel´ese az infonnak. Egy-egy infon t´erben ´es id˝ oben is elhelyezett, rendezett. Teh´at minden infonhoz mint esem´enyhez rendelhet˝o egy t´erid˝ o vektor.

Az egyes vektorkomponensek parci´alis f¨ uggv´enyeknek tekinthet˝ok ´es

k¨ ul¨onf´ele viszonyt le´ır´ o kapcsolatot defini´ alhatunk k¨oz¨ott¨ uk. Egyfel˝ol az id˝o dimenzi´oban ´ertelmezz¨ uk az (id˝oben) megel˝ ozi” rel´ aci´ ot, m´ asfel˝ ol az egyes dimenzi´ok tartom´any´ara megk¨ ul¨onb¨oztetj¨ uk az ´atfed´esi ´es ” a tartalmaz´asi rel´ aci´ okat. Fontos megjegyezni, hogy az infon ¨onmag´aban ilyen inform´aci´ot nem tartalmaz,

A szavak h´al´oj´aban

Az inform´ aci´ o´ abr´azol´as matematikai m´odszerei

11

teh´at az Anita sz´ep kuty´ at aj´ and´ekozott tegnap Bulcs´ unak” szint´en a fenti p´eld´akkal azonos infont ” jelenti. A helyzetk´epelm´elet m´ asik k¨ ozponti fogalma a helyzetk´ep vagy szitu´aci´o, amely a val´os vil´ag valamely r´eszlet´et ragadja ki. A helyzetk´ep Dretske szerint anal´og” fogalom, inform´aci´os rendszerek eset´eben ” azonban diszkr´et mennyis´egnek felt´etelezz¨ uk. Az infon ´es a helyzetk´ep k¨oz¨otti rel´aci´ot tartalmaz´asnak nevezz¨ uk – azt mondjuk, hogy egy adott helyzetk´ep (nem) tartalmazza vagy mag´aban foglalja (nem foglalja mag´aban) az adott infont. Term´eszetesen, ez egy igazs´ag´ert´ekel´esnek felfoghat´o. A helyzetk´epek k¨oz¨ott a tartalmaz´ ashoz hasonl´ o rendez´esi rel´aci´o is defini´alhat´o, amely megmondja, hogy melyik szitu´aci´o foglalja mag´aban a m´ asik szitu´ aci´ ot. A helyzetk´epeket koherensnek tessz¨ uk fel, azaz semelyik infonnak nem jelenik meg egyszerre ´ all´ıt´ ask´ent ´es tagad´ask´ent is alakja egy helyzetk´epben. A infonok sokszor hasonl´ o´ all´ıt´ ast ´ırnak le, mint m´as infonok, legfeljebb egy-egy r´eszlet – p´eld´aul egyegy benne szerepl˝ o individuum (neve) v´ altozik. Ennek megfelel˝oen az infonok oszt´alyozhat´oak aszerint, hogy milyen s´em´ aba illeszkednek bele. P´eld´aul a Budapest felett der¨ ult az ´eg”, a Berlin felett der¨ ult ” ” az ´eg” ´es a London felett der¨ ult az ´eg” azonos s´em´aba illeszkednek, de k¨ ul¨onb¨oz˝o infonokr´ol van sz´ o. ” Ezeket a infons´em´ akat nevezz¨ uk t´ıpusoknak. K´et t´ıpus, ϕ ´es φ k¨oz¨ott ´ertelmezhet¨ unk egy k´enyszert vagy viszonyt, amit ϕ → φ-vel jel¨ol¨ unk; ´es ami azt fejezi ki, hogy egy adott s1 helyzetk´ep φ t´ıpusa egy s2 helyzetk´ep ϕ t´ıpus´ u infonj´ anak l´etez´es´et ´ all´ıtja. Az inform´aci´o-visszakeres´esben ez a rel´aci´o feleltethet˝o meg (form´alisan) a relevancia fogalm´ anak. A helyzetk´epelm´elet nem egy matematikai ´ertelemben vett logikai appar´atus – ennek megfelel˝oen nem rendelkezik konkr´et bizony´ıt´aselm´eleti megk¨ozel´ıt´essel. T¨orekv´esek ugyan vannak ilyenek kidolgoz´as´ara. Az elm´elet c´elja els˝ osorban az, hogy az inform´aci´ok le´ır´asa ´es elhelyez´ese megfelel˝o, egyszer˝ u formaliz´al´assal el˝ o´ all´ıthat´ o – ´es visszakereshet˝o – legyen, de nem t¨orekszik igazs´ag´ert´ekek el˝o´all´ıt´as´ara. ¨ Osszefoglalva: az alkalmaz´asi ter¨ ulete f˝ oleg az inform´aci´ofeldolgoz´as ´es -lek´epez´es (szemantikai) helyess´eg´enek ellen˝ orz´ese, a relevancia abszol´ ut m´erhet˝os´ege lehet.

7.

Logikai modellek az inform´ aci´ o-visszakeres´ esben Az inform´ aci´ o-visszakeres´esi modellben egy meghat´arozott k´erd´esre vonatkoz´oan az arra v´alaszol´o

vagy azzal kapcsolatos dokumentumok egy halmaz´at szeretn´enk meghat´arozni. Ha a k´erd´es logikai formula – amely az esetek t´ ulnyom´ o t¨ obbs´eg´eben igaz –, akkor olyan dokumentumokat keres¨ unk, amelyben a k´erd´es mint logikai formula igazz´ a tehet˝ o a dokumentumok tartalma alapj´an. K´ın´alkozik a lehet˝os´eg, hogy valamilyen k¨ ovetkezm´enyfogalommal azonos´ıtsuk a v´alaszad´ast. A legegyszer˝ ubb modellben legyen D mondatok valamilyen halmaza, amely a dokumentumot, ´es q legyen egy logikai mondat, amely a k´erd´est jel¨oli. Ennek megfelel˝ oen az olyan D dokumentumokat keress¨ uk, amelynek szemantikai k¨ovetkezm´enye a q k´erd´es – azaz D minden modellj´en q igaz. Egy-egy visszakeres´es j´os´aga legink´abb azon m´ ulik, hogy D ´es q milyen formaliz´ alt alakj´ at tudjuk ¨ osszevetni egym´assal. P´eld´anak ok´ a´ert, ha D-t ´es q-t u ´gy tekintj¨ uk, mint szavak logikai ´es” kapcsolat´aval el˝o´all´o mondatok ” halmaz´at, akkor a modell¨ unk l´enyeg´eben a Boole-modellel lesz azonos, felt´eve persze, hogy k¨ ul¨onb¨oz˝o alak´ u szavak k¨ ul¨ onb¨ oz˝ o individuumokat jel¨ olnek. A Boole-modellnek, ahogy azt kor´abban is l´athattuk sz´amos hi´anyoss´ aga akad. A meg´ allap´ıt´ ast a logikai modellek ismertet´es´evel tov´abb ´altal´anos´ıthatjuk. Az els˝orend˝ u (extenzion´ alis) logikai modellek alkalmaz´as´aval nem vagyunk k´epesek megragadni: • F¨ uggetlen ´ all´ıt´ asok szemantikai k¨ ovetkezm´enye nem kiz´arhat´o. Azaz, ha q egy logikai igazs´ag,

NKFP-2/0019/2002

12

Zs. T. Kardkov´acs akkor b´armely D dokumentum szemantikus k¨ovetkezm´enye is egyben. Az ilyen, vagy ehhez hasonl´o trivi´alis esetek sz˝ ur´ese mindenk´eppen c´elszer˝ u ´es sz¨ uks´eges.

• A t¨obbsz¨ or¨ osen el˝ ofordul´ o elemek s´ ulyoz´as´at, hiszen a ϕ ∧ ϕ ⇐⇒ ϕ. Ugyanakkor a magasabb rend˝ u logik´akban ez m´ ar megoldhat´ o, csakhogy ott meg sz´am´ıthat´os´agi probl´em´akkal kell megk¨ uzden¨ unk. • Neh´ez megragadni az azonos alak´ u szavak k¨oz¨otti jelent´esbeli k¨ ul¨onbs´egeket – ha u ´gy tetszik a szavak intenzi´ oj´ at. A pontos jelent´es csak a sz¨ovegk¨ornyezetb˝ol der¨ ulhet ki, teh´at valamilyen intenzion´ alis oper´ atort kell tudni bevezetni. Az ilyen jelleg˝ u probl´em´ak megold´as´at az eddig t´argyalt matematikai m´ odszerek nem teszik lehet˝ov´e, ehhez az inform´aci´o´abr´azol´as egy t´agabb defin´ıci´oj´ara – p´eld´aul u ´n. helyzetelemz´esre, vagy u ´n. inform´aci´ofolyam modellez´esre – van sz¨ uks´eg. • Egy-egy dokumentumban tal´ alhat´ o ´ all´ıt´as olykor csak r´eszlegesen, vagy m´as dokumentumban tal´alhat´ o inform´ aci´ ok alapj´ an ´ert´ekelhet˝o ki. Ilyen bizonytalans´agot ugyan a t¨obb´ert´ek˝ u logika k´epes kezelni, de az els˝ orend˝ u logika kereteibe ez nem illeszthet˝o term´eszetes m´odon bele. • Megjelenhet tov´ abbi ´ertelmez´esi bizonytalans´ag egy-egy dokumentum formaliz´al´asa eset´en, amely a tartalmaz´asi rel´ aci´ ok term´eszetes nyelvi elmos´od´as´ab´ol ered. Olyan esetekre kell itt gondolni, amikor p´eld´aul a madarak rep¨ ul´esi k´epess´egeir˝ol ´all´ıtunk bizonyos dolgokat – mik¨ozben k¨oztudom´as´ uan van n´eh´any olyan mad´ ar, amelyik nem rep¨ ul. Ha a struccokr´ol, esetlegesen azok (valamikori) rep¨ ul´esi k´epess´egeir˝ ol keres¨ unk dokumentumokat, akkor a strucc egy mad´ar” (igaz) ´all´ıt´as figyelembe v´etele ” megk´erd˝ ojelezhet˝ o (konkr´et k¨ ornyezetekben). Ilyen bizonytalans´agok kifejez´es´ere nem alkalmas k¨ozvetlen¨ ul az els˝ orend˝ u logika, azonban a nem monoton k¨ovetkez´esek seg´ıts´eg´evel, megfelel˝o algoritmussal ´es adat´ abr´ azol´ assal beleilleszthet˝o. • Hasonl´oan kellemetlen probl´em´ aval ´allunk szemben, ha rokon ´ertelm˝ u, vagy m´as nyelven, de ugyanaz a sz´ o szerepel k¨ ul¨ onb¨ oz˝ o logikai ´all´ıt´asokban. A rokon ´ertelm˝ u szavak ¨osszekapcsol´as´ara a le´ır´o logika ad lehet˝ os´eget – amely szint´en t´ ulmutat az els˝orend˝ u logika keretein.

8.

¨ Osszefoglal´ o A fejezetben arra kerest¨ uk a v´ alaszt, hogy milyen nyelvi, nyelvtani szerkezetek ragadhat´oak meg

logikai eszk¨oz¨okkel, milyen hat´ekonys´ aggal. A logikai rendszerek ´altal´aban az els˝orend˝ u logik´at pr´ob´alt´ ak meg kiterjeszteni – sok esetben arra visszavezethet˝o m´odon. Mindenk´eppen meg´allap´ıthatjuk, hogy b´ ar a term´eszetes nyelvi elemek javar´eszt lefedhet˝oek k¨ ul¨onb¨oz˝o logikai formalizmusok seg´ıts´eg´evel, egys´eges, k¨onnyen modellezhet˝ o ´es sz´ am´ıthat´ o (vagy ´eppen eld¨onthet˝o) matematikai rendszer jelenleg nem ´all rendelkez´es¨ unkre. Ez mindenk´eppen arra kell, hogy ¨oszt¨on¨ozze az inform´aci´o-visszakeres´es ter¨ ulet´en kutat´o szakembereket, hogy t¨ obb l´epcs˝ os, vagy p´arhuzamos feldolgoz´ast lehet˝ov´e tev˝o rendszereket tervezzenek, illetve alak´ıtsanak ki. A tov´abbiakban megmutatjuk, hogy milyen – a m´ar ismertetett matematikai rendszereket mag´ aban foglal´ o – megold´asok, aj´anl´asok keletkeztek eddig.

A szavak h´al´oj´aban

Az inform´ aci´ o´ abr´azol´as matematikai m´odszerei

13

Hivatkoz´ asok [1] Baader, F., Nutt, W.: Basic Description Logics. Description Logic Handbook. Cambridge University Press, (2002) pp. 47-100. ISBN 0521-781760. [2] Berwise, J., Cooper, R.: Simple Situation Theory and its Graphical Representation. Partial and Dynamic Semantics 3. ed. J. Selignan. Dyana Delivarable, (1991), Edinburgh, UK. [3] Cooper, R.: A working person’s guide to situation theory. Topics in Semantic Interpretation. ed. S. L. Hansen, F. Sorensen. Samfundslitteratur, (1992), Frederiksberg, Denmark. [4] Crestani, F., Ruthven, I., Sanderson, M., Rijsbergen, K.: The troubles with using a logical model of IR on a large collection of documents. TREC-4, (1995), Washington, USA. [5] Huibers, T.W.C., Lalmas, M., Rijsbergen, C.J.: Information Retrieval and Situation Theory. SIGIR Forum (30)1, (1996), pp. 11-25. [6] Lalmas, M.: Logical Models in Information Retrieval: Introduction and Overview. Information Processing and Management 34(1), (1998), pp. 19-33. [7] Pinheiro, F.A.C.:

Preliminary Thoughts on Using Situation Theory for Scenario Modelling.

IDEAS’2002, (2002), Valencia, Spain. [8] Ruzsa, I.: Bevezet´es a modern logik´ aba. Osiris kiad´o, (2000), Budapest, Hungary, ISBN 963-379-9783. [9] Zalta, E.N. (ed): Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford, UK, ISSN 1095-5054. [10] Tin, E., Akman, V.: Computational Situation Theory. SIGART Bulletin 5(4), (1994), pp. 4-17.

NKFP-2/0019/2002