lógica epistémica dinámica

En la secuela,${\displaystyle AGTS=\{1,\ldots ,n\}}$es un conjunto finito cuyos elementos se llaman agentes y${\displaystyle PROP}$es un conjunto de letras proposicionales.

El lenguaje epistémico es una extensión del lenguaje multimodal básico de la lógica modal con un operador de conocimiento común .${\displaystyle C_{A}}$y un operador de conocimiento distribuido${\displaystyle D_{A}}$Formalmente, el lenguaje epistémico${\displaystyle {\mathcal {L}}_{\textsf {EL}}^{C}}$se define inductivamente mediante la siguiente gramática en BNF :

${\displaystyle {\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ónde${\displaystyle p\in PROP}$,${\displaystyle j\in {AGTS}}$y${\displaystyle A\subseteq {AGTS}}$El lenguaje epistémico básico${\displaystyle {\mathcal {L}}_{EL}}$es el idioma${\displaystyle {\mathcal {L}}_{EL}^{C}}$sin los operadores de conocimiento común y conocimiento distribuido. La fórmula${\displaystyle \bot }$es una abreviatura de${\displaystyle \neg p\land p}$(para un dado${\displaystyle p\in PROP}$), ${\displaystyle \langle K_{j}\rangle \phi }$es una abreviatura de${\displaystyle \neg K_{j}\neg \phi }$,${\displaystyle E_{A}\phi }$es una abreviatura de${\displaystyle \bigwedge \limits _{j\in A}K_{j}\phi }$y${\displaystyle C\phi }$una abreviatura de${\displaystyle C_{AGTS}\phi }$.

Nociones de grupo: conocimiento general, común y distribuido.

En un entorno multiagente existen tres conceptos epistémicos importantes: conocimiento general, conocimiento distribuido y conocimiento común. La noción de conocimiento común fue estudiada por primera vez por Lewis en el contexto de las convenciones. ^{[ 13 ]} Posteriormente se aplicó a sistemas distribuidos ^{[ 12 ]} y a la teoría de juegos , ^{[ 14 ]} donde permite expresar que la racionalidad de los jugadores, las reglas del juego y el conjunto de jugadores son de conocimiento común.

Conocimiento general.

Conocimientos generales de${\displaystyle \phi }$significa que todos en el grupo de agentes${\displaystyle {AGTS}}$sabe que${\displaystyle \phi }$Formalmente, esto corresponde a la siguiente fórmula:

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

Conocimiento general.

Conocimiento común de${\displaystyle \phi }$significa que todo el mundo lo sabe${\displaystyle \phi }$pero también que todo el mundo sabe que todo el mundo sabe${\displaystyle \phi }$, que todo el mundo sabe que todo el mundo sabe que todo el mundo sabe${\displaystyle \phi }$y así sucesivamente hasta el infinito . Formalmente, esto corresponde a la siguiente fórmula.

${\displaystyle C\phi$ :=E\phi \land EE\phi \land EEE\phi \land \ldots }

Como no permitimos la conjunción infinita, la noción de conocimiento común tendrá que introducirse como un concepto primitivo en nuestro lenguaje.

Antes de definir el lenguaje con este nuevo operador, vamos a dar un ejemplo introducido por Lewis que ilustra la diferencia entre las nociones de conocimiento general y conocimiento común. Lewis quería saber qué tipo de conocimiento se necesita para que la afirmación${\displaystyle p}$“Todo conductor debe conducir por la derecha” es una convención entre un grupo de agentes. En otras palabras, quería saber qué tipo de conocimiento se necesita para que todos se sientan seguros al conducir por la derecha. Supongamos que solo hay dos agentes.${\displaystyle i}$y${\displaystyle j}$Entonces todos lo saben${\displaystyle p}$(formalmente${\displaystyle Ep}$) no es suficiente. De hecho, aún podría ser posible que el agente${\displaystyle i}$considera posible que el agente${\displaystyle j}$no lo sabe${\displaystyle p}$(formalmente${\displaystyle \neg K_{i}K_{j}p}$). En ese caso el agente${\displaystyle i}$no se sentirá seguro conduciendo por la derecha porque podría considerar que el agente${\displaystyle j}$, sin saberlo${\displaystyle p}$, podría conducir por la izquierda. Para evitar este problema, podríamos entonces suponer que todo el mundo sabe que todo el mundo sabe que${\displaystyle p}$(formalmente${\displaystyle EEp}$). Esto tampoco es suficiente para garantizar que todos se sientan seguros al conducir por la derecha. De hecho, aún podría ser posible que el agente${\displaystyle i}$considera posible que el agente${\displaystyle j}$considera posible que el agente${\displaystyle i}$no lo sabe${\displaystyle p}$(formalmente${\displaystyle \neg K_{i}K_{j}K_{i}p}$). En ese caso y desde${\displaystyle i}$punto de vista,${\displaystyle j}$considera posible que${\displaystyle i}$, sin saberlo${\displaystyle p}$, conducirá por la izquierda. Entonces desde${\displaystyle i}$punto de vista,${\displaystyle j}$También podría conducir por la izquierda (siguiendo el mismo argumento que el anterior). Así que${\displaystyle i}$no se sentirá seguro conduciendo por la derecha. Razonamiento por inducción, Lewis demostró que para cualquier${\displaystyle k\in \mathbb {N} }$,${\displaystyle Ep\land E^{1}p\land \ldots \land E^{k}p}$No basta con que los conductores se sientan seguros al conducir por la derecha. De hecho, lo que necesitamos es una conjunción infinita. En otras palabras, necesitamos un conocimiento común de${\displaystyle p}$:${\displaystyle Cp}$.

Conocimiento distribuido.

Conocimiento distribuido de${\displaystyle \phi }$significa que si los agentes reunieran todo su conocimiento, sabrían que${\displaystyle \phi }$se sostiene. En otras palabras, el conocimiento de${\displaystyle \phi }$se distribuye entre los agentes. La fórmula${\displaystyle D_{A}\phi }$Se lee como "es conocimiento distribuido entre el conjunto de agentes".${\displaystyle A}$eso${\displaystyle \phi }$sostiene'.

La lógica epistémica es una lógica modal. Por lo tanto, lo que llamamos un modelo epistémico es...${\displaystyle {\mathcal {M}}=(W,R_{1},\ldots ,R_{n},I)}$es simplemente un modelo de Kripke tal como se define en la lógica modal. El conjunto${\displaystyle W}$es un conjunto no vacío cuyos elementos se llaman mundos posibles y la interpretación${\displaystyle I:W\rightarrow 2^{PROP}}$es una función que especifica qué hechos proposicionales (como 'Ann tiene la tarjeta roja') son verdaderos en cada uno de estos mundos. Las relaciones de accesibilidad${\displaystyle R_{j}\subseteq W\times W}$son relaciones binarias para cada agente${\displaystyle j\in AGTS}$; están diseñados para capturar la incertidumbre de cada agente (sobre el mundo real y sobre la incertidumbre de los otros agentes). Intuitivamente, tenemos${\displaystyle (w,v)\in R_{j}}$cuando el mundo${\displaystyle v}$es compatible con el agente${\displaystyle j}$información en el mundo${\displaystyle w}$o, en otras palabras, cuando el agente${\displaystyle j}$considera que el mundo${\displaystyle v}$podría corresponder al mundo${\displaystyle w}$(desde este punto de vista). Escribimos de forma abusiva${\displaystyle w\in {\mathcal {M}}}$para${\displaystyle w\in W}$y${\displaystyle R_{j}(w)}$denota el conjunto de mundos${\displaystyle \{v\in W;(w,v)\in R_{j}\}}$.

Intuitivamente, un modelo epistémico preciso${\displaystyle ({\mathcal {M}},w)}$, dónde${\displaystyle w\in {\mathcal {M}}}$, representa desde un punto de vista externo cómo es el mundo real${\displaystyle w}$es percibido por los agentes${\displaystyle {AGTS}}$.

Para cada modelo epistémico${\displaystyle {\mathcal {M}}}$, cada${\displaystyle w\in {\mathcal {M}}}$y cada${\displaystyle \phi \in {\mathcal {L}}_{\textsf {EL}}}$, definimos${\displaystyle {\mathcal {M}},w\models \phi }$inductivamente mediante las siguientes condiciones de verdad :

dónde${\displaystyle \left({\underset {j\in A}{\bigcup }}R_{j}\right)^{+}}$es el cierre transitivo de${\displaystyle {\underset {j\in A}{\bigcup }}R_{j}}$: tenemos eso${\displaystyle v\in \left({\underset {j\in A}{\bigcup }}R_{j}\right)^{+}(w)}$si, y solo si, hay${\displaystyle w_{0},\ldots ,w_{m}\in {\mathcal {M}}}$y${\displaystyle j_{1},\ldots ,j_{m}\in A}$de tal manera que${\displaystyle w_{0}=w,w_{m}=v}$y para todos${\displaystyle i\in \{1,\ldots ,m\}}$,${\displaystyle w_{i-1}R_{j_{i}}w_{i}}$.

A pesar de que la noción de creencia común debe introducirse como un elemento primitivo en el lenguaje, podemos observar que la definición de modelos epistémicos no tiene que modificarse para otorgar valor de verdad a los operadores de conocimiento común y distribuido.

Ejemplo de tarjeta:

Jugadores${\displaystyle A}$,${\displaystyle B}$y${\displaystyle C}$(que representan a Ann, Bob y Claire) juegan a las cartas con tres cartas: una roja, una verde y una azul. Cada uno tiene una sola carta, pero desconocen las cartas de los demás jugadores. Ann tiene la carta roja, Bob la verde y Claire la azul. Este ejemplo se representa en el modelo epistémico de puntos.${\displaystyle ({\mathcal {M}},w)}$representado a continuación. En este ejemplo,${\displaystyle AGTS:=\{A,B,C\}}$y${\displaystyle PROP:=\{{\color {red}{A}},{\color {green}{B}},{\color {blue}{C}},{\color {red}{B}},{\color {green}{C}},{\color {blue}{A}},{\color {red}{C}},{\color {green}{A}},{\color {blue}{B}}\}}$Cada mundo está etiquetado por las letras proposicionales que son verdaderas en este mundo y${\displaystyle w}$corresponde al mundo real. Hay una flecha indexada por agente.${\displaystyle j\in \{A,B,C\}}$de un mundo posible${\displaystyle u}$a un mundo posible${\displaystyle v}$cuando${\displaystyle (u,v)\in R_{j}}$. Se omiten las flechas reflexivas, lo que significa que para todos${\displaystyle j\in \{A,B,C\}}$y todo${\displaystyle v\in {\mathcal {M}}}$, tenemos eso${\displaystyle (v,v)\in R_{j}}$.

${\displaystyle {\color {red}{A}}}$significa  : "${\displaystyle A}$tiene la tarjeta roja ''

${\displaystyle {\color {blue}{C}}}$significa: "${\displaystyle C}$tiene la tarjeta azul ''

${\displaystyle {\color {green}{B}}}$significa: "${\displaystyle B}$tiene la tarjeta verde ''

etcétera...

Cuando las relaciones de accesibilidad son relaciones de equivalencia (como en este ejemplo) y tenemos que${\displaystyle (w,v)\in R_{j}}$, decimos que el agente${\displaystyle j}$no puede distinguir el mundo${\displaystyle w}$del mundo${\displaystyle v}$(o mundo)${\displaystyle w}$es indistinguible del mundo${\displaystyle v}$para agente${\displaystyle j}$). Así que, por ejemplo,${\textstyle A}$no puede distinguir el mundo real${\displaystyle w}$del mundo posible donde${\displaystyle B}$tiene la tarjeta azul (${\displaystyle {\color {blue}{B}}}$),${\displaystyle C}$tiene la tarjeta verde (${\displaystyle {\color {green}{C}}}$) y${\displaystyle A}$aún tiene la tarjeta roja (${\displaystyle {\color {red}{A}}}$).

En particular, se cumplen las siguientes afirmaciones:

${\displaystyle {\mathcal {M}},w\models ({\color {red}{A}}\land K_{A}{\color {red}{A}})\land ({\color {blue}{C}}\land K_{C}{\color {blue}{C}})\land ({\color {green}{B}}\land K_{B}{\color {green}{B}})}$

'Todos los agentes conocen el color de su tarjeta'.

${\displaystyle {\mathcal {M}},w\models K_{A}({\color {blue}{B}}\vee {\color {green}{B}})\land K_{A}({\color {blue}{C}}\vee {\color {green}{C}})}$

'${\displaystyle A}$sabe que${\displaystyle B}$tiene la tarjeta azul o la verde y eso${\displaystyle C}$tiene la tarjeta azul o la verde.

${\displaystyle {\mathcal {M}},w\models E({\color {red}{A}}\vee {\color {blue}{A}}\vee {\color {green}{A}})\land C({\color {red}{A}}\vee {\color {blue}{A}}\vee {\color {green}{A}})}$

'Todo el mundo sabe que${\displaystyle A}$tiene la tarjeta roja, verde o azul, y esto es de conocimiento común entre todos los agentes.

Utilizamos la misma notación.${\displaystyle K_{j}}$tanto para el conocimiento como para la creencia. Por lo tanto, dependiendo del contexto,${\displaystyle K_{j}\phi }$leerá 'el agente'${\displaystyle j}$Sabe que${\displaystyle \phi }$sostiene' o 'el agente${\displaystyle j}$Cree que${\displaystyle \phi }$se sostiene'. Una diferencia crucial es que, a diferencia del conocimiento, las creencias pueden ser erróneas : el axioma${\displaystyle K_{j}\phi \rightarrow \phi }$Esto se aplica únicamente al conocimiento, pero no necesariamente a la creencia. Este axioma, llamado axioma T (de Verdad), establece que si el agente conoce una proposición, entonces esta es verdadera. A menudo se considera el sello distintivo del conocimiento y no ha sido objeto de ningún ataque serio desde su introducción en el Teeteto de Platón .

La noción de conocimiento podría ajustarse a otras restricciones (o axiomas) como por ejemplo:${\displaystyle K_{j}\phi \rightarrow K_{j}K_{j}\phi }$: si agente${\displaystyle j}$Ella sabe algo, sabe que lo sabe. Estas limitaciones podrían afectar la naturaleza de las relaciones de accesibilidad.${\displaystyle R_{j}}$que luego pueden cumplir con algunas propiedades adicionales. Por lo tanto, ahora vamos a definir algunas clases particulares de modelos epistémicos que agregan algunas restricciones adicionales a las relaciones de accesibilidad.${\displaystyle R_{j}}$Estas restricciones se corresponden con axiomas particulares para el operador de conocimiento.${\displaystyle K_{j}}$. Debajo de cada propiedad, damos el axioma que define ^{[ 15 ]} la clase de marcos epistémicos que cumplen esta propiedad. (${\displaystyle K\phi }$representa${\displaystyle K_{j}\phi }$para cualquier${\displaystyle j\in AGTS}$.)

Analizamos los axiomas anteriores. El axioma 4 establece que si el agente conoce una proposición, entonces sabe que la conoce (este axioma también se conoce como el «principio KK» o la «tesis KK»). En epistemología, el axioma 4 tiende a ser aceptado por los internalistas , pero no por los externalistas . ^{[ 16 ]} Sin embargo, el axioma 4 es ampliamente aceptado por los científicos informáticos (pero también por muchos filósofos, incluidos Platón , Aristóteles , San Agustín , Spinoza y Schopenhauer , como recuerda Hintikka ). Un axioma más controvertido para la lógica del conocimiento es el axioma 5 para la euclidicidad: este axioma establece que si el agente no conoce una proposición, entonces sabe que no la conoce. La mayoría de los filósofos (incluido Hintikka) han atacado este axioma, ya que numerosos ejemplos de la vida cotidiana parecen invalidarlo. ^{[ 17 ]} En general, el axioma 5 se invalida cuando el agente tiene creencias erróneas, que pueden deberse, por ejemplo, a percepciones erróneas, mentiras u otras formas de engaño. El axioma B establece que no puede ser el caso que el agente considere posible que conozca una proposición falsa (es decir,${\displaystyle \neg (\neg \phi \land \neg K\neg K\phi )}$Si asumimos que los axiomas T y 4 son válidos, entonces el axioma B es vulnerable al mismo ataque que el del axioma 5, ya que este axioma es derivable. El axioma D establece que las creencias del agente son consistentes. En combinación con el axioma K (donde el operador de conocimiento se reemplaza por un operador de creencia), el axioma D es, de hecho, equivalente a un axioma D' más simple que transmite, quizás de forma más explícita, el hecho de que las creencias del agente no pueden ser inconsistentes:${\displaystyle \neg B\bot }$Los otros axiomas complejos .2, .3, .3.2 y .4 fueron introducidos por lógicos epistémicos como Lenzen y Kutchera en la década de 1970 ^{[ 10 ] [ 18 ]} y presentados para algunos de ellos como axiomas clave de la lógica epistémica. Pueden caracterizarse en términos de axiomas de interacción intuitiva que relacionan el conocimiento y las creencias. ^{[ 19 ]}

El sistema de prueba de Hilbert K para la lógica modal básica se define mediante los siguientes axiomas y reglas de inferencia : para todo${\displaystyle j\in AGTS}$,

Los axiomas de una lógica epistémica muestran obviamente la forma en que razonan los agentes. Por ejemplo, el axioma K junto con la regla de inferencia Nec implican que si yo sé${\displaystyle \phi }$(${\displaystyle K\phi }$) y sé que${\displaystyle \phi }$implica${\displaystyle \psi }$ (${\displaystyle K(\phi \rightarrow \psi ))}$entonces sé que${\displaystyle \psi }$(${\displaystyle K\psi }$). Se pueden agregar restricciones más fuertes. Los siguientes sistemas de prueba para${\displaystyle {\mathcal {L}}_{\textsf {EL}}}$Se utilizan con frecuencia en la literatura.

Definimos el conjunto de sistemas de prueba${\displaystyle \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}}\}}$.

