Procesarea Cunostintelor Comune Si Distribuite

Introducere

În orice domeniu, cunoașterea informațiilor pe care le deține un grup este o condiție esențială pentru a lua o decizie cât mai corectă.

Această lucrare realizează un studio asupra cunoștințelor pe care un grup le deține sau le poate deține.

In primul capitol sunt prezentate noțiuni despre cunoștințele commune unui grup, precum și câteva probleme care folosesc aceste cunoștințe.

Capitolul II al lucrării se axează pe logica modală, componentele acesteia și prezintă modalități de reprezentare cu ajutorul structurilor Kripke.

În capitolul III este prezentată noțiunea de cunoștință ditribuită pentru un grup. Tot în acest capitol sunt descries și proprietăți ale cunoașterii.

Capitolul al patrulea al lucrării prezintă modalitatea de reprezentare a cunoștințelor commune și distribuite folosind reprezentare pe bază de evenimente prin structura Aumann și legătura dintre structura Aumann și structura Kripke.

Capitolul V conține două probleme specifice pentru logica modală : problema așilor și optarilor și problema copiilor murdari.

În ultimul capitol este descrisă aplicația utilizată pentru a reprezenta cunoștințele folosind structurile Kripke.Aceasta aplicație este realizată în limbajul Java. Am ales acest limbaj pentru a realize aplicația deoarece este un limbaj de programare foarte puternic, dar se poate obține și o versiune gratis a acestuia.

CAPITOLUL I

CUNOȘTINȚE COMUNE

Noțiuni generale. Exemple

În general un grup este văzut ca o mulțime de indivizi (ființe sau neființe) care utilizează o bază de cunoștințe în comun. Elementele unui grup se numesc agenți. Un asemenea agent poate fi negociator într-o anumită situație, un robot de comunicare, mesaje sau buffere de mesaje într-un calculator, programe logice distincte etc. El trebui să ia contact nu numai cu faptele ci trebuie de asemenea să cunoască date despre ceilalți agenți din grup.

Spre exemplu: dacă avem o tranzacție de mașini, vânzătorul trebuie să ia în considerare ce cunoaște cumpărătorul despre valoarea mașinii, iar acesta la rândul lui trebuie să ia în considerare ce știe vânzătorul cu privire la ceea ce știe cumpărătorul cu privire la valoarea mașinii și ce nu.

Spre exemplu: toți șoferii cunosc că lumina roșie a semaforului înseamnă “stai”, iar lumina verde “pleacă”. Va fi fiecare șofer atunci în siguranță? Răspunsul la această întrebare este nu, pentru că unii nu cunosc regulile, iar alții care le cunosc nu le respectă. Sau unii șoferi consideră posibil că nu toți cunosc regulile și atunci mulți dintre ei trec pe lumina roșie.

În exemplele prezentate ne-am referit la o cunoștință comună.

În general se va nota cu o cunoștință. Dacă simultan au loc următoarele:

fiecare agent cunoaște ;

fiecare cunoaște că fiecare cunoaște ;

fiecare cunoaște că fiecare cunoaște că fiecare cunoaște etc,

atunci devine o cunoștință comună.

Această noțiune a fost la început studiată de David Lewis în contextul convențiilor. Lewis a considerat aceasta ca fiind o convenție, că un fapt trebuie să fie comun la câți mai mulți agenți ai unui grup (spre exemplu, lumina roșie și verde a semeforului, este un fapt cuoscut de cei mai mulți șoferi și astfel aceasta devine o cunoștință comună).

John McCarthy în contextul studiului raționamentului în comun, caracteriza cunoștința în comun ca fiind “any fool”; cunoașterea “any fool” este o cunoștință comună la mai mulți membri ai societății.

Spre exemplu: “Ana întrebă pe Bob: “ce gândești tu despre mișcare? ” Referindu-se la cartea X pe care a citit-o. Ana și Bob trebuie să cunoască faptul că mișcarea se referă la cartea X; Ana trebuie să cunoască, că Bob cunoaște că mișcarea se referă la cartea X; Bob trebuie să cunoască că, că Ana cunoaște, că Bob cunoaște, că mișcarea se referă la cartea X”.

Notăm cu = “mișcarea se referă la cartea X” și atunci aceasta devine cunoștință comună.

Pentru a urmării raționamentul cu mai mulți agenți, vom prezenta o piesă de cunoștere care să urmărească aspectele legate de acest lucru.

1.2.Prezentarea generală a unor probleme

Avem următoarea piesă de cunoaștere: “O mamă are n copii care se joacă împreună. Ea îi anunță că dacă se vor murdări atunci vor urma consecințe severe. Astfel, fiecare copil urmărește să se păstreze curat, dar fiecăruia i-ar plăcea să-l vadă pe celălalt murdar. În timpul jocului, o parte din copii, să zicem k, se murdăresc pe frunte. Fiecare poate să vadă murdăria celuilalt, dar nu se poate vedea pe sine. Între timp vine tatăl copiilor, care afirmă: ”Cel puțin unul dintre voi este murdarit pe frunte”. Presupunem k1. Tatăl copiilor întrebă: “Cunoaște vreunul dintre voi că că s-a murdărit pe frunte?” și repetă acest lucru de mai multe ori. Presupunem că fiecare copil este receptiv, inteligent și că ei răspund simultan la întrebare. Se pune problema ce se întâmplă în acest caz?”.

Există o demonstrație a faptului că la primele k-1 întrebările sunt “No”, dar apoi la următoarea întrebare copiii cu fruntea murdară răspund “Yes”. Demonstrația se face prin inducție:

Să luăm : singurul copil murdar vede că ceilalți sunt curați, iar afirmația tatălui spune că cel puțin unul dintre ei este murdar, atunci copilul răspunde cu “Yes”.

Presupunem atunci există doi copii murdari X și Y. Fiecare răspunde cu “No” la prima întrebare a tatălui. Dar când Z spune “No”, X înțelege că el este murdar. Astfel a doua întrebare a tatălui X răspunde cu “Yes”. La fel Y.

Presupunem și notăm cu X,Y și Z copii murdari.

Copilul X judecă astfel: presupunem că eu nu m-am murdărit pe frunte. Dacă ar fi adevărat atunci conform cazului k=2, la a doua întrebare Y și Z trebuie să răspundă cu “Yes”, ceea ce nu este adevărat. Prin urmare X află că este cel murdar și atunci la a treia întrebare a tatălui el răspunde cu “Yes”. La fel și Y și Z.

În acest exemplu cunoștința comună este propoziția: p=“cel puțin un copil are fruntea murdară”. Dacă k1 atunci fiecare copil poate să vadă cel puțin un copil cu fruntea murdară. Deci inițial toți copii cunosc p. De aceea, se pare că afirmația tatălui p nu este necesară, lucru fals. Dacă tatăl nu ar face afirmația p atunci copii nu ar putea spune cine este murdar și cine nu. Vom demonstra acest lucru: vom aplica metoda inducției după q pentru a arăta că indiferent câți copii sunt murdari, toți răspund cu “No” la primele q întrebări.

La prima întrebare toți răspund cu “No”.

Pentru q=1 evident că răspunsul este “No”. În mod analog ca mai sus se va demonstra că toți copiii vor răspunde cu “No” la primele q întrebări. Când tatăl pune a q+1 întrebare copilul îi va răspunde tot cu “No”. Din nou el nu știe că este sau nu murdar pe frunte.

Când tatăl anunță la început p aceasta devine o informație utilă pentru fiecare copil. De ce? Să conșiderăm cazul k=2. Bineînțeles că înainte ca tatăl să anunțe p toți cunosc p, însă ceea ce nu se știe este că “fiecare copil știe că fiecare cunoaște p”. Dacă Mary și Boby sunt doi copi murdari, atunci înainte de afirmația tatălui, Mary consideră că este posibil ca ea să nu fie murdară și dacă este așa atunci Boby nu cunoaște p. După ce tatăl anunță p atunci Mary și Boby cunoaște p și deci dacă Boby răspunde cu “No” la prima întrebare atunci Mary deduce că ea este murdară, deci la a doua întrebare va răspunde cu “Yes”. La fel și Boby.

Așadar există doi copii murdari, atunci este foarte utilă informația: “fiecare cunoaște p”. Dacă există trei copii murdari este important ca: “fiecare cunoaște că fiecare cunoaște p” ș.a.m.d.

În general dacă notăm cu faptul că: “fiecare cunoaște că fiecare cunoaște că … că fiecare cunoaște p” (de k ori) și cu faptul că este cunoștință comună, atunci se arată ușor că dacă exact k copii sunt murdari, are loc înainte ca tatăl să vorbească, dar nu are loc .

Anunțul tatălui conduce la a da copiilor cunoștința comună p. Se impun câteva observații:

Dacă tatăl nu face afirmația p, atunci ori de câte ori îi întrebă pe copii, aceștia răspund cu “No” fapt demonstrat mai sus.

Este foarte importantă afirmația p pentru că fiecare cunoaște p și fiecare cunoaște că fiecare cunoaște p ș.a.m.d. Astfel p este o cunoștință comună.

Ce se întâmplă dacă tatăl ia pe rând pe fiecare copil și îi transmite p? Evident că ea nu mai este atunci cunoștință comună, deși fiecare o cunoaște însă nu știe fiecare că fiecare cunoaște p. Atunci aceasta devine o cunoștință în grup, copiii neștiind să spună cine este murdar și cine nu.

Vom încerca să tratăm o variantă a problemei de mai sus.

Problema se referă la trei înțelepți. Cunoștința comună este dată de următoarea afirmație: ei au împreună trei pălări roșii și două albe.

Regele pune câte o pălărie pe capul fiecărui înțelept, după care îi întreabă: “Știți ce culoare are pălăria de pe capul vostru?”.

Primul înțelept răspunde cu “no”, al doilea cu “no”, iar al treilea cu “yes”. Ce culoare are pălăria celui de-al treilea înțelept?

Să notăm cu p= “cei trei înțelepți au trei pălării roșii și două albe”.

Regele pune întrebarea: “Ce culoare are pălăria fiecăruia?”

Notăm cei trei înțelepți cu I,II și III. Primul se uită la II și III și răspunde cu “no” deci în mod sigur II și III nu au amândoi pălări albe. Al doilea (II) se uită si el la I și la III și răspundem cu “no” ceea ce însemnă că I și III nu au amândoi pălări albe.

Dar din răspunsurile lui I și II, III va putea răspunde cu “yes” numai în cazul în care I și II au pălări de culoare albă. Atunci el va spune că are pălărie de culoare roșie.

Cum a raționat III? Dacă I a răspuns cu “no” atunci în mod sigur II și III nu au aceeași culoare la pălărie, deci unul are o are albă și celălalt roșie. Cum II răspunde tot cu “no”, însemnă că I și III nu au aceeași culoare. Atunci III se uită la I și II și ținând cont de răspunsurile lor, singura lor posibilitate este să aibă culoare roșie, și va răspunde cu “yes”.

Ce s-ar întâmpla însă dacă cel de-al treilea înțelept nu ar vedea? Ar mai putea el să răspundă cu “yes”?

De data aceasta este aceași cunoștință comună p, la care se adaugă faptul că III este orb. Răspunsurile lui I și II sunt tot “no”, dar nici III nu va putea răspunde cu “yes” ci tot cu “no”. De ce acest lucru? Din moment ce III nu îi mai poate vedea pe I și II aceștia pot avea amândoi pălării de culoare roșie și atunci el nu ar putea ști dacă are pălărie roșie sau sau albă ținând cont că el cunoaște p.

Problema așilor și a optarilor este un simplu joc care prezintă un raționament al cunoașterii, puțin mai sofisticat.

Se joacă cu patru ași, patru optari și trei jucători. Șase cărți sunt împărțite între cei trei jucători, iar două rămân cu fața în jos pe masă.

Fără să se uite la cărțile pe care le au în mână, fiecare jucător, văzând cărțile celorlalți, trebuie să încerce să ghicească ce cărți deține.

Dacă un jucător nu poate afirma ce cărți are, atunci el trebuie să recunoască acest lucru.

Să presupunem că avem următorii jucători: Alice, Bob și Mary. Cunoștința în comun este că fiecare nu minte și are o gândire rațională. Există mai multe situații:

În primul joc, Alice, care este prima, deține doi ași, iar Bob, care este al doilea, are doi optari. Nici Alice, nici Bob nu pot determina ce cărți dețin. Ce cărți are Mary? (Indiciu: ce s-ar întâmpla dacă Mary ar avea doi ași sau doi optari?). Pentru a simplifica calculul vom nota A un as și cu 8 un optar.

Atunci am avea pentru Alice, în acest caz, posibilitatea de a deține doi ași, adică (A,A).

Bob, care are doi optari, va apărea sub forma (8,8).

O stare posibilă (sau o lume posibilă) în acest caz aparesub forma:

Ordinea în care sunt întrebați jucătorii este următoarea: Alice, Bob, Mary. Vom analiza pentru fiecare jucător în parte situațiile posibile:

* Alice, care este prima, vede: (8,8) Bob

(X,Y) Mary

unde (X,Y){(A,A),(8,8),(A,8)} pentru că avem patru ași și ob și Mary. Cunoștința în comun este că fiecare nu minte și are o gândire rațională. Există mai multe situații:

În primul joc, Alice, care este prima, deține doi ași, iar Bob, care este al doilea, are doi optari. Nici Alice, nici Bob nu pot determina ce cărți dețin. Ce cărți are Mary? (Indiciu: ce s-ar întâmpla dacă Mary ar avea doi ași sau doi optari?). Pentru a simplifica calculul vom nota A un as și cu 8 un optar.

Atunci am avea pentru Alice, în acest caz, posibilitatea de a deține doi ași, adică (A,A).

Bob, care are doi optari, va apărea sub forma (8,8).

O stare posibilă (sau o lume posibilă) în acest caz aparesub forma:

Ordinea în care sunt întrebați jucătorii este următoarea: Alice, Bob, Mary. Vom analiza pentru fiecare jucător în parte situațiile posibile:

* Alice, care este prima, vede: (8,8) Bob

(X,Y) Mary

unde (X,Y){(A,A),(8,8),(A,8)} pentru că avem patru ași și patru optari.

Deci pentru Alice avem lumile:

X,Y{A,8}.

Se observă că dacă există mai multe posibilități. De aceea la prima întrebare “Știi ce cărți ai?”, Alice nu poate răspunde.

* Bob vede cărțile lui Alice și Mary: (A,A)

(X,Y)

