Dynamisk epistemisk logik

Dynamisk epistemisk logik (DEL) är ett logiskt ramverk som handlar om kunskaps- och informationsförändring. Vanligtvis fokuserar DEL på situationer som involverar flera agenter och studerar hur deras kunskap förändras när händelser inträffar. Dessa händelser kan ändra faktiska egenskaper hos den faktiska världen (de kallas ontiska händelser ): till exempel är ett rött kort målat i blått. De kan också åstadkomma förändringar av kunskap utan att förändra världens faktiska egenskaper (de kallas epistemiska händelser ): till exempel avslöjas ett kort offentligt (eller privat) som rött. Ursprungligen fokuserade DEL på epistemiska händelser. Vi presenterar bara i det här inlägget några av grundidéerna i det ursprungliga DEL-ramverket; mer information om DEL i allmänhet finns i referenserna.

På grund av arten av dess studieobjekt och dess abstrakta tillvägagångssätt är DEL relaterad och har tillämpningar till många forskningsområden, såsom datavetenskap ( artificiell intelligens ), filosofi ( formell epistemologi ), ekonomi ( spelteori ) och kognitionsvetenskap . Inom datavetenskap är DEL till exempel mycket relaterat till multi-agent system , som är system där flera intelligenta agenter interagerar och utbyter information.

Som en kombination av dynamisk logik och epistemisk logik är dynamisk epistemisk logik ett ungt forskningsfält. Det började egentligen 1989 med Plazas logik med offentligt tillkännagivande. Oberoende av varandra föreslog Gerbrandy och Groeneveld ett system som dessutom behandlade privat tillkännagivande och som var inspirerat av Veltmans arbete. Ett annat system föreslogs av van Ditmarsch vars främsta inspiration var Cluedo -spelet. Men det mest inflytelserika och originella systemet var systemet som föreslogs av Baltag, Moss och Solecki. Detta system kan hantera alla typer av situationer som studerats i verken ovan och dess underliggande metodik är konceptuellt grundad. Vi kommer att presentera några av dess grundläggande idéer i det här inlägget.

Formellt utökar DEL vanlig epistemisk logik genom att inkludera händelsemodeller för att beskriva åtgärder, och en produktuppdateringsoperatör som definierar hur epistemiska modeller uppdateras som en konsekvens av att utföra åtgärder som beskrivs genom händelsemodeller. Epistemisk logik kommer först att återkallas. Sedan kommer åtgärder och händelser in i bilden och vi kommer att introducera DEL-ramverket.

Epistemisk logik

Epistemisk logik är en modal logik som handlar om begreppen kunskap och tro. Som en logik handlar det om att förstå processen för resonemang om kunskap och tro: vilka principer som relaterar till begreppen kunskap och tro är intuitivt rimliga? Liksom epistemologi härrör det från det grekiska ordet $\epsilon \pi \iota \sigma \tau \eta \mu \eta$ eller 'episteme' som betyder kunskap. Epistemologi är ändå mer angelägen om att analysera själva naturen och omfattningen av kunskap och ta upp frågor som "Vad är definitionen av kunskap?" eller "Hur förvärvas kunskap?". Faktum är att epistemisk logik växte fram ur epistemologin under medeltiden tack vare ansträngningarna från Burley och Ockham. Det formella arbete, baserat på modal logik, som invigde samtida forskning om epistemisk logik går tillbaka endast till 1962 och beror på Hintikka . Det väckte sedan på 1960-talet diskussioner om principerna för kunskap och tro och många axiom för dessa föreställningar föreslogs och diskuterades. Till exempel anses interaktionsaxiomen $Kp\rightarrow Bp$ och $Bp\rightarrow KBp$ ofta vara intuitiva principer: om en agent vet $p$ då (s)han tror också $p$ , eller om en agent tror $p$ , då (s)han vet att (s)han tror $p$ . På senare tid har den här typen av filosofiska teorier tagits upp av forskare inom ekonomi , artificiell intelligens och teoretisk datavetenskap där resonemang om kunskap är ett centralt ämne. På grund av den nya miljön där epistemisk logik användes, lades nya perspektiv och nya funktioner som beräkningsbarhetsfrågor till på forskningsagendan för epistemisk logik.

Syntax

I uppföljaren är $AGTS=\{1,\ldots ,n\}$ en finit mängd vars element kallas agenter och $PROP$ är en uppsättning satsbokstäver.

Det epistemiska språket är en förlängning av det grundläggande multimodala språket för modal logik med en gemensam kunskapsoperator $C_{A}$ och en distribuerad kunskapsoperator D $\displaystyle D_{A}}$ . Formellt definieras det epistemiska språket ${\mathcal {L}}_{\textsf {EL}}^{C}$ induktivt av följande grammatik i BNF :

${\mathcal {L}}_{\textsf {EL}}^{ C}:\phi ~~::=~~p~\mid ~\neg \phi ~\mid ~(\phi \land \phi )~\mid ~K_{j}\phi ~\mid ~C_{A }\phi ~\mid ~D_{A}\phi$

där $p\in PROP$ , $j\in {AGTS}$ och $A\subseteq {AGTS}$ . Det grundläggande epistemiska språket ${\mathcal {L}}_{EL}$ är språket ${\mathcal {L}}_{EL}^{C}$ utan allmän kunskap och distribuerade kunskapsoperatörer. Formeln $\bot$ är en förkortning för $\neg p\land p$ (för ett givet ${\displaystyle p\in PROP} )$ , $\langle K_{j}\rangle \phi$ är en förkortning för $\neg K_{j}\neg \phi$ , $E_{A} \phi$ är en förkortning för $\bigwedge \limits _{j\in A}K_{j}\phi$ och $C\phi$ en förkortning för $C_{AGTS}\phi$ .

Gruppbegrepp: allmän, gemensam och distribuerad kunskap.

I en miljö med flera agenter finns det tre viktiga epistemiska begrepp: allmän kunskap, distribuerad kunskap och allmän kunskap. Begreppet allmän kunskap studerades först av Lewis i samband med konventioner. Det applicerades sedan på distribuerade system och på spelteori , där det gör det möjligt att uttrycka att spelarnas rationalitet, spelreglerna och spelaruppsättningen är allmänt kända.