Además, para todos${\displaystyle {\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}}$, definimos el sistema de prueba${\displaystyle {\mathcal {H}}^{\textsf {C}}}$agregando los siguientes esquemas axiomáticos y reglas de inferencia a los de${\displaystyle {\mathcal {H}}}$Para todos.${\displaystyle A\subseteq AGTS}$,

La fuerza relativa de los sistemas de prueba del conocimiento es la siguiente:

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

Entonces, todos los teoremas de${\displaystyle {\textsf {S4.2}}}$También son teoremas de${\displaystyle {\textsf {S4.3}},{\textsf {S4.3.2}},{\textsf {S4.4}}}$y${\displaystyle {\textsf {S5}}}$Muchos filósofos afirman que, en los casos más generales, la lógica del conocimiento es${\displaystyle {\textsf {S4.2}}}$o${\displaystyle {\textsf {S4.3}}}$. ^{[ 18 ] [ 20 ]} Típicamente, en ciencias de la computación y en muchas de las teorías desarrolladas en inteligencia artificial, se toma como lógica de la creencia ( lógica doxástica )${\displaystyle {\textsf {KD45}}}$y se considera que la lógica del conocimiento ( lógica epistémica ) es${\displaystyle {\textsf {S5}}}$, incluso si${\displaystyle {\textsf {S5}}}$es adecuado únicamente para situaciones en las que los agentes no tienen creencias erróneas. ^{[ 17 ]}${\displaystyle {\textsf {Br}}}$Floridi la ha propuesto como la lógica de la noción de "estar informado", que se diferencia principalmente de la lógica del conocimiento por la ausencia de introspección para los agentes. ^{[ 21 ]}