unde (X,Y){(A,A),(8,8),(A,8)}

Deci lumile (stările) posibile pentru Bob sunt:

X,Y{A,8}.

Evident, în funcție de cărțile pe care le are Mary, sunt stabilite lumile posibile pentru fiecare în parte.

* Mary vede: (A,A) Alice

(8,8) Bob

și singurele posibilități ale ei sunt: (A,A),(8,8),(A,8).

Vom lua în considerare cazul în care Mary deține doi ași: (A,A).

Atunci lumile posibile pentru Alice sunt:

(A,A)

(8,8) (8,8),(A,A)

(A,8)

Alice Bob Mary

Pentru Bob lumile posibile sunt:

(A,A) – (8,8) – (A,A)

Alice Bob Mary

în acest caz se observă că la prima întrebare Bob ar răspunde cu “yes” ceea ce ar contrazice ipoteza. Deci Mary nu poate deține doi ași.

Trecem mai departe și considerăm că Mary are (8,8).

Lumile posibile pentru Alice sunt:

(A,A) – (8,8) – (8,8)

Alice Bob Mary

Se observă că Alice, în aceste condiții, la prima întrebare ar răspunde cu “yes”, pentru că poate să determine ce cărți are în mână și se contrazice ipoteza.

Rămâne cazul în care Mary deține (A,8) și (8,A).

Facem observația că ordinea în perechile de forma (X,Y) cu X,Y{A,8}, nu contează. De aceea cazul (A,8) și (8,A) îl luăm o singură dată.

Lumile posibile pentru Alice:

(A,A)

(8,8) – (A,8)

(A,8)

Alice Bob Mary

Se observă că avem mai multe posibilități. De aceea la prima întrebare “Știi ce cărți ai?” Alice nu poate răspunde cu “yes”.

Lumile posibile pentru Bob sunt:

(8,8)

(A,A) (A,8)

(A,8)

Alice Bob Mary

Și aici observăm că Bob are mai multe posibilități. Așadar la întrebarea “Știi ce cărți ai?”, el nu poate răspunde afirmativ.

Evident că Mary, văzând cărtile lui Alice și Bob ((A,A),(8,8)), nu poate trage concluzia ce cărți are, deci răspunde și ea tot negativ.

Pentru a avea ordinea de interogare: Alice, Bob, Mary și răspunsul “no” pentru fiecare în parte, Mary trebuie să dețină un as și un optar.

Răspunsul la acest punct (a) din problemă este următorul: Mary are (A,8) sau (8,A).

În jocul al doilea, Mary este prima, Alice este a doua, are doi optari, iar Bob, cel de-al treilea, are un as și un optar. Nici unul nu știe ce cărți deține la primul tur de întrebări. Ce cărți are Mary?

Ordinea de interogare fiind Mary, Alice, Bob, vom stabili lumile posibile pentru fiecare în parte, după cum urmează:

* Mary vede (A,A) și (A,8). Atunci lumi posibile pentru ea sunt:

(A,8)

(A,A) (8,8)

(8,8)

Mary Alice Bob

* Alice vede în mod sigur (A,8), cărțile lui Bob și pe cele ale lui Mary:

(A,8)

(X,Y) (8,8)

(8,8)

Mary Alice Bob

X,Y{A,8}.

* Bob vede (A,A), cărțile lui Alice și, în plus, pe cele ale lui Mary.

(A,8)

(A,A) (X,Y)

(8,8)

Mary Alice Bob

X,Y{A,8}.

Vom considera fiecare situație în legătură cu Mary. Dacă Mary are (A,8), atunci vom reanaliza lumile posibile.

Pentru Alice avem:

(A,A)

(A,8) (8,8) (A,8)

(A,8)

Mary Alice Bob

Se observă că Alice are mai multe posibilități. Deși la prima întrebare “Știi ce cărți ai?” va răspunde cu “no” și verifică ipoteza.

Pentru Bob avem:

(8,8)

(A,8) (A,A)

(A,8)

Mary Alice Bob

Și pentru Bob avem mai multe cazuri posibile, deci și al va răspunde la primul tur de întrebări cu “no”.

Evident că Mary, prima interogată, va răspunde cu “no”.

Se observă că pentru acest joc doi, un răspuns ar fi: Mary deține un as și un optar, (A,8).

Observație: Nici în această situație nu se face distincția între perechile de forma (X,Y) și (Y,X), cu X,Y{A,8}.

Dacă luăm pentru Mary cazul (8,8), atunci avem următoarele lumi posibile pentru jucători:

Alice are:

(A,A)

(8,8) (A,8)

(A,8)

Mary Alice Bob

Există mai multe cazuri pentru Alice, de aceea va răspunde cu “no” la primul set de întrebări.

Bob are:

(A,A)

(8,8) (A,A) (8,8)

(A,8)

Mary Alice Bob

Și pentru acesta avem mai multe posibilități, de aceea răspunsul este tot “no”.

În concluzie, pentru jocul doi un alt răspuns ar fi: Mary are doi optari, (8,8).

Pentru jocul doi, răspunsul la întrebarea “Ce cărți are Mary?”, nu este unul singur, căci am văzut că atât cazul în care Mary deține (A,8), cât și cazul în care are (8,8), convin și se încadrează în ipoteză.

În jocul al treilea, Mary este a doua, Alice, care este prima, are un as și un optar.

Nici unul nu va răspunde cu “yes” la primul tur de întrebări.

Alice nu poate să determine cărțile sale nici la cel de-al doilea tur de întrebări. Ce cărți are Mary?

Vom lua, în parte, fiecare jucător în ordinea: Alice, Mary, Bob. Stabilim, mai întâi, lumile posibile pentru Mary:

(A,A)

(A,8) (8,8) (A,8)

(A,8)

Alice Mary Bob

Considerăm, pe rând, fiecare situație pentru Mary:

Dacă Mary are (A,A) atunci avem:

Alice deține următoarele posibilități:

(A,8)

(A,A) (A,8)

(8,8)

Alice Mary Bob

Bob are:

(A,8)

(A,8) (A,A)

(8,8)

Alice Mary Bob

Evident că răspunsul la primul tur de întrebări este “no” pentru fiecare jucător în parte.

La al doilea tur de întrebări, Alice răspunde tot cu “no”,conform ipotezei. Vom verifica acest lucru. Mary, care este prima care răspunde, vede un (A,8) și un (A,8) și gândește în felul următor: “Eu pot deține un (A,A) sau (A,8) sau (8,8)”.

Alice, care este a doua, vede un (A,A) (suntem în cazul în care Mary deține perechea (A,A)) și un (A,8) și gândește în felul următor: “Eu pot să am un (8,8) sau un (A,8)”.

Bob vede cărțile lui Mary și ale lui Alice, respectiv (A,A), (A,8) și gândește în felul următor: “Eu pot avea un (A,8) sau un (8,8)”.

Acesta a fost primul tur de întrebări. La al doilea tur de întrebări, Mary gândește astfel: ea vede în continuare un (A,8) (cărțile lui Alice) și un (A,8) (cărțile lui Bob). Dar cum Alice, care vede și ea un (A,8) și una din posibilitățile: (8,8), (A,8), răspunde cu “no” la prima întrebare, atunci Mary nu poate determina nici acum ce cărți are.

Alice, care este prima și în setul al doilea de întrebări, vede cărțile lui Mary care sunt (A,A) și cărțile lui Bob respectiv (A,b) și nu poate afirma nici acum ce cărți are.

În mod analog se întâmplă și în cazurile în care Mary ar avea un (8,8) sau un (A,8). În nici una din aceste situații nu se poate determina răspunsul sigur la întrebări.

Spre exemplu, să analizăm situația în care Mary are (A,8). Vom lua pe rând fiecare jucător în parte, în ordinea în care răspund la întrebări: Alice, Mary, Bob.

Lumile posibile ale lui Alice sunt:

(A,8)

(8,8) (A,8) (A,8)

(A,A)

Alice Mary Bob

Bob vede: (A,8) și (A,8), lumile lui posibile fiind:

(8,8)

(A,8) (A,8) (A,8)

(A,A)

Alice Mary Bob

Este evident, știind cont că atât pentru Alice cât și pentru Bob avem mai multe posibilități, răspunsul rămâne “no” și în acest caz. Concluzia este: la jocul trei nu se poate stabili cu exactitate ce cărți are Mary.

CAPITOLUL II

LOGICA MODALĂ

2.1. Sintaxa unui limbaj

Logica modală a fost discutată de câțiva autori în perioada antică, în special de Aristotel în lucrarea “De Interpretatione” și în “Prior Analytics”, precum și de logicienii medievali, dar, ca toate lucrările de dinaintea epocii moderne, ea nu era sistematizată. Prima sistematizare a acestui subiect pare fi făcută de Lewis începând cu 1912 și culminând cu lucrarea “Logica simbolică” a lui Langford (1959). Carnap (1946, 1947) sugera folosirea lumilor posibile pentru a atribui semantici modalităților. Semanticile lumilor posibile au fost dezvoltate în continuare, în mod independent, de către mai mulți cercetători, inclusiv de Bayard (1958), Hintikka (1957, 1961), Kanger, Kriple (1956), Meredith (1956), Montaque (1960) și Prior (care a atribuit ideea lui P.T. Geach), ajungându-se la forma lor actuală (prezentată în lucrarea de față). Mulți din acești autori au observat că prin varierea proprietăților relațiilor KI putem obține diferite proprietăți ale cunoașterii.

Opera inițială despre logica modală considera numai modalitățile probabilității și necesității. Ideea de a sesiza semantica cunoașterii din acest punct de vedere aparține lui Hintikka care, de asemenea, a fost primul care a observat proprietățile cunoașterii discutate. Analiza problemei copiilor murdari în termenii structurii lui Kripke aparține lui Halpern și Vardi (1991). Structurile Aumann au fost definite de Aumann în 1976. Acesta definește cunoașterea comună în termenii întâlnirii. O abordare asemănătoare, care definește cunoașterea ca un operator asupra evenimentelor, este studiată de Orlowska (1989).

2.2 Elemente de logică modală

Se știe că un limbaj este caracterizat prin:

Pentru a defini sintaxa unui limbaj ne vom folosi de elemente furnizate de logica modală.

Să presupunem că avem un grup G cu n – agenți notați prin: 1,2,…,n. Presupunem că acești agenți vor acționa într-o lume deschisă de elementele unei mulțimi care se numesc propoziții primitive, notate cu p,q,…,p`,q`,… .Aceste propoziții enunță fapte de bază cum ar fi “Alice este murdară pe mână” sau “Este frumos și cald afară” etc.

Avem ={ p,q,…,p`,q`,…}.

Fiecărui agent i, cu i=1,2,…,n care poartă numele de operator Ki, cu i=1,2,…,n care poartă numele de operator modal.

Dacă este cunoștință atunci semnificația intuitivă a lui Ki este “agentul i cunoaște ”.

Formulele limbajului se obțin din elementele lui combinând-ule cu negația, conjuncția și operatorii modali K1,K2,…,Kn.

Definiția 1: Conceptul de formulă se definește recursiv în felul următor:

elementele lui sunt formule;

dacă , sunt formule, atunci , , Ki (i=1,2,…,n) sunt formule.

Când avem (), atunci când nu există pericolul de confuzii, parantezele pot lipsi.

Cu operatorii , se poate obține disjuncția, implicația și echivalența în felul următor:

disjuncția se obține cu ();

implicația se obține cu ;

echivalența se obține cu ()() adică ()().

True este considerat ca o tautologie propozițională, spre exemplu, pp, iar false este abrevierea pentru true.

Cu ajutorul acestor operatori putem scrie formule cum ar fi

K1 K2p K2 K1K2p

care înseamnă: “agentul 1 cunoaște că agentul 2 cunoaște p și agentul 2 nu cunoaște că agentul 2 cunoaște p”.

Pentru un agent oarecare cunoștința este posibilă dacă el cunoaște . De exemplu, pentru agentul 1, este posibilă dacă K1.

Un enunț de forma: “Andrei este agentul 1 și Marius este agentul 2. Andrei nu cunoaște dacă Marius cunoaște că Andrei cunoaște că Marius cunoaște că Mary a plecat la munte” se transcrie astfel:

Andrei = agentul 1; Marius = agentul 2.

p= “Mary a plecat la munte”

K1(K2K1K1p)K1(K2K1K2p)

Am folosit faptul că un enunț de forma: “Andrei nu cunoaște dacă p” înseamnă că Andrei consideră atât pe p cât și pe p ca fiind posibile.

Vom căuta să definim în continuare semantica limbajului. Pentru aceasta vom folosi noțiunea de structură Kripke.

2.2. Descrierea unei Kripke. Exemple

Definiția 2: O structură Kipke M pentru n agenți peste este un sistem M=(S,,K1,…,Kn) unde:

S este mulțimea stărilor sau a lumilor posibile;

este o interpretare a lui , adică pentru fiecare sS

(s):{True, False}

KI este inclus în SxS, i{1,2,…,n}

!Observație: Dacă (s)(p)=True, atunci p este True în lumea s.

Pentru (s,t)Ki avem semnificația: agentul i primind o informație din lumea s consideră că t este o lume posibilă. De aceea Ki o numim relație de posibilitate.

Vom cere ca Ki să fie o relație de echivalență pe S:

Ki să fie reflexivă în sensul că sS avem (s,s) Ki;

Ki este simetrică: s,tS avem (s,t) Ki atunci (t,s)Ki;

Ki este tranzitivă: s,t,uS avem (s,t) Ki atunci (s,u)Ki.

Pentru a demonstra aceste proprietăți pornind de la definiția lui Ki : agentul consideră t ca fiind lume posibilă în starea (lumea) s, dacă în starea s și t agentul are aceeași informație despre lume.

Vom defini ce înseamnă că o formulă este True sau False în raport cu structura Kripke. Pentru aceasta definim mai întâi relația recursivă de deducție “=”.

Definiția 3:

Dacă p atunci (M,s)=p iff (s)(p) = True;