Allmänbildning.

Allmän kunskap om $\phi$ betyder att alla i gruppen av agenter ${AGTS}$ vet att $\phi$ . Formellt motsvarar detta följande formel:

$E\phi :={\underset {j\in {AGTS}}{\bigwedge }}K_{j}\phi .$

Allmänbildning.

Allmän kunskap om $\phi$ betyder att alla känner till $\phi$ men också att alla vet att alla vet $\phi$ , att alla vet att alla vet att alla vet $\phi$ , och så vidare i det oändliga . Formellt motsvarar detta följande formel

$C\phi :=E\phi \land EE\phi \land EEE\phi \land \ldots$

Eftersom vi inte tillåter oändlig konjunktion måste begreppet allmän kunskap introduceras som en primitiv i vårt språk.

Innan vi definierar språket med denna nya operator, kommer vi att ge ett exempel introducerat av Lewis som illustrerar skillnaden mellan begreppen allmän kunskap och allmän kunskap. Lewis ville veta vilken typ av kunskap som behövs så att påståendet $p$ : "alla förare måste köra till höger" blir en konvention bland en grupp agenter. Med andra ord ville han veta vilken typ av kunskap som behövs för att alla ska känna sig trygga att köra till höger. Anta att det bara finns två agenter $i$ och $j$ . Då räcker inte alla som känner till $p$ (formellt ${\displaystyle Ep} ) .$ Det kan faktiskt fortfarande vara möjligt att agenten $i$ anser att agenten $j$ inte känner till $p$ (formellt $\neg K_ {i}K_{j}p$ ). I så fall kommer agenten $i$ inte att känna sig säker att köra till höger eftersom han kanske anser att agenten ${\displaystyle j} ,$ utan att veta $p$ , skulle kunna köra till vänster. För att undvika detta problem skulle vi då kunna anta att alla vet att alla vet att $p$ (formellt ${\displaystyle EEp} )$ . Detta är återigen inte tillräckligt för att säkerställa att alla känner sig säkra att köra till höger. Det kan faktiskt fortfarande vara möjligt att agent $i$ anser möjligt att agent $j$ anser vara möjligt att agent $i$ inte känner till $p$ (formellt $\neg K_{i}K_{j}K_{i}p$ ). I så fall och från $i$ s synvinkel, anser ${\displaystyle j} att det är möjligt att$${\displaystyle i} ,$ utan att veta $p$ , kommer att köra till vänster. Så från $i$ s synvinkel kan $j$ också köra till vänster (med samma argument som ovan). Så $i$ kommer inte att känna sig säker att köra till höger. Med induktionsresonemang visade Lewis att för alla $k\in \mathbb {N}$ , $Ep\land E^{1}p\ land \ldots \land E^{k}p$ räcker inte för att förarna ska känna sig trygga att köra till höger. Det vi behöver är faktiskt en oändlig konjunktion. Med andra ord behöver vi allmän kunskap om $p$ : $Cp$ .

Distribuerad kunskap.

Distribuerad kunskap om $\phi$ betyder att om agenterna drog ut sin kunskap helt och hållet skulle de veta att $\phi$ gäller. Med andra ord är kunskapen om $\phi$ fördelad mellan agenterna. Formeln $D_{A}\phi$ lyder som 'det är distribuerad kunskap bland uppsättningen agenter $A$ som $\phi$ innehåller'.

Semantik

Epistemisk logik är en modal logik . Så, vad vi kallar en epistemisk modell ${\mathcal {M}}=(W,R_{1},\ldots ,R_{n}, I)$ är bara en Kripke-modell enligt definition i modal logik. Mängden $W$ är en icke-tom mängd vars element kallas möjliga världar och tolkningen $I:W\rightarrow 2^{PROP}$ är en funktion som specificerar vilka propositionella fakta (som "Ann har det röda kortet") som är sanna i var och en av dessa världar. Tillgänglighetsrelationerna $R_{j}\subseteq W\times W$ är binära relationer för varje agent ${\displaystyle j\in AGTS$ } ; de är avsedda att fånga osäkerheten hos varje agent (om den faktiska världen och om de andra agenternas osäkerhet). Intuitivt har vi $(w,v)\in R_{j}$ när världen $v$ är kompatibel med agent $j$ s information i world $w$ eller, med andra ord, när agent $j$ anser att världen $v$ kan motsvara världen $w$ (ur denna synvinkel). Vi skriver felaktigt $w\in {\mathcal {M}}$ för $w\in W$ och $R_{j}(w)$ betecknar mängden världar $\{v\in W;(w,v)\in R_{j}\}$ .

Intuitivt representerar en spetsig epistemisk modell $({\mathcal {M}},w)$ , där $w\in {\mathcal {M}}$ , från en extern synvinkel hur den faktiska världen $w$ uppfattas av agenterna ${AGTS}$ .

För varje epistemisk modell ${\mathcal {M}}$ , varje $w\in {\mathcal {M}}$ och varje $\phi \in {\ mathcal {L}}_{\textsf {EL}}$ , vi definierar ${\mathcal {M}},w\models \phi$ induktivt med följande sanningsvillkor :

${\mathcal {M}},w\models p$	iff	$p\in I(w)$
${\mathcal {M}},w\models \neg \phi$	iff	${\textrm {det~är~inte~fallet~att~}}{\mathcal {M}},w\modeller \ phi$
${\mathcal {M}},w\models \phi \land \psi$	iff	${\mathcal {M}},w\models \phi {\textrm {~and~}}{\mathcal {M}},w\models \ psi$
${\mathcal {M}},w\models K_{j}\phi$	iff	${\textstyle {\textrm {for~all~}}v\in R_{j}(w),{\mathcal {M}},v \models \phi }$
${\mathcal {M}},w\models C_{A}\phi$	iff	${\textrm {för~alla~}}v\in \left({\underset {j\in A}{\bigcup }}R_{j}\right)^{+}(w),{\mathcal {M}},v\models \phi$
${\mathcal {M}},w\models D_{A}\phi$	iff	${\textrm {for~all~}}v\in {\underset {j\in A}{\bigcap } }R_{j}(w),{\mathcal {M}},v\models \phi$