A pesar de${\displaystyle {\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}}$, la clase de${\displaystyle {\mathcal {H}}}$–modelos o${\displaystyle {\mathcal {H}}^{\textsf {C}}}$–modelos es la clase de modelos epistémicos cuyas relaciones de accesibilidad satisfacen las propiedades enumeradas anteriormente definidas por los axiomas de${\displaystyle {\mathcal {H}}}$o${\displaystyle {\mathcal {H}}^{\textsf {C}}}$. Entonces, para todos${\displaystyle {\mathcal {H}}\in \mathbb {L} _{\textsf {EL}}}$,${\displaystyle {\mathcal {H}}}$es sólido y muy completo para${\displaystyle {\mathcal {L}}_{\textsf {EL}}}$con respecto a la clase de${\displaystyle {\mathcal {H}}}$–modelos y${\displaystyle {\mathcal {H}}^{\textsf {C}}}$es sólido y muy completo para${\displaystyle {\mathcal {L}}_{\textsf {EL}}^{\textsf {C}}}$con respecto a la clase de${\displaystyle {\mathcal {H}}^{\textsf {C}}}$–modelos.

El problema de satisfacibilidad para todas las lógicas introducidas es decidible . A continuación, enumeramos la complejidad computacional del problema de satisfacibilidad para cada una de ellas. Nótese que se vuelve lineal en tiempo si solo hay un número finito de letras proposicionales en el lenguaje. Para${\displaystyle n\geq 2}$Si restringimos el anidamiento a un número finito de proposiciones, el problema de satisfacibilidad es NP-completo para todas las lógicas modales consideradas. Si además restringimos el lenguaje a un número finito de proposiciones primitivas, la complejidad se reduce a lineal en tiempo en todos los casos. ^{[ 22 ] [ 23 ]}