Dacă (M,s)= iff (M,s) = și (M's) =;

Dacă (M's) = iff (M,s);

unde M =(S,fl,K1,… ,K~) este o structura Kripke.

!Observatie: Relația (M,s) o citim astfel:

* este True in (M,s) sau

* (M,s) satisface pe .

!Observație: Pentru orice formulă și orice structură Kripke M avem (M,s)= sau (M,s), dar nu pe amandouă simultan. Logica modală definită are doar două valori.

Definitița 4: Adăugăm la definiția de mai sus:

(M,s)Ki iff (M,t) ) pentru toți t astfel încât (s,t)Ki.

!Observație: O structură Kripke se poate reprezenta sub forma unui graf orientat etichetat în felul următor:

* nodurile sunt elementele lui S, iar eticheta unui nod descrie care propoziții primitive sunt True și care sunt False în acea stare;

* arcele sunt etichetate cu ajutorul mulțimii de agenți: de la s la t avem un arc etichetat cu i dacă (s,t)Ki.

De exemplu: Avem ={pS, n=2, M=(S,II,K1,K2), unde S={s,t,u}.

adică avem:

(s)(p) = true

(u)(p) = true

(t)(p) = false

K1={(s,s), (s,t), (t,s), (t,t), (u,u)} (adică K1 nu distinge pe s de t).

K2={(s,s), (s,u), (t,t), (u,s), (u,u)} (adică K2 nu distinge pe s de u).

Graful va fi următorul:

!Observație: pe graful de mai sus am prezentat numai elementele care sunt true.

Să considerăm că în exemplul de mai sus avem p = “este frig la Londra”.

În starea S se consideră că: “este frig la Londra”, dar agentul 1 nu cunoaște acest fapt deci (M,s) K1p pentru că agentul 1 consideră stările s și t ca fiind posibile (iar (M,t) p deși (s,t)Ki).

Agentul 2 în starea s cunoaște că “este frig la Londra”, deoarece în cele două lumi posibile s și u, p este true. În starea t agentul 2 cunoaște că: “nu este frig la Londra”. Să vedem dacă în starea s agentul 1 cunoaște că agentul 2 cunoaște dacă sau nu este frig la Londra.

Anume:

(M,s) K1(K2p K2p) deoarece:

(M,s) K2p K2p

(M,t)K2p K2p.

Într-adevăr avem: (M,s) K2p și (M,t) K2p.

Astfel, deși din starea s agentul 1 nu cunoaște cum este vremea la Londra, el știe că agentul 2 cunoaște cum este vremea la Londra.

Agentul 2 în starea s nu știe că agentul 1 nu cunoaște acest fapt.

Formal am de demonstrat că:

(M,s) K2K1p.

Într-adevăr:

(M,s)K2K1p iff (M,s)K2K1p iff există o stare astfel încât (s,)K2 și (M,) K1p iff există o stare astfel încât (s, )K2 și (M, ) K1p iff există

o stare a astfel încât (s, )K2 și (M, )p pentru orice stare cu (,)K1.

Observăm acum că starea = u satisface această condiție. Așadar avem:

(M,s)p; (M,s) K1p; (M,s) K1(K2p K2p); (M,s) K2K1p.

Concluzia este:

(M,s) p K1p K2p K1(K2p K2p) K2 K1p.

!Observație: S-ar părea că una din stările s sau u poate fi eliminată deoarece în ambele stări p (singura propoziție primitivă !) are aceeași valoare: true. Dar nici una nu poate fi eliminată deoarece le separă cei doi agenți. Din starea s agentul 1 consideră că t este stare posibilă, dar agentul 2 nu face la fel, el consideră lumea u ca lume posibilă.

Drept consecintă agentul 1 nu cunoaște pe p în s, dar agentul 2 cunoaște.

Exemplu:

Presupunem că avem următoarea piesă de cunoaștere:

“Se consideră trei carți de joc A, B și C și doi agenți. Fiecare agent extrage o carte. A treia carte rămâne pe masă cu fața în jos".

O stare sau o lume posibilă a structurii va fi definită de o pereche de carți (cele extrase de cei doi agenți). Spre exemplu lumea (A,B) arată că agentul 1 a extras cartea A, agentul 2 a extras cartea B, iar C a rămas pe masă cu fața, în jos. Există 6 lumi posibile: (A,B); (A,C); (B,A); (B,C); (C,A); (C,B).

De asemenea este clar că în lumea (A,B) agentul 1 gândește că există două lumi posibile: (A,B) și (A,C). Agentul 1 cunoaște că el a extras cartea A și consideră că agentul 2 a extras cartea B sau C.

Similar, în lumea (A,B) agentul 2 gândește că lumile posibile sunt (A,B) sau (C,B).

În general în lumea (x,y) agentul 1 consideră lumile posibile (x,y) și (x,z), iar agentul 2 consideră pe (x,y) sau (z,y) ( Se consideră că avem 3 stări: x,y,z).

În exemplul nostru: n=2. Vom construi relațiile K1 și K2 (avem doar doi agenți) în felul următor:

K1={((A,B),(A,C)),((A,C),(A,B)),((A,B),(A,B)),((A,C),(A,C)),

((B,A),(B,C)),((B,C),(B,A)),((B,A),(B,A)), ((B,C),(B,C)),

((C,A),(C,B)), ((C,B),(C,A)), ((C,A),(C,A)), ((C,B),(C,B))}.

K2={((A,B),(C,B)), ((C,B),(A,B)), ((A,B),(A,B)), ((C,B),(C,B)),

((B,A),(C,A)), ((B,A),(C,A),((B,A),(B,A)), ((C,A),(C,A)),

((A,C),(B,C)), ((B,C),(A,C)), ((B,C),(B,C)), ((A,C),(A,C))}.

Atunci graful atașat devine:

Structura Kripke pentru jocul cu cărți

Când avem arce în ambele direcții care poartă aceeași etichetă nu se orientează. Limbajul acestei structuri este următorul:

propozițiile primitive sunt de forma lA, 2A, 2B etc. care sunt interpretate în felul următor: “agentul 1 are în mână cartea A”, “agentul 2 are în mână cartea A”, “agentul 2 are în mână cartea B” etc.

interpretarea este definită astfel:

((A,B))(1A) = true; ((A,B))(1B)=false etc.

Notam cu MC structura Kripke găsită în acest mod:

Mc=(S, , K1, K2)

Spre exemplu:

(MC(A,B)) 1A 2B

(MC(A,B)) K1(2B 2C)

Știm că agentul 1 are cartea A și atunci el consideră că agentul 2 are B sau C adică agentul 1 cunoaște că 2 are B sau C.

K1(2B 2C).

În mod similar avem (MC(A,B)) K1K2(1A) care se traduce prin: agentul 1 știe că agentul 2 nu știe că agentul 1 are cartea A.

Cum vom realiza conceptul de cunoștință comună și distribuită?

Având o cunoștință prin Ki înțelegem că “agentul i cunoaște ”.

Se pune problema cunoașterii informației de către cât mai mulți agenți ca în problema copiilor murdari în care doar i cunoșteau informația, ceilalti nu.

Spre exemplu, dacă nu avem o informație suplimentară, nu putem afirma prea ușor, dacă Alice cunoaște guvernatorii tuturor statelor.

Cu alte cuvinte x(State(x) y(KAliceGuvernator (x,y)): pentru toate statele x, există un y pe care Alice îl cunoaște ca fiind guvernator al lui x, lucru care nu se poate întâmpla cu certitudine.

2.3. Semantica unul Iimbaj. Operatori modali

Limbajul introdus în cele prezentate nu ne permite să exprimăm cunoștințele comune și distribuite. Vom introduce pentru aceasta trei operatori modali în felul următor:

Dacă avem un grup G format din n agenți 1, 2,… ,n, definim:

EG care se citește: “fiecare din grupul G cunoaște”

CG care se citește: “este o cunoștință comună pentru agenții din G”

DG care se citește: “este o cunoștință distribuită pentru agenții din G”.

Dacă este o formulă, atunci avem:

EG = “fiecare agent din G cunoaște ”

CG = “ cunoștința comună pentru agenții din G”

DG = “ cunoșința, distribuită pentru agenții din G”.

Spre exemplu:

K3C{1,2}p înseamnă că: “agentul 3 cunoaște că p nu este o cunoștință comună pentru agenții 1 și 2”.

Atunci când G= { 1,2,… ,n} vom omite indicele G de la acești operatori.

Dq Cq înseamnă că: “q este cunoștință distribuită, dar nu este comună pentru agenții G”.

Extindem acum semantica limbajului pentru a defini adevărul noilor formule: EG, CG, DG.

Definiția 4: (M,s)= EG iff (M,s) = Ki pentru toți iG adică EG este true iff fiecare agent din G cunoaște pe .

Pentru a defini cunoștințele comune avem nevoie de o interpretare grafică.

2.4. Interpretarea grafica a unei structuri Kripke

Fie M = (S, , K1,…,Kn) o structură Kripke și G = {1,2,…, n} un grup de n agenți.

Definiția 1: Spunem că tS este G-accesibilă din s în k pași, k1 dacă există un drum în graful atașat structurii Kripke (sau dacă există stările so, si,.. ,sk astfel încât so=s, sk=t și pentru orice j{0,1,2,…,k-1} există iG astfel încât (sj,sj+1)Ki) de la s la t care este etichetat cu elemente din G și are lungimea k.

Definiția 2: Spunem că t este G-accesibilă din s dacă există k1 astfel încât t este G-accesibilă din s în k pași.

Definiția 3: Dacă G = {1,2,… ,n} vom spune că t definit prin definiția 2 este accesibilă din s.

Proprietatea 1: (M,s)= iff (M,t) pentru toate stările t care sunt G-acesibile din s în k pași (k1).

Demonstrație: Vom demonstra prin inducție dupa k:

k=1 avem (M,s) =EG, (M,s) =Ki, iG iff (M,t) = t astfel încât (s,t)Ki, iG.

Presupunem afirmația adevarată pentru k pași și vom demonstra pentru k+1:

(M,s) iff (M,t) (din ipoteza inducției).

Proprietatea 2: (M,s) CG iff (M,t) pentru toate stările t care sunt G-accesibile din s.

Demonstrație: Din proprietatea 1: (M,s) iff (M,t). Mai știm că (M,s)CG iff (M,s) , k1.

Din cele două afirmații rezultă că (M,s) CG iff (M,t) t o stare G-accesibilă din s.

!Observație: Rezultatul anterior dat de cele două propoziții are loc chiar dacă Ki sunt relații binare oarecare, fără să fie relații de echivalență.

CAPITOLUL III

CUNOȘTINȚE DISTRIBUITE

3.1. Noțiuni generale. Exemple

Definiția 1: Spunem că (M,s)DG dacă și numai dacă pentru orice t, stare

a structurii, avem: (M,s) cu proprietatea că (s,t) , G cu alte cuvinte este cunoștință distribuită pentru grupul G dacă cunoștințele “combinate” ale membrilor lui G implică .

Spre exemplu:

Fie doi agenți Mike și Ana care se întâlnesc: Mike știe: “Peter iubește pe Maria sau pe Susan”. Ana știe: “Peter nu iubește pe Susan”. Informația “Peter iubește pe Maria” este o cunoștință distribuită la cei doi agenți.

Alt exemplu:

Să revenim la jocul cu cărțile unde G este grupul format de cei doi jucatori, adică G = {l,2}. Fie s o stare oarecare.

Avem:

(MC,t)= lA lB 1C

pentru orice t stare accesibilă din s.

Rezulta că:

(MC,s)=CG(lA lB 1C)

Vom arăta că de asemenea avem relația:

(MC,s) =CG(lA (lB 1C))

Avem:

lB (2A 2C) “” lB 2A 2C.

(MC,s) = lB 2A 2C “”

(MC,s) =2B 2A 2C relație care este adevărată.

Mai avem:

(MC, (A,B)) DG(1A 2B)

deoarece K1 K2 = {((x,y), (x,y)) x,y{A,B,C,}}.

Deci putem afirma că pentru s= (A,B) avem un singur t astfel încât

(s,t)K1 K2 și anume t = (A,B).

Dar (MC, (A,B)) = 1A 2B, pentru că (MC,(A,B)) = lA și (MC,(A,B)) =2B.

Să revenim la problema copiilor murdari pe frunte. Să considerăm situația dinainte ca tatăl să le vorbească copiilor. Numerotăm copiii cu: 1,2,…,n. Unii din ei au fruntea murdară, alții nu. O situație oarecare poate fi descrisă printr-un vector (x1,x2 …… ,xn) în care:

xi=1, dacă copilul i are fruntea murdară;

xj=0, dacă copilul i are fruntea curată.

Să presupunern că n = 3. Un vector, de exemplu (1,0,1) arată că au fruntea murdară copiii 1 și 3, iar copilul 2 are fruntea curată. Să considerăm că situația actuală este descrisă de acest vector. Copilul 1 vede frunțile celorlalți doi copii, dar nu o vede pe a sa. De aceea pentru copilul 1 situațile posibile sunt:

(0,0,1);

(1,0,1).

Pentru al doilea copil situațiile posibile sunt:

(1,0,1);

(1,1,1).

În general, pentru copilul i exisă două lumi posibile.

Să reprezentăm situația generală printr-o structură Kripke. Ea constă 2n stări, deoarece există 2n vectori binari de forma (x1, .., xn). Vom considera mulțimea

= {p1, p2,…, pn,p}, unde:

p = “cel putin un copil are fruntea murdară” aceasta reprezentând afirmația initială a tatălui;

pi = “copilul i are fruntea murdară” cu i{1,2,…,n}.

Definim interpretarea astfel:

(x1,…, xn)(pi) = 1 iff xi=1

(x1, … ,xn)(p) = 1 iff există j{1,2,…,n} cu xj=1.

Rezultă că vom avea:

(M, (x1, x2, … ,xn)) = pi iff xi = 1.

(M,(x1,x2, …,xn)) =p iff există j{1,2,…,n} cu xj= 1.

Să mai observăm că valoarea de adevăr a lui p se poate determina în funcție de valorile de adevăr pentru p1, p2,…, pn, deoarece propoziția p este echivalentă cu p1p2…pn.

Această dependență nu are nici o implicație deoarece nu se impune, în general, nici o condiție cu privire la dependența sau independența propozițiilor primitive.

Să definim relațiile Ki în felul următor:

((x1,… ,xn), (y1, … ,yn)) Ki iff (x1,…,xi-1, xi+1,…, xn) = (yi, … ,yi-1, yi+1,…,yn), adică (s,t)Ki dacă s și t au aceleași componente în afară de cea de pe poziția 1.

Să observăm că relațiile Ki definite mai sus sunt relații de echivalentă deoarece:

(s,s)Ki este adevarată pentru orice s=(x1,x2,…,xn), deci Ki este reflexivă;

2. Dacă (s,t)Ki rezultă că (t,s)Ki adevărat deoarece: să luăm s=(x1,x2,… ,xn) și t=(y1, y2,…, yn). Cum (s,t)Ki rezultă că avem:

(x1, x2,…, xi+1,xi+1,…, xn) = (y1,y2,…,yi-1, yi+1,…, yn) “”

(y1, y2,…, yi-1, yi+1,…, yn) = (x1, x2,…, xi-1,xi+1,…, xn) “” (t,s)Ki , deci relațiile Ki sunt simetrice;

3. Dacă (s,t)Ki și (t,u) Ki “” (s,u) Ki. Să luăm s=(x1, x2,…,xn),

t=(y1,y2,…,yn), u = (z1,z2,…,zn).

Cum (s,t)Ki avem (x1, x2,…, xi-1,xi+1,…, xn)=(y1, y2,…, yi-1, yi+1,…, yn) și (t,u)Ki adică (y1, y2,…, yi-1, yi+1,…, yn)=(z1, z2,…, zi-1, zi+1,…, zn), rezultă că:

(x1, x2,…, xi-1,xi+1,…, xn)=(z1, z2,…, zi-1, zi+1,…, zn), deci (s,u)Ki.

Cu alte cuvinte am demonstrat că relațiile Ki sunt tranzitive.

Să revenim la cazul particular analizat atunci când n=3. Structura Kripke obtinută are o reprezentare grafică clară. Stările ei sunt date de vârfurile unui hipercub cu latura de 1 în spațiul tridimensional. Dacă în prima etapă nu ținem seama de etichetele arcelor, atunci două noduri se unesc printr-o muchie dacă ele diferă exact într-o componentă. Avem urmatorul graf atașat structurii Kripke descrisă sus pentru cazul particular n=3:

Intuitiv fiecare copil cunoaște care din ceilalți, copii are fruntea murdară. Intuiția se poate demonstra în sistemul formal descris mai sus.

De exemplu:

Daca situația actuală este (1,0,1) atunci:

(M,(1,0,1)) K1p2

Să demonstrăm acest lucru:

(M,(1,0,1)) p2

pentru că (M,(0,0, 1)) p2.

În același timp și (M,(1,0,1))Kip3 și (M, (1,0,1))K1p1 care înseamnă: copilul 1 cunoaște că al treilea copil este murdar, iar copilul 1 nu cunoaște dacă el este murdar sau nu, pentru că lumile lui posibile sunt (1,0,1) sau (0,0,1).

Spre exemplu:

Formula p2K1p2 înseamnă că, dacă copilul 2 este murdar, atunci copilul 1 știe aceasta și devine cunoștință comună adică C(p2K1p2) este adevarată în orice stare, adică:

(M,s) C(p2K1p2)

Deoarece orice stare t este accesibilă din s rezultă ca trebuie să verificăm că pentru orice stare t avem:

(M,t)(p2K2p2) sau echivalent

(M,t)p2K1p2

Avem două situații:

(M,t) p2, cu t = (x,1,y) și x,y{0,1}. Atunci orice stare cu (t,)K1 are componenta a doua egala cu 1, deci (M,)p2.

Rezultă că (M,t) K1p2.

2) (M,t) p2, atunci (M,t)p2

Cele două situații de mai sus ne arată că(M,t)p2K1p2.

În lumea (1,0,1) fiecare copil cunoaște p. Așadar avem:

(M,(1,0,1))Kip, i{1,2,3}

ceea ce se poate de asemenea demonstra formal.

Rezultă că: (M,(1,0,1))E2. În același timp (M,(1,0,1))E2.

Știind că p este adevarată în starea (0,0,0) este nevoie de doi pași pentru a se ajunge în starea (1,0,1) ((M,(0,0,0))p).

Putem generaliza acest lucru pentru un n-tuplu și anume dacă pentru k componente avem că este true atunci nu este true.

!Observație: Noțiunea de cunoșință comună este privită din două puncte de vedere:

formal sau tehnic: o formulă este cunoștință comună în starea s dacă este true în orice stare accesibilă din s;

informal: un fapt (nu neapărat exprimabil în limbajul introdus de noi) este cunoștința comună dacă este true în toate stările structurii;

Spre exemplu:dacă revenim la problema copiiior murdari pentru cazul în care n=3. În starea (1,0,1) copilul 1 consideră posibilă situația (0,0,1). Tot în această stare copilul 3 consideră (0,0,0) ca fiind lume posibilă. Adevărul este că în lumea (1,0,1), înainte ca tatăl să vorbească, copilul 1 crede că copilul 3 crede că nici un copil nu are fruntea murdară. Astfel cunoștința “cel puțin un copil are fruntea murdară” apărută după ce vorbește tatăl, devine cunoștință comuna. După fiecare răspuns “No” al grupului, apar trunchieri noi în hipercub. Astfel, după primul răpuns “No”, dispar toate nodurile etichetate cu vectori care au un singur 1. Apoi devine cunoșință comună faptul că “cel puțin doi copii au fruntea murdară”. Raționamentul se extinde pentru k răspunsuri “No”. După k răspunsuri “No”, devine cunoșință comună: “există cel puțin k+ 1 copii cu fruntea murdară”.

Atunci structura Kripke după ce tatăl afirmă p, devine:

Vom demonstra afirmația făcută mai sus în sensul următor:

Dacă avem situația descrisă prin tuplul (1,0,0,… ,0) atunci copilul 1 consideră inițial două lumi posibile (0,0,… ,0) și (1,0,… .,0). Numai după ce tatăl vorbește atunci starea (0,0,… ,0) nu este posibilă, deci rămâne numai starea (1,0,…,0) și asta înseamnă că numai un copil este murdar pe frunte. După ce fiecare răspunde cu “No” la prima întrebare a tatălui cunoștința comună în acest caz nu poate fi (1,0,…,0) (se consideră că toți copiii sunt inteligenți și capabili să raspundă la întrebarea tatalui). După un astfel de răspuns înseamnă că cel puțin doi copii sunt murdari pe frunte și acest lucru devine noua cunoșință comună. Se raționează în mod analog din aproape în aproape pentru toți cei k copii murdari.

3.2. Propietăți ale cunoașterii

Până acum am descris un limbaj care utilizează operatorii modali Ki și am definit noțiunea de true, care în particular determină dacă o formulă Ki este true într-o lume posibilă. De obicei am sugerat ca formula Ki să fie citită: “agentul i cunoaște ”. Este aceasta o modalitate rezonabilă de a citi această formulă? Semantica definită, adică structura Kripke împreună cu definirea adevărului, capturează în mod real proprietățile cunoașterii în mod rezonabil?

Pentru aceasta vom studia formulele care sunt întotdeauna adevarate.

Definiția 1: Fie M= (S, , K1,…,Kn) o structură Kripke. Spunem că este validă în M și scriem M, dacă (M,s) pentru orice sS.

Definiția 2: Spunem că este satisfiabilă în M dacă (M,s) pentru o anumită stare sS.

Definitția 3: Spunem că este validă și scriem , dacă este validă în toate structurile.

Definiția 4: Spunem că este satisfiabilă dacă ea este satisfiabilă într-o anumită structură.

!Observație: Se observă că este validă (respectiv validă în M) iff este nesatisfiabilă (respectiv nesatisfiabilă în M).

Vom enumera câteva proprietați valide. Reamintim că se cere ca relațiile Ki de posibilitate să fie relații de echivalență.

Proprietatea 1 (Axioma de distribuție):

(Ki Ki( ))Ki, , formule.

Proprietatea 2 (Regula de generalizare a cunoșințelor)

Pentru orice structură Kripke M, dacă M atunci MKi.

Corolar: Dacă , este validă atunci Ki este validă.

Această regulă este diferită de formula Ki care spune că este adevărată dacă agentul i cunoaste . Agentul nu trebuie neapărat să cunoască că aceasta este adevărată (Spre exemplu în cazul problemei copiilor murdari, dacă considerăm ca adevăr că agentul 1 este murdar pe frunte, acest lucru nu trebuie cunoscut neapărat de el).

Vom demonstra cele două posibilitați:

(Ki Ki( ))Ki este o formulă validă?

sS avem (M,s) (Ki Ki( ))Ki

Să presupunem că: (M,s) Ki Ki( ) (M,s) Ki și

(M,s)Ki( )

Trebuie să demonstrăm că (M,s)Ki.

Pentru orice tS avem (s,t)Ki și atunci (M,t)

Fie tS: (M,t), (s,t)Ki

(M,t)( ), (s,t)Ki ceea ce conduce la

(M,t) , tS (s,t)KI

Am folosit faptul că (M,s)( ) “” (M,s) “”(M,s) atunci (M,s).

Avem formulă validă tS: (M,t)

tS: (M,t)Ki (tS: (s,t)KI avem (M,t)) este adevărată.

!Observație: În realitate, un agent nu cunoaște neapărat toate faptele adevărate.

Proprietatea 3 (Axioma adevărului): Ki .

Demonstratie:

sS: (M,s)Ki deducem tS astfel încât (s,t)Ki avem (M,t) ).

Dar Ki sunt relații de echivalenă, deci (s,s)Ki. Atunci pentru t=s vom avea (M,s).

Deci sS: (M,s)Ki .

Proprietatea 4 (Axioma introspecției pozitive): KiKiKi.

Demonstrație:

KiKiKi este o formulă validă?

Fie sS astfel încât (M,s)Ki. Trebuie să arătăm că (M,s) KiKi. Pentru

tS: (s,t)Ki avem (M,t)

tS: (s,t)Ki avem (M,t)Ki

uS: (t,u)Ki avem (M,u) .

Cum Ki sunt relații de echivalentă din tranzitivitate rezultă:

(s,u)Ki: (M,u) .

!Observație: dacă un agent nu cunoaște pe atunci el știe că nu cunoaște pe .

Proprietatea 5 (Axioma introspecției negative):Ki KiKi. Demonstrație:

Vom presupune că Ki este validă într-o structură M. Atunci oricare ar fi sS, (M,s) Ki deci există uS astfel încât

(M,u) (s,u)Ki.

Fie tS: (s,t)Ki, (M,t) Ki, tS; (s,t)Ki “” (M,s) KiKi.

Din simetria relațiilor de echivalentă, Ki avem că (t,s)Ki. Folosind și tranzitivitatea se obține (t,u)Ki “”(M,t) Ki,

Demonstrațiile făcute mai sus ne arată că cele cinci proprietăți prezente sunt adevarate din punct de vedere formal.

!Observație: Cele cinci proprietăți prezentate sunt numite proprietățile S5 pentru cunoaștere (ele sunt “cele 5 axiome”).

Folosind operatorii EG, CG, DG introduși în paragrafele anterioare vom pune în evidență urmatoarea teoremă:

Teoremă: Pentru orice formulă și , orice structură Kripke M și orice G{1,2,… ,n},G avem:

MEG Ki;

MCG EG( CG);

dacă M EG( ) atunci M CG.

Demonstrație:

MEG “” sS: (M,s) (EG Ki);

Deci (M,s) EG dacxă și numai dacă (M,s) Ki.

MCG EG ( CG);

Presupunem că (M,s)CG, sS. Din proprietatea 2, paragraful 2.4. rezultă că (M,t), t G-accesibilă din s. În particular, dacă u este G-accesibilă din s într-un singur pas atunci (M,u) și (M,t) pentru toate stările t G-accesibile din u.

Astfel, (M,u)CG pentru toate stările u care sunt G-accesibile din s într-un singur pas. Așadar avem (M,s) EG( CG).

Reciproc, să presupunem că (M,s) EG( CG). Presupunem că t este Gaccesibilă din s și că s' este prima stare după s în drumul de la s la t, al cărui arc este etichetat cu un element din G.

Deoarece (M,s) EG( CG) rezultă că (M, s') CG. Ori s' = t ori t este accesibilă din s'. În primul caz avem (M,t) deoarece (M,s').

În al doilea caz, (M,t) din proprietatea 1, paragraful 2.4. și din faptul că

(M,s)CG. Deoarece (M,t) pentru toți t care sunt G-accesibile din s, rezultă că (M,s')CG.

(c) Presupunem că M EG() și (M,s). Demonstrăm prin inducție după k că pentru orice k avem (M,t) pentru toți t care sunt Gaccesibile din s în k pași.

Presupunem că t este G-accesibilă din s într-un singur pas.

Deoarece M EG() rezultă că (M,s) EG(). Deoarece t este G-accesibilă din s într-un pas, prin proprietatea 1, paragraful 2.4., avem (M,t) ceea ce ne trebuia.

Dacă k = k'+ 1, atunci există un t' care este G-accesibilă din s în k' pași astfel încât este G-accesibilă din t' într-un pas. Prin ipoteza inducției, avem (M,t').

Același argument ca în cazul de bază ne arată că (M,t) ceea ce completează inducția.

Deoarece (M,t) pentru toți t care sunt G-accesibili din s, rezultă că (M,s)CG.

!Observație: Punctul (b) din teorema de mai sus se mai numește axioma punctului fix, care spune că este cunoștința comună pentru G iff toți membrii lui G cunosc că este true și că este cunoștință comună.

Cu alte cuvinte CG poate fi văzut ca un punct fix pentru funcția f(x)=EG(x)

!Observațe: Punctul (c) din teorema de mai sus se mai numește regula inducției. Demonstrația ei arată de ce antecedentul dă suficiente ingrediente pentru a demonstra, prin inducție dupa k, că EG() este validă pentru toți k.

Relativ la cunoștințele distribuite, acestea satisfac toate proprietațile cunoștințelor, ca orice cunoștință.

Proprietate: D{i}Ki

DGDG dacă GG

Demonstrația acestei propoziții se face în mod analog ca la cele cinci proprietați care au fost demonstrate anterior.

CAPITOLUL IV

FORME DE REPREZENTARE A CUNOȘTINȚELOR COMUNE ȘI DISTRIBUITE

4.1. Reprezentarea pe bază de evenimente. Structura Aumaun

Abordarea anterioară a modelarii cunoașterii este cunoscută sub numele de abordare bazată pe logică. Acum vom prezenta o altă abordare care este tipic utilizată în jocuri și în economia matematică. Ea se numește abordare bazată pe evenimente. Aceasta diferă de prima abordare din doua puncte de vedere. În primul rând, avem sprijinul teoriei probabilităților.

Fie o multime S de elemente numite stări.

Un eveniment este o mulțime eS. Spunem că evenimentul e are loc în starea s dacă se.

Vom defini următorii operatori:

Conjuncția a două evenimente se definește ca intersecție a lor.

Negația unui eveniment este complementara sa față de S.

Modelul formal al abordarii bazată pe evenimente este structura Aumann. Ea seamănă cu o structură Kripke, cu două diferențe: prima se datorează functiei (aici nu există, deoarece nu avem propoziții primitive); a doua diferentă provine din faptul că în locul relațiilor Ki, care defineau lumile posibile pentru agentul i, în structura Aumann se consideră o partiție Pi a lui S pentru agentul i.

Dacă Pi = {S1, S2,…, Sr} atunci Sj se numesc celulele partiției Pi sau mulțimile de informații pentru agentul i.

Din punct de vedere intuitiv, Sj este o mulțime de informații pentru agentul i și dacă sSj atunci lumea stărilor pe care agentul i le consideră posibile este exact Sj.

Definiția 1: O structură Aumann A este un tuplu (S, P1, P2,. ..,Pn), unde S este mulțimea stărilor lumii și Pi este o partiție a lui S pentru agentul i.

Notăm cu Pi(s) celula partiției Pi în care apare S. Deoarece Pi este o partiție, rezultă că pentru fiecare agent i și fiecare pereche de stări s,tS, avem ori P1(s)= Pi(t) ori P1(s) Pi(t)=. Intuitiv, când s și t sunt în aceeași mulțime de informații a agentului i, în starea s agentul i consideră că starea t este posibilă.

Cum definim cunoșințele în această abordare?

Deoarece obiectele cu care lucrăm sunt evenimente, este evident că în acest caz cunoștințele vor fi exprimate prin evenimente.

Definiția 2: Fie (S, P1,…,Pn) o structura Aumann. Definim:

Ki: 2S2S, pentru i=1,2,…,n prin:

Ki={sSPi(s)e}

Spre exemplu:

În acest caz e este o mulțime delimitată punctual.

Ki(e)=ab

Definiția 3: Introducem operatorii EG, CG, DG în felul următor:

Operatorul “fiecare în grupul G cunoaște e” este definit de

EG: 2S2S, prin:

EG(e)=Ki(e)

Iterațiile din E se definesc în modul următor:

(b) Operatorul “cunoașterea comună a unui eveniment e printre agenții unui grup G” este notat cu CG(e) și se definește prin:

CG: 2S2S, prin:

CG(e)=EkG(e);

(c) Operatorul “cunoașterea distribuită a unui eveniment e de către agenții unui grup G” este definit de:

DG: 2S2S, prin:

DG(e)={sSPi(s)s}

4.2. Legatura dintre structura Kripke și structura Aumann

Am prezentat două metode de reprezentare a unei propoziții: una cu ajutorul formulelor, iar alta cu ajutorul evenimentelor.

Fie structura Kripke M=(S, , K1, K2,…, Kn), unde Ki sunt relații de echivalență.

Definim o structură Aumann corespunzatoare:

AM=(S,P1,P2,…,Pn)

cu aceeași mulțime de stări S, luând partiția Pi ca fiind definită de relația de echivalență, Ki.

Trebuie să demonstrăm că M și AM dau aceeași “semantică”.

Fie o formulă în limbajul lui M. Definim:

M={sS(M,s)}

Fie ={p1,p2,…,pn}, unde pi sunt propoziții primitive.

Pentru orice p definim evenimentul eMp astfel:

eMp ={sS(M,s)p}.

Pentru fiecare formulă definim evenimentul atașat evM() prin inducție după structura lui :

FxF F

evMxevM evM

2Sx2S 2S

, Ki, CG,DG

F F

evM evM

2S 2S

C, Ki, CG, DG

Avem:

evM(p)=eMp;

evM(12) = evM(1) evM(2);

evM() = S-evM();

evM(Ki) = Ki(evM());

evM(CG) = CG(evM());

evM(DG) = DG(evM()).

Propoziție: Fie M o structură, unde fiecare relație de posibilitate Ki este relație de echivalență. Fie AM structura Aumann corespunzătoare. Atunci, pentru orice formulă avem:

evM()=M.

Demonstrație:

Considerăm structura Kripke M=(S, , K1,… ,Kn) și A = (S, P1,…,Pn) o structură Aumann corespunzatoare (mulțimea stărilor S este una singură).

Vom demonstra prin recurentă, după structura formulei .

Pentru = p egalitatea, prin definiție, este adevarată;

Presupunem că este adevarată pentru și . Avem

evM()=evM()evM()=MM =()M

evM() = S-evM()=S-M=()M.

4. Să demonstrăm că dacă evM()=M atunci evM(Ki)=(KiM), adică Ki(evM())=(Ki)M. Cu alte cuvinte, să demonstrăm că:

s Ki(evM()) iff (M,s)Ki.

Dar (M,s)Ki iff (M,t) pentru toți (s,t)Ki. Ținând seama de definiția lui Ki, rezu1tă că trebuie să demonstrăm că:

s Ki(M) iff (M,t)Ki pentru toți t cu (s,t)Ki.

Dacă s Ki(M) atunci Pi(s)M. Dar Pi(s) = {tS(s,t)Ki}.

Așdar:

s Ki(M) iff Pi(s)M iff pentru orice stare tS cu (s,t)Ki, avem tM iff pentru orice t cu (s,t)Ki, avem (M,t).

5. Să demonstrăm că dacă evM()=M atunci evM(CG)=(CGM).

Deci cu alte cuvinte, trebuie să demonstrăm că:

s CG(evM()) iff (M,s)CG adică:

s(M) iff (M,s) CG, pentru orice k1.

Pentru k = 1 avem:

s E(M) iff s(M) iff pentru orice iG avem s Ki(M)

s Ki(M) iff pentru orice tS cu (s,t)Ki, avem tM iff pentru orice tS cu (s,t)Ki avem (M,t) iff (M,s)Ki.

Așadar:

s EG(M) iff (M,s)Ki pentru orice iG deci s EG(M) iff (M,s)EG.

Presupunem că pentru k fixat avem:

s (M) iff (M,s) ().

Avem:

s (M) iff sEG( (M)) iff s( (M))

iff pentru orice iG: s( (M))

iff pentru orice iG: Pi(s) (M)

iff pentru orice iG: orice tS cu (s,t)Ki : (M,t) ()

iff (M,s) EG( ()).

6. Să demonstrăm că evM(DG)=(DGM) dacă evM()=M, adică:

s DG(evM()) iff (M,s)DG sau

sDG(M)

Avem sDG(M) iff Pi(S)M

iff pentru orice iG, orice tS cu (s,t)Ki avem

tM iff orice t cu (s,t) Ki avem (M,t)

iff (M,s)CG.

Deci am arătat cum pornind de la o structură Kripke obținem una Aumann.

Fie acum A=(S,P1,…,Pn) o structură Aumann. Vom defini o structură Kripke M = (S, , K1,…,Kn) cu aceeași mulțime S.

Definirea lui Ki este simplă și anume sunt relații de echivalentă corespunzatoare partiției Pi.

Cum în structură Aumann nu ne interesează propozițiile primitive și nici funcția , acestea vor fi arbitrare, și anume le vom obține din piesa de cunoaștere dată la început.

Definim structura Kripke corespunzătoare lui A și în felul următor:

MA,= (S, , K1,…,Kn) unde Ki sunt corespunzatori partiției Pi, pentru i=1,2,..,n. Se poate arăta că structura Aumann corespunzătoare lui MA, este A.

CAPITOLUL V

PREZENTAREA ȘI MODELAREA UNOR PROBLEME

FOLOSIND ELEMENTE DE LOGICĂ MODALĂ

5.1. Problema ași1or și optarilor.

Se joacă cu 4 ași și 4 optari, între trei jucători. Regula jocului este: se împart câte două cărți la fiecare dintre jucători, două cărți rămânând cu fața în jos pe masă. Fiecare jucător își ridică cărțile în dreptul frunții astfel încât ceilalți doi jucători să vadă ce cărți deține, dar el să nu știe.

Fiecare va căuta să determine ce cărți are, iar în cazul în care nu poate să afirme acest lucru trebuie să spună. Să presupunem că cei trei jucători sunt: Alice, Bob și Mary. Se presupune că nici unul din ei nu minte, acest lucru fiind cunoștință comună.

Vom nota cu A un as și cu 8 un optar. Atunci o stare posibilă ar fi:

Alice – (A,A), Bob – (A,8), Mary – (A,8).

Deci dacă Alice ar avea (A,A) și Bob (A,8), atunci cel mai ușor se pot determina lumile posibile ale lui Mary căci ea vede cărțile lui Alice și Bob și se gândește că ea poate avea fie (A,8) fie (8,8).

(a)Să presupunem că se ignoră cererea (ordinea) cărților. Astfel, de exemplu, nu facem distincție între o mână cu asul de romb și cu asul inima roșie și una cu asul de treflă și asul cu inima roșie.

Câte lumi posibile sunt în acest caz? Avem următoarele lumi posibile:

((A,A), (A,8), (A,8)), ((A,A), (A,8), (8,8)), ((A,A), (A,A), (8,8)),

((A,8), (A,8), (A,A)), ((A,8), (A,8), (A,8)), ((A,8), (A,8), (8,8)),

((A,8), (A,A), (A,8)), ((A,8), (A,A), (8,8)), ((A,A), (A,8), (A,A)),

((A,A), (8,8), (A,A)), ((A,A), (8,8), (A,8)),

((A,8), (8,8), (A,8)), ((A,8), (8,8), (A,A)),

((8,8), (A,A), (A,A)), ((8,8), (A,A), (8,8)), ((8,8), (A,A), (A,8)),

((8,8), (A,8), (A,8)), ((8,8), (A,8), (A,A)),

((8,8), (8,8), (A,A)).

sau, pentru a le urmări mai ușor: prima pereche este cea deținută de Alice, a doua de Bob, iar a treia de Mary.

Dacă Alice are o mână formată din 2 ași (nu contează ordinea, deci nu contează care și sunt).

(A,A) are posibilitățile pentru Bob:

– (A,8)

– (A,A) Ă – (8,8)

– (A,8)

Dacă Alice are un (A,8)

(A,8)

Dacă Alice are (8,8)

(8,8)

Se observă că starile pentru un jucător sunt: (A,A), (A,8), (8,8) atunci când nu contează ordinea cărților.

Deci numărul lumilor posibile este 19.

(b) Desenați structura Kripke care descriind problema.

Vom defini relațiile K1, K2, K3;

K1 pentru jucătorul 1-Alice;

K2 pentru jucătorul 2 – Bob;

K3 pentru jucătorul 3 – Mary.

Evident că Alice poate avea: (A,A), (A,8) sau (8,8). Atunci, în general, dacă avem starea (x,y,z), agentul 1 consideră lumi posibile pe (t,y,z) sau (v,y,z), (w,y,z); agentul 2 consideră lumi posibile: (x,t,z), (x,v,z) și (x,w,z); agentul 3 consideră lumi posibile: (x,y,t), (x,y,v), (x,y,w), unde x,y,z,t,v,w{(A,A), (A,8), (8,8)}.

Vom considera o situație descrisă de (x1, x2, x3), unde x1,x2,x3{(A,A), (A,8), (8,8)}. Problema apare ca o particularizare a problemei copiilor murdari. Relațiile Ki le definim în felul următor:

Ki iff au o singură componentă diferită pe poziția i.

Această structură Kripke este complet definită:

Pentru a putea urmări mai ușor vom scrie:

(A,8)

(8,8) (A,A),(A,A) (8,8) (A,8),(A,8)

(A,A)

este vârf izolat

(8,8) (8,8)

(A,8),(A,A) (A,A),(A,8)

(A,8) (A,8)

(A,A) (A,A)

(A,8) (8,8),(A,A) (A,8) (A,A),(8,8)

(8,8) (8,8)

(A,8) (A,A)

(8,8),(A,8) (A,8),(8,8)

(A,A) (A,8)

(A,A) (8,8) (8,8) vârf izolat.

Structura nu este completă.

Pentru K2 avem primul și ultimul element egale și se determină în felul următor:

(A,A) (8,8) (A,A) este vârf izolat.

(8,8)

(A,A) (A,A) (A,8)

(A,8)

(A,A)

(A,A) (A,8) (8,8)

(8,8)

(A,8) (8,8)

(A,8) (A,A) (A,8); (A,8) (A,A) (A,A)

(8,8) (A,8)

(A,A) (A,8)

(A,8) (A,A (8,8); (8,8) (A,A) (A,A)

(A,8) (8,8)

(A,8)

(8,8) (8,8) (A,8); (8,8) (A,A) (8,8)

(A,A) vârf izolat

Pentru K3, primele două componente sunt egale:

(A,A) (A,A) (8,8) vârf izolat

(A,8) (A,A) (A,8)

(8,8) (8,8) (A,A) (8,8) (A,A)

(A,8)

(8,8)

(A,8) (A,A)

(A,8)

(A,8)

(A,8) (A,8) (8,8)

(A,A)

(A,8)

(A,8) (8,8)

(A,A)

(A,A)

(8,8) (A,8) (8,8)

(A,8)

(A,8)

(8,8) (A,8)

(A,A)

(8,8) (8,8) (A,A)

vârf izolat

K1={((8,8),(A,A),(A,A)), ((A,8),(A,8),(A,8)), ((8,8),(A,8),(A,8)), ((A,A),(A,8),(A,8)), ((8,8),(A,8),(A,A)), ((A,8),(A,8),(A,A)), ((8,8),(A,A),(A,8)), ((A,8),(A,A),(A,8)), ((A,A),(8,8),(A,A)), ((A,8),(8,8),(A,A)), ((8,8),(8,8),(A,A)), ((A,A),(A,A),(8,8)), ((A,8),(A,A),(8,8)), ((8,8),(A,A),(8,8)), ((A,8),(8,8),(A,8)), ((A,A),(8,8),(A,8)), ((A,A),(8,8),(A,8)), ((A,A),(A,8),(8,8)), ((A,8),(A,8),(8,8))}. K2={((A,A),(8,8),(A,A)), ((A,A),(8,8),(A,8)), ((A,A),(A,8),(A,8)), ((A,A),(A,A),(8,8)), ((A,A),(A,8),(8,8)), ((A,A),(8,8),(A,8)), ((A,8),(A,8),(A,8)), ((A,8),(A,A),(A,8)), ((A,8),(8,8),(A,8)), ((A,8),(8,8),(A,A)), ((A,8),(A,8),(A,A)), ((A,8),(A,A),(8,8)), ((A,8),(A,8),(8,8)), ((8,8),(A,8),(A,A)), ((8,8),(A,A),(A,A)), ((8,8),(8,8),(A,A)), ((8,8),(A,8),(A,8)), ((8,8),(A,A),(A,8)), ((8,8),(A,A),(8,8))}. K3={((A,A),(A,A),(8,8)), ((A,A),(A,8),(A,8)), ((A,A),(A,8),(8,8)), ((A,A),(8,8),(8,8)), ((A,A),(8,8),(A,A)), ((A,A),(8,8),(A,8)), ((A,8),(A,A),(8,8)), ((A,8),(A,A),(A,8)), ((A,8),(A,8),(A,8)), ((A,8),(8,8),(8,8)), ((A,8),(A,8),(A,A)), ((A,8),(8,8),(A,8)), ((A,8),(8,8),(A,A)), ((8,8),(A,A),(A,A)), ((8,8),(A,A),(8,8)), ((8,8),(A,8),(A,8)), ((8,8),(A,8),(A,A)), ((8,8),(8,8),(A,A))}.

Graful atașat acestei structuri este prezentat in figura următoare

(c) Dacă considerăm că Alice are în mână 2 ași și Bob are doi optari, iar la prima întrebare: “Ce cărți aveți în mână?” nici Alice nici Bob nu pot răspunde, cum construim structura Kripke?

Cel mai ușor este să stabilim lumile posibile pentru Mary căci ea vede 2-A la Alice și 2-B la Bob. Atunci ea considera că nu poate avea decât (A,8), (A,A) sau (8,8).

Pentru Alice avem următoarele lumi posibile: (X, (8,8), Z) unde Alice știe Z. ((A,A), (8,8), (A,8)) sau ((A,8), (8,8), (A,8)) Z= (A,8)

((A,A), (8,8),(8,8)) Z= (8,8) caz care cade pentru că la prima întrebare Alice nu poate răspunde.

((A,A), (8,8), (A,A)), ((8,8), (8,8), (A,A)), ((A,8), (8,8), (A,A))

Pentru Bob avem lumile posibile ((A,A), X, Z) unde Z este cunoscut.

((A,A), (8,8), (A,A)) , Z = (A,A) caz care nu este valabil

((A,A), (A,8), (A,8)), ((A,A), (8,8), (A,8)), Z= (A,8)

((A,A), (A,A), (8,8)), ((A,A), (A,8), (8,8)), ((A,A), (8,8), (8,8)), Z=(8,8).

Pentru Mary lumile posibile sunt de forma: ((A,A), (8,8), X) unde X={(A,8), (A,A), (8,8)}.

Vom construi structura Kripke din structura anterioară păstrând doar nodurile scrise mai sus.

Deci K1 are componenta 2, (8,8) iar a treia X{(A,A), (A,8), (8,8)}

K2 are componenta 1, (A,A) iar a treia X{(A,A), (A,8), (8,8)}

K3 are componenta 1 (A,A), componenta 2 (8,8), iar a treia X{(A,A), (A,8), (8,8)}.

5.2. Problema copillor murdari

Se dă problema copiilor murdari. Să presupunem ca toți copiii sunt orbi. Cum arată reprezentarea unei structuri Kripke descriind situația dinainte ca tatăl să vorbească? Dar după ce tatăl vorbește?

Răspuns:

Să considerăm cazul în care n=3. Relațiile Ki rămân așa cum au fost definite în cadrul acestei probleme. Se schimbă însă lumile posibile pentru fiecare dintre cei trei copii în parte.

Fiecare copil (toți fiind orbi și luând în considerare momentul dinainte ca tatăl să vorbească) se consideră curat. Reamintim ca o lume posibilă se transcrie cu ajutorul unui vector (în cazul nostru cu trei componente) de forma (x1, x2, x3) unde:

Să considerăm copilul numărul 1. Lumile posibile pentru acesta sunt:

(0,1,1), (0,1,0), (0,0,1), (0,0,0)

Pentru copilul numărul 2 lumile posibile sunt:

(1,0,1), (1,0,0), (0,0,1), (0,0,0)

Pentru copilul număru1 3 lumile posibile sunt:

Se observă că pentru fiecare copil i în parte lumile posibile se determină menținând pe poziția xi pe 0 și făcând toate combinațiile posibile pe celelalte poziții.

Starea (0,0,0) cea în care toți copiii sunt curați este o lume posibilă pentru fiecare agent (copil) în parte, deoarece ne aflăm în situația dinainte ca tatăl să vorbească.

Reamintim că pi = “fiecare copil i are fruntea murdară”, iar p=”cel puțin unul dintre copii este murdar” unde p devine cunoștința, comuna după ce tatăl vorbește.

Structura Kripke în situația următoare:

– n=3

– toti copiii sunt orbi

– tatăl nu a afirmat încă p

va fi următoarea:

K1={ ((0,1,1),(0,0,1)), ((0,1,1),(0,1,0)), ((0,1,1),(0,0,0)), ((0,1,0),(0,0,1)), ((0,1,0),(0,0,0)), ((0,0,1),(0,0,0))}.

K2={ ((1,0,1),(1,0,0)), ((1,0,1),(0,0,1)), ((1,0,1),(0,0,0)), ((1,0,0),(0,0,1)), ((1,0,0),(0,0,0)), ((0,0,1),(0,0,0))}.

K3={ ((1,1,0),(1,0,0)), ((1,1,0),(0,1,0)), ((1,1,0),(0,0,0)), ((1,0,0),(0,1,0)), ((1,0,0),(0,0,0)), ((0,1,0),(0,0,0))}.

Exemplu:

În acest exemplu formalizăm jocul așilor și optarilor.

Se consideră situația în care există trei jucători: Alice, Bob, Mary. În acest caz Mary este prima. Alice, care este a doua, are doi optari. Bob, al treilea, are un as și un optar. Nici unul dintre ei nu poate răspunde ce cărți deține la primul tur de întrebări. Să se construiască structura Kipke în acest caz.

Răspuns:

Avem următoarea descriere a problemei:

Mary – prima; Alice – a doua; Bob – al treilea

8 8

Alice Bob

8 A

Răspunsul la primul tur de întrebări este “No”.

Mary (care este prima) vede (8,8) și (8,A) și atunci psibilitățile ei sunt: (8,A), (A,A). Deci la prima întrebare cu “No”.

Alice (care este a doua) vede, în mod sigur, (8,A) și ce are Mary. Prin urmare sunt următoarele posibilități:

Evident, se observă că indiferent de ce cărți are Mary, Alice nu poate afirma ce cărți deține.

Bob (care este al treilea) vede, în mod sigur (la Alice) și ce are Mary, deci avem următoarele posibilități:

Evident că pentru Bob se înlătură cazul în care Mary ar avea (8,8), căci ținând cont de faptul că Alice are (8,8), în mod sigur Bob ar avea (A,A) și ar răspunde la primul tur de întrebari cu “Yes” , ceea ce contrazice ipoteza problemei.

Deci vom avea următorii operatori:

K1 = {((8,A),(8,8),(8,A)), ((A,A),(8,8),(8,A))}

K2 = {((8,A),(8,A),(8,A)), ((8,A),(8,8),(8,A)), ((8,A),(A,A),(8,A)), ((A,A), (8,A),(8,A)), ((A,A),(8,8),(8,A))}

K3 = {((8,A),(8,8),(8,A)), ((8,A),(8,8),(A,A)), ((A,A),(8,8),(8,A)), ((A,A), (8,8),(A,A)), ((A,A),(8,8), ((A,A),(8,8),(8,8))}

Atunci vom avea următoarea structură Kripke:

CAPITOLUL VI

PREZENTARE APLICAȚIE

Aplicația descrisă în acest capitol realizează implementarea unei structuri Kripke prin desenarea interactivă a grafului atașat.Aplicația este formată din 11 fisiere și este realizată în limbajul Java. Fisierele folosite la realizarea aplicației sunt :Draw.java, Back.java, Polonez.java, Arbore.java

Analiza.java, Arc.java, Punct.java, Agent.java, Propozitie.java, Stare.java, Ajutor.java.

Programul principal al aplicației este Draw.java și contine crearea ferestrei aplicației precum și funcțiile necesare realizării desenului și a editării formulei. Fișierele Stare.java, Propozitie.java, Agent.java implementează noțiunile de stare, propoziție, agent utilizate în structurile Kripke, iar fișierele Punct.java și Arc.java implementează noțiunile de punct și arc utilizate în desenarea grafului atașat unei structuri Kripke. Fișierele Analiza.java, Polonez.java, Arbore.java, Back.java realizează analiza formulei introduse și calculează valoarea acesteia.

În paragraful următor se află listingul acestor fișiere.

Draw.java

import java.awt.event.*;

import java.awt.*;

import java.util.*;

import java.io.*;

class Meniu{

Draw f;

public Meniu(Draw parent){f=parent;setMeniu();}

void setMeniu(){

MenuBar meniu= new MenuBar();

Menu m1= new Menu("Fisier");

Menu m2= new Menu("Ajutor");

MenuItem m11=new MenuItem("Desen Nou");

MenuItem m12=new MenuItem("Iesire");

MenuItem m21=new MenuItem("Utilizare Program");

MenuItem m22=new MenuItem("Despre program");

m1.add(m11);m1.addSeparator();m1.add(m12);

m2.add(m21);m2.add(m22);

meniu.add(m1);meniu.add(m2);

ActionListener MenuH=new ActionListener(){

public void actionPerformed(ActionEvent event){

Despre d=new Despre(f);}

};

m22.addActionListener(MenuH);

ActionListener MenuH1=new ActionListener(){

public void actionPerformed(ActionEvent event){

Ajutor d=new Ajutor();}

};

m21.addActionListener(MenuH1);

ActionListener MenuD=new ActionListener(){

public void actionPerformed(ActionEvent event){

Despre d=new Despre(f);}

};

ActionListener DesenNou=new ActionListener(){

public void actionPerformed(ActionEvent event){

f.desen.back.removeAll() ;

f.desen .repaint();

f.buton.clear(); }

};

m11.addActionListener(DesenNou);

ActionListener Exit=new ActionListener(){

public void actionPerformed(ActionEvent event){

System.exit(0); }

};

m12.addActionListener(Exit);

f.setMenuBar(meniu);

}

}

public class Draw extends Frame{

DrawArea desen;

Butoane buton;

public void maxim(){

Dimension ecran=Toolkit.getDefaultToolkit().getScreenSize();

setSize(ecran);

setLocation(0,0);

}

public Draw(){

super("Draw");

this.maxim();

setLayout(new BorderLayout());

new Meniu(this);

desen = new DrawArea(this);

buton = new Butoane(desen,this);

add("Center", desen);

add("West",buton);

addWindowListener(new Inchide());

setVisible(true);

}

public static void main(String args[]){

Draw draw = new Draw();

}

}

class Despre extends Dialog{

Frame parent;

public Despre(Frame parent){

super(parent);

this.addWindowListener(new InchideDialog());

this.parent=parent;

this.setModal(true);

this.setSize(210,100);this.setResizable(false);

this.setTitle("Despre program");

this.setVisible(true);

}

public void paint(Graphics g){

g.drawString("BARBU BOGDAN-VIOREL",10,70);

g.drawString(" iunie 2002",50,90);

}

}

class Mesaj extends Dialog{

Frame parent;

String mesaj,titlu;

public Mesaj(Frame parent,String titlu,String mesaj){

super(parent);

this.addWindowListener(new InchideDialog());

this.parent=parent;

this.mesaj=mesaj;

this.setModal(true);

this.setSize(250,60);

this.setTitle(titlu);

this.setVisible(true);

}

public void paint(Graphics g) {

g.drawString(this.mesaj,10,40);

}

}

class Inchide extends WindowAdapter{

public void windowClosing(WindowEvent e){

System.exit(0);

}

}

class InchideDialog extends WindowAdapter{

public void windowClosing(WindowEvent e){

e.getWindow().dispose();

}

}

class DrawArea extends Canvas implements MouseListener,

MouseMotionListener{

int PUNCT=0;

int LINIE=1;

Back back=new Back();

Draw parent;

int desen=PUNCT;

int x1=-1,y1=-1;

int x2=-1,y2=-1;

Punct p1,p2;

public DrawArea(Draw parent) {

this.parent=parent;

setBackground(Color.white);

addMouseMotionListener(this);

addMouseListener(this);

}

public void mouseDragged(MouseEvent e){

e.consume();

desen=LINIE;

x2 = e.getX();

y2 = e.getY();

repaint();

}

public void mouseMoved(MouseEvent e){ }

public void mousePressed(MouseEvent e){

e.consume();

desen=PUNCT;

x1 = e.getX();

y1 = e.getY();

int np=back.punct.size();

for(int i=0;i<np;i++){

Punct p=(Punct)back.punct.elementAt(i);

if(p.contine(x1,y1)){

desen=LINIE;

p1=new Punct(p);

break;

}

}

if(desen==PUNCT){

Punct p=new Punct(x1,y1,10);

if(p.editStare(parent)){

back.add(p);

p1=new Punct(p);

}

repaint();

}

}

public void mouseReleased(MouseEvent e) {

if(desen==LINIE){

Agent t=new Agent();

int np=back.punct.size();

int i,j=0;

for(i=0;i<np;i++){

Punct p=(Punct)back.punct.elementAt(i);

if(p.contine(e.getX(),e.getY()))

if(t.editAgent(parent)){

Arc a=new Arc();

a.setCuloare(getForeground());

a.setP1(new Punct(p1));

a.setP2(new Punct(p));

a.setAgent(new Agent(t));

back.add(new Agent(t));

back.add(new Arc(a));

break;

}

}

}

repaint();

}

public void mouseEntered(MouseEvent e){

parent.setCursor(new Cursor(Cursor.CROSSHAIR_CURSOR));

}

public void mouseExited(MouseEvent e){

parent.setCursor(new Cursor(Cursor.DEFAULT_CURSOR));

}

public void mouseClicked(MouseEvent e){}

void desenPunct(Punct p,Graphics g) { p.desen(g);}

public void paint(Graphics g){

g.setColor(getForeground());

int np = back.arc.size();

for (int i=0; i < np; i++){

Arc p = (Arc)back.arc.elementAt(i);

p.desen(g);

}

np=back.punct.size();

for(int i=0;i<np;i++){

desenPunct((Punct)back.punct.elementAt(i),g);

}

g.setColor(getForeground());

if (x2 != -1){

g.drawLine(x1, y1, x2, y2);

}

y2=-1;x2=-1;

}

}

class Butoane extends Panel{

static Draw parent;

static DrawArea target;

Label formulaL=new Label("Formulå:");

TextField formulaT= new TextField();

Label stareL= new Label("Stare:");

TextField stareT=new TextField();

Label rezultatL=new Label("Rezultat:");

TextField rezultatT=new TextField();

Button ok=new Button("Calculeaza"),

cancel=new Button("Anuleaza");

Button culoare=new Button();

public void clear(){

stareT.setText("");

rezultatT.setText("");

formulaT.setText("");

}

public Butoane(DrawArea target,Draw parent){

this.target = target;

this.parent=parent;

setLayout(null);

setBackground(Color.lightGray);

stareL.setBounds(10,10,50,20);

stareT.setBounds(60,10,80,20);

formulaL.setBounds(10,40,50,20);

formulaT.setBounds(60,40,80,20);

rezultatL.setBounds(10,70,50,20);

rezultatT.setBounds(60,70,80,20);

rezultatT.setEditable(false);

ok.setBounds(10,100,70,20);

cancel.setBounds(80,100,70,20);

culoare.setBounds(10,140,40,20);

culoare.setBackground(Color.black);

ActionListener cc=new ActionListener(){

public void actionPerformed(ActionEvent e) {

Butoane.target.repaint();

new PaletaCulori(culoare,Butoane.parent,Butoane.target);

}

};

culoare.addActionListener(cc);

ActionListener cancelA=new ActionListener(){

public void actionPerformed(ActionEvent e){

stareT.setText("");

formulaT.setText("");

rezultatT.setText("") ;

}

};

cancel.addActionListener(cancelA);

ActionListener okA=new ActionListener(){

public void actionPerformed(ActionEvent e){

char ss=stareT.getText() .charAt(0);

String form=formulaT.getText() ;

rezultatT.setText(Butoane.target.back.convert(Butoane.target.back .

calculeaza(ss,form)) ) ;

}

};

ok.addActionListener(okA);

add(stareL);add(stareT);

add(formulaL);add(formulaT);

add(rezultatL);add(rezultatT);

add(ok);add(cancel);

add(culoare);

setBounds(0,0,150,500);

}

public void paint(Graphics g) {}

}

class PaletaCulori extends Dialog implements ActionListener{

Button culori[]=new Button[13];

Color color[]={Color.black,Color.red,Color.blue,Color.green,

Color.yellow,Color.gray,Color.lightGray,

Color.magenta,Color.orange,Color.pink,Color.white,

Color.cyan,Color.darkGray};

Frame parent;

Color culoare;

Button apel;

DrawArea target;

public void centru(){

Dimension ecran=Toolkit.getDefaultToolkit().getScreenSize();

setLocation((ecran.width-100)/2,(ecran.height-100)/2);

}

public void distruge(){

apel.setBackground(culoare);

target.setForeground(culoare);

this.dispose();}

public PaletaCulori(Button apelant,Frame parent,DrawArea target){

super(parent,true);

this.apel=apelant;

this.target=target;

this.addWindowListener(new InchideDialog());

this.setLayout(new GridLayout(4,4));

this.setSize(100,100);

centru();

for(int i=0;i<13;i++){

culori[i]=new Button();

culori[i].setBackground(color[i]);

culori[i].addActionListener(this);

this.add(culori[i]);

}

this.setVisible(true);

}

public void actionPerformed(ActionEvent e){

this.culoare=((Button)e.getSource()).getBackground();

distruge();

};

}

Stare.java

import java.util.Vector;

public class Stare{

char nume;

Vector propozitii;

public Stare(){ propozitii=new Vector(); }

public Stare(char nume){

this.nume=nume;

propozitii=new Vector();}

public Stare(Stare s){

this.nume=s.getStare();

propozitii=new Vector();

for(int i=0;i<s.getCountPropozitii();i++)

propozitii.addElement(new Propozitie(s.getPropozitieAt(i)));

}

public void setStare(char nume){this.nume=nume; }

public void setStare(Stare s){

this.propozitii.removeAllElements();

this.nume=s.getStare();

propozitii=new Vector();

for(int i=0;i<s.getCountPropozitii();i++)

propozitii.addElement(new Propozitie(s.getPropozitieAt(i)));

}

public boolean contine(char p){

int n=propozitii.size();

Propozitie x;

for(int i=0;i<n;i++){

x=(Propozitie)propozitii.elementAt(i);

if(x.get()==p) return true;

}

return false;

}

public boolean contine(Propozitie p) {return propozitii.contains(p);}

public boolean valoare(Propozitie p) {return propozitii.contains(p);}

public void removeAll(){propozitii.removeAllElements(); }

public void addPropozitie(Propozitie p) {

propozitii.addElement(new Propozitie(p));

}

public Propozitie getPropozitieAt(int index) {

return (Propozitie)propozitii.elementAt(index);

}

public Propozitie[] getAll(){

Propozitie aux[]=new Propozitie[getCountPropozitii()];

for(int i=0;i<aux.length;i++)

aux[i]=new Propozitie(getPropozitieAt(i));

return aux; }

public int getCountPropozitii(){return propozitii.size();}

public char getStare(){return this.nume;}

public boolean agent(char c){

switch (c){

case '0' : return true;

case '1' : return true;

case '2' : return true;

case '3' : return true;

case '4' : return true;

case '5' : return true;

case '6' : return true;

case '7' : return true;

case '8' : return true;

case '9' : return true;

}

return false;

}

public String toString(){

String aux=new String("(");

aux=aux+getStare()+"-[";

for(int i=0;i<getCountPropozitii();i++)

aux=aux+getPropozitieAt(i).toString()+",";

aux=aux+"]-)";

return aux;

}

}

Punct.java

import java.awt.*;

import java.awt.event.*;

import java.util.*;

public class Punct{

int x,y;

int raza;

Stare s;

public Punct() {

x=y=raza=0;

s=new Stare();

}

public Punct(int x, int y){

this.x=x;

this.y=y;

raza=10;

s=new Stare();

}

public Punct(int x, int y, int raza){

this.x=x;

this.y=y;

this.raza=raza;

this.s=new Stare();

}

public Punct(Punct p){

this.x=p.getX();

this.y=p.getY();

this.raza=p.getR();

this.s=new Stare(p.getStare());

}

public void setStare(Stare stare){

this.s=new Stare(stare);

}

public Stare getStare(){

return new Stare(this.s);

}

public void setPropozitii(Propozitie prop[]){

s.removeAll();

for(int i=0;i<prop.length;i++)

s.addPropozitie(new Propozitie(prop[i]));

}

public boolean contine(int x1, int y1){

if((x1-x)*(x1-x)+(y1-y)*(y1-y)-raza*raza<=0) return true;

else return false;

}

public int getX(){return this.x;}

public int getY(){return this.y;}

public int getR(){return this.raza;}

public void desen(Graphics g){

g.fillOval(getX(),getY(),getR(),getR());

g.drawString(getStare().toString(),getX()+getR(),getY());

}

public boolean editStare(Frame parent){

EditStare es=new EditStare(parent);

if(es.OKapasat()){

this.setStare(es.getStare());

return true;

}

return false;

}

}

class EditStare extends Dialog implements ActionListener{

Label stareL, propozitiiL;

TextField stare,propozitii;

Propozitie prop[];

Stare s;

Button ok, cancel;

boolean apasatOK;

public boolean OKapasat(){return apasatOK;}

public void centru(){

Dimension ecran=Toolkit.getDefaultToolkit().getScreenSize();

setLocation((ecran.width-100)/2,(ecran.height-100)/2);

}

public EditStare(Frame parent){

super(parent,"Editare stare pentru punct",true);

stareL=new Label("Starea:");

stare=new TextField();

propozitiiL=new Label("Propozitii:");

propozitii=new TextField();

ok=new Button("OK");

cancel=new Button("Cancel");

setSize(150,120);

centru();

stareL.setBounds(30,30,50,20); stare.setBounds(80,30,50,20);

propozitiiL.setBounds(30,60,50,20);

propozitii.setBounds(80,60,50,20);

ok.setBounds(20,90,50,20);cancel.setBounds(70,90,70,20);

ok.addActionListener(this); cancel.addActionListener(this);

this.addWindowListener(new InchideDialog());

setLayout(null);

add(stareL);add(stare);add(propozitiiL);add(propozitii);

add(ok);add(cancel);

setBounds(0,0,150,120);

setVisible(true);

}

void setStare(){this.s=new Stare(stare.getText().charAt(0));}

Stare getStare(){return new Stare(this.s);}

void setPropozitii(){

StringTokenizer pt=new StringTokenizer(propozitii.getText(), ",");

String a;

try{

int n= pt.countTokens();

for(int i=0;i<n;i++){

a=pt.nextToken();

this.s.addPropozitie(new Propozitie(a.charAt(0)));

}

}catch(Exception err){apasatOK=false;}

}

public void actionPerformed(ActionEvent e){

if(((Button)e.getSource()).getLabel()=="OK"){

apasatOK=true;

setStare();

setPropozitii(); }

else apasatOK=false;

this.dispose();

}

}

Propozitie.java

public class Propozitie{

char nume;

public Propozitie(){}

public Propozitie(char nume ){this.nume=nume;}

public Propozitie(Propozitie p ){this.nume=p.get();}

public void set(char nume ){this.nume=nume;}

public char get(){return this.nume;}

public boolean valoare(Stare s){return s.valoare(this);}

}

Polonez.java

public class Polonez{

String expresie,formaPoloneza;

public Polonez(){

expresie=null;

formaPoloneza=null;

}

public Polonez(String expresie) {

this.expresie=new String(expresie);

this.formaPoloneza=new String(poloneza(this.expresie));

}

public String getPoloneza() {return new String(formaPoloneza);}

static int P(char operator){

switch (operator) {

case '$' : return 0;

case '(' : return 0;

case '+' : return 3;

case '|' : return 3;

case '*': return 4;

case '&': return 4;

case '~' : return 5;

case '-' : return 5;

case '!' : return 5;

case '=' : return 3;

case '>' : return 3;

case '0': return 5;

case '1': return 5;

case '2': return 5;

case '3': return 5;

case '4': return 5;

case '5': return 5;

case '6': return 5;

case '7': return 5;

case '8': return 5;

case '9': return 5;

}

return -1;

}

public static boolean operatorBinar(char a){

switch (a) {

case '+' : return true;

case '|' : return true;

case '=' : return true;

case '>' : return true;

case '*' : return true;

case '&' : return true;

}

return false;

}

public static boolean operatorUnar(char a){

switch (a) {

case '~' : return true;

case '-' : return true;

case '!' : return true;

case '0': return true;

case '1': return true;

case '2': return true;

case '3': return true;

case '4': return true;

case '5': return true;

case '6': return true;

case '7': return true;

case '8': return true;

case '9': return true;

}

return false;

}

public static boolean operator(char a){

return (operatorUnar(a))||(operatorBinar(a));

}

public static boolean operand(char a){

return ((!operator(a))&&(a!='(')&&(a!='$')&&(a!='@')&&(a!=')'))

}

public char charAt(StringBuffer b, int i){

if((b==null)||(b.length()==0)) return '@';

else return b.charAt(i);

}

public boolean finalBuffer(StringBuffer b){

return ((b==null)||((b.length()==1)&&

((b.charAt(0)=='$')||(b.charAt(0)=='@'))));

}

public String poloneza(String formula) {

StringBuffer b1,b2,b3;

char a,b,c;

b1=new StringBuffer(formula+"@");

b2=new StringBuffer("$");

b3=new StringBuffer("@");

boolean ok=false;

while(!ok){

if(finalBuffer(b1)&&finalBuffer(b2)){ok=true;}

else{

a=charAt(b1,0);

b=charAt(b2,0);

c=charAt(b3,0);

if((!finalBuffer(b1))&&(operand(a))){

b3.append(a);

b1=elimina(b1);

}else

if((a=='(')&&((operator(a)&&(P(a)>=P(b)))){

b2.insert(0,a);

b1=elimina(b1);

}else

if(operator(a)&&(P(a)<P(b))){

b3.append(b);

b2=elimina(b2);

}

else

if((b=='(')&&(a==')')){

b1=elimina(b1);

b2=elimina(b2);

}else

if((b!='(')&&(a==')')) {

b3.append(b);

b2=elimina(b2);

}else

if(finalBuffer(b1)&&(!finalBuffer(b2))){

b3.append(b);

b2=elimina(b2);

}

}

}

return (elimina(b3)).toString();

}

public StringBuffer elimina(StringBuffer b){

String b1=new String();

for(int i=1;i<b.length();i++) b1=b1+charAt(b,i);

return new StringBuffer(b1);

}

}

Agent.java

import java.util.Vector;

import java.awt.*;

import java.awt.event.*;

public class Agent{

Vector s1,s2;

char nume;

public Agent(){

s1=new Vector();

s2=new Vector();

}

public Agent(char nume){

s1=new Vector();

s2=new Vector();

}

public Agent(Agent a){

this.nume=a.getNume();

s1=new Vector();

s2=new Vector();

Stare aux[]=a.getAllS1();

for(int i=0;i<aux.length;i++)

s1.addElement(new Stare(aux[i]));

aux=a.getAllS2();

for(int i=0;i<aux.length;i++)

s2.addElement(new Stare(aux[i]));

}

public void add(Stare s){

if (!contine(s,s)){

s1.addElement(new Stare(s));

s2.addElement(new Stare(s));

}

}

public void add(Stare s,Stare k) {

if (!contine(s,k)){

s1.addElement(new Stare(s));

s2.addElement(new Stare(k));

}

if (!contine(k,s)){

s1.addElement(new Stare(k));

s2.addElement(new Stare(s));

}

}

public boolean contine(Stare s, Stare k){

if(s1.indexOf(s)==s2.indexOf(k)) return true;

return false;

}

public int getCountS1(Stare s){

int k=0;

for(int i=s1.indexOf(s);i<s1.lastIndexOf(s);i++)

if(s.equals((Stare)s1.elementAt(i))) k++;

return k;

}

public int getCountS2(Stare s){

int k=0;

for(int i=s2.indexOf(s);i<s2.lastIndexOf(s);i++)

if(s.equals((Stare)s2.elementAt(i))) k++;

return k;

}

public Stare[] getStareS1(Stare s){

Stare aux[]=new Stare[getCountS1(s)];

for(int i=s1.indexOf(s);i<s1.lastIndexOf(s);i++)

if(s.equals((Stare)s1.elementAt(i))) {

aux[i]=new Stare((Stare)s2.elementAt(i));

}

return aux;

}

public Stare[] getStareS2(Stare s){

Stare aux[]=new Stare[getCountS2(s)];

for(int i=s2.indexOf(s);i<s2.lastIndexOf(s);i++)

if(s.equals((Stare)s2.elementAt(i))) {

aux[i]=new Stare((Stare)s1.elementAt(i));

}

return aux;

}

public Stare[] getAllS1(){

Stare aux[]=new Stare[s1.size()];

for(int i=0;i<s1.size();i++)

aux[i]=new Stare((Stare)s1.elementAt(i));

return aux;

}

public Stare[] getAllS2(){

Stare aux[]=new Stare[s2.size()];

for(int i=0;i<s2.size();i++)

aux[i]=new Stare((Stare)s2.elementAt(i));

return aux;

}

public char getNume(){return this.nume;}

public void append(Agent a){

Stare []as1=a.getAllS1();

Stare []as2=a.getAllS2();

for(int i=0;i<as1.length;i++)

this.add(as1[i],as2[1]);

}

public String toString(){

char c[]=new char[1];

c[0]=this.nume;

return new String(c);

}

public boolean editAgent(Frame parent) {

EditAgent es=new EditAgent(parent);

if(es.OKapasat()){

this.nume=es.getNume();

s1=new Vector();

s2=new Vector();

return true;

}

return false;

}

}

class EditAgent extends Dialog implements ActionListener{

Label stareL;

TextField nume;

Button ok, cancel;

boolean apasatOK;

public boolean OKapasat(){return apasatOK;}

public char getNume(){return nume.getText().charAt(0);}

public void centru() {

Dimension ecran=Toolkit.getDefaultToolkit().getScreenSize();

setLocation((ecran.width-100)/2,(ecran.height-100)/2);

}

public EditAgent(Frame parent){

super(parent,true);

stareL=new Label("Numar agent:");

nume=new TextField();

ok=new Button("OK");

cancel=new Button("Cancel");

setSize(300,300);

centru();

stareL.setBounds(30,30,80,20); nume.setBounds(113,30,50,20);

ok.setBounds(20,90,50,20);cancel.setBounds(70,90,70,20);

ok.addActionListener(this);cancel.addActionListener(this);

this.addWindowListener(new InchideDialog());

setLayout(null);

add(stareL);add(nume);add(ok);add(cancel);

setBounds(0,0,150,120);

setVisible(true);

}

public void actionPerformed(ActionEvent e) {

if(((Button)e.getSource()).getLabel()=="OK"){apasatOK=true;}

else apasatOK=false;

this.dispose();

}

}

Analiza.java

public class Analiza {

static String formula,polonez;

static Polonez p;

static Arbore arbore;

public Analiza() {}

public String getFormula(){return new String(formula);}

public String getPoloneza(){return new String(polonez);}

public Analiza(String formula){

this.p=new Polonez(formula);

this.formula=new String(formula);

this.polonez =new String(p.getPoloneza());

this.arbore =new Arbore(this.polonez);

}

public static String eliminaSpatii(String expresie){

StringBuffer s1=new StringBuffer(expresie);

int n=expresie.length();

int k=0;

for(int i=0;i<n;i++)

if(expresie.charAt(i)==' '){

s1.deleteCharAt(i-k);k++;

}

return new String(s1.toString());

}

public static boolean paranteze(String expresie){

int n=expresie.length() ;

int k=0;

for(int i=0;i<n;i++){

if(expresie.charAt(i)=='(') k++;

if(expresie.charAt(i)==')') k–;

if(k<0) return false;

}

return (k==0);

}

public static boolean erori(String expresie){

String a=eliminaSpatii(expresie);

int n=a.length();

if(p.operatorBinar(a.charAt(0))) return true;

if(p.operator(a.charAt(n-1))) return true;

for(int i=0;i<n-1;i++){

if((a.charAt(i)=='(')&&(p.operatorBinar(a.charAt(i+1))))

return true;

if((a.charAt(i)=='(')&&(a.charAt(i+1)==')')) return true;

if((p.operator(a.charAt(i)))&&(a.charAt(i+1)==')')) return true;

if((a.charAt(i)==')')&&(a.charAt(i+1)=='(')) return true;

if((a.charAt(i)==')')&&(p.operand(a.charAt(i+1)))) return true;

if((p.operand(a.charAt(i)))&&(a.charAt(i+1)=='(')) return true;

}

return false;

}

public static boolean corect(String expresie){

return (paranteze(expresie)&&(!erori(expresie))); }

public Arbore getArbore(){return new Arbore(this.arbore);}

}

Arbore.java

public class Arbore{

private String formula,polonez;

private Polonez p=new Polonez();

char radacina;

Arbore stanga,dreapta;

public Arbore(){stanga=null;dreapta=null;}

public Arbore(char inf){

radacina=inf;

stanga=null;dreapta=null;}

public String element(String expresie,int pozitie){

if(p.operand(expresie.charAt(pozitie))){

char c[]=new char[1];

c[0]=expresie.charAt(pozitie) ;

return new String(c);

}

if(p.operatorUnar(expresie.charAt(pozitie))){

return new String(expresie.charAt(pozitie)+

element(expresie,pozitie-1));

}

if(p.operatorBinar(expresie.charAt(pozitie))){

return new String(expresie.charAt(pozitie)+

element(expresie,pozitie-1)+

element(expresie,primPozitie(expresie,pozitie-1)-1));

}

return null;

}

public int primPozitie(String expresie, int pozitie){

if(p.operand(expresie.charAt(pozitie))) return pozitie;

if(p.operatorUnar(expresie.charAt(pozitie)))

return primPozitie(expresie,pozitie-1);

if(p.operatorBinar(expresie.charAt(pozitie)))

return primPozitie(expresie,primPozitie(expresie,pozitie-1)-1);

return -1;

}

public Arbore(Arbore arb){

if(arb!=null){

this.radacina=arb.radacina;

if(arb.stanga !=null) this.stanga =new Arbore(arb.stanga);

else this.stanga=null;

if(arb.dreapta!=null) this.dreapta =new Arbore(arb.dreapta);

else this.dreapta=null;

}

}

public Arbore(String expresie){

int pozitie=expresie.length()-1;

radacina=expresie.charAt(pozitie);

if(p.operatorUnar(radacina)){

int poz=primPozitie(expresie,pozitie-1);

stanga=new Arbore(expresie.substring(poz,pozitie));

dreapta=null;

} else

if(p.operatorBinar(radacina)) {

int p1=primPozitie(expresie,pozitie-1);

int p2=primPozitie(expresie,p1-1);

stanga=new Arbore(expresie.substring(p1,pozitie) );

dreapta=new Arbore(expresie.substring(p2,p1) );

}else{

dreapta=null;

stanga=null;

}

}

}

Arc.java

import java.awt.*;

public class Arc {

Punct p1,p2;

Agent a;

Color culoare;

public Arc(){p1=null;p2=null;a=null;}

public Arc(Arc arc){

p1=new Punct(arc.p1);

p2=new Punct(arc.p2);

a=new Agent(arc.a);

a.add(p1.getStare());a.add(p2.getStare());

a.add(p1.getStare(),p2.getStare());

culoare=arc.culoare;

}

public void setP1(Punct p){p1=new Punct(p);}

public void setP2(Punct p){p2=new Punct(p);}

public void setAgent(Agent agent) {

a=new Agent(agent);

a.add(p1.getStare());a.add(p2.getStare());

a.add(p1.getStare(),p2.getStare());

}

public void setCuloare(Color c){culoare=c;}

public void desen(Graphics g){

g.setColor(culoare);

g.drawLine(p1.getX(),p1.getY(),p2.getX(),p2.getY());

g.drawString(a.toString(),(p1.getX()+p2.getX())/2,(p1.getY()+

p2.getY())/2);

}

}

Back.java

import java.util.Vector;

public class Back {

Vector agent=new Vector(),

stare=new Vector(),

propozitie=new Vector(),

punct=new Vector(),

arc=new Vector();

Analiza analiza=new Analiza();

Arbore arbore;

String formula,poloneza;

Polonez polonez=new Polonez();

Stare s=new Stare();

public Back() {}

public void removeAll(){

agent.removeAllElements() ;

stare.removeAllElements() ;

propozitie.removeAllElements() ;

punct.removeAllElements() ;

arc.removeAllElements() ;

formula=null;poloneza=null;arbore=null;analiza=null;s=null;

}

public boolean contine(Agent a){

int n=agent.size();

Agent x;

for(int i=0;i<n;i++){

x=(Agent)agent.elementAt(i);

if(x.getNume()==a.getNume()) return true;

}

return false;

}

public boolean contine(Stare s){

int n=stare.size();

Stare x;

for(int i=0;i<n;i++){

x=(Stare)stare.elementAt(i);

if(x.getStare() ==s.getStare()) return true;

}

return false;

}

public boolean contine(Punct p){

int n=punct.size();

Punct x;

for(int i=0;i<n;i++){

x=(Punct)punct.elementAt(i);

if((x.getX()==p.getX())&&(x.getY()==p.getY())) return true;

}

return false;

}

public boolean contine(Arc a){return arc.contains(a);}

public boolean contine(Propozitie p){

int n=propozitie.size();

Propozitie x;

for(int i=0;i<n;i++){

x=(Propozitie)propozitie.elementAt(i);

if(x.get()==p.get()) return true;}

return false;

}

public void add(Agent a){

if(!contine(a)) agent.addElement(new Agent(a));

else {

int n=getAgentIndex(a);

Agent x=(Agent)agent.remove(n);

x.append(a);

agent.addElement(new Agent(x));

}

}

public int getAgentIndex(Agent a){

int n=agent.size();

Agent x;

for(int i=0;i<n;i++){

x=(Agent)agent.elementAt(i);

if(x.getNume()==a.getNume()) return i;

}

return -1;

}

public void add(Stare s){

if(!contine(s)){

stare.addElement(new Stare(s));

Propozitie p[]=s.getAll();

for(int i=0;i<p.length;i++) add(new Propozitie(p[i]));

}

}

public void add(Punct p){

if(!contine(p)){

punct.addElement(new Punct(p));

add(p.getStare());

}

}

public void add(Arc a){

if(!contine(a)) arc.addElement(new Arc(a));

}

public void add(Propozitie p){

if(!contine(p)) propozitie.addElement(new Propozitie(p));

}

public Stare getStare(char s){

int n=stare.size();

Stare x;

for(int i=0;i<n;i++){

x=(Stare)stare.elementAt(i);

if(x.getStare()==s) return x;

}

return null;

}

public Agent getAgent(char nume){

int n=agent.size();

Agent x;

for(int i=0;i<n;i++){

x=(Agent)agent.elementAt(i);

if(x.getNume()==nume) return x;

}

return null;

}

public boolean analiza(Stare s, Arbore a){

if(Polonez.operand(a.radacina))

if(s.contine(a.radacina)) return true;

else return false;

else

if(Polonez.operator(a.radacina)){

switch(a.radacina) {

case '+' : return analiza(s,a.stanga)||analiza(s,a.dreapta);

case '|' : return analiza(s,a.stanga)||analiza(s,a.dreapta);

case '*' : return analiza(s,a.stanga)&&analiza(s,a.dreapta);

case '&' : return analiza(s,a.stanga)&&analiza(s,a.dreapta);

case '~' : return !analiza(s,a.stanga);

case '-' : return !analiza(s,a.stanga);

case '!' : return !analiza(s,a.stanga);

case '>' : return !analiza(s,a.dreapta)||analiza(s,a.stanga);

case '=' : return (!analiza(s,a.stanga)||analiza(s,a.dreapta))&&

(!analiza(s,a.dreapta)||analiza(s,a.stanga));

default : {

Agent x=getAgent(a.radacina);

Stare ss[] =x.getStareS2(s);

for(int i=0;i<ss.length ;i++){

if(!analiza(ss[i],a.stanga)) return false;}

return true;

}

}

}

return false;

}

public boolean calculeaza(char s,String formula){

Analiza a=new Analiza(formula);

if(a.corect(formula)){

this.formula=a.getFormula() ;

this.poloneza=a.getPoloneza();

this.arbore=a.getArbore();

this.s=getStare(s);

return analiza(this.s,arbore);

}

return false;

}

public String convert(boolean b){

if(b) return new String("Adevarat");

return new String ("Fals");

}

public void setFormula(String formula){

this.formula =new String(formula);

analiza=new Analiza(this.formula);

arbore=new Arbore(analiza.getArbore());

poloneza=new String(analiza.polonez);

}

}

Ajutor.java

import java.awt.*;

import java.io.*;

import java.awt.event.*;

class FC extends WindowAdapter{

public void windowClosing(WindowEvent e){

e.getWindow().dispose();}

}

public class Ajutor{

Frame editor=new Frame("Ajutor Kripke");

Panel p=new Panel();

TextArea text;

List cuprins=new List();

String[] fisier={"1.krk","2.krk","3.krk","4.krk"};

public void openFisier(String nume){

try{

RandomAccessFile d=new RandomAccessFile(

new File("data\\"+nume),"r");

String s=new String(),s1=new String();

while((s=d.readLine())!=null) s1+="\n"+s;

text.setText(s1);

}catch(IOException e){text.setText(e.getMessage());

}

}

public void addComponents(){

ItemListener cuprinsClick=new ItemListener(){

public void itemStateChanged(ItemEvent e){

openFisier(fisier[cuprins.getSelectedIndex()]);

}

};

cuprins.addItemListener(cuprinsClick);

text=new TextArea();

text.setEditable(false);

text.setBackground(Color.white);

cuprins.add("Program Structuri Kripke");

cuprins.add("I – Utilizare Program");

cuprins.add(" 1. Desenare ");

cuprins.add(" 2. Formula");

editor.setLayout(new BorderLayout());

editor.add(cuprins, BorderLayout.WEST) ;

editor.add(text,BorderLayout.CENTER);

}

public Ajutor(){

addComponents();

editor.setSize(550,400);

editor.setVisible(true);

editor.addWindowListener(new FC());

}

}

Bibliografie

Țăndăreanu Nicolae ,,Baze de cunoștințe’’ ,

Curs Anul III Facultatea de Matematică-Informatică ,

Craiova, 2001.

Petre Băzăvan ,,Programare distribuită în Internet.Limbajul

Java’’

Curs Anul IV Facultatea de Matematică-Informatică ,

Craiova, 2001.

Watson Mark ,,Aplicații Java inteligente pentru Internet și

Intranet-uri’’.