där ${\displaystyle \left({\underset {j\in A}{\bigcup }}R_{j}\right)^{+}} är$ den transitiva stängningen av ${\displaystyle {\underset {j\in A}{\bigcup }}R_{j}} :$ vi har att $v\in \ vänster({\underset {j\in A}{\bigcup }}R_{j}\right)^{+}(w)$ om, och endast om, det finns $w_{0},\ldots ,w_{m}\in {\mathcal {M}}$ och $j_{1},\ldots ,j_{m}\in A$ så att $w_{0}=w,w_{m}=v$ och för alla $i\in \{1, \ldots ,m\}$ , $w_{i-1}R_{j_{i}}w_{i}$ .

Trots att begreppet gemensam tro måste introduceras som en primitiv i språket, kan vi notera att definitionen av epistemiska modeller inte behöver modifieras för att ge sanningsvärde åt den gemensamma kunskapen och distribuerade kunskapsoperatörer.

Exempel på kort:

Spelare $A$ , $B$ och $C$ (står för Ann, Bob och Claire) spelar ett kortspel med tre kort: ett rött, ett grönt och ett blått. Var och en av dem har ett enda kort men de känner inte till de andra spelarnas kort. Ann har det röda kortet, Bob har det gröna kortet och Claire har det blåa kortet. Detta exempel är avbildat i den spetsiga epistemiska modellen $({\mathcal {M}},w)$ som representeras nedan. I det här exemplet, $PROP:=\{{\color {röd}{A}},{\color {grön}{B}},{\color {blå}{C}}, {\color {röd}{B}},{\color {grön}{C}},{\color {blå}{A}},{\color {röd}{C}},{\color {grön} {A}},{\color {blå}{B}}\}$$AGTS:=\{A,B,C\}$ och . Varje värld är märkt med satsbokstäverna som är sanna i denna värld och $w$ motsvarar den faktiska världen. Det finns en pil indexerad av agent $j\in \{A,B,C\}$ från en möjlig värld $u$ till en möjlig värld $v$ när $(u,v)\in R_{j}$ . Reflexiva pilar utelämnas, vilket betyder att för alla $j\in \{A,B,C\}$ och alla $v\in {\mathcal { M}}$ , vi har att $(v,v)\in R_{j}$ .

Kortexempel: spetsig epistemisk modell $({\mathcal {M}},w)$

${\color {red}{A}}$ står för: " $A$ har det röda kortet''

${\color {blue}{C}}$ står för: " $C$ har det blå kortet''

${\color {green}{B}}$ står för: " $B$ har det gröna kortet''

och så vidare...

När tillgänglighetsrelationer är ekvivalensrelationer (som i det här exemplet) och vi har att $(w,v)\in R_{j}$ , säger vi att agent $j$ kan inte skilja värld $w$ från värld $v$ (eller värld $w$ går inte att skilja från värld $v$ för agent $j$ ). Så till exempel ${\textstyle A}$ inte skilja den faktiska världen $w$ från den möjliga världen där $B$ har det blå kortet ( ${\color {blue}{B }}$ ), $C$ har det gröna kortet ( ${\color {green}{C}}$ ) och $A$ har fortfarande det röda kortet ( ${ \color {röd}{A}}$ ).

I synnerhet gäller följande uttalanden:

${\mathcal {M}},w\modeller ({\färg {röd}{A }}\land K_{A}{\color {röd}{A}})\land ({\color {blå}{C}}\land K_{C}{\color {blå}{C}})\ land ({\color {grön}{B}}\land K_{B}{\color {grön}{B}})$

"Alla agenter vet färgen på sitt kort".

${\mathcal {M}},w\modeller K_{A}({\color {blå}{B}}\vee {\color {grön}{B}})\land K_{A}({\color {blå}{C}}\vee {\color {grön}{C}})$

' $A$ vet att $B$ har antingen det blåa eller det gröna kortet och att $C$ har antingen det blåa eller det gröna kortet'.

${\mathcal {M}},w\models E({\color {röd}{A}}\vee { \color {blå}{A}}\vee {\color {grön}{A}})\land C({\color {röd}{A}}\vee {\color {blå}{A}}\vee {\color {grön}{A}})$

"Alla vet att $A$ har antingen det röda, gröna eller blåa kortet och detta är till och med allmänt känt bland alla agenter".

Kunskap kontra tro

Vi använder samma notation $K_{j}$ för både kunskap och tro. Därför, beroende på sammanhanget, $K_{j}\phi$ antingen att läsa 'agenten $j$ K nu som $\phi$ gäller' eller 'agenten ${ \displaystyle j}$ Tror att $\phi$ gäller'. En avgörande skillnad är att till skillnad från kunskap kan föreställningar vara fel : axiomet $K_{j}\phi \rightarrow \phi$ gäller bara för kunskap, men inte nödvändigtvis för tro. Detta axiom som kallas axiom T (för sanning) säger att om agenten känner till en proposition så är denna proposition sann. Den anses ofta vara kunskapens kännetecken och den har inte utsatts för någon allvarlig attack ända sedan den introducerades i Theaetetus av Platon .

Begreppet kunskap kan överensstämma med vissa andra begränsningar (eller axiom) såsom ${\displaystyle K_{j}\phi \rightarrow K_{j}K_{j}\phi } :$ om agent $j$ vet något, hon vet att hon vet det. Dessa begränsningar kan påverka karaktären på tillgänglighetsrelationerna $R_{j}$ som sedan kan överensstämma med några extra egenskaper. Så vi kommer nu att definiera några speciella klasser av epistemiska modeller som alla lägger till några extra begränsningar för tillgänglighetsrelationerna $R_{j}$ . Dessa begränsningar matchas av särskilda axiom för kunskapsoperatorn $K_{j}$ . Under varje egenskap ger vi axiomet som definierar klassen av epistemiska ramar som uppfyller denna egenskap. ( $K\phi$ står för $K_{j}\phi$ för alla $j\in AGTS$ .)

Egenskaper för tillgänglighetsrelationer och motsvarande axiom