La complejidad computacional del problema de verificación de modelos pertenece al grupo P en todos los casos.

En esta sección, asumimos que todos los eventos son públicos. Comenzamos dando un ejemplo concreto donde se puede usar DEL, para comprender mejor lo que sucede. Este ejemplo se llama el rompecabezas de los niños embarrados . Luego, presentaremos una formalización de este rompecabezas en una lógica llamada Lógica de Anuncio Público (PAL). El rompecabezas de los niños embarrados es uno de los rompecabezas más conocidos que desempeñó un papel en el desarrollo de DEL. Otros rompecabezas significativos incluyen el rompecabezas de la suma y el producto , el dilema de Monty Hall , el problema de las cartas rusas , el problema de los dos sobres , ^la paradoja de Moore , la paradoja del ahorcado , etc. ^{[ 24} ]

Ejemplo de niños embarrados:

Tenemos dos niños, A y B, ambos sucios. A puede ver a B pero no a sí mismo, y B puede ver a A pero no a sí misma.${\displaystyle p}$Sea la proposición que afirma que A está sucio, y${\displaystyle q}$Sea la proposición que afirma que B está sucio.

1. Representamos la situación inicial mediante el modelo epistémico señalado.${\displaystyle ({\mathcal {N}},s)}$representados a continuación, donde las relaciones entre mundos son relaciones de equivalencia. Estados${\displaystyle s,t,u,v}$representar intuitivamente mundos posibles, una proposición (por ejemplo${\displaystyle p}$) que sea satisfacible en uno de estos mundos significa intuitivamente que en el mundo posible correspondiente, la interpretación intuitiva de${\displaystyle p}$(A está sucio) es verdadero. Los vínculos entre mundos etiquetados por agentes (A o B) expresan intuitivamente una noción de indistinguibilidad para el agente en cuestión entre dos mundos posibles. Por ejemplo, el vínculo entre${\displaystyle s}$y${\displaystyle t}$Etiquetado por A intuitivamente significa que A no puede distinguir el mundo posible.${\displaystyle s}$de${\displaystyle t}$y viceversa. En efecto, A no puede verse a sí mismo, por lo que no puede distinguir entre un mundo donde está sucio y otro donde no lo está. Sin embargo, sí puede distinguir entre mundos donde B está sucio o no, porque puede ver a B. Con esta interpretación intuitiva, llegamos a suponer que nuestras relaciones entre mundos son relaciones de equivalencia.

   

