La lógica epistémica dinámica (DEL) es un marco lógico que se ocupa del cambio de conocimiento e información. Normalmente, DEL se centra en situaciones que involucran a múltiples agentes y estudia cómo cambia su conocimiento cuando ocurren eventos . Estos eventos pueden cambiar propiedades reales del mundo real (se llaman eventos ónticos ): por ejemplo, una tarjeta roja se pinta de azul. También pueden provocar cambios de conocimiento sin cambiar las propiedades fácticas del mundo (se les llama eventos epistémicos ): por ejemplo, una carta se revela públicamente (o en privado) como roja. Originalmente, DEL se centró en eventos epistémicos. Sólo presentamos en esta entrada algunas de las ideas básicas del marco DEL original; Se pueden encontrar más detalles sobre DEL en general en las referencias.
Por la naturaleza de su objeto de estudio y su enfoque abstracto, DEL se relaciona y tiene aplicaciones a numerosas áreas de investigación, como la informática ( inteligencia artificial ), la filosofía ( epistemología formal ), la economía ( teoría de juegos ) y las ciencias cognitivas . En informática, DEL está, por ejemplo, muy relacionado con los sistemas multiagente , que son sistemas donde múltiples agentes inteligentes interactúan e intercambian información.
Como combinación de lógica dinámica y lógica epistémica , la lógica epistémica dinámica es un campo de investigación joven. Realmente comenzó en 1989 con la lógica de anuncio público de Plaza. [1] Independientemente, Gerbrandy y Groeneveld [2] propusieron un sistema que se ocupaba además del anuncio privado y que se inspiró en el trabajo de Veltman. [3] Otro sistema fue propuesto por van Ditmarsch cuya principal inspiración fue el juego Cluedo . [4] Pero el sistema más influyente y original fue el propuesto por Baltag, Moss y Solecki. [5] [6] Este sistema puede abordar todos los tipos de situaciones estudiadas en los trabajos anteriores y su metodología subyacente está fundamentada conceptualmente. Presentaremos en esta entrada algunas de sus ideas básicas.
Formalmente, DEL extiende la lógica epistémica ordinaria mediante la inclusión de modelos de eventos para describir acciones y un operador de actualización de producto que define cómo se actualizan los modelos epistémicos como consecuencia de la ejecución de acciones descritas a través de modelos de eventos. Primero recordaremos la lógica epistémica. Luego, las acciones y eventos entrarán en escena e introduciremos el marco DEL. [7]
La lógica epistémica es una lógica modal que trata de las nociones de conocimiento y creencia. Como lógica , se ocupa de comprender el proceso de razonamiento sobre el conocimiento y la creencia: ¿qué principios que relacionan las nociones de conocimiento y creencia son intuitivamente plausibles? Al igual que la epistemología, proviene de la palabra griega o "episteme", que significa conocimiento. Sin embargo, la epistemología está más preocupada por analizar la naturaleza misma y el alcance del conocimiento, abordando preguntas como "¿Cuál es la definición de conocimiento?" o “¿Cómo se adquiere el conocimiento?”. De hecho, la lógica epistémica surgió de la epistemología en la Edad Media gracias a los esfuerzos de Burley y Ockham. [8] El trabajo formal, basado en la lógica modal, que inauguró la investigación contemporánea sobre la lógica epistémica se remonta sólo a 1962 y se debe a Hintikka . [9] Luego desató en la década de 1960 discusiones sobre los principios de conocimiento y creencia y se propusieron y discutieron muchos axiomas para estas nociones. [10] Por ejemplo, los axiomas de interacción y a menudo se consideran principios intuitivos: si un agente sabe entonces también cree , o si un agente cree , entonces sabe que cree . Más recientemente, este tipo de teorías filosóficas fueron adoptadas por investigadores de economía , [11] inteligencia artificial e informática teórica [12] donde el razonamiento sobre el conocimiento es un tema central. Debido al nuevo entorno en el que se utilizó la lógica epistémica, se agregaron nuevas perspectivas y nuevas características, como cuestiones de computabilidad , a la agenda de investigación de la lógica epistémica.
En la secuela, es un conjunto finito cuyos elementos se denominan agentes y 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 y un operador de conocimiento distribuido . Formalmente, el lenguaje epistémico se define inductivamente mediante la siguiente gramática en BNF :
dónde y . El lenguaje epistémico básico es el lenguaje sin conocimiento común ni operadores de conocimiento distribuido. La fórmula es una abreviatura de (para un dado ), es una abreviatura de , es una abreviatura de y una abreviatura de .
Nociones de grupo: conocimientos generales, comunes y distribuidos.
En un entorno multiagente existen tres conceptos epistémicos importantes: conocimiento general, conocimiento distribuido y conocimiento común. Lewis estudió por primera vez la noción de conocimiento común en el contexto de las convenciones. [13] Luego fue aplicado a los 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 comúnmente conocidos.
Conocimientos generales.
Conocimiento general de significa que todos en el grupo de agentes lo saben . Formalmente, esto corresponde a la siguiente fórmula:
Conocimiento común.
El conocimiento común de significa que todo el mundo sabe, pero también que todo el mundo sabe, que todo el mundo sabe , que todo el mundo sabe, que todo el mundo sabe, que todo el mundo sabe , y así hasta el infinito . Formalmente, esto corresponde a la siguiente fórmula
Como no permitimos la conjunción infinita, la noción de conocimiento común deberá introducirse como primitiva en nuestro lenguaje.
Antes de definir el lenguaje con este nuevo operador, vamos a poner 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 : “todo conductor debe conducir por la derecha” sea una convención entre un grupo de agentes. En otras palabras, quería saber qué tipo de conocimientos se necesitan para que todos se sientan seguros al conducir por la derecha. Supongamos que solo hay dos agentes y . Entonces no basta con que todo el mundo lo sepa (formalmente ). De hecho, aún podría ser posible que el agente considere posible que no sepa (formalmente ). En ese caso el agente no se sentirá seguro conduciendo por la derecha porque podría considerar que el agente , sin saberlo , podría conducir por la izquierda. Para evitar este problema, podríamos asumir que todo el mundo sabe que todo el mundo lo sabe (formalmente ). Una vez más, esto no 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 considere posible que el agente considere posible que el agente no sepa (formalmente ). En ese caso y desde su punto de vista, considera posible que , sin saberlo , conduzca por la izquierda. Entonces, desde el punto de vista de, también podría conducir por la izquierda (con el mismo argumento anterior). Por lo tanto, no se sentirá seguro al conducir por la derecha. Razonando por inducción, Lewis demostró que para cualquier caso no es suficiente 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 conocimiento común de : .
Conocimiento distribuido.
Conocimiento distribuido de significa que si los agentes reunieran su conocimiento por completo, sabrían que eso es válido. En otras palabras, el conocimiento de se distribuye entre los agentes. La fórmula dice: "es conocimiento distribuido entre el conjunto de agentes que lo posee".
La lógica epistémica es una lógica modal. Entonces, lo que llamamos modelo epistémico es simplemente un modelo de Kripke tal como se define en la lógica modal. El conjunto es un conjunto no vacío cuyos elementos se denominan mundos posibles y la interpretación 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 son relaciones binarias para cada agente ; Su objetivo es capturar la incertidumbre de cada agente (sobre el mundo real y sobre la incertidumbre de los otros agentes). Intuitivamente, tenemos cuando el mundo es compatible con la información del agente en el mundo o, en otras palabras, cuando el agente considera que el mundo podría corresponder al mundo (desde este punto de vista). Escribimos abusivamente y denotamos el conjunto de mundos .
Intuitivamente, un modelo epistémico puntual , donde representa desde un punto de vista externo cómo los agentes perciben el mundo real .
Para cada modelo epistémico , todos y cada uno , lo definimos inductivamente por las siguientes condiciones de verdad :
donde está la clausura transitiva de : tenemos que si, y sólo si, hay y tales que y para todos ,.
A pesar de que la noción de creencia común debe introducirse como una primitiva en el lenguaje, podemos notar que la definición de modelos epistémicos no necesita ser modificada para dar valor de verdad a los operadores de conocimiento común y conocimiento distribuido.
Ejemplo de tarjeta:
Los jugadores y ( que representan a Ann, Bob y Claire) juegan un juego de cartas con tres cartas: una roja, una verde y una azul. Cada uno de ellos tiene una sola carta pero no conocen las cartas de los demás jugadores. Ann tiene la tarjeta roja, Bob tiene la tarjeta verde y Claire tiene la tarjeta azul. Este ejemplo se representa en el modelo epistémico puntiagudo que se representa a continuación. En este ejemplo, y . Cada mundo está etiquetado por las letras proposicionales que son verdaderas en este mundo y corresponden al mundo real. Hay una flecha indexada por agente desde un mundo posible a un mundo posible cuando . Se omiten las flechas reflexivas, lo que significa que para todos y todos tenemos eso .
significa: " tiene la tarjeta roja''
significa: " tiene la tarjeta azul''
significa: " tiene la tarjeta verde''
etcétera...
Cuando las relaciones de accesibilidad son relaciones de equivalencia (como en este ejemplo) y tenemos eso , decimos que el agente no puede distinguir mundo de mundo (o que el mundo es indistinguible del mundo para el agente ). Así, por ejemplo, no se puede distinguir el mundo real del mundo posible donde tiene la tarjeta azul ( ), tiene la tarjeta verde ( ) y todavía tiene la tarjeta roja ( ).
En particular, se sostienen las siguientes afirmaciones:
'Todos los agentes conocen el color de su tarjeta'.
' sabe que tiene la tarjeta azul o la verde y que tiene la tarjeta azul o la verde'.
'Todo el mundo sabe que tiene la tarjeta roja, la verde o la azul e incluso esto es de conocimiento común entre todos los agentes'.
Usamos la misma notación tanto para el conocimiento como para la creencia. Por lo tanto, dependiendo del contexto, se leerá "el agente sabe que sostiene" o "el agente B cree que sostiene". Una diferencia crucial es que, a diferencia del conocimiento, las creencias pueden ser erróneas : el axioma es válido sólo para el conocimiento, pero no necesariamente para las creencias. Este axioma llamado axioma T (de Verdad) establece que si el agente conoce una proposición, entonces esta proposición 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 cumplir con otras restricciones (o axiomas) tales como : si el agente sabe algo, sabe que lo sabe. Estas restricciones podrían afectar la naturaleza de las relaciones de accesibilidad que luego podrían cumplir con algunas propiedades adicionales. Entonces, ahora vamos a definir algunas clases particulares de modelos epistémicos que agregan algunas restricciones adicionales a las relaciones de accesibilidad . Estas restricciones van acompañadas de axiomas particulares para el operador del conocimiento . Debajo de cada propiedad, damos el axioma que define [15] la clase de marcos epistémicos que cumplen esta propiedad. ( significa cualquiera ).
Discutimos 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 “principio KK” o “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 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 de la euclididad: 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 queda invalidado 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 darse el caso de que el agente considere posible que conozca una proposición falsa (es decir, ). Si suponemos que los axiomas T y 4 son válidos, entonces el axioma B es víctima del mismo ataque que el 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 es reemplazado por un operador de creencia), el axioma D es de hecho equivalente a un axioma más simple D' que transmite, tal vez más explícitamente, el hecho de que las creencias del agente no pueden ser inconsistentes: . Los otros intrincados axiomas .2, .3, .3.2 y .4 han sido 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. Se pueden caracterizar en términos de axiomas de interacción intuitiva que relacionan conocimientos y creencias. [19]
El sistema de prueba de Hilbert K para la lógica modal básica está definido por los siguientes axiomas y reglas de inferencia : para todos ,
Los axiomas de una lógica epistémica obviamente muestran la forma en que razonan los agentes. Por ejemplo, el axioma K junto con la regla de inferencia Nec implican que si sé ( ) y sé que eso implica ( entonces sé que ( ). Se pueden agregar restricciones más fuertes. Los siguientes sistemas de prueba para se utilizan a menudo en la literatura. .
Definimos el conjunto de sistemas de prueba .
Además, para todos , definimos el sistema de prueba agregando los siguientes esquemas de axiomas y reglas de inferencia a los de . Para todos ,
La fuerza relativa de los sistemas de prueba del conocimiento es la siguiente:
Entonces, todos los teoremas de son también teoremas de y . Muchos filósofos afirman que en los casos más generales, la lógica del conocimiento es o . [18] [20] Normalmente, en informática y en muchas de las teorías desarrolladas en inteligencia artificial, se considera que la lógica de la creencia ( lógica doxástica ) es y la lógica del conocimiento ( lógica epistémica ) es , incluso si Sólo es adecuado para situaciones en las que los agentes no tienen creencias equivocadas. [17] ha sido propuesta por Floridi como la lógica de la noción de "estar informado" que difiere principalmente de la lógica del conocimiento por la ausencia de introspección por parte de los agentes. [21]
Para todos , la clase de –modelos o –modelos es la clase de modelos epistémicos cuyas relaciones de accesibilidad satisfacen las propiedades enumeradas anteriormente definidas por los axiomas de o . Entonces, para todo , es sólido y fuertemente completo para la clase de –modelos, y es sólido y fuertemente completo para la clase de –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 uno de ellos. Tenga en cuenta que se vuelve lineal en el tiempo si solo hay un número finito de letras proposicionales en el lenguaje. Por ejemplo , si nos restringimos al anidamiento finito, entonces el problema de satisfacibilidad es NP-completo para todas las lógicas modales consideradas. Si luego restringimos aún más el lenguaje a tener sólo un número finito de proposiciones primitivas, la complejidad desciende a lineal en el tiempo en todos los casos. [22] [23]
La complejidad computacional del problema de verificación del modelo está en P en todos los casos.
La lógica epistémica dinámica (DEL) es un marco lógico para modelar situaciones epistémicas que involucran a varios agentes y los cambios que ocurren en estas situaciones como resultado de la información entrante o, más generalmente, de la acción entrante. La metodología de DEL es tal que divide la tarea de representar las creencias y conocimientos de los agentes en tres partes:
Normalmente, un evento informativo puede ser un anuncio público a todos los agentes de una fórmula : este anuncio público y su correlativa actualización constituyen la parte dinámica. Sin embargo, los eventos epistémicos pueden ser mucho más complejos que un simple anuncio público, incluyendo ocultar información para algunos de los agentes, hacer trampa, mentir, fanfarronear, etc. Esta complejidad se aborda cuando introducimos la noción de modelo de evento. Primero nos centraremos en los anuncios públicos para tener una intuición de las principales ideas subyacentes de DEL.
En esta sección, asumimos que todos los eventos son públicos. Comenzamos dando un ejemplo concreto donde se puede utilizar DEL para comprender mejor lo que está sucediendo. 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 fangosos es uno de los rompecabezas más conocidos que jugó un papel en el desarrollo de DEL. Otros acertijos importantes incluyen el acertijo 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 hijos, 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. Sea la proposición que dice que A está sucia y la proposición que dice que B está sucia.
Lógica de anuncio público (PAL):
Presentamos la sintaxis y la semántica de la Lógica de Anuncio Público (PAL), que combina características de la lógica epistémica y la lógica dinámica proposicional . [25]
Definimos el lenguaje inductivamente mediante la siguiente gramática en BNF :
dónde .
El lenguaje se interpreta sobre modelos epistémicos. Las condiciones de verdad para los conectivos del lenguaje epistémico son las mismas que las de la lógica epistémica (ver arriba). La condición de verdad para la nueva modalidad de acción dinámica se define de la siguiente manera:
donde con
,
para todos y
.
La fórmula intuitivamente significa que después de un anuncio veraz de ella se cumple. Un anuncio público de una propuesta cambia el modelo epistémico actual, como se muestra en la siguiente figura.
El sistema de prueba que se define a continuación es sólido y muy completo para la clase de todos los modelos epistémicos puntuales.
Los axiomas Rojo 1 - Rojo 4 se llaman axiomas de reducción porque permiten reducir cualquier fórmula de a una fórmula demostrablemente equivalente de en . La fórmula es un teorema demostrable en . Afirma que después de un anuncio público de , el agente sabe que se cumple.
PAL es decidible , su problema de verificación de modelo se puede resolver en tiempo polinómico y su problema de satisfacibilidad es PSPACE-completo . [26]
Rompecabezas de niños embarrados formalizado con PAL:
Estas son algunas de las afirmaciones que se sostienen en el rompecabezas de los niños embarrados formalizado en PAL.
"En la situación inicial, A está sucio y B está sucio".
"En la situación inicial, A no sabe si está sucio y B tampoco".
"Después del 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:
'Después del anuncio público de que al menos uno de los niños A y B está sucio, todavía no saben que están sucios'. Además:
"Después de los sucesivos anuncios públicos de que al menos uno de los niños A y B está sucio y que todavía no saben si están sucios, A y B saben entonces que están sucios".
En esta última afirmación, vemos en funcionamiento una característica interesante del proceso de actualización: una fórmula no es necesariamente cierta después de ser anunciada. Eso 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 y la actualización inducida por este anuncio, 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 eventos y en cómo actualizar un modelo epistémico con tal representación de eventos mediante una actualización de producto.
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 a de que su tarjeta es roja también puede describirse en términos de conocimiento y creencias: mientras dice que su tarjeta es roja (evento ) cree que no pasa nada (evento ). Esto lleva a definir la noción de modelo de evento cuya definición es muy similar a la de un modelo epistémico.
Un modelo de evento puntual representa cómo los agentes perciben el evento real representado por . Intuitivamente, significa que mientras ocurre el posible evento representado por , el agente considera posible que el posible evento representado por esté ocurriendo realmente.
Un modelo de evento es una tupla donde:
denota el conjunto para el que escribimos y se denomina modelo de evento puntual ( a menudo representa el evento real).
Ejemplo de tarjeta:
Retomemos el ejemplo de las cartas y supongamos que los jugadores se muestran sus cartas entre sí. Resulta que se dio cuenta de que le mostró su tarjeta, pero no se dio cuenta de que lo hacía . Los jugadores ya lo saben. Este evento se representa a continuación en el modelo de evento .
El evento posible corresponde al evento real 'jugadores y se muestran sus cartas respectivamente entre sí' (con condición previa ), representa el evento 'el jugador muestra su tarjeta verde' (con condición previa ) y representa el evento atómico 'el jugador muestra su tarjeta roja' (con condición previa ). Los jugadores se muestran sus cartas entre sí, los jugadores lo saben y lo consideran posible, mientras que el jugador considera posible que muestre su tarjeta roja y también considera posible que muestre su tarjeta verde, ya que no conoce su tarjeta. De hecho, eso es todo lo que esa jugadora considera posible porque no se dio cuenta de que mostraba su carta.
A continuación se ofrece otro ejemplo de modelo de eventos. Este segundo ejemplo corresponde al evento en el que la jugadora muestra su tarjeta roja públicamente a todos. Jugadora muestra su tarjeta roja, jugadores , y 'lo saben', jugadores , y 'saben' que cada uno de ellos 'lo sabe', etc. En otras palabras, hay un conocimiento común entre los jugadores , y ese jugador muestra su tarjeta roja.
La actualización del producto DEL se define a continuación. [5] Esta actualización produce un nuevo modelo epistémico puntual que representa cómo los agentes perciben la nueva situación previamente representada por .
Sea un modelo epistémico y sea un modelo de evento. La actualización del producto de y es el modelo epistémico definido de la siguiente manera: para todos y todos ,
Si y son tales que entonces denota el modelo epistémico puntiagudo . Esta definición de actualización del producto está fundamentada conceptualmente. [6]
Ejemplo de tarjeta:
Como resultado del primer evento descrito anteriormente (Jugadores y mostrarse sus cartas frente al jugador ), los agentes actualizan sus creencias. Obtenemos la situación representada en el modelo epistémico señalado a continuación. En este modelo epistémico puntual, se cumple la siguiente afirmación: afirma que el jugador sabe que tiene la carta pero el jugador "cree" que no es así.
El resultado del segundo evento se representa a continuación. En este modelo epistémico puntual, se cumple la siguiente afirmación: . Afirma que hay conocimiento común entre ellos y que conocen el verdadero estado del mundo (es decir, tiene la tarjeta roja, tiene la tarjeta verde y tiene la tarjeta azul), pero no lo saben.
Con base en estos tres componentes (modelo epistémico, modelo de eventos y actualización de 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]
{{cite book}}
: CS1 maint: multiple names: authors list (link)