serie	$R(w)\neq \emptyset$
D	$K\phi \rightarrow \langle K\rangle \phi$
transitiv	${\textrm {If}}~w'\in R(w)~{\textrm { och}}~w''\in R(w'),~{\textrm {sedan}}~w''\in R(w)$
4	$K\phi \rightarrow KK\phi$
Euklidicitet	${\textrm {If}}~w'\in R(w)~{\textrm { och}}~w''\in R(w),~{\textrm {sedan}}~w'\in R(w'')$
5	$\neg K\phi \rightarrow K\neg K\phi$
reflexiv	$w\in R(w)$
T	$K\phi \rightarrow \phi$
symmetrisk	${\textrm {If}}~w'\in R(w),~{\textrm {then}}~w\in R (w')$
B	$\phi \rightarrow K\neg K\neg \phi$
sammanflytande	${\textrm {Om}}~w'\in R(w){\textrm {~and~}}w''\in R(w),{\textrm {då~finns~}}v{\ textrm {~sådant~att}}~v\in R(w'){\textrm {~and~}}v\in R(w'')$
.2	$\langle K\rangle K\phi \högerpil K\langle K\rangle \phi$
svagt ansluten	${ \displaystyle {\textrm {If}}~w'\in R(w){\textrm {~and~}}w''\in R(w),{\textrm {~then~}}w'=w ''{\textrm {~or~}}w'\in R(w''){\textrm {~or~}}w''\in R(w')}$
.3	$_ \phi \land \langle K\rangle \psi \rightarrow \langle K\rangle (\phi \land \psi )\vee \langle K\rangle (\psi \land \langle K\rangle \phi )\vee \langle K\rangle (\phi \land \langle K\rangle \psi )}$
halveuklidiskt	${\textrm {If~ }}w''\in R(w){\textrm {~and~}}w\notin R(w''){\textrm {~and~}}w'\in R(w),{\textrm {~then~}}w''\in R(w')$
.3.2	$(\langle K\rangle \phi \land \langle K\rangle K\psi )\högerpil K(\langle K\rangle \phi \vee \psi )$
R1	${\textrm {If~}}w ''\in R(w){\textrm {~and~}}w\neq w''{\textrm {~and~}}w'\in R(w),{\textrm {~then~}} w''\in R(w')$
.4	$(\phi \land \langle K\rangle K\phi )\högerpil K\phi$

Vi diskuterar axiomen ovan. Axiom 4 säger att om agenten känner till en proposition, så vet hon att hon kan den (detta axiom är också känt som "KK-principen" eller "KK-uppsatsen"). I epistemologi tenderar axiom 4 att accepteras av internalister , men inte av externalister . Axiom 4 är ändå allmänt accepterat av datavetare (men också av många filosofer, inklusive Platon , Aristoteles , Saint Augustine , Spinoza och Schopenhauer , som Hintikka minns). Ett mer kontroversiellt axiom för kunskapens logik är axiom 5 för euklidicitet: detta axiom säger att om agenten inte känner till en proposition så vet hon att hon inte vet den. De flesta filosofer (inklusive Hintikka) har angripit detta axiom, eftersom många exempel från vardagslivet verkar ogiltigförklara det. Generellt sett ogiltigförklaras axiom 5 när agenten har felaktiga uppfattningar, vilket kan bero på till exempel missuppfattningar, lögner eller andra former av bedrägeri. Axiom B anger att det inte kan vara så att agenten anser att det är möjligt att hon känner till en falsk proposition (det vill säga $\neg (\neg \phi \land \neg K\neg K\phi )$ ). Om vi ​​antar att axiomen T och 4 är giltiga, faller axiom B offer för samma attack som den för axiom 5 eftersom detta axiom är härledbart. Axiom D säger att agentens övertygelser är konsekventa. I kombination med axiom K (där kunskapsoperatorn ersätts med en trosoperator) är axiom D i själva verket ekvivalent med ett enklare axiom D' som förmedlar, kanske mer explicit, det faktum att agentens övertygelser inte kan vara inkonsekventa: $\neg B\bot$ . De andra invecklade axiomen .2, .3, .3.2 och .4 har introducerats av epistemiska logiker som Lenzen och Kutchera på 1970-talet och presenterades för några av dem som nyckelaxiom för epistemisk logik. De kan karakteriseras i termer av intuitiva interaktionsaxiom som relaterar till kunskap och övertygelser.

Axiomatisering

Hilbert- bevissystemet K för den grundläggande modala logiken definieras av följande axiom och slutledningsregler : för alla $j\in AGTS$ ,

Bevissystem ${\textsf {K}}$ för ${\mathcal {L}}_{EL}$

Stötta	Alla axiom och slutledningsregler för propositionell logik
K	$K_{j}(\phi \rightarrow \psi )\rightarrow (K_{j}\phi \rightarrow K_{j}\psi )$
Nec	Om $\phi$ så $K_{j}\phi$

Axiomen för en epistemisk logik visar uppenbarligen hur agenterna resonerar. Till exempel innebär axiomet K tillsammans med inferensregeln Nec att om jag känner till $\phi$ ( ${\displaystyle K\phi } )$ och jag vet att $\phi$ innebär ${ \displaystyle \psi }$ ( $K(\phi \rightarrow \psi ))$ då vet jag att $\psi$ ( $K\psi$ ). Starkare begränsningar kan läggas till. Följande bevissystem för ${\mathcal {L}}_{\textsf {EL}}$ används ofta i litteraturen.

Vanliga bevissystem för ${\mathcal {L}}_{EL}$

KD45

=

K+D+4+5

S4.2

=

S4+.2

S4.3.2

=

S4+.3.2

S5

=

S4+5

S4

=

K+T+4

S4.3

=

S4+.3

S4.4

=

S4+.4

Br

=

K+T+B

Vi definierar uppsättningen av bevissystem $\mathbb {L} _{\textsf {EL }}:=\{{\textsf {K}},{\textsf {KD45}},{\textsf {S4}},{\textsf {S4.2}},{\textsf {S4.3}}, {\textsf {S4.3.2}},{\textsf {S4.4}},{\textsf {S5}}\}$ .

Dessutom, för alla ${\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}$ definierar vi bevissystemet ${\mathcal {H }}^{\textsf {C}}$ genom att lägga till följande axiomscheman och inferensregler till de för ${\mathcal {H}}$ . För alla $A\subseteq AGTS$ ,