2. Ahora, supongamos que su padre viene y anuncia que al menos uno está sucio (formalmente,${\displaystyle p\vee q}$). Luego actualizamos el modelo y esto produce el modelo epistémico señalado que se representa a continuación. Lo que realmente hacemos es suprimir los mundos donde el contenido del anuncio no se cumple. En nuestro caso, este es el mundo donde${\displaystyle \neg p}$y${\displaystyle \neg q}$son ciertas. Esta supresión es lo que llamamos la actualización. Entonces obtenemos el modelo que se muestra a continuación. Como resultado del anuncio, tanto A como B saben que al menos uno de ellos está sucio. Podemos deducir esto del modelo epistémico.

   

3. Supongamos ahora que hay un segundo (y último) anuncio que dice que ninguno sabe que está sucio (un anuncio puede expresar hechos sobre la situación, así como hechos epistémicos sobre el conocimiento que poseen los agentes). Actualizamos entonces el modelo de forma similar, suprimiendo los mundos que no satisfacen el contenido del anuncio, o, equivalentemente, conservando los mundos que sí lo satisfacen. Este proceso de actualización produce el modelo epistémico puntuado que se representa a continuación. Al interpretar este modelo, obtenemos que tanto A como B saben que están sucios, lo que parece contradecir el contenido del anuncio. Sin embargo, si asumimos que A y B son razonadores perfectos y que esto es de conocimiento común entre ellos, entonces esta inferencia tiene perfecto sentido.