Dis	$K_{j}\phi \rightarrow D_{A}\phi$
Blanda	$C_{A}\phi \rightarrow E_{A}(\phi \land C_{A}\phi )$
Ind	${\textrm {if~}}\phi \rightarrow E_{A}(\psi \land \phi ){\textrm { ~then~}}\phi \rightarrow C_{A}\psi$

Den relativa styrkan hos bevissystemen för kunskap är följande:

${\textsf {S4}}\subset {\textsf {S4.2}}\subset {\textsf {S4.3}}\subset {\textsf {S4.3.2}}\subset {\textsf {S4 .4}}\subset {\textsf {S5}}.$

Så alla satser i ${\textsf {S4.2}}$ är också satser för ${\textsf {S4.3}}, {\textsf {S4.3.2}},{\textsf {S4.4}}$ och ${\textsf {S5}}$ . Många filosofer hävdar att kunskapens logik i de mest allmänna fallen är ${\textsf {S4.2}}$ eller ${\textsf {S4.3}}$ . Vanligtvis, inom datavetenskap och i många av teorierna som utvecklats inom artificiell intelligens, anses troslogiken ( doxastisk logik) vara ${\textsf {KD45}}$ och kunskapslogiken ( epstemisk logik) är tas som ${\textsf {S5}}$ , även om ${\textsf {S5}}$ endast är lämplig för situationer där agenterna inte har felaktiga övertygelser. ${\textsf {Br}}$ har framställts av Floridi som logiken i begreppet "att bli informerad" som huvudsakligen skiljer sig från kunskapens logik genom frånvaron av introspektion för agenterna.

För alla ${\displaystyle {\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}} ,$ klassen av ${\mathcal {H}}$ –modeller eller ${\mathcal {H}}^{\textsf {C}}$ –modeller är klassen av epistemiska modeller vars tillgänglighetsrelationer uppfyller de egenskaper som anges ovan definierade av axiomen för ${\mathcal {H}}$ eller ${\mathcal {H}}^{\textsf {C}}$ . Sedan, för alla ${\displaystyle {\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}} , är$ H { $displaystyle {\mathcal {H}}}$ ljud och starkt komplett för ${\mathcal {L}}_{\textsf {EL}}$ med avseende på klassen ${\mathcal {H}}$ –modeller och ${ \mathcal {H}}^{\textsf {C}}$ är ljud och starkt komplett för ${\mathcal {L}}_{\textsf {EL}}^{\textsf {C}}$ med klassen av ${\mathcal {H}}^{\textsf {C}}$ –modeller.

Beslutbarhet och komplexitet

Tillfredsställbarhetsproblemet för alla introducerade logiker är avgörbart . Vi listar nedan den beräkningsmässiga komplexiteten för tillfredsställbarhetsproblemet för var och en av dem. Observera att det blir linjärt i tiden om det bara finns ändligt många satsbokstäver i språket. För $n\geq 2$ , om vi begränsar oss till ändlig kapsling, är tillfredsställbarhetsproblemet NP-komplett för alla modala logiker som beaktas. Om vi ​​sedan ytterligare begränsar språket till att bara ha ändligt många primitiva satser, går komplexiteten ner till linjär i tiden i alla fall.

Tillfredsställbarhetsproblemets komplexitet

Logik	$n=1$	$n\geq 2$	med allmän kunskap
K, S4	PSPACE	PSPACE	EXPTIME
KD45	NP	PSPACE	EXPTIME
S5	NP	PSPACE	EXPTIME

Beräkningskomplexiteten för modellkontrollproblemet är i alla fall i P.

Lägger till dynamik

Dynamisk epistemisk logik (DEL) är ett logiskt ramverk för att modellera epistemiska situationer som involverar flera agenter, och förändringar som inträffar i dessa situationer som ett resultat av inkommande information eller mer allmänt inkommande åtgärder. Metodiken för DEL är sådan att den delar upp uppgiften att representera agenternas tro och kunskap i tre delar:

1. Den ena representerar deras föreställningar om en initial situation tack vare en epistemisk modell ;
2. En representerar deras uppfattning om en händelse som äger rum i denna situation tack vare en händelsemodell ;
3. Den ena representerar hur agenterna uppdaterar sin uppfattning om situationen efter (eller under) händelsen, tack vare en produktuppdatering .

Vanligtvis kan en informativ händelse vara ett offentligt tillkännagivande till alla agenter av en formel $\psi$ : detta offentliga tillkännagivande och korrelativa uppdatering utgör den dynamiska delen. Emellertid kan epistemiska händelser vara mycket mer komplexa än enkla offentliga tillkännagivanden, inklusive att dölja information för några av agenterna, fusk, lögn, bluff, etc. Denna komplexitet behandlas när vi introducerar begreppet händelsemodell. Vi kommer först att fokusera på offentliga tillkännagivanden för att få en intuition av de huvudsakliga bakomliggande idéerna för DEL.

Offentliga evenemang

I det här avsnittet utgår vi från att alla evenemang är offentliga. Vi börjar med att ge ett konkret exempel där DEL kan användas, för att bättre förstå vad som pågår. Detta exempel kallas det leriga barnpusslet . Sedan kommer vi att presentera en formalisering av detta pussel i en logik som kallas Public Announcement Logic (PAL). Det leriga barnpusslet är ett av de mest välkända pusslen som spelade en roll i utvecklingen av DEL. Andra viktiga pussel inkluderar summan och produktpusslet , Monty Hall-dilemmat , problemet med ryska kort, problemet med två kuvert , Moores paradox , bödelparadoxen , etc.

Muddy Children Exempel:

Vi har två barn, A och B, båda smutsiga. A kan se B men inte sig själv, och B kan se A men inte sig själv. Låt $p$ vara satsen som anger att A är smutsig, och $q$ vara satsen som anger att B är smutsig.