Lógica de anuncios públicos (PAL):

Presentamos la sintaxis y la semántica de la lógica de anuncios públicos (PAL), que combina características de la lógica epistémica y la lógica dinámica proposicional . ^{[ 25 ]}

Definimos el lenguaje${\displaystyle {{\mathcal {L}}_{PAL}}}$inductivamente mediante la siguiente gramática en BNF :

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

dónde${\displaystyle j\in AGTS}$.

El idioma${\displaystyle {{\mathcal {L}}_{PAL}}}$se interpreta sobre modelos epistémicos. Las condiciones de verdad para los conectores del lenguaje epistémico son las mismas que en la lógica epistémica (véase más arriba). La condición de verdad para la nueva modalidad de acción dinámica${\displaystyle [\psi$ !]\phi } se define de la siguiente manera:

dónde${\displaystyle {\mathcal {M}}^{\psi }:=(W^{\psi },R_{1}^{\psi },\ldots ,R_{n}^{\psi },I^{\psi })}$con

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

${\displaystyle R_{j}^{\psi }:=R_{j}\cap (W^{\psi }\times W^{\psi })}$a pesar de${\displaystyle j\in \{1,\ldots ,n\}}$y

${\displaystyle I^{\psi }(w):=I(w){\textrm {~for~all~}}w\in W^{\psi }}$.

La fórmula${\displaystyle [\psi$ !]\phi } intuitivamente significa que después de un anuncio veraz de${\displaystyle \psi }$,${\displaystyle \phi }$se sostiene. Un anuncio público de una propuesta${\displaystyle \psi }$modifica el modelo epistémico actual como se muestra en la figura siguiente.

El sistema de pruebas${\displaystyle {\mathcal {H}}_{PAL}}$Definido a continuación es sólido y muy completo para${\displaystyle {{\mathcal {L}}_{PAL}}}$con respecto a la clase de todos los modelos epistémicos señalados.

Los axiomas Rojo 1 - Rojo 4 se denominan axiomas de reducción porque permiten reducir cualquier fórmula de${\displaystyle {{\mathcal {L}}_{PAL}}}$a una fórmula demostrablemente equivalente de${\displaystyle {\mathcal {L}}_{EL}}$en${\displaystyle {\mathcal {H}}_{PAL}}$La fórmula${\displaystyle [q!]Kq}$es un teorema demostrable en${\displaystyle {\mathcal {H}}_{PAL}}$. Afirma que después de un anuncio público de${\displaystyle q}$, el agente sabe que${\displaystyle q}$sostiene.

PAL es decidible , su problema de verificación de modelos es resoluble en tiempo polinomial y su problema de satisfacibilidad es PSPACE-completo . ^{[ 26 ]}

El rompecabezas infantil "Muddy Children" se formalizó con PAL:

Aquí están algunas de las afirmaciones que se mantienen en el rompecabezas de los niños embarrados formalizado en PAL.

${\displaystyle {\mathcal {N}},s\models p\land q}$

'En la situación inicial, A está sucio y B está sucio'.

${\displaystyle {\mathcal {N}},s\models (\neg K_{A}p\land \neg K_{A}\neg p)\land (\neg K_{B}q\land \neg K_{B}\neg q)}$

«En la situación inicial, A no sabe si está sucio y B tampoco».

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

«Tras el anuncio público de que al menos uno de los niños A y B está sucio, ambos saben que al menos uno de ellos está sucio». Sin embargo:

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

«Tras el anuncio público de que al menos uno de los niños A y B está sucio, siguen sin saber que lo está». Además:

${\displaystyle {\mathcal {N}},s\models [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)}$

«Tras los sucesivos anuncios públicos de que al menos uno de los niños A y B estaba sucio y de que aún no sabían si lo estaban, A y B finalmente supieron que estaban sucios».

En esta última afirmación, observamos una característica interesante del proceso de actualización: una fórmula no es necesariamente verdadera después de ser anunciada. Esto es lo que técnicamente llamamos “autopersistencia”, y este problema surge para las fórmulas epistémicas (a diferencia de las fórmulas proposicionales). No se debe confundir el anuncio con la actualización inducida por este, que podría anular parte de la información codificada en el anuncio. ^{[ 27 ]}

En esta sección, asumimos que los eventos no son necesariamente públicos y nos centramos en los puntos 2 y 3 anteriores, es decir, en cómo representar los eventos y en cómo actualizar un modelo epistémico con dicha representación de eventos mediante una actualización del producto.

Modelo de evento

Los modelos epistémicos se utilizan para modelar cómo los agentes perciben el mundo real. Su percepción también puede describirse en términos de conocimiento y creencias sobre el mundo y sobre las creencias de los otros agentes. La idea del enfoque DEL es que se puede describir cómo los agentes perciben un evento de una manera muy similar. De hecho, la percepción que los agentes tienen de un evento también puede describirse en términos de conocimiento y creencias. Por ejemplo, el anuncio privado de${\displaystyle A}$a${\displaystyle B}$que su carta es roja también puede describirse en términos de conocimiento y creencias: mientras que${\displaystyle A}$cuenta${\displaystyle B}$que su tarjeta es roja (evento${\displaystyle e}$)${\displaystyle C}$cree que no pasa nada (evento)${\displaystyle f}$). Esto lleva a definir la noción de modelo de eventos, cuya definición es muy similar a la de un modelo epistémico.

Un modelo de eventos puntuales${\displaystyle ({\mathcal {E}},e)}$representa cómo el evento real representado por${\displaystyle e}$es percibido por los agentes. Intuitivamente,${\displaystyle f\in R_{j}(e)}$significa que mientras el posible evento representado por${\displaystyle e}$está ocurriendo, agente${\displaystyle j}$considera posible que el posible evento representado por${\displaystyle f}$Está ocurriendo realmente.

Un modelo de evento es una tupla${\displaystyle {\mathcal {E}}=(W^{\alpha },R_{1}^{\alpha },\ldots ,R_{m}^{\alpha },I^{\alpha })}$dónde:

• ${\displaystyle W^{\alpha }}$es un conjunto no vacío de eventos posibles ,
• ${\displaystyle R_{j}^{\alpha }\subseteq W^{\alpha }\times W^{\alpha }}$es una relación binaria llamada relación de accesibilidad en${\displaystyle W^{\alpha }}$, para cada${\displaystyle j\in AGTS}$,
• ${\displaystyle I^{\alpha }:W^{\alpha }\rightarrow {\mathcal {L}}_{\textsf {EL}}}$es una función llamada función de precondición que asigna a cada posible evento una fórmula de${\displaystyle {\mathcal {L}}_{\textsf {EL}}}$.

${\displaystyle R_{j}^{\alpha }(e)}$denota el conjunto${\displaystyle \{f\in W^{\alpha };(e,f)\in R_{j}^{\alpha }\}}$Nosotros escribimos${\displaystyle e\in {\mathcal {E}}}$para${\displaystyle e\in W^{\alpha }}$, y${\displaystyle ({\mathcal {E}},e)}$se denomina modelo de evento puntual (${\displaystyle e}$(a menudo representa el evento real).

Ejemplo de tarjeta:

Retomemos el ejemplo de la carta y supongamos que los jugadores${\displaystyle A}$y${\displaystyle B}$Se muestran sus tarjetas mutuamente. Resulta que,${\displaystyle C}$notó que${\displaystyle A}$mostró su tarjeta a${\displaystyle B}$pero no me di cuenta de eso${\displaystyle B}$lo hizo para${\displaystyle A}$Jugadores${\displaystyle A}$y${\displaystyle B}$Ten esto en cuenta. Este evento se representa a continuación en el modelo de eventos.${\displaystyle ({\mathcal {E}},e)}$.

El posible evento${\displaystyle e}$corresponde al evento real 'jugadores'${\displaystyle A}$y${\displaystyle B}$mostrar sus cartas respectivamente el uno al otro (con condición previa)${\displaystyle {\color {red}{A}}\land {\color {green}{B}}}$),${\displaystyle f}$representa el evento 'jugador'${\displaystyle A}$muestra su tarjeta verde (con condición previa)${\displaystyle {\color {green}{A}}}$) y${\displaystyle g}$representa el evento atómico 'jugador'${\displaystyle A}$muestra su tarjeta roja' (con condición previa)${\displaystyle {\color {red}{A}}}$). Jugadores${\displaystyle A}$y${\displaystyle B}$Los jugadores muestran sus cartas entre sí.${\displaystyle A}$y${\displaystyle B}$saber esto y considerar posible, mientras que el jugador${\displaystyle C}$considera posible que el jugador${\displaystyle A}$muestra su tarjeta roja y también considera posible que el jugador${\displaystyle A}$Le muestra su tarjeta verde, ya que él no conoce su tarjeta. De hecho, eso es todo lo que ese jugador${\displaystyle C}$considera posible porque no se dio cuenta de que${\displaystyle B}$mostró su tarjeta.