1. Vi representerar initialsituationen med den spetsiga epistemiska modellen $({\mathcal {N}},s)$ som representeras nedan, där relationer mellan världar är ekvivalensrelationer. Tillstånd $s,t,u,v$ representerar intuitivt möjliga världar, en proposition (till exempel $p$ ) som är tillfredsställbar i en av dessa världar betyder intuitivt att i motsvarande möjliga värld , den intuitiva tolkningen av $p$ (A är smutsig) är sann. Länkarna mellan världar märkta av agenter (A eller B) uttrycker intuitivt en föreställning om omöjlighet att särskilja den agent som står på spel mellan två möjliga världar. Till exempel, länken mellan $s$ och $t$ märkta med A betyder intuitivt att A inte kan skilja den möjliga världen $s$ från $t$ och vice versa. A kan faktiskt inte se sig själv, så han kan inte skilja mellan en värld där han är smutsig och en där han inte är smutsig. Han kan dock skilja mellan världar där B är smutsig eller inte eftersom han kan se B. Med denna intuitiva tolkning förmås vi att anta att våra relationer mellan världar är ekvivalensrelationer.
   

   Initial situation: spetsig epistemisk modell $({\mathcal {N}},s)$
2. Anta nu att deras far kommer och meddelar att minst en är smutsig (formellt ${\displaystyle p\vee q} )$ . Sedan uppdaterar vi modellen och detta ger den spetsiga epistemiska modellen som representeras nedan. Vad vi faktiskt gör är att undertrycka världar där innehållet i tillkännagivandet inte uppfylls. I vårt fall är detta världen där $\neg p$ och $\neg q$ är sanna. Denna undertryckning är vad vi kallar uppdateringen. Vi får då modellen avbildad nedan. Som ett resultat av tillkännagivandet vet både A och B att åtminstone en av dem är smutsig. Vi kan läsa detta från den epistemiska modellen.
   

   Uppdaterad epistemisk modell efter det första tillkännagivandet $p\vee q$
3. Anta nu att det finns ett andra (och sista) meddelande som säger att ingen av dem vet att de är smutsiga (ett meddelande kan uttrycka fakta om situationen såväl som epistemiska fakta om den kunskap som agenterna innehar). Vi uppdaterar sedan modellen på liknande sätt genom att undertrycka de världar som inte uppfyller innehållet i tillkännagivandet, eller på motsvarande sätt genom att behålla de världar som uppfyller tillkännagivandet. Denna uppdateringsprocess ger alltså den spetsiga epistemiska modellen som representeras nedan. Genom att tolka denna modell får vi att A och B båda vet att de är smutsiga, vilket verkar motsäga innehållet i tillkännagivandet. Men om vi antar att A och B båda är perfekta resonemang och att detta är allmänt känt bland dem, så är denna slutsats helt vettig.

Uppdaterad epistemisk modell efter det andra tillkännagivandet

Offentlig tillkännagivande logik (PAL):

Vi presenterar syntaxen och semantiken för Public Announcement Logic (PAL), som kombinerar egenskaper från epistemisk logik och propositionell dynamisk logik .

Vi definierar språket ${{\mathcal {L}}_{PAL}}$ induktivt med följande grammatik i BNF :

${{\mathcal {L}}_{PAL}}:\phi ~~::=~~p~\mid ~\neg \phi ~\mid ~(\phi \land \phi )~ \mid ~K_{j}\phi ~\mid ~[\phi !]\phi$

där $j\in AGTS$ .

Språket ${{\mathcal {L}}_{PAL}}$ tolkas över epistemiska modeller. Sanningsvillkoren för det epistemiska språkets bindemedel är desamma som i epistemisk logik (se ovan) . Sanningsvillkoret för den nya dynamiska handlingsmodaliteten $[\psi !]\phi$ definieras enligt följande:

${\mathcal {M}},w\models [\psi !]\phi$

iff

${\mbox{if }}{\mathcal {M}},w\models \psi {\mbox{ sedan }}{\mathcal {M}} ^{\psi },w\models \phi$

där ${\displaystyle {\mathcal {M}}^{\psi }:=(W^{\psi },R_{$ med

$W^{\psi }:=\{w\in W;{\mathcal {M}},w\models \psi \}$ ,

$R_{j}^{\psi }:=R_{j}\cap (W^{\psi }\times W^{\psi } )$ för alla $j\in \{1,\ldots ,n\}$ och

$I^{\psi }(w):=I(w){\textrm {~för~alla~}}w \in W^{\psi }$ .

Formeln $[\psi !]\phi$ betyder intuitivt att efter ett sanningsenligt tillkännagivande av ${\displaystyle \psi } ,$ gäller ϕ $\displaystyle \phi } .$ Ett offentligt tillkännagivande av en proposition $\psi$ ändrar den nuvarande epistemiska modellen som i figuren nedan.

Eliminera alla världar som för närvarande inte uppfyller $\psi$

Bevissystemet ${\mathcal {H}}_{PAL}$ som definieras nedan är bra och starkt komplett för ${{\mathcal {L}}_{PAL}}$ enligt klassen för alla spetsiga epistemiska modeller.

${\textsf {K}}$		Axiomen och inferensreglerna för bevissystemet ${\displaystyle {\textsf {K}}} ($ se ovan)
Röd 1		$[\psi !]p\leftrightarrow (\psi \rightarrow p)$
röd 2		$[\psi !]\neg \phi \leftrightarrow (\psi \rightarrow \neg [\psi !]\phi )$
Röd 3		$[\psi !](\phi \land \chi )\leftrightarrow ([\psi !]\phi \land [\ psi !]\chi )$
Röd 4		$[\psi !]K_{i}\phi \leftrightarrow \left(\psi \rightarrow K_{i}(\psi \rightarrow [\psi !]\phi )\right)$

Axiomen Red 1 - Red 4 kallas reduktionsaxiom eftersom de gör det möjligt att reducera vilken formel som helst av ${{\mathcal {L}}_{PAL}}$ till en bevisligen ekvivalent formel för ${ \displaystyle {\mathcal {L}}_{EL}}$ i ${\mathcal {H}}_{PAL}$ . Formeln $[q!]Kq$ är ett teorem som kan bevisas i ${\mathcal {H}}_{PAL}$ . Den anger att efter ett offentligt tillkännagivande av $q$ vet agenten att $q$ gäller.

PAL är avgörbart , dess modellkontrollproblem är lösbart i polynomtid och dess tillfredsställbarhetsproblem är PSPACE-komplett .

Lerigt barnpussel formaliserat med PAL:

Här är några av de uttalanden som håller i det leriga barnpusslet som formaliserats i PAL.

${\mathcal {N}},s\modeller p\land q$

"I utgångsläget är A smutsig och B är smutsig".

${\displaystyle {\mathcal {N}},s\modeller (\neg K_{A$

"I utgångsläget vet inte A om han är smutsig och B inte heller".

${\mathcal {N}},s\models [p\vee q!](K_{A}(p\vee q) \land K_{B}(p\vee q))$

"Efter det offentliga tillkännagivandet att minst ett av barnen A och B är smutsigt vet båda att minst ett av barnen är smutsigt". Dock:

${\displaystyle {\mathcal {N}},s\models [p\vee q!]$

"Efter det offentliga tillkännagivandet att minst ett av barnen A och B är smutsigt vet de fortfarande inte att de är smutsiga". Dessutom:

${\mathcal {N}},s\modeller [p\vee q!][(\neg K_{A}p\land \neg K_{A}\neg p)\land (\neg K_{B}q\land \neg K_{B}\neg q)!](K_{A}p\land K_{B}q)$

"Efter de på varandra följande offentliga tillkännagivandena om att åtminstone ett av barnen A och B är smutsiga och att de fortfarande inte vet om de är smutsiga, vet A och B båda att de är smutsiga".

I detta sista uttalande ser vi på jobbet ett intressant inslag i uppdateringsprocessen: en formel är inte nödvändigtvis sann efter att den tillkännages. Det är vad vi tekniskt kallar "självbeständighet" och detta problem uppstår för epistemiska formler (till skillnad från propositionella formler). Man får inte blanda ihop tillkännagivandet och uppdateringen som induceras av detta tillkännagivande, vilket kan ta bort en del av informationen som kodas i meddelandet.

Godtyckliga händelser

I det här avsnittet antar vi att händelser inte nödvändigtvis är offentliga och vi fokuserar på punkterna 2 och 3 ovan, nämligen på hur man representerar händelser och på hur man uppdaterar en epistemisk modell med en sådan representation av händelser med hjälp av en produktuppdatering.

Händelsemodell

Epistemiska modeller används för att modellera hur agenter uppfattar den faktiska världen. Deras uppfattning kan också beskrivas i termer av kunskap och föreställningar om världen och om de andra agenternas tro. Insikten med DEL-upplägget är att man kan beskriva hur en händelse uppfattas av agenterna på ett väldigt likartat sätt. Agenternas uppfattning av en händelse kan faktiskt också beskrivas i termer av kunskap och övertygelser. Till exempel kan det privata tillkännagivandet av $A$ till $B$ att hennes kort är rött också beskrivas i termer av kunskap och övertygelser: medan $A$ säger till $B$ att hennes kort är rött (händelse $e$ ) $C$ tror att ingenting händer (händelse ${\displaystyle f} )$ . Detta leder till att definiera begreppet händelsemodell vars definition är mycket lik den för en epistemisk modell.

En spetsig händelsemodell $({\mathcal {E}},e)$ representerar hur den faktiska händelsen som representeras av $e$ uppfattas av agenterna. Intuitivt $f\in R_{j}(e)$ att medan den möjliga händelsen som representeras av $e$ inträffar, anser agent ${\displaystyle j} att det är möjligt att$ den möjliga händelsen som representeras av $f$ inträffar faktiskt.

En händelsemodell är en tuppel ${\mathcal {E}}=(W^{\alpha },R_{1}^{ \alpha },\ldots ,R_{m}^{\alpha },I^{\alpha })$ där:

• $W^{\alpha }$ är en icke-tom uppsättning möjliga händelser ,
• ${\displaystyle R_{j}^{\alpha }\subseteq W^{\alpha }\times W^{\alpha }} är$ en binär relation som kallas en tillgänglighetsrelation på ${ \displaystyle W^{\alpha }}$ , för varje $j\in AGTS$ ,
• ${\displaystyle I^{\alpha }:W^{\alpha }\rightarrow {\mathcal {L}}_{\textsf {EL}}} är en funktion som kallas$ precondition function assigning till varje möjlig händelse en formel för ${\mathcal {L}}_{\textsf {EL}}$ .

$R_{j}^{\alpha }(e)$ betecknar mängden ${\displaystyle \{f\in W^{\alpha };(e,f)\in R_{j}^{\alpha }\}} .Vi$ skriver $e\in {\mathcal {E}}$ för $e\in W^{\alpha }$ och $({\mathcal {E}} ,e)$ kallas en spetsig händelsemodell ( $e$ representerar ofta den faktiska händelsen).

Exempel på kort:

Låt oss återuppta kortexemplet och anta att spelare $A$ och $B$ visar sina kort för varandra. Det visade sig $C$ märkte att $A$ visade sitt kort till $B$ men märkte inte att $B$ gjorde det mot $A$ . Spelare $A$ och $B$ vet detta. Denna händelse representeras nedan i händelsemodellen $({\mathcal {E}},e)$ .

Den möjliga händelsen $e$ motsvarar den faktiska händelsen 'spelare $A$ och $B$ visar sina respektive kort för varandra' (med förutsättning ${\color {röd}{A}}\land {\color {grön}{B}}$ ), $f$ står för händelsen 'spelare $A$ visar sitt gröna kort' (med förutsättning ${ \displaystyle {\color {grön}{A}}}$ och $g$ står för atomhändelsen 'spelare $A$ visar sitt röda kort' (med förutsättning ${\color { röd}{A}}$ ). Spelare $A$ och $B$ visar sina kort för varandra, spelare $A$ och $B$ vet detta och anser att det är möjligt, medan spelare $C$ anser att det är möjligt att spelare $A$ visar sitt röda kort och anser också att det är möjligt att spelare $A$ visar sitt gröna kort, eftersom han inte känner till hennes kort. Det är faktiskt allt som spelare $C$ anser vara möjligt eftersom hon inte märkte att $B$ visade sitt kort.

Pointed event-modell $({\mathcal {E}},e)$ : Spelare A och B visar sina kort för varandra framför spelare C

Ett annat exempel på händelsemodell ges nedan. Detta andra exempel motsvarar händelsen där spelare $A$ visar sitt röda kort offentligt för alla. Spelare $A$ visar sitt röda kort, spelare $A$ , $B$ och ${\displaystyle C} "$ vet" det, spelare $A$ , $B$ och $C$ 'vet' att var och en av dem 'vet' det, etc. Det finns med andra ord allmän kunskap bland spelarna $A$ , $B$ och ${\ displaystyle C}$ att spelare $A$ visar sitt röda kort.

Spetsad händelsemodell $({\mathcal {F}},e)$

Produktuppdatering

DEL-produktuppdateringen definieras nedan. Denna uppdatering ger en ny spetsig epistemisk modell ${\displaystyle ({\mathcal {M}},w)\otimes ({\mathcal {E}},e)} som$ representerar hur ny situation som tidigare representerades av $({\mathcal {M}},w)$ uppfattas av agenterna efter inträffandet av händelsen representerad av $({ \mathcal {E}},e)$ .

Låt ${\mathcal {M}}=(W,R_{1},\ldots ,R_{n},I)$ vara en epistemisk modell och låt $displaystyle {\mathcal {E}}=(W^{\alpha },R_{1}^{\alpha}, \ldots ,R_{n}^{\alpha },I^{\alpha })}$ vara en händelsemodell. Produktuppdateringen av ${\mathcal {M}}$ och $mathcal {E}}}$ \ är den epistemiska modellen ${\mathcal {M}}\otimes {\mathcal {\mathcal {E}}}=(W^{\otimes },R_{1}^{\otimes },\ldots ,R_ {n}^{\otimes },I^{\otimes })$ definieras enligt följande: för alla $v\in W$ och alla $f\in W^{\ alfa }$ ,

$W^{\otimes }$	=	$\{(v,f)\in W\times W^{\alpha };{\mathcal {M}},v\models I^{\alpha }( f)\}$
$R_{j}^{\otimes }(v,f)$	=	$\{(u,g)\in W^{\otimes };u\in R_{j}(v){\ textrm {~and~}}g\in R_{j}^{\alpha }(f)\}$
$I^{\otimes }(v,f)$	=	$I(v)$

Om $w\in W$ och $e\in W^{\alpha }$ är sådana att ${\mathcal {M }},w\models I^{\alpha }(e)$ sedan $({\mathcal {M}},w)\otimes ({\mathcal {E }},e)$ betecknar den spetsiga epistemiska modellen $({\mathcal {M}}\otimes {\mathcal {E}},(w,e))$ . Denna definition av produktuppdateringen är konceptuellt grundad.

Exempel på kort:

Som ett resultat av den första händelsen som beskrivs ovan (Spelare $A$ och $B$ visar sina kort för varandra framför spelare $C$ ), uppdaterar agenterna sina övertygelser. Vi får situationen representerad i den spetsiga epistemiska modellen $({\mathcal {M}},w)\otimes ({\mathcal {E}},e)$ nedan . I denna spetsiga epistemiska modell gäller följande påstående: ${\displaystyle ({\mathcal {M}},w)\otimes ({\mathcal {E}},e)\modeller ({\color {grön}{B}}\land K_{A}{\color { grön}{B}})\land K_{C}\neg K_{A}{\color {grön}{B}}.} Det står att spelare A {\$ displaystyle $}$ vet att spelare $B$ har kortet men spelare $C$ 'tror' att det inte är fallet.

Uppdaterad spetsig epistemisk modell $({\mathcal {M}},w)\otimes ({\mathcal {E}},e)$

Resultatet av den andra händelsen visas nedan. I denna spetsiga epistemiska modell gäller följande uttalande: $({ \mathcal {M}},w)\otimes ({\mathcal {F}},e)\modeller C_{\{B,C\}}({\color {röd}{A}}\land {\color {grön}{B}}\land {\color {blå}{C}})\land \neg K_{A}({\color {grön}{B}}\land {\color {blå}{C} })$ . Det sägs att det är allmänt känt bland $B$ och $C$ att de känner till världens sanna tillstånd (nämligen $A$ har det röda kortet, $B$ har det gröna kortet och $C$ har det blå kortet), men $A$ känner inte till det.

Uppdaterad spetsig epistemisk modell $({\mathcal {M}},w)\otimes ({\mathcal {F}},e)$

Baserat på dessa tre komponenter (epistemisk modell, händelsemodell och produktuppdatering) definierade Baltag, Moss och Solecki ett allmänt logiskt språk inspirerat av propositionell dynamisk logiks logiska språk för att resonera kring information och kunskapsförändring.

Se även

• Epistemisk logik
• Epistemologi
• Logik i datavetenskap
• Modal logik

Anteckningar

•   van Benthem, Johan (2011). Logisk dynamik för information och interaktion . Cambridge University Press. ISBN 978-0521873970 .
•   Hans, van Ditmarsch; Halpern, Joseph; van der Hoek, Wiebe; Kooi, Barteld (2015). Handbok i epistemisk logik . London: College publikation. ISBN 978-1848901582 .
•   van Ditmarsch, Hans, van der Hoek, Wiebe, och Kooi, Barteld (2007). Dynamisk epistemisk logik . Ithaca: volym 337 av Synthese library. Springer. ISBN 978-1-4020-5839-4 . {{ citera bok }} : CS1 underhåll: flera namn: lista över författare ( länk )
•   Fagin, Ronald; Halpern, Joseph; Moses, Yoram; Vardi, Moshe (2003). Resonemang om Kunskap . Cambridge: MIT Press . ISBN 978-0-262-56200-3 . En klassisk referens.
•   Hintikka, Jaakko (1962). Kunskap och tro - En introduktion till de två föreställningarnas logik . Ithaca: Cornell University Press . ISBN 978-1-904987-08-6 . .

externa länkar

• Baltag, Alexandru; Renne, Bryan. "Dynamisk epistemisk logik" . I Zalta, Edward N. (red.). Stanford Encyclopedia of Philosophy .
• van Ditmarsch, Hans; van der Hoek, Wiebe; Kooi, Barteld. "Dynamisk epistemisk logik" . Internet Encyclopedia of Philosophy .
• Hendricks, Vincent; Symons, John. "Epistemisk logik" . I Zalta, Edward N. (red.). Stanford Encyclopedia of Philosophy .
• Garson, James. "Modallogik" . I Zalta, Edward N. (red.). Stanford Encyclopedia of Philosophy .