Otro ejemplo de modelo de evento se muestra a continuación. Este segundo ejemplo corresponde al evento por el cual el jugador${\displaystyle A}$Muestra su tarjeta roja públicamente a todo el mundo. Jugadora${\displaystyle A}$muestra su tarjeta roja, jugadores${\displaystyle A}$,${\displaystyle B}$y${\displaystyle C}$'Lo saben', jugadores${\displaystyle A}$,${\displaystyle B}$y${\displaystyle C}$"Saben" que cada uno de ellos "lo sabe", etc. En otras palabras, existe un conocimiento común entre los jugadores.${\displaystyle A}$,${\displaystyle B}$y${\displaystyle C}$ese jugador${\displaystyle A}$Le muestra la tarjeta roja.

Actualización del producto

La actualización del producto DEL se define a continuación. ^{[ 5 ]} Esta actualización produce un nuevo modelo epistémico específico.${\displaystyle ({\mathcal {M}},w)\otimes ({\mathcal {E}},e)}$representando cómo la nueva situación que anteriormente estaba representada por${\displaystyle ({\mathcal {M}},w)}$es percibido por los agentes después de la ocurrencia del evento representado por${\displaystyle ({\mathcal {E}},e)}$.

Dejar${\displaystyle {\mathcal {M}}=(W,R_{1},\ldots ,R_{n},I)}$ser un modelo epistémico y dejar${\displaystyle {\mathcal {E}}=(W^{\alpha },R_{1}^{\alpha },\ldots ,R_{n}^{\alpha },I^{\alpha })}$ser un modelo de evento. La actualización del producto de${\displaystyle {\mathcal {M}}}$y${\displaystyle {\mathcal {E}}}$es el modelo epistémico${\displaystyle {\mathcal {M}}\otimes {\mathcal {\mathcal {E}}}=(W^{\otimes },R_{1}^{\otimes },\ldots ,R_{n}^{\otimes },I^{\otimes })}$definido de la siguiente manera: para todos${\displaystyle v\in W}$y todo${\displaystyle f\in W^{\alpha }}$,

Si${\displaystyle w\in W}$y${\displaystyle e\in W^{\alpha }}$son tales que${\displaystyle {\mathcal {M}},w\models I^{\alpha }(e)}$entonces${\displaystyle ({\mathcal {M}},w)\otimes ({\mathcal {E}},e)}$denota el modelo epistémico señalado${\displaystyle ({\mathcal {M}}\otimes {\mathcal {E}},(w,e))}$Esta definición de actualización de producto tiene fundamentos conceptuales. ^{[ 6 ]}

Ejemplo de tarjeta:

Como resultado del primer evento descrito anteriormente (Jugadores${\displaystyle A}$y${\displaystyle B}$mostrar sus cartas el uno al otro frente al jugador${\displaystyle C}$), los agentes actualizan sus creencias. Obtenemos la situación representada en el modelo epistémico señalado.${\displaystyle ({\mathcal {M}},w)\otimes ({\mathcal {E}},e)}$A continuación. En este modelo epistémico específico, se cumple la siguiente afirmación:${\displaystyle ({\mathcal {M}},w)\otimes ({\mathcal {E}},e)\models ({\color {green}{B}}\land K_{A}{\color {green}{B}})\land K_{C}\neg K_{A}{\color {green}{B}}.}$Afirma que el jugador${\displaystyle A}$sabe que el jugador${\displaystyle B}$tiene la tarjeta pero el jugador${\displaystyle C}$'Cree' que no es así.

El resultado del segundo evento se representa a continuación. En este modelo epistémico específico, se cumple la siguiente afirmación:${\displaystyle ({\mathcal {M}},w)\otimes ({\mathcal {F}},e)\models C_{\{B,C\}}({\color {red}{A}}\land {\color {green}{B}}\land {\color {blue}{C}})\land \neg K_{A}({\color {green}{B}}\land {\color {blue}{C}})}$Afirma que existe conocimiento común entre${\displaystyle B}$y${\displaystyle C}$que conocen el verdadero estado del mundo (a saber,${\displaystyle A}$tiene la tarjeta roja,${\displaystyle B}$tiene la tarjeta verde y${\displaystyle C}$tiene la tarjeta azul), pero${\displaystyle A}$no lo sabe.

Basándose en estos tres componentes (modelo epistémico, modelo de eventos y actualización del producto), Baltag, Moss y Solecki definieron un lenguaje lógico general inspirado en el lenguaje lógico de la lógica dinámica proposicional ^{[ 25 ]} para razonar sobre el cambio de información y conocimiento. ^{[ 5 ] [ 6 ]}