Lógica Epistémica Dinámica

TRABAJO DE FIN DE GRADO L´ogica Epist´emica Din´amica Propuestas para enfoques probabil´ısticos y aplicaciones Realizado por Alexander Romero Vinogradov Para la obtenci´on del t´ıtulo de Doble Grado en Matem´aticas y Estad´ıstica Dirigido por D. Andr´es Cord´on Franco Realizado en el departamento de Ciencias de la Computaci´on e Inteligencia Artificial Convocatoria de julio, curso 2022/23 Agradecimientos Agradezco a: Mis padres, por haberme tra´ıdo a este mundo, por haberme proporcionado siempre su cari˜no, su amor y la mejor educaci´on posible, y por haberme mantenido econ´omicamente mientras escrib´ıa textos absurdos sobre formalismos extra˜nos. Mi novia, por haberme apoyado siempre con su cari˜no y su amor incondicional, por cuidar de m´ı cuando lo necesito, y por seguir apoy´andome y cuid´andome incluso mientras escribo textos absurdos sobre formalismos extra˜nos. Mi tutor, Andr´es Cord´on Franco, por haberme guiado magn´ıficamente en la composici´on de este trabajo, por haber dirigido mi atenci´on a fuentes sugerentes y ´utiles que han inspirado muchas de mis ideas en el mismo, y por haber sido tan simp´atico y amable durante todo el proceso. El resto de los profesores que he tenido a lo largo de mi carrera, por hab´erme proporcionado una formaci´on imprescindible para escribir un trabajo como este. En particular, a Luis Valencia Cabrera por haberme puesto en contacto con Andr´es. Mi amigo Juan Luis, por haber sido el primero en mencionar la “l´ogica intensional de Kripke” en mi presencia, hecho que sin lugar a dudas plant´o en mi cabeza una semilla de curiosidad sin la cual probablemente este trabajo hubiese contado con un entusiasmo mucho menor por mi parte. Douglass R. Hofstadter, c´elebre pol´ımata, por haber escrito un magn´ıfico libro que siempre constituir´a una de mis inspiraciones fundamentales, aunque solo sea indirectamente, en esta clase de ´ambitos (y tambi´en en otros). David Mart´ınez Rubio, a quien pude considerar mi mentor durante un breve periodo (aunque probablemente ´el no me considere su aprendiz), por hab´erme recomendado un magn´ıfico libro de Douglass R. Hofstadter, por hab´erme inculcado el h´abito de contar en binario con los dedos de las manos, y por haber sido, en general, otra de mis grandes inspiraciones en esta clase de ´ambitos (y tambi´en en otros). Y a muchas m´as personas a las que tambi´en deber´ıa agradecer, pero que har´ıan de esta lista algo interminable, por haber contribuido conjuntamente a definir las actitudes hacia el mundo que me hacen ser la persona que soy. ¡Y, por ´ultimo, a m´ı mismo! (Y de nuevo a mi novia por darme la idea de acabar as´ı mis agradecimientos.) i ii Resumen En este trabajo hacemos un repaso de algunas de las principales propuestas en el ´area de la l´ogica epist´emica din´amica, rama de la l´ogica modal: l´ogica epist´emica (interpretada sobre la clase sem´antica S5), l´ogica epist´emica con anuncios p´ublicos y l´ogica epist´emica probabil´ıstica. Se exponen propiedades b´asicas y conceptos de inter´es para cada uno de estos sistemas, y se discuten en el contexto de ejemplos, muchos de ellos cl´asicos, que ponen de manifiesto su relevancia en diversos ´ambitos de la realidad pr´actica. En aras de integrar los sistemas anteriormente mencionados, y en part´ıcular la l´ogica epist´emica con anuncios p´ublicos y la l´ogica epist´emica probabil´ıstica, se propone una generalizaci´on de los anuncios p´ublicos que es coherente con los aspectos probabil´ısticos de nuestro lenguaje, y se estudian tambi´en las propiedades te´oricas b´asicas de esta propuesta. Se discuten varias conjeturas, de las que se espera obtener resultados adicionales en investigaciones futuras, sobre el comportamiento formal de esta nueva construcci´on. iii iv Abstract In this monograph we review some of the main proposals in the area of dynamic epistemic logic, a branch of modal logic: epistemic logic (interpreted on the semantic class S5), epistemic logic with public announcements and probabilistic epistemic logic. We set forth some of the basic properties and relevant concepts for each of these systems, which are discussed in the context of examples (many of which are classical problems in the field) which showcase their relevance in several scopes of application. For the sake of integrating the previous systems, and in particular epistemic logic with public announcements and probabilistic epistemic logic, a generalisation of public announcements which is coherent with the probabilistic aspects of our language is proposed, and the basic theoretical properties of this proposal are studied. We discuss some conjectures, for which aditional developments through further research are expected, about the formal behaviour of this new construction. v vi ´ Indice general 1. Introducci´on 1 2. L´ogica Modal Multiagente, L´ogica Epist´emica 5 2.1. Breve sinopsis hist´orica y conceptual . . . . . . . . . . . . . . . . . . . 5 2.1.1. Ilustraci´on preliminar: El Lucero del Alba . . . . . . . . . . . . 7 2.1.2. L´ogica Epist´emica . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Sintaxisysem´antica ............................ 10 2.3. Resultados b´asicos y conceptos importantes . . . . . . . . . . . . . . . 16 2.3.1. Familias de modelos interesantes . . . . . . . . . . . . . . . . . . 18 2.3.2. Bisimulaciones ........................... 21 3. Anuncios P´ublicos 25 3.1. Ideaymotivaci´on.............................. 25 3.2. Sintaxisysem´antica ............................ 27 3.3. Conceptos importantes . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4. L´ogica epist´emica probabil´ıstica 37 4.1. Ideaymotivaci´on.............................. 37 4.2. Sintaxisysem´antica ............................ 38 4.3. Propiedades y resultados b´asicos . . . . . . . . . . . . . . . . . . . . . . 42 5. L´ogica epist´emica probabil´ıstica din´amica 53 5.1. Ideaymotivaci´on.............................. 53 5.2. Pre´ambulo: la propuesta de Kooi . . . . . . . . . . . . . . . . . . . . . 54 5.3. Sintaxisysem´antica ............................ 56 5.4. Algunos ejemplos ilustrativos . . . . . . . . . . . . . . . . . . . . . . . 62 5.4.1. Ejemplo: Al´ı Bab´a y los nladrones ................ 62 5.4.2. Ejemplo: Incertidumbre Probabil´ıstica y Esencial (II) . . . . . . 66 5.5. Algunas propiedades del lenguaje LPK[ ] ................. 67 vii viii ´ INDICE GENERAL 6. Conocimiento Com´un 75 6.1. Ideaymotivaci´on.............................. 75 6.2. Sintaxis, sem´antica y propiedades b´asicas . . . . . . . . . . . . . . . . . 76 6.3. Algunosejemplos .............................. 78 6.3.1. N´umeros Consecutivos . . . . . . . . . . . . . . . . . . . . . . . 78 6.3.2. Ni˜nosconBarro........................... 80 6.3.3. Generales Bizantinos . . . . . . . . . . . . . . . . . . . . . . . . 85 7. Sistemas axiom´aticos 91 7.1. Ideaymotivaci´on.............................. 91 7.2. Sistemas axiom´aticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 7.2.1. LK.................................. 93 7.2.2. LKC ................................. 93 7.2.3. LK[ ] ................................. 94 7.2.4. LKC[ ] ................................ 95 7.2.5. LPK................................. 95 7.2.6. LPKC ................................ 97 7.2.7. LPK[ ] yLPKC[ ] ........................... 97 8. Conclusiones 99 Bibliograf´ıa 103 2.1. BREVE SINOPSIS HIST ´ ORICA Y CONCEPTUAL 7 futura), “siempre ha sido el caso que A” (l´ogica temporal en modalidad pasada). En nuestro trabajo no nos interesa en particular ninguno de los enfoques anteriores: m´as bien, nos centraremos en el enfoque epist´emico (del griego episteme, “conocimiento”), y quiz´a nos detengamos tangencialmente en el dox´astico (del griego doxa, “opini´on” o “creencia”); el lector podr´a intuir ya m´as o menos lo que implica cada uno de estos enfoques. Si es que se incluye alg´un aspecto que pudiese interpretarse como “temporal” en nuestros formalismos l´ogicos, ser´a en la componente din´amica, que tiene que ver m´as con las “transformaciones discretas de estados de conocimiento” que con un concepto m´as abstracto y “por s´ı mismo” de temporalidad; finalmente, tambi´en incluiremos elementos probabil´ısticos que van algo m´as all´a del enfoque modal b´asico, y requieren por lo tanto de construcciones adicionales para su estudio. Todos estos aspectos ir´an siendo propiamente introducidos a lo largo de los correspondientes cap´ıtulos del trabajo, empezando por el aspecto epist´emico, que introduciremos a continuaci´on; no obstante, antes de hacer esto, me gustar´ıa ilustrar de manera concreta al menos en una ocasi´on el concepto de “necesidad” m´as general, con un ejemplo que, como el lector ver´a, enlaza de maravilla con toda la conversaci´on filos´ofica sobre el conocimiento, la creencia, y la naturaleza limitada de nuestro acceso al y nuestra conceptualizaci´on del mundo. 2.1.1. Ilustraci´on preliminar: El Lucero del Alba El ejemplo a continuaci´on se ha extra´ıdo del art´ıculo de Stanford de L´ogica Intensional [8]. Coloquialmente, el planeta Venus es conocido como “El Lucero del Alba”, dado que a menudo puede observarse su brillo intenso en el cielo del amanecer. Similarmente, tambi´en se le llama a veces “El Lucero del Atardecer”, aunque esto es mucho m´as com´un en la esfera angloparlante (“The Evening Star”). Si bien a d´ıa de hoy sabemos que las etiquetas “Venus”, “El Lucero del Alba” y “El Lucero del Atardecer” se refieren en los tres casos al mismo objeto astron´omico (a saber, el planeta Venus), en principio, para una persona que ignore el contexto que hemos expuesto aqu´ı, esta equivalencia no es algo obvio. De esta forma, mientras que puede entenderse que las frases “El lucero del alba es el lucero del Atardecer” y “El lucero del alba es el planeta Venus” pueden aportar informaci´on nueva en determinadas situaciones, una frase como “El planeta Venus es el planeta Venus” nos choca como algo c´omicamente obvio. ¿C´omo es esto posible, si, en los tres casos, estamos reafirmando la equivalencia de tres objetos que efectivamente son “el mismo”? Como ya hemos observado m´as arriba, el estudio de este tipo de cuestiones no se limita al siglo pasado, sino que, de hecho, una parte importante de los esfuerzos en el desarrollo inicial de la l´ogica modal “moderna” buscan precisamente redescubrir unas categor´ıas de modalidad que se pueden hallar ya en la filosof´ıa, teolog´ıa y escol´astica medieval [9], y cuyos or´ıgenes pueden trazarse al menos hasta Arist´oteles2. Acerc´andonos algo m´as a nuestros tiempos, pueden tambi´en encontrarse ciertos para- 2¿A qui´en le sorprende? 8CAP´ ITULO 2. L ´ OGICA MODAL MULTIAGENTE, L ´ OGICA EPIST´ EMICA lelismos con el trabajo de Kant3, y m´as concretamente con la distinci´on entre juicios “a priori anal´ıticos” y “a priori sint´eticos” que este plantea en su Cr´ıtica de la Raz´on Pura [10], donde reflexiona sobre en qu´e medida y por qu´e mecanismos afirmaciones como 5 + 7 = 12 (secci´on tercera, cap´ıtulo 1: axiomas de la intuici´on) nos “aportan”, “producen” o “descubren” un conocimiento nuevo, que no ten´ıamos antes. No obstante, lo que s´ı nos proporciona la l´ogica modal, y m´as concretamente la sem´antica de Kripke “de los mundos posibles”, es un marco formal en el que razonar sobre este tipo de cuestiones con el rigor propio de una forma de proceder matem´atica. En particular, el ejemplo anterior plantea una situaci´on en la que agentes hipot´eticos pueden tener un conocimiento limitado del mundo, que despu´es puede ser actualizado a trav´es de afirmaciones que se les anuncian de alguna forma (“¿Recuerdas ese lucero del alba y ese lucero del atardecer de los que me has hablado alguna vez? ¡Pues resulta que son la misma cosa!”). Este es el tipo de situaciones, grosso modo, que se prestan naturalmente a ser estudiadas en L´ogica Epist´emica Din´amica. 2.1.2. L´ogica Epist´emica Dejemos por ahora de lado la parte “din´amica”, y centr´emonos en tratar de caracterizar antes de nada qu´e es lo que se supone que estudia la l´ogica epist´emica. Por la palabra epist´emica, puede deducirse que se trata de algo que tiene que ver con “el conocimiento”, pero, ¿qu´e es “el conocimiento”? Desde luego, hay muchos enfoques posibles a la hora de estudiar una cuesti´on tan amplia como esta (y muchos dir´ıan que es inabarcable). La epistemolog´ıa, por ejemplo, se hace preguntas sobre qu´e es lo que constituye un “conocimiento (cient´ıfico) adecuado” en relaci´on con los mecanismos que se emplean para su obtenci´on / fabricaci´on y los sesgos impl´ıcitos en cada uno de ellos, o incluso con el contexto social / institucional en el que debe ser producido. La gnoseolog´ıa, por otra parte, se preocupa m´as bien por cuestiones fenomenol´ogicas relativas a nuestro acceso a las experiencias del mundo y sobre c´omo estas nos producen “certezas”. Tambi´en pueden considerarse enfoques m´as t´ecnicos, como los desarrollados por Shannon o Kolmogorov en el contexto de una “teor´ıa de la informaci´on”, que tienen que ver con los aspectos cuantificables de la informaci´on (p.e., ¿Cu´anta informaci´on contiene un mensaje? ¿Qu´e recursos computacionales son necesarios para describir algo?). Pueden considerarse muchas otras posibilidades: desde los diversos enfoques psicol´ogicos hasta las interpretaciones de la probabilidad como “grado de certeza” o “certidumbre” sobre determinados hechos, pasando por los esfuerzos de diversos paradigmas de la inform´atica para desarrollar inteligencias artificiales que, de alguna manera, tendr´ıan que estar dotadas de una “capacidad para conocer” como requisito para poder calificarse realmente como inteligentes. Por supuesto, en ning´un momento debe entenderse que estos enfoques est´an de alguna manera mutuamente aislados; y, en particular, aunque la l´ogica epist´emica tiene su propio enfoque caracter´ıstico a la 3Aunque el trabajo de Kant no suele citarse como una de las principales influencias en el desarrollo de la l´ogica modal contempor´anea, consideramos que los paralelismos que pueden trazarse con otros trabajos son demasiado claros, que su influencia en el pensamiento moderno en general es demasiado amplia, y, sobre todo, que la posici´on de su trabajo en la cronolog´ıa del pensamiento moderno, as´ı como la naturaleza de su contenido, se ajustan demasiado bien al postulado de su influencia sobre el desarrollo de los nuevos enfoques que caracterizan a la l´ogica modal moderna como para ignorarlo. 2.1. BREVE SINOPSIS HIST ´ ORICA Y CONCEPTUAL 9 hora de aproximarse a esta cuesti´on, ser´ıa ingenuo decir que, en ´ultima instancia, est´a separada por completo del resto de la ciencia en su conjunto, como si de un diminuto archipi´elago de formalismo abstracto se tratase. ¿De qu´e manera podemos sintetizar, entonces, en qu´e consiste el enfoque caracter´ıstico de la l´ogica epist´emica? Trataremos de ofrecer una caracterizaci´on m´as o menos original. Lo esencial ser´ıa lo siguiente: la l´ogica epist´emica no se pregunta en ning´un momento cuestiones fundamentales como qu´e es el conocimiento oc´omo tenemos acceso a nuestras intuiciones m´as inmediatas, al menos no como base de su metodolog´ıa; por el contrario, la suposici´on b´asica de este enfoque es que se partir´a en todos los casos de un concepto preestablecido de lo que constituye un “hecho sobre el mundo”, o se operar´a siempre dentro de contextos donde la validez de la aplicaci´on de este tipo de consideraciones ser´a, al menos en un sentido funcional o pragm´atico, “evidente”. Partiendo de esta base, se definir´an formalismos que en cierto modo deber´an capturar las relaciones que de manera “natural” deber´ıa satisfacer cualquier construcci´on de conocimiento a partir de estos hechos, teniendo tambi´en en cuenta las diversas estructuras de accesibilidad que los diversos agentes “susceptibles de conocer” tienen respecto a cada uno de estos hechos. En particular, estos formalismos hacen naturalmente atractiva la posibilidad de razonar sobre formulaciones epist´emicas de orden superior, a saber, formulaciones sobre el conocimiento que un agente posee sobre el conocimiento que posee otro agente (con potencialmente infinitos grados de recursividad). La naturalidad con la que este tipo de razonamientos pueden aplicarse a ´areas como la teor´ıa de juegos es evidente, y se nos viene inmediatamente a la cabeza en el tipo de intrigas que caracterizan una parte significativa de los thrillers en la ficci´on contempor´anea. Un ´area que ha contribuido enormemente al desarrollo de la l´ogica epist´emica es el an´alisis de sistemas (inform´aticos) distribuidos – como manifiestan, sin ir m´as lejos, Ronald Fagin y Joseph Y. Halpern en su art´ıculo Reasoning about Knowledge and Probability [3], que citaremos profusamente en secciones posteriores de este trabajo. En principio, podr´ıa parecer algo extra˜no, dado que los componentes de estos sistemas no son “conscientes” en ning´un sentido evidente de la palabra (o al menos no lo han sido hasta el momento), y por lo tanto podr´ıa ser extra˜no imaginar que pueden “conocer” algo. No obstante, en muchos aspectos funcionales, los formalismos de la l´ogica epist´emica tambi´en resultan muy adecuados para describir los diversos estados en los que dichos sistemas distribuidos pueden encontrarse en distintos puntos del tiempo. Esto tiene sentido si consideramos la naturaleza asim´etrica del acceso y el intercambio de la informaci´on para cada componente en un sistema de este tipo. Un ejemplo cl´asico que veremos m´as adelante (en el cap´ıtulo 6) es el problema de los generales bizantinos, entre otros. Por ´ultimo, mencionamos brevemente una familia muy cercana de modelos l´ogicos, que constituyen la l´ogica dox´astica (de la creencia) dada la estrecha relaci´on filos´ofica que existe entre “conocer algo” y “creer en algo”. Efectivamente, uno de los debates centrales en la epistemolog´ıa desde, posiblemente, hace siglos gira en torno a la siguiente reflexi´on: es bastante claro que entre “saber algo” y “creer en algo que es verdad” hay una diferencia importante, dado que, grosso modo, puede que “creas en algo correcto por las razones equivocadas” - por ejemplo, el jugador que tras desperdiciar una fortuna en la m´aquina tragaperras, razona que como ya ha invertido tanto 10 CAP´ ITULO 2. L ´ OGICA MODAL MULTIAGENTE, L ´ OGICA EPIST´ EMICA dinero en el juego, le queda muy poco para ganar el gran premio, y acaba gan´andolo por casualidad a pesar de que su razonamiento es completamente falaz. En su c´elebre art´ıculo de 1963 [11], Gettier plantea ejemplos todav´ıa m´as interesantes de situaciones en las que, incluso cuando una creencia verdadera parece estar bien justificada, sigue sin ser del todo claro que debiera considerarse conocimiento. La cuesti´on es, entonces, tratar de caracterizar en qu´e consiste exactamente esa “brecha”. El estudio comparado de las l´ogicas epist´emica y dox´astica proporciona un posible enfoque en este respecto. 2.2. Sintaxis y sem´antica de los modelos de Kripke multiagentes La definici´on del lenguaje modal b´asico se construye sobre un conjunto finito de agentes A, que normalmente denotaremos con las primeras letras del alfabeto a,b,c ..., y en casos m´as generales a1,a2, ... , ak; y un conjunto numerable de ´atomos At, que denotaremos con las letras p,q,r..., y en casos m´as generales p1,p2, ... , pk, e incluir´an tambi´en a los s´ımbolos ⊤(tautolog´ıa / “siempre verdadero”) y ⊥(contradicci´on / “siempre falso”). Definici´on 2.1. Lenguaje modal multiagente b´asico. Sea At un conjunto numerable de ´atomos y Aun conjunto finito de agentes. Definimos el lenguaje modal (multiagente) b´asico LKinductivamente con la notaci´on de Backus-Naur (BNF): φ::= p| ¬φ|φ1∧φ2|Kaφ(2.1) donde p∈At ya∈A.□ Nota 2.1.Dado que esta ´ultima notaci´on no es del todo com´un, una breve aclaraci´on sobre su significado: “todos los ´atomos son f´ormulas”; “si φes una f´ormula, entonces ¬φtambi´en lo es”; “si φ1yφ2son f´ormulas, entonces φ1∧φ2tambi´en lo es”; “si φes una f´ormula, entonces Kaφtambi´en lo es”. □ Nota 2.2.Adem´as de las conectivas (¬,∧; “negaci´on l´ogica” y “conjunci´on l´ogica”, respectivamente) utilizadas en la definici´on anterior, utilizaremos varias notaciones convencionales t´ıpicas, cuyas definiciones, aunque probablemente sean conocidas m´as que de sobra por el lector, escribiremos a continuaci´on en aras de la exhaustividad: φ∨ψsignifica ¬(¬φ∧ ¬ψ); el s´ımbolo ∨se llamar´a “disyunci´on l´ogica”. φ→ψsignifica ¬φ∨ψ; el s´ımbolo →se llamar´a “implicaci´on l´ogica”. φ↔ψsignifica (φ→ψ)∧(ψ→φ); el s´ımbolo ↔se llamar´a “equivalencia l´ogica”. Adem´as, el lector habr´a percibido que, para evitar un uso tedioso y excesivo de los par´entesis, estamos asumiendo impl´ıcitamente ciertas “reglas de prioridad” de unas conectivas sobre otras. La jerarqu´ıa est´andar de prioridades ser´a, de mayor a 2.2. SINTAXIS Y SEM ´ ANTICA 11 menor prioridad: ¬,∧,∨,→,↔. En cuanto a los operadores modales (como Kao sus derivados), la prioridad de estos ser´a mayor que la de cualquier conectiva proposicional binaria. De la misma forma, utilizaremos tambi´en notaciones especiales para “abreviar” f´ormulas en las que aparezca el operador modal, Ka. De todas estas, quiz´a la m´as importante sea ˆ Kaφ, que significa ¬Ka¬φ, y nos referiremos a este nuevo operador como el “dual” de Ka. La definici´on del lenguaje modal b´asico podr´ıa haberse hecho perfectamente incluyendo todos estos s´ımbolos (conectivas adicionales y operador modal dual) como parte de la misma. Si no se ha hecho esto, es para evitar tener que incluir sus respectivas sem´anticas en la definici´on de verdad que daremos m´as adelante. □ Kayˆ Kason los llamados operadores epist´emicos, o, circunscribi´endonos a un contexto m´as general, operadores modales. En este trabajo los notamos con la letra “K” en referencia a la palabra inglesa “knows” (“conoce”), pero en otros contextos se utiliza una gran diversidad de notaciones alternativas. En el contexto de la l´ogica epist´emica, la f´ormula Kaφsuele leerse en lenguaje natural como “el agente aconoce φ / sabe que φ”, o simplemente “aconoce φ/asabe que φ”; por otra parte, la f´ormula ˆ Kaφsuele leerse como “aconsidera que φes posible”. De ah´ı que nos referiremos a ellos, de aqu´ı en adelante, como “operador conocimiento” y “operador posibilidad”, respectivamente. Para que el lector pueda hacerse una idea preliminar de la interpretaci´on de estos operadores epist´emicos, la ilustraremos con un ejemplo de c´omo se leer´ıan algunas f´ormulas en lenguaje natural. Por ejemplo: digamos que arepresenta al agente “Jos´e Arcadio”, brepresenta al agente “Mr. Brown”, y “p” es la afirmaci´on “Jos´e Arcadio sigue vivo”. Entonces las f´ormulas siguientes se podr´ıan leer como: Kap:Jos´e Arcadio sabe que (´el mismo) est´a vivo. ¬Kbp:Mr. Brown no sabe que Jos´e Arcadio est´a vivo. ˆ KaKbp:Jos´e Arcadio considera posible que Mr. Brown sepa que est´a vivo. ¬Kbˆ KaKbp: Mr. Brown no sabe que Jos´e Arcadio considera posible que Mr. Brown sepa que est´a vivo. En particular, las ´ultimas dos f´ormulas son ejemplos de proposiciones epist´emicas de orden superior. Nota 2.3.Una notaci´on m´as “cl´asica” y, en cierto modo, neutral, es la que utiliza los s´ımbolos “caja” (□a) y “diamante” (⋄a), respectivamente. Como ya adelantamos en la introducci´on, es com´un referirse al primer s´ımbolo como un “operador modal de necesidad”, y al segundo como un “operador modal de posibilidad”. M´as adelante en nuestro trabajo, veremos que “Ka”y“ˆ Ka” no son los ´unicos operadores modales que se ajustan a esta dicotom´ıa de necesidad y posibilidad (como adelanto, algunos otros “operadores modales de tipo necesidad” ser´an Ca(conocimiento com´un) y [φ](anuncio p´ublico), y algunos otros “de tipo posibilidad” ser´an ˆ Cay⟨φ⟩). Todos estos operadores ir´an por parejas, y se dir´a que son “duales” dado que satisfar´an las relaciones mutuas 12 CAP´ ITULO 2. L ´ OGICA MODAL MULTIAGENTE, L ´ OGICA EPIST´ EMICA ⋄φ≡ ¬□¬φy□φ≡ ¬⋄¬φ(la primera es por definici´on, la segunda se deducir´a de la sem´antica). □ Ya tenemos el esquema b´asico para construir cualquier f´ormula modal. Ahora tenemos que dotarlas de una sem´antica para poder razonar sobre su valor de verdad. Para ello tenemos que definir primero lo que es un modelo de Kripke. Definici´on 2.2. Modelo de Kripke multiagente. Dado un conjunto numerable de ´atomos At y un conjunto finito de agentes A, un modelo de Kripke (o de los mundos posibles) multiagente (o polimodal) es una estructura M=⟨S, RA, V At⟩donde: S es un conjunto de estados o “mundos”. Tambi´en nos referiremos a S como el dominio de M,D(M). RAes una aplicaci´on que, para cada a∈A, proporciona una “relaci´on de accesibilidad” RA a⊆S×S(es decir, un subconjunto arbitrario de tuplas del producto cartesiano de Spor s´ı mismo). VAt :At → P(S)es una “aplicaci´on evaluadora” que, para cada p∈At, proporciona un subconjunto VAt(p)⊆S(como se ver´a a continuaci´on cuando definamos la sem´antica, dicho subconjunto se interpretar´a como “el conjunto de los estados donde se satisface p”). □ Nota 2.4.A menudo prescindiremos de referencias expl´ıcitas a los conjuntos At yA, y notaremos simplemente M=⟨S, R, V ⟩(a veces utilizaremos par´entesis, (S, R, V ), en lugar de los “corchetes diamante”, simplemente porque nos resulta dif´ıcil recordar ser consistentes en un aspecto tan trivial). A veces tambi´en notaremos ∼en lugar de R, y∼aen lugar de Ra(principalmente utilizaremos esta notaci´on para expresar que se trata de una relaci´on de equivalencia 2.6). Otra notaci´on que utilizaremos t´ıpicamente es Rast en lugar de s, t ∈Ra; la notaci´on equivalente para ∼aser´a s∼at. En lenguaje natural, acostumbraremos a leer Rast como “tes accesible desde s(para el agente a)”. □ Definici´on 2.3. Definici´on de verdad en un modelo de Kripke multiagente. El valor de verdad de las f´ormulas modales multiagentes se eval´ua en tuplas (M, s) (modelo, estado), que llamaremos “modelos puntuados” o, abusando de la terminolog´ıa, simplemente “estados”, de la siguiente manera: M, s ⊨p sii s ∈V(p) M, s ⊨¬φ sii no se tiene M, s ⊨φ M, s ⊨φ∧ψ sii M, s ⊨φ y M, s ⊨ψ M, s ⊨Kaφ sii Para todo t ∈S:Rast =⇒M, t ⊨φ (2.2) Donde a∈Ayp∈At.□ 2.2. SINTAXIS Y SEM ´ ANTICA 13 Nota 2.5.A partir de la sem´antica anterior, el lector puede comprobar que la “cl´ausula sem´antica” para decidir si una proposici´on de la forma ˆ Kaφes verdadera en un modelo puntuado puede escribirse de la siguiente manera: M, s ⊨ˆ Kaφ sii Existe t ∈S:Rast y M, s ⊨φ(2.3) □ Nota 2.6.A partir de ahora, notaremos “No se tiene M, s ⊨φ” como M, s ⊭φ.□ En cualquier construcci´on te´orica siempre es importante tratar de dar un “sentido informal” a los formalismos que vamos construyendo, y sobre todo cuando utilizan terminolog´ıa tan sugerente como “mundos posibles” y “relaciones de accesibilidad”. De modo que, ¿qu´e es todo esto de los mundos posibles y las relaciones de accesibilidad? ¿Universos paralelos? ¿Portales ultradimensionales? Nada tan emocionante (aunque, por supuesto, los lectores m´as visionarios siempre son libres de dar cualquier interpretaci´on alternativa que les parezca adecuada e interesante). A efectos de nuestro planteamiento conceptual, un modelo de los mundos posibles es una forma de modelar la incertidumbre de los agentes en una situaci´on epist´emica, y la naturaleza limitada de su certeza sobre los hechos en el mundo. M´as concretamente, cada estado o “mundo posible” representa un conjunto de hechos que se podr´ıan dar de manera simult´anea, y las relaciones de accesibilidad de cada agente representan los conjuntos de situaciones que resultan indistinguibles para los agentes en cuesti´on desde sus respectivos puntos de vista. En este sentido, que un agente conozca un hecho significa que en todos los estados que le resultan indistinguibles desde el “real” se satisface este hecho; por otra parte, que un agente considere posible un hecho significa que en al menos uno de los estados que le resultan indistinguibles desde el “real” se satisface este hecho. Un lector sagaz podr´a percibir que, en general, los operadores de tipo necesidad se comportan de manera an´aloga a un cuantificador universal ∀, y los operadores de tipo posibilidad se comportan de manera an´aloga a un cuantificador existencial ∃. En realidad, puede considerarse que la l´ogica modal constituye un fragmento de la l´ogica de primer orden; para m´as detalles, consultar Van Benthem [2] (cap´ıtulo 7). Una forma c´omoda de representar modelos de Kripke que no sean demasiado complejos es a trav´es de esquemas gr´aficos. Ilustramos esto con un ejemplo cl´asico que aparece en Van Ditmarsch [1] (p´aginas 16-22). Ejemplo 2.1.Situaci´on Groningen-Liverpool-Otago (GLO). Consideremos la siguiente situaci´on: Anna, Bradley y Charles (a,byc) son tres amigos, residentes en Groningen, Liverpool y Otago, respectivamente. Supongamos que por alguna raz´on Anna decide desarrollar una teor´ıa sobre el tiempo que hace en Groningen y en Liverpool: en Groningen, o bien hace sol (g) o bien est´a nublado (¬g). An´alogamente en Liverpool, lo¬l. Si consideramos todos los estados contemplados en esta teor´ıa, obtenemos cuatro posibilidades, que podemos representar como ⟨g, l⟩,⟨g, ¬l⟩,⟨¬g, l⟩y⟨¬g, ¬l⟩. Dado que ase encuentra en Groningen, sabe el tiempo que hace all´ı, pero desconoce si en Liverpool hace o no hace sol; por lo tanto, los estados de la forma ⟨x, l⟩y⟨x, ¬l⟩, 14 CAP´ ITULO 2. L ´ OGICA MODAL MULTIAGENTE, L ´ OGICA EPIST´ EMICA Figura 2.1: Ilustraci´on del planteamiento inicial de la situaci´on GLO. con xfijo, son indistinguibles para a(esto lo escribir´ıamos como Ra⟨x, l⟩⟨x, ¬l⟩, o quiz´a como ⟨x, l⟩ ∼a⟨x, ¬l⟩). Obviamente, bse encuentra en una situaci´on an´aloga. Supongamos adem´as, por ´ultimo, que aybson conscientes de sus respectivas circunstancias4. Esquem´aticamente, esta situaci´on podr´ıa representarse como en la figura 2.1. En esta figura, las l´ıneas continuas representan las relaciones de accesibilidad del agente a, las l´ıneas discontinuas representan las relaciones de accesibilidad del agente b, y las l´ıneas mixtas representan que existen relaciones de accesibilidad de los dos agentes; en este caso, las l´ıneas mixtas corresponden a las relaciones reflexivas, es decir, las que hay desde cada estado a s´ı mismo. Dado que, como veremos m´as adelante 2.6, estas relaciones de accesibilidad siempre se tienen en los modelos epist´emicos, a menudo prescindiremos de ellas en las representaciones. Concluyamos este ejemplo con un precursor del tipo de situaciones que se considerar´an a partir de la parte din´amica de este trabajo. Supongamos que es de noche en Otago (por lo tanto es de d´ıa en Groningen y Liverpool), y c, que por alguna raz´on est´a despierto, decide llamar a sus amigos aybpor tel´efono para hablar sobre sus negocios conjuntos. Empieza llamando a a, que se encuentra en Groningen, y ale comenta casualmente que en Groningen hace un d´ıa soleado. Antes de finalizar la conversaci´on, cle dice (verazmente5) a aque a continuaci´on va a informar a b, con quien tambi´en tiene negocios, sobre todo lo que ha hablado con a. 4Aunque ahora mismo estamos utilizando esta noci´on de “ser conscientes de sus respectivas circunstancias” de manera algo informal, en el cap´ıtulo 6veremos que se puede formalizar rigurosamente a trav´es del operador de conocimiento com´un CB; por ahora, el lector puede simplemente considerar que esta noci´on simplemente hace referencia a que los agentes involucrados en el ejemplo tienen un mapa mental completo de la situaci´on que hemos descrito. 5A menos que se indique expl´ıcitamente lo contrario, en todos los ejemplos de este libro donde alg´un agente “diga”, “comente”, o de cualquier otra forma comparta con todos o con algunos de los agentes una afirmaci´on, se supondr´a que la afirmaci´on es veraz. Esta es otra de las limitaciones que 2.2. SINTAXIS Y SEM ´ ANTICA 15 Figura 2.2: Ilustraci´on de una situaci´on algo m´as compleja. Al finalizar la llamada, ase pregunta si cle hablar´a tambi´en a bsobre su comentario casual acerca del tiempo que hace en Groningen. De este modo, ase plantea dos (conjuntos de) estados posibles: el primero, que denotaremos como antes ⟨g, y⟩, donde ypuede referirse tanto a lcomo a ¬l, representar´a la situaci´on en la que se tenga g∧y∧ ¬Kbg, es decir, el estado en el que cno le ha transmitido a bla informaci´on de asobre el tiempo que hace en Groningen; el segundo, que denotaremos ⟨⟨g, y⟩⟩, representar´a el estado en el que se tenga g∧y∧Kbg(la otra posibilidad). Esta situaci´on es bastante m´as compleja que la original, pero un esquema como el de 2.2, donde las l´ıneas continuas representan las relaciones de accesibilidad del agente ay las discontinuas las del agente b(las reflexivas se han obviado), nos facilita enormemente su interpretaci´on. Alguien podr´ıa observar que, en realidad, este modelo no se ajusta a lo que nosotros hemos definido propiamente como Modelo de Kripke, dado que, adem´as de los conjuntos V(p), parecer´ıa que tenemos que considerar tambi´en un conjunto adicional V(Kbg), que no se corresponde con el valor de verdad de ninguna f´ormula at´omica, sino de una f´ormula m´as compleja. Esto es cierto, pero, por ahora, lo dejaremos de lado para regresar sobre ello cuando introduzcamos los aspectos din´amicos de nuestra l´ogica. Por el momento, qued´emonos con el siguiente mensaje: que este tipo de diagramas puede ser realmente ´util para resumir visualmente situaciones bastante complejas. □ Nota 2.7.Adem´as de las notaciones que ya hemos mencionado, otras abreviaturas importantes que utilizaremos en ocasiones ser´an EBφyˆ EBφ, donde B⊆Aes un subconjunto de los agentes. Dichas abreviaturas se definen, respectivamente, como: EBφ:= V a∈B Kaφ ˆ EBφ:= ¬EB¬φ algunos podr´ıan percibir de la l´ogica epist´emica: en principio, no plantea ninguna manera obvia de modelar situaciones, del todo comunes, en las que a alguno de los agentes le podr´ıa interesar mentir. En la conclusi´on de nuestro trabajo (8) trataremos de incluir algunas propuestas en este respecto. 16 CAP´ ITULO 2. L ´ OGICA MODAL MULTIAGENTE, L ´ OGICA EPIST´ EMICA Recordemos que el conjunto de agentes Asiempre ser´a finito en nuestras construcciones, lo que garantiza la buena definici´on de su sem´antica a partir de la sem´antica ya proporcionada. La elecci´on de la letra “E” hace referencia a la palabra “everybody” (todo el mundo) en ingl´es, dado que una forma natural de leer estas abreviaturas ser´ıa “Todos los agentes del conjunto Bsaben que φ” o “Alguno de los agentes del conjunto B consideran posible que φ”. Esta abreviatura se tratar´a a efectos pr´acticos como su propio operador. Observemos el aspecto “asim´etrico” de estos operadores: para que se tenga EBφ, tiene que darse que, para todos los agentes b∈B, se tenga Kbφ; en cambio, para que se tenga ˆ EBφ, basta con que haya un solo agente b∈Bpara el que Kbφ. Por ´ultimo, otra abreviatura de car´acter m´as t´ecnico es la correspondiente a la aplicaci´on iterada de operadores modales, a saber: Kk a:= KaKk−1 a, donde kes un n´umero natural mayor que 0 (y las respectivas para ˆ K,Eyˆ E), y K1 a:= Ka. Retomando nuestro ejemplo de Jos´e Arcadio y Mr. Brown, la f´ormula ˆ E3 Aˆ Kbp, con A={a, b}podr´ıa leerse como “Alguno entre Jos´e Arcadio y Mr. Brown considera posible que alguno entre Jos´e Arcadio y Mr. Brown considere posible que alguno entre Jos´e Arcadio y Mr. Brown considere posible que Mr. Brown considere posible que Jos´e Arcadio est´e vivo”. Naturalmente, vemos por qu´e el lenguaje natural no es el m´as adecuado para trabajar con este tipo de razonamientos - aunque, sin lugar a dudas, podemos estar seguros de que cualquiera que haya trabajado durante un tiempo en l´ogica epist´emica y haya obtenido alg´un resultado inveros´ımil en alg´un momento habr´a tratado de convencerse o disuadirse a s´ı mismo de su correcci´on pronunciando para s´ı mismo su “significado” en voz alta, con las esperanzas de que esto le proporcione alguna claridad adicional. □ 2.3. Resultados b´asicos y conceptos importantes En esta secci´on, como su nombre indica, presentaremos algunos resultados b´asicos y conceptos importantes que, con sus respectivas generalizaciones, ir´an apareciendo de manera recurrente a lo largo del resto de nuestro trabajo. A continuaci´on plantearemos un primer resultado que nos resultar´a de gran utilidad a la hora de razonar sobre la validez de f´ormulas en la medida en que dichos razonamientos no involucren la parte propiamente modal del lenguaje, y nos permitir´a, en resumen, hacer el mismo tipo de sustituciones, equivalencias y deducciones que si estuvi´esemos operando simplemente con f´ormulas de la l´ogica proposicional. Esto es sumamente conveniente, dado que el ´enfasis de nuestro trabajo estar´a casi exclusivamente en la parte modal, y un resultado as´ı nos ahorra much´ısimo tiempo que de otra forma tendr´ıamos que invertir en cuestiones t´ecnicas de inter´es escaso. La prueba de este resultado no se proporciona dado que puede considerarse “est´andar” en el campo, y, en todo caso, se trata de un resultado sumamente intuitivo. 2.3. RESULTADOS B ´ ASICOS Y CONCEPTOS IMPORTANTES 23 S1={s1} ∪ NS2={s2, ω} ∪ N R1={s1} × NR2={s2} × (N∪ {ω}) V1(pn) = {n}V2(pn) = {n} (2.5) El modelo M2tiene un estado adicional ωen el que ning´un ´atomo es cierto. En este caso, no es dif´ıcil ver que los modelos M1, s1yM2, s2no son bisimilares, dado que no se puede dar la condici´on de vuelta: en M2el estado ωes accesible desde s2, pero en M1no hay ning´un estado en el que ning´un ´atomo sea cierto que sea accesible desde s1. Veamos ahora que, sorprendentemente, dichos modelos s´ı son equivalentes. Demostraci´on. Procedemos por inducci´on estructural sobre las f´ormulas. Caso base. Obvio, dado que en s1y en s2no se satisface ning´un ´atomo. Hip´otesis de inducci´on. Sea φ∈ LKde profundidad a lo sumo m. Entonces M1, s1⊨φ⇐⇒ M2, s2⊨φ. Operadores negaci´on y conjunci´on. Se comprueban f´acilmente. Operador epist´emico. Sea φ=Kψ, con ψde profundidad a lo sumo m. Supongamos que φpuede distinguir ambos modelos (es decir, se tiene en uno de ellos pero no en el otro). Observemos que cada estado n∈Nsatisface las mismas f´ormulas en ambos modelos: efectivamente, cada uno satisface el ´atomo pncorrespondiente y no satisface ning´un otro, y, adem´as, desde estos estados ning´un estado es accesible (ni siquiera ´el mismo), de modo que las f´ormulas modales que se satisfacen para cada estado son las mismas en ambos modelos. Por lo tanto, la ´unica forma de φdistinga ambos modelos es que se tenga M1, s1⊨φpero no se tenga M2, s2⊨φ, o sea, que se tenga Mi, k ⊨ψ para todo k∈N,i= 1,2, pero que se tenga tambi´en M2, ω ⊭ψ. Ahora bien, la f´ormula ψes finita, por lo que solo aparece en ella a lo sumo una cantidad finita de ´atomos. Sea nel mayor natural tal que pnaparece en ψ. Claramente, los estados (n+ 1) y ωdeben coincidir en φ(M2, n + 1 ⊨ψ⇐⇒ M2, ω ⊨ψ). En particular, como M2, ω ⊭ψ, tenemos tambi´en que M2, n + 1 ⊨ψ. Pero esto contradice el hecho de que ψse tiene en todos los estados k∈N. Concluimos pues que, en efecto, se tiene M1, s1≡LKM2, s2. Q.E.D. □ 24 CAP´ ITULO 2. L ´ OGICA MODAL MULTIAGENTE, L ´ OGICA EPIST´ EMICA 3. L´ogica epist´emica din´amica con anuncios p´ublicos La exposici´on de este cap´ıtulo est´a basada principalmente en el cap´ıtulo 4 de Van Ditmarsch [1]. 3.1. Idea y motivaci´on En el cap´ıtulo anterior hemos presentado una l´ogica para razonar sobre situaciones de conocimiento que involucran a varios agentes, y, si bien en un ´ambito puramente te´orico el estudio de esta l´ogica y de las posibles construcciones que se pueden realizar en torno a ella ya nos ofrece una enorme variedad de v´ıas de investigaci´on de gran inter´es, en un contexto pr´actico podr´ıa ser razonable pedir algo m´as de nuestras herramientas conceptuales. M´as concretamente, el mundo – al margen de consideraciones filos´oficas en las que tratemos de concebir la sucesi´on de todos los instantes del tiempo como una simultaneidad en alg´un plano de abstracci´on superior al de nuestra experiencia cotidiana – es un lugar din´amico, caracterizado por una infinidad de cambios que se dan de un momento a otro, y que es importante tener en cuenta si queremos tratar de modelar alguna situaci´on real de manera pr´actica. Conceptualmente, y de manera provisional, podemos considerar b´asicamente dos tipos de cambios que pueden tener lugar en una situaci´on epist´emica, donde varios agentes razonan sobre el conocimiento que ellos mismos y los dem´as tienen sobre un determinado conjunto de hechos del mundo. El primer tipo tiene que ver con los cambios que se pueden dar en el mundo como tal, y en particular, en el conjunto de hechos que estar´ıan considerando los agentes. En este trabajo no se tratar´a este tipo de cambios, y tampoco son, por lo general, los que se est´an considerando cuando se habla de “l´ogica epist´emica din´amica”. M´as bien, se trata del segundo tipo de cambios: aquellos que tienen que ver con la informaci´on de la que disponen los propios agentes sobre un mismo conjunto de hechos, y con lo que las acciones y el comportamiento de estos mismos agentes revela ocomunica sobre la informaci´on de la que disponen. Un primer enfoque para modelar este tipo de cambios es el de los anuncios p´ublicos. Un modelo conceptual b´asico para pensar sobre los anuncios p´ublicos es el siguiente: adem´as de los agentes involucrados en la situaci´on epist´emica, existe tambi´en un “agente externo omnisciente”, que conoce tanto la situaci´on epist´emica como el estado actual del mundo, y que comunica informaci´on veraz a todos los agentes involucrados de forma p´ublica (es decir, de tal forma que cada uno de los agentes es consciente de que el resto de los agentes tambi´en han obtenido esta informaci´on), con la que dichos agentes actualizan sus modelos mentales de la situaci´on epist´emica. No obstante, existen situaciones m´as all´a de este modelo conceptual b´asico que tambi´en podr´ıan ser modeladas perfectamente con anuncios p´ublicos: sin ir m´as lejos, en una situaci´on en la que alguno de los agentes involucrados compartiese cierta informaci´on y el resto de los 25 26 CAP´ ITULO 3. ANUNCIOS P ´ UBLICOS agentes tuviesen garant´ıas de que esta informaci´on es veraz tambi´en podr´ıa considerarse que lo que ha tenido lugar es un anuncio p´ublico; no obstante, lo que se anuncia en este caso no es simplemente la informaci´on como tal, sino tambi´en el hecho de que el agente que la ha anunciado la conoc´ıa anteriormente (en t´erminos de nuestro lenguaje formal, lo que se anuncia no es φ, sino Kaφ). Por supuesto, los modelos de anuncios p´ublicos tienen grandes limitaciones, dado que no son capaces (por s´ı solos) de capturar la enorme complejidad y diversidad de situaciones comunicativas que pueden darse entre varios agentes epist´emicos (de hecho, la segunda parte del ejemplo que planteamos sobre la situaci´on GLO (2.1) ya no se ajustar´ıa a este paradigma, dado que el agente asabe que el agente cva a comunicar cierta informaci´on al agente b, pero no conoce exactamente el contenido de esta informaci´on); no obstante, los presentamos como “primera incursi´on” hacia la l´ogica epist´emica din´amica dado que puede considerarse que se tratan del “caso m´as simple” dentro de este ´ambito, y, con todas sus limitaciones, ya nos permiten atacar una cantidad considerable de problemas que de otra forma ser´ıa mucho m´as tedioso plantear y analizar con rigor. Sorprendentemente, no puede decirse que los anuncios p´ublicos, al menos por s´ı solos, sean estrictamente hablando imprescindibles para plantear el tipo de situaciones para las que fueron dise˜nados: como veremos m´as adelante, el lenguaje l´ogico LK[ ] (l´ogica epist´emica con anuncios p´ublicos) es igual de expresivo1que el lenguaje LK. Esto no significa que los anuncios p´ublicos sean un desprop´osito y que no merezca la pena estudiarlos: como m´ınimo, disponer de anuncios p´ublicos supone una ventaja enorme desde el punto de vista del “usuario”, tanto por la claridad conceptual que proporcionan como por simplificar enormemente las f´ormulas que se hace necesario manejar; y, como veremos en el cap´ıtulo 6, el lenguaje LKC[ ] s´ı que es m´as expresivo que el lenguaje LKC . Finalmente, y antes de proseguir con la presentaci´on formal del nuevo lenguaje, es importante hacer un peque˜no aviso: el modelo de anuncio p´ublico que vamos a presentar en este cap´ıtulo no es el ´unico que se ha propuesto, y tampoco me atrever´ıa a asegurar que es el “paradigm´atico” o el m´as ampliamente extendido y aceptado dentro del campo de la l´ogica epist´emica, aunque posiblemente lo sea2. En el cap´ıtulo 5 trabajaremos brevemente con un modelo de anuncios p´ublicos, utilizado en el art´ıculo de Kooi [4] sobre L´ogica Din´amica Probabil´ıstica, y tratado brevemente tambi´en en van 1En este trabajo mencionamos a veces el concepto de “expresividad”, o decimos que “un lenguaje es m´as expresivo que otro”, pero nunca estudiamos rigurosamente lo que esto quiere decir. La idea b´asica es la siguiente: dos lenguajes son igual de expresivos si para cualquier f´ormula en uno de ellos, existe una f´ormula equivalente (que toma los mismos valores de verdad en los mismos estados) en el otro, y viceversa; por lo tanto, un lenguaje Aser´a m´as expresivo que otro lenguaje Bsi todas las f´ormulas de Btienen una f´ormula equivalente en A, pero existe alguna f´ormula de Aque no tiene ninguna f´ormula equivalente en B. Si el lector est´a interesado en indagar m´as al respecto, lo referimos a van Ditmarsch [1] (cap´ıtulo 8). 2De paso, creo que con esto se hace apropiado mencionar algo importante sobre la l´ogica epist´emica, y m´as generalmente la l´ogica modal, como campos de investigaci´on, y es que se tratan de campos extremadamente heterog´eneos y poco estandarizados, al menos en comparaci´on con otros campos y en base a la min´uscula experiencia que tengo trabajando en el mismo. De hecho, conforme he ido avanzando en este trabajo, uno de los objetivos que me he propuesto ha sido el de proporcionar herramientas que puedan facilitar, al cabo del tiempo, una posible estandarizaci´on; aunque, desde luego, entiendo tambi´en los beneficios de tener un campo heterog´eneo y din´amico como el que tenemos ahora mismo. 3.2. SINTAXIS Y SEM ´ ANTICA 27 Ditmarsch [1] (cap´ıtulo 4, secci´on 9), distinto al que presentaremos aqu´ı. Hay varias razones por las que hemos considerado apropiado trabajar con este modelo de anuncios p´ublicos y no con alg´un otro, que podr´ıan resumirse en: i) Por continuidad con el modelo proporcionado en van Ditmarsch [1], que es una de nuestras referencias principales. ii) Porque consideramos que es el m´as apropiado para la l´ogica epist´emica, dado que, en cierto modo, “asegura” que los ´unicos anuncios p´ublicos que tenga sentido hacer sean precisamente aquellos que son veraces (el modelo de anuncios p´ublicos utilizado en Kooi [4] podr´ıa considerarse, por otra parte, m´as apropiado para situaciones dox´asticas). iii) Porque consideramos que el estudio del operador dual del “operador anuncio p´ublico” proporcionado por este modelo (esto se ver´a m´as adelante) tambi´en es de inter´es especial. iv) En definitiva, por preferencia personal. v) Y tambi´en porque, en todo caso, hab´ıa que tomar una decisi´on arbitraria sobre el modelo de anuncios p´ublicos que se presentar´ıa en este trabajo. 3.2. Sintaxis y sem´antica de la l´ogica epist´emica din´amica Definici´on 3.1. Sintaxis del lenguaje LK[ ].Dado un conjunto finito de agentes Ay un conjunto numerable de proposiciones at´omicas At, definimos el lenguaje epist´emico con anuncios p´ublicos LK[ ](A, At)(por lo general, como ya es costumbre, obviaremos AyAt en la notaci´on anterior) con la siguiente BNF: φ::= p| ¬φ|φ1∧φ2|Kaφ|[φ1]φ2(3.1) Con p∈At ya∈A.□ La nueva construcci´on que se ha introducido nos permite escribir f´ormulas de la forma [φ]ψ. Como veremos m´as adelante, el operador [ ] (operador de anuncio p´ublico o “corchetes caja”) es de tipo necesidad, de modo que, estrictamente, en lenguaje natural la f´ormula [φ]ψdeber´ıa leerse “despu´es de cualquier anuncio p´ublico y veraz de φse tiene ψ”; no obstante, dado que, como tambi´en veremos m´as adelante, este operador tiene la propiedad de ser funcional respecto a su interpretaci´on en el conjunto de los modelos de Kripke puntuados3, podemos permitirnos leerla de forma m´as simplificada como “tras anuncio p´ublico y veraz de φse tiene ψ”. El dual de [ ] se denotar´a ⟨ ⟩ (operador de anuncio p´ublico dual o “corchetes diamante”), y la f´ormula ⟨φ⟩ψse leer´a “tras alg´un anuncio p´ublico y veraz de φse tiene ψ”. Quiz´a ahora mismo la diferencia entre estos dos operadores pueda parecer demasiado sutil y esquiva, pero con la 3Es decir, dada una f´ormula φ, el conjunto de las f´ormulas {ψi}i∈Λdonde se satisface la f´ormula [φ]ψisolo depende del estado M, s donde esta se eval´ue. 28 CAP´ ITULO 3. ANUNCIOS P ´ UBLICOS correspondiente sem´antica y algunos ejemplos ilustrativos quedar´a todo mucho m´as claro. Nota 3.1.En contextos m´as generales, la palabra “anuncio” es a veces sustituida por “actualizaci´on” (mucho m´as apropiada, por ejemplo, en el contexto del an´alisis de sistemas distribuidos). □ Definici´on 3.2. Sem´antica de LK[ ].Dado un modelo de Kripke M=⟨S, R, V ⟩ con agentes Ay ´atomos At, M, s ⊨p sii s ∈V(p) M, s ⊨¬φ sii M, s ⊭φ M, s ⊨φ∧ψ sii M, s ⊨φ y M, s ⊨ψ M, s ⊨Kaφ sii Para todo t ∈S:Rast ⇒M, t ⊨φ M, s ⊨[φ]ψ sii (M, s ⊨φ) =⇒(M|φ, s ⊨ψ) ( %) (3.2) Donde M|φ=⟨S′, R′, V ′⟩se denomina “la restricci´on del modelo Ma la proposici´on φ”, y se define como sigue: S′=S(φ) := {s∈S|M, s ⊨φ} R′ a:= Ra∩(S′×S′) V′ p:= Vp∩S′ Y donde la marca ( %) indica que la cl´ausula debe ser evaluada perezosamente4. □ De nuevo, es importante tratar de comprender informalmente las construcciones que hemos definido de manera formal y rigurosa. En este caso, la intuici´on que hay tras el formalismo es bastante f´acil de ver: tras anunciarse p´ublicamente una determinada informaci´on, los agentes proceden a “actualizar” sus modelos mentales de la situaci´on, descartando todos los estados que son “incompatibles” con la informaci´on que han recibido, y continuan razonando en estos nuevos modelos actualizados. Ilustremos esto con un ejemplo b´asico, extra´ıdo parcialmente de van Ditmarsch [1]. Ejemplo 3.1.Ana (a), Benito (b) y Catalina (c) han extra´ıdo respectivamente una carta de un mont´on de tres, 0, 1 y 2, y todos ellos conocen com´unmente estas circunstancias. Ana ha extra´ıdo la carta 0, Benito ha extra´ıdo la carta 1 y Catalina ha extra´ıdo la carta 2. Obviamente, cada “jugador” conoce la carta que le ha tocado, pero no conoce las de los dem´as. Una forma de representar esta situaci´on es con el modelo de la figura 3.1, donde los estados vienen representados por ternas ABC, donde Arepresenta 4La evaluaci´on perezosa es una estrategia de evaluaci´on de expresiones que evita calcular el valor de sub-expresiones hasta que estos sean necesarios. Por ejemplo: una forma no-perezosa (impaciente) de evaluar la expresi´on 0 ∗(1+1) ser´ıa 0 ∗(1+ 1) = 0∗2 = 0. Una forma perezosa ser´ıa 0 ∗(1+ 1) = 0, haciendo uso de una regla que afirme que el producto de 0 por cualquier suma de naturales es tambi´en nula. En el caso de nuestra definici´on, el hecho de que la evaluaci´on sea perezosa significa que, si el antecedente es falso, no hay que evaluar el consecuente. La raz´on para especificar este detalle aparentemente irrelevante se expondr´a m´as adelante, pero, b´asicamente, lo que se busca es evitar problemas de indefinici´on. 3.2. SINTAXIS Y SEM ´ ANTICA 29 Figura 3.1: Estados posibles en el ejemplo 3.1. la carta que le ha tocado a a, y as´ı sucesivamente. Las l´ıneas continuas representan las relaciones de accesibilidad de a, las l´ıneas de puntos representan las relaciones de accesibilidad de b, y las l´ıneas discontinuas repreesentan las relaciones de accesibilidad de c(en todos casos obviando las relaciones reflexivas). En nuestro ejemplo, el estado actual del mundo es el 012. Digamos que los hechos se representan con ´atomos de la forma 0a, “atiene la carta 0”, y llamemos Hexa a nuestro modelo, por darle un nombre ingenioso. En este modelo y en el estado 012, se tiene que “Ana sabe que nadie m´as sabe cu´al es su carta”, que formalmente se escribir´ıa: Hexa, 012 ⊨Ka¬(Kb0a∨Kb1a∨Kb2a)∨(Kc0a∨Kc1a∨Kc2a) Supongamos ahora que un agente externo con informaci´on privilegiada, Donoso, anuncia p´ublicamente la proposici´on ¬1a(“Ana no tiene la carta 1”). Con esto, el modelo actualizado o restringido Hexa|¬1aquedar´ıa como en la figura 3.2, y en esta nueva situaci´on Ana sabe que o bien Benito o bien Catalina (pero no ambos) saben cu´al es su carta. Abreviando (Kx0y∨Kx1y∨Kx2y) como knowsx,y, esto se escribir´ıa: Hexa|¬1a,123 ⊨Ka(knowsb,a ∧ ¬knowsc,a)∨(knowsc,a ∧ ¬knowsb,a) El operador de anuncio p´ublico nos permite expresar la “transici´on” de un modelo a otro en una sola f´ormula: 30 CAP´ ITULO 3. ANUNCIOS P ´ UBLICOS Figura 3.2: Modelo actualizado con la proposici´on ¬1a. Figura 3.3: Modelo actualizado con la proposici´on Ka¬0b. Hexa, 012 ⊨Ka¬(knowsb,a ∨knowsc,a) ∧ [¬1a]Ka(knowsb,a ∧ ¬knowsc,a)∨(knowsc,a ∧ ¬knowsb,a) De hecho, quiz´a ser´ıa todav´ıa m´as apropiado utilizar en este caso el operador dual, pero dejaremos estas consideraciones para m´as adelante. Ahora supongamos que no es un agente externo quien hace el anuncio p´ublico, sino que es Ana quien anuncia p´ublicamente: “Benito no tiene la carta 0”. Los ´unicos estados en los que Ana sabe que Benito no tiene la carta 0, es decir, los estados en los que se tiene Ka¬0b, son precisamente aquellos donde es ella quien tiene esta carta. En esta nueva situaci´on (figura 3.3), los agentes bycconocen exactamente la distribuci´on de las cartas entre los jugadores, pero el agente ano la conoce. Esto tiene sentido, dado que la informaci´on que se ha anunciado p´ublicamente era algo que Ana ya sab´ıa, mientras que, para Benito y Catalina, la informaci´on s´ı aporta algo nuevo. De hecho, observamos, comparando este anuncio p´ublico con el que planteamos antes, que los anuncios p´ublicos de la forma [Kaφ] parecen revelar “m´as informaci´on” que anuncios p´ublicos “neutrales” [φ]. Esto tambi´en tiene sentido, dado que, al menos en modelos epist´emicos, la validez de una proposici´on Kaφimplica la validez de la proposici´on φ, pero el rec´ıproco (obviamente) no es cierto. □ 3.3. CONCEPTOS IMPORTANTES 31 Observaci´on 3.1.Evaluaci´on perezosa de los operadores de anuncio p´ublico. Antes de proseguir, es importante hacer un peque˜no apunte t´ecnico sobre este operador y su dual para evitar confusiones mayores en el futuro. Comenzamos observando que, de acuerdo a la definici´on general de los operadores duales, la f´ormula ⟨φ⟩ψ, en realidad una abreviatura de ¬[φ]¬ψ, se interpretar´ıa mediante la cl´ausula sem´antica: M, s ⊨⟨φ⟩sii (M, s ⊨φ)y(M|φ, s ⊨ψ)( %) (3.3) Tanto en el caso del operador “primal” como del operador dual, es importante que la cl´ausula se interprete evaluando de forma perezosa la parte derecha de la misma. Quiz´a un lector sagaz ya haya visto por qu´e esto es as´ı, pero, en cualquier caso, la raz´on no es compleja, y se puede ilustrar con un ejemplo extremadamente simple. Supongamos que Mes un modelo con un solo estado s, en el que se satisfacen los ´atomos pyq. ¿C´omo se interpretar´ıa entonces la validez de la f´ormula [¬p]qen el estado M, s? Tenemos que ver si se tiene (M, s ⊨p) =⇒(M|p, s ⊨q). No obstante, si evalu´asemos esta expresi´on de forma impaciente, nos encontrar´ıamos con un problema, dado que el conjunto de estados del modelo M|pes el vac´ıo, y, en particular, s∈ ∅. Dado que no sabemos interpretar la validez de f´ormulas sobre estados que no pertenecen al conjunto de estados del modelo, el resultado ser´ıa indefinido. En cambio, si evaluamos la expresi´on de forma perezosa y aplicamos la regla de que “si el antecedente de una implicaci´on es falso, entonces, independientemente del consecuente, esta es verdadera”, tendr´ıamos que la f´ormula se interpreta como verdadera – lo cual tiene sentido si consideramos que “del anuncio p´ublico de algo falso se puede deducir cualquier cosa”. El mismo problema lo tendr´ıamos si quisi´esemos interpretar la validez de ⟨¬p⟩q, y, de nuevo, la evaluaci´on perezosa nos lo resuelve si aplicamos la regla de que “si el primer t´ermino de una conjunci´on es falso, entonces, independientemente del segundo t´ermino, la conjunci´on es falsa”, y consideramos que el “aut´omata” encargado de interpretar estas expresiones siempre eval´ua en las conjunciones el primer t´ermino antes que el segundo. □ 3.3. Conceptos importantes de la l´ogica epist´emica con anuncios p´ublicos La primera propiedad que enunciaremos es de especial importancia en el contexto de la l´ogica epist´emica, ya que nos dice que si el modelo del que partimos es epist´emico, su restricci´on tras un anuncio p´ublico nos proporciona un modelo que sigue siendo epist´emico; esta propiedad, por lo tanto, es indispensable para poder hacer uso de los anuncios p´ublicos en este contexto. 32 CAP´ ITULO 3. ANUNCIOS P ´ UBLICOS Proposici´on 3.1.Sea M∈ S5 y φ∈ LK[ ]. Entonces M|φ∈ S5. Demostraci´on. Sea a∈Aun agente arbitrario. Si Raes la relaci´on de accesibilidad asociada a aen el modelo MyR′ aes la relaci´on de accesibilidad asociada a aen el modelo restringido, tenemos que comprobar tres cosas: R′ aes reflexiva. R′ aes sim´etrica. R′ aes transitiva. Reflexiva. Trivial. Sim´etrica. Sean s, t ∈S(φ) con (s, t)∈R′ a, esto es, (s, t)∈Ra∩S(φ)2. Por simetr´ıa de Ra, tenemos: (s, t)∈Ra=⇒(t, s)∈Ra Por otra parte, es obvio que (s, t)∈S(φ)2=⇒(t, s)∈S(φ)2. Usando ambas implicaciones, obtenemos finalmente: (t, s)∈R′ a Transitiva. Sean s, t, u ∈S(φ) con (s, t),(t, u)∈R′ a=Ra∩S(φ)2. Por transitividad de Ra, tenemos: (s, t),(t, u)∈Ra=⇒(s, u)∈Ra Y, obviamente, (s, t),(t, u)∈S(φ)2=⇒(s, u)∈S(φ)2. Usando ambas implicaciones, obtenemos finalmente: (s, u)∈R′ a Q.E.D. □ A continuaci´on presentamos varias propiedades y conceptos importantes, y a menudo sorprendentes, relacionados con el comportamiento del operador de anuncio p´ublico y su dual. Dado que se trata de muchas propiedades y que son bien conocidas en el campo, presentaremos la mayor´ıa de ellas sin demostraci´on. La primera tiene que ver con la relaci´on entre el operador de anuncio p´ublico y la negaci´on. Proposici´on 3.2.Anuncios p´ublicos y negaci´on. La f´ormula [φ]¬ψ↔(φ→ ¬[φ]ψ) es v´alida (en cualquier modelo de Kripke). □ 4.2. SINTAXIS Y SEM ´ ANTICA 39 bsabe que la probabilidad de que el agente asepa que la probabilidad del hecho psea mayor o igual que Qes mayor o igual que Q′”. M´as all´a de ver, una vez m´as, lo impracticable que ser´ıa hacer este tipo de razonamientos sin disponer de un formalismo adecuado, el lector podr´a percibir tambi´en que existe una dualidad entre que un agente “asigne” una probabilidad a un hecho y que el agente “sepa” cu´al es la probabilidad de este hecho, que en un principio podr´ıa resultar un tanto extra˜na. Grosso modo, el motivo de introducir esta dualidad es que, en determinadas situaciones, tiene sentido considerar que un agente asigne simult´aneamente varias probabilidades a un mismo hecho (lo veremos m´as claramente en los ejemplos). Aunque esta distinci´on pueda parecer inicialmente confusa, si se comprende y se usa adecuadamente puede dotar al formalismo de una enorme versatilidad respecto a otros que podr´ıan parecer “m´as naturales” a priori. Dado que, seg´un parece, este lenguaje introduce una nueva dimensi´on probabil´ıstica totalmente ajena a los conceptos “cl´asicos” de modalidad, resulta necesario definir una nueva familia de modelos para interpretarlo. Definici´on 4.2. Modelos de Kripke probabil´ısticos. Dado un conjunto numerable de ´atomos At y un conjunto finito de agentes A, un modelo de Kripke probabil´ıstico es una estructura M=⟨S, RA, V At,ΠA,At⟩, donde: La estructura ⟨S, RA, V At⟩define un modelo de Kripke. ΠA,At :A×S→Probs(S), donde Probs(S)es la notaci´on que usaremos para representar el conjunto de los espacios probabil´ısticos sobre subconjuntos de S. M´as concretamente, ΠA,At : (a, s)7→ ⟨S(a,s),A(a,s), Pr(a,s)⟩ donde: •S(a,s)⊆Ses el espacio muestral para aen s. •A(a,s)es un σ-´algebra sobre S(a,s). •Pr(a,s)es una medida de probabilidad sobre A(a,s)(Pr(a,s):A(a,s)→[0,1]). Como recordatorio, en cualidad de medida de probabilidad, Pr(a,s)debe satisfacer las siguientes propiedades [5]3: Pr(a,s)(S(a,s)) = 1 Pr(a,s)(E)≥0∀E∈A(a,s) (Aditividad numerable) Sean {Ek}∞ k=0 ⊆A(a,s)una familia numerable de conjuntos disjuntos en el σ-´algebra. En tal caso, se tiene: 3Tambi´en se ha propuesto, en este mismo campo, el uso de nociones no est´andar de probabilidad para resolver ciertas limitaciones de la noci´on “cl´asica”; el propio Halpern hace propuestas en esta direcci´on en su art´ıculo Lexicographic probability, conditional probability, and nonstandard probability [12]. 40 CAP´ ITULO 4. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA Pr(a,s)( ∞ [ k=0 Ek) = ∞ X k=0 Pr(a,s)(Ek) Como de costumbre, evitaremos hacer referencia expl´ıcita a AyAt a menos que las ambig¨uedades del contexto lo ameriten. □ Definici´on 4.3. Sem´antica de LPK.Dado un modelo de Kripke probabil´ıstico M=⟨S, R, V, Π⟩con agentes Ay ´atomos At, M, s ⊨p sii s ∈V(p), p ∈At M, s ⊨¬φ sii M, s ⊭φ M, s ⊨φ∧ψ sii M, s ⊨φ y M, s ⊨ψ M, s ⊨Kaφ sii Para todo t ∈S:Rast ⇒M, t ⊨φ M, s ⊨Pn (k=0) QkPra(φk)≥Q sii Pn k=0 QkPr∗(a,s)(S(a,s)(φk)) ≥Q (4.2) Donde: El conjunto S(a,s)(φ)se define como S(a,s)(φ) := {s∈S(a,s)|M, s ⊨φ} El asterisco ( ∗) en la funci´on de probabilidad denota que estamos utilizando la medida interior, es decir, Pr∗(a,s)(G) := sup{Pr(a,s)(E)|E∈A(a,s), E ⊆G} (La mayor de las medidas de subconjuntos de Sen el σ-´algebra.) □ Nota 4.1.Abusando de la notaci´on, escribiremos Pr∗(a,s)(φk) en lugar de Pr∗(a,s)(S(a,s)(φk)) □ Observaci´on 4.1.La raz´on por la que tenemos que recurrir a utilizar la medida interior para la sem´antica del operador probabil´ıstico es que, en principio, no siempre podemos asegurar que todos los conjuntos de la forma S(a,s)(φ) sean medibles (que est´en en el σ-´algebra). Tambi´en podr´ıa haberse hecho uso del concepto an´alogo de “medida exterior” (la menor de las medidas de subconjuntos de Sen el σ-´algebra), pero quiz´a resulte m´as natural hacerlo de esta manera, dado que de la otra pueden darse algunas situaciones un tanto extra˜nas (por ejemplo, podemos tener dos conjuntos disjuntos con medida exterior 1, lo cual traducido a los t´erminos de nuestra l´ogica implicar´ıa 4.2. SINTAXIS Y SEM ´ ANTICA 41 que podr´ıamos tener f´ormulas mutuamente contradictorias de forma que todas ellas evaluasen a probabilidad 1 para una misma asignaci´on). M´as adelante veremos ciertas condiciones suficientes para que todos los conjuntos considerados sean medibles. La principal ventaja de esto es que nos permitir´a definir una axiom´atica completa m´as sencilla y natural, aunque, como tambi´en veremos, el caso “no medible” tambi´en admite una axiom´atica completa. □ Como ya hemos hecho en cap´ıtulos anteriores, tratemos de dar cierto sentido informal a los formalismos que acabamos de definir. B´asicamente, la situaci´on que tendr´ıamos es la siguiente: adem´as de las relaciones de accesibilidad que ya ten´ıamos como parte de la sem´antica de Kripke, que configurar´ıan la parte modal de nuestro lenguaje y nos permitir´ıan razonar en t´erminos de “conocer” y “considerar posible”, a˜nadimos ahora tambi´en que, para cada agente aen cada estado s, se considera una distribuci´on de probabilidad sobre alg´un subconjunto (no vac´ıo) de S, sobre la cual se interpretar´ıa la parte probabil´ıstica del lenguaje. Obs´ervese que los conjuntos S(a,s) (espacio muestral de aen s) y Ra(s) := {t∈S|Rast}(conjunto de estados accesibles para adesde s) no tienen por qu´e coincidir; de hecho, ni siquiera tiene por qu´e ocurrir que el primero sea un subconjunto del segundo. Esto tiene varias “consecuencias imprevistas de interpretaci´on no trivial”, como que un agente pueda considerar posibles (utilizando la noci´on modal de posibilidad) varios estados del mundo asignando probabilidades solo a algunos de ellos; que considere posible un estado al que asigna una probabilidad nula; o, incluso, que asigne probabilidades positivas a estados que ni siquiera considera posibles. Todo esto, no obstante, debe verse como una ventaja por parte del formalismo, y no como una limitaci´on, dado que significa que el conjunto de situaciones que podemos representar es mucho m´as general de lo que podr´ıamos haber pensado en un principio; y, si queremos estudiar situaciones m´as concretas, basta con a˜nadir restricciones adicionales a la versi´on m´as general del formalismo. De hecho, estas consideraciones podr´ıan dar pie a que nos pregunt´asemos: ¿son los modelos epist´emicos (consider´andolos sin la parte probabil´ıstica) los m´as apropiados para plantear este tipo de situaciones? (¿O bajo qu´e circunstancias lo son?) De hecho, en el pr´oximo cap´ıtulo veremos que hay autores que consideran conveniente trabajar en una clase todav´ıa m´as general de modelos (a saber, la clase m´as general posible: el conjunto Kde todos los modelos de Kripke). En todo caso, aunque los conceptos y resultados m´as generales que presentamos en este trabajo no se limitan en su aplicaci´on y relevancia a los modelos en S5, en aras de la concreci´on trataremos de enmarcarlos siempre en el contexto de alguna situaci´on epist´emica. Nota 4.2.El lector habr´a observado que, en principio, el lenguaje que hemos definido solo incluye el constructor para f´ormulas de la forma Q1Pra( ) + ... +QkPra( ) ≥Q, y no para otras desigualdades e igualdades que podr´ıa resultar natural querer expresar. Por suerte, la mayor´ıa de estas puede expresarse a partir de la desigualdad que ya tenemos. Escribimos a continuaci´on algunos ejemplos: Q1Pra(φ1) + ... +QkPra(φk)< Q ⇐⇒ ¬(Q1Pra(φ1) + ... +QkPra(φk)≥Q) Q1Pra(φ1)+...+QkPra(φk)≤Q⇐⇒ (−Q1)Pra(φ1)+...+(−Qk)Pra(φk)≥ −Q 42 CAP´ ITULO 4. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA Q1Pra(φ1)+...+QkPra(φk) = Q⇐⇒ ((−Q1)Pra(φ1) + ... + (−Qk)Pra(φk)≥ −Q) ∧(Q1Pra(φ1) + ... +QkPra(φk)≥Q) Q1Pra(φ1)≥Q2Pra(φ2)⇐⇒ Q1Pra(φ1)−Q2Pra(φ2)≥0 Otra notaci´on de la que haremos uso habitualmente ser´a KP≥Q aφ, que ser´a una abreviatura de la expresi´on Ka(Pa(φ)≥Q). Esta abreviatura nos servir´ıa para expresar de manera concisa la afirmaci´on “el agente asabe que la probabilidad de φes mayor o igual que Q”, dado que, como vimos en nuestros ejemplos iniciales, debe distinguirse en nuestra sem´antica entre la asignaci´on de una probabilidad y el conocimiento de dicha asignaci´on. Finalmente, de manera an´aloga podr´ıamos definir otras notaciones como KP=Q a,KP<Q a, etc´etera. □ 4.3. Propiedades y resultados b´asicos de la l´ogica epist´emica probabil´ıstica Introducimos esta secci´on con un ejemplo de Halpern y Fagin [3] que nos permite observar la gran pluralidad de matices que es posible expresar con el lenguaje LPK, y, por otra parte, la importancia de tener en cuenta estos matices a la hora de modelar una situaci´on. Ejemplo 4.1.Incertidumbre probabil´ıstica e incertidumbre esencial. Consideremos la siguiente situaci´on: un sistema distribuido est´a constituido por dos nodos a yb. El nodo badmite un bit de input con valor 0 o 1. Una vez introducido el input, el mismo nodo simula el lanzamiento de una moneda justa, y realiza una acci´on Act si el input coincide con el resultado del lanzamiento (es decir, si el input es 1 y en el resultado del lanzamiento es cara, o el input es 0 y en el resultado del lanzamiento es cruz). El nodo adesconoce el valor del input introducido en b. Dado que el valor del input es conocido para b, es f´acil razonar que este nodo sabe que la probabilidad de realizar la acci´on Act (antes de haberse simulado el lanzamiento de la moneda) es de 1/2. Se podr´ıa razonar de forma similar para el nodo a, que no conoce el valor del input: por una parte, si el input de bes 0, entonces realizar´a la acci´on en el caso en que el resultado del lanzamiento sea cruz, hecho cuya probabilidad es 1/2; an´alogamente si el input de bes 1, entonces la acci´on se realizar´a si el resultado del lanzamiento es cara (probabilidad 1/2). Por lo tanto, independientemente del input de b, la probabilidad de que se realice Act es 1/2. Obs´ervese que este razonamiento no requiere de tener que especificar una distribuci´on de probabilidad sobre el valor del input introducido; en todo caso, si tal distribuci´on de probabilidad existiese, esto no afectar´ıa a nuestro argumento. Tratemos ahora de formalizar el argumento anterior en nuestro sistema. Tenemos cuatro estados posibles del mundo: (0, X), (0, C), (1, X), (1, C) (la primera componente representa el valor del input de b, y la segunda representa el resultado del lanzamiento de la moneda). Llam´emoslos respectivamente s1,s2,s3ys4, y sea Sel conjunto de estos cuatro estados. Consideremos las siguientes proposiciones at´omicas: 4.3. PROPIEDADES Y RESULTADOS B ´ ASICOS 43 Con Act denotamos el hecho de que se lleva a cabo Act Con C,Xdenotamos cada uno de los resultados del lanzamiento (cara y cruz, respectivamente). Con B0,B1denotamos cada uno de los posibles valores del input de b. Los nombres de los estados son autodescriptivos en cuanto a si se tiene o no en cada caso C,X,B0oB1. Los estados en los que se tiene Act son (0, X) y (1, C). Las relaciones de accesibilidad tambi´en est´an claras: para el nodo a, todos los estados son accesibles desde cualquier otro; para el nodo b, un estado es accesible desde otro si y solo si sus primeras componentes (es decir, el valor del input) coinciden. Nos queda una cuesti´on por resolver: la asignaci´on de probabilidades. A continuaci´on presentamos varias opciones para el nodo a(tambi´en habr´ıa que definir la asignaci´on de probabilidades del nodo b, pero en este ejemplo nos bastar´a con la del nodo apara ilustrar lo que nos interesa), todas ellas en principio razonables: i)Modelo M0. Podemos asociar a cada estado sel espacio muestral Sformado por todos los estados posibles. En principio esta podr´ıa parecer la opci´on m´as natural, dado que estamos considerando que el espacio muestral coincide en cada estado scon el conjunto de los estados accesibles (para a) desde s. Dado que asumimos que los eventos de introducir un input u otro no son probabil´ısticos, los ´unicos conjuntos medibles que podemos considerar, adem´as del vac´ıo y el total, son {(0, C),(1, C)}y{(0, X),(1, X)}(es decir, {s2, s4}y{s1, s3}), cada uno de ellos con probabilidad 1/2. ii)Modelo M1. Otra posibilidad es asociar a cada estado sel espacio muestral formado por aquellos estados cuyo input coincida con el del propio estado s. A los estados (0, X) y (0, C) se les asociar´ıa el espacio muestral {(0, X),(0, C)}, y los conjuntos medibles no triviales ser´ıan los unitarios con probabilidad 1/2 en cada caso; para los estados (1, X) y (1, C) tendr´ıamos lo an´alogo. iii)Modelo M2. Por ´ultimo, tenemos la opci´on trivial de asignar a cada estado s el espacio muestral formado por el propio estado s, con probabilidad 1 en cada caso. De estas tres opciones, la ´unica en la que el razonamiento informal que hemos expresado m´as arriba es correcto es en el modelo M1. En efecto, no es dif´ıcil comprobar que en cualquiera de los estados de este modelo se tiene KP=1/2 aAct. Como podemos observar en la figura 4.2, en cualquiera de los estados sel nodo considera posibles dos asignaciones de probabilidad, y en ambas se tiene que el conjunto S(a,s)(Act) (que en unos casos es el conjunto unitario {(0, X)}y en otros es el conjunto unitario {(1, C)}) tiene una probabilidad de exactamente 1/2. No es este el caso en el modelo M0 (figura 4.1), donde para todo estado sse tiene una misma asignaci´on de probabilidad, y en dicha asignaci´on el conjunto S(a,s)(Act) := {(0, X),(1, C)}no es medible, y su medida interior es nula. Finalmente, en el modelo M2 (figura 4.3) tenemos una situaci´on un tanto curiosa: en cualquier estado s, es posible o bien que Pa(Act) = 0 o bien que Pa(Act) = 1; esto es, que en todos los estados se tiene M2, s ⊨Ka(Pa(Act) = 1 ∨Pa(Act) = 0). Un comentario final sobre este ejemplo es que las consideraciones anteriores no 44 CAP´ ITULO 4. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA Figura 4.1: Representaci´on del modelo M0. Las “cajas punteadas” representan los subconjuntos medibles de cada espacio muestral. En este caso, el ´unico espacio muestral est´a representado con la caja de l´ıneas continuas. Las rectas continuas representan la relaci´on de accesibilidad del nodo a, y las rectas discontinuas representan la relaci´on de accesibilidad del nodo b. Figura 4.2: Representaci´on del modelo M1. 4.3. PROPIEDADES Y RESULTADOS B ´ ASICOS 45 Figura 4.3: Representaci´on del modelo M2. En este caso, cada estado se identifica con un espacio muestral. deben dar pie a la interpretaci´on de que el modelo M1 es “el correcto” en esta situaci´on. Una interpretaci´on m´as completa podr´ıa obtenerse considerando que los modelos M2 y M1 representan dos instantes sucesivos en la evoluci´on de un sistema (una consecuencia un tanto confusa de la forma de la que hemos decidido nombrar a nuestros modelos es que el instante correspondiente al modelo M2 ser´ıa cronol´ogicamente anterior al que corresponde al modelo M1). En el primer instante (modelo M2), el nodo b ya ha obtenido el input pero todav´ıa no ha realizado el lanzamiento de la moneda; por lo tanto, cada uno de los estados correspondientes se encuentra todav´ıa “indeterminado”, y se les pueden asignar distribuciones de probabilidad. En el segundo instante (modelo M1), el lanzamiento ya se ha realizado, y puede considerarse que no tiene ya sentido asignar a cada uno de los estados una probabilidad de 1/2, aunque, obviamente, el nodo ano conoce el resultado (de ah´ı que en todos los estados se tenga M2, s ⊨Ka(Pa(Act)=1∨Pa(Act) = 0)). Una forma de distinguir entre ambos tipos de incertidumbre es asignando nombres distintos a cada una de ellas: el primer tipo de incertidumbre (el nodo considera que existe una distribuci´on de probabilidad que gobierna un determinado subconjunto de estados) puede llamarse “incertidumbre probabil´ıstica”, mientras que el segundo tipo (el nodo no considera que exista ninguna distribuci´on de probabilidad gobernando un determinado subconjunto de estados) puede llamarse “incertidumbre esencial”; obviamente, en muchas ocasiones puede transformarse una situaci´on “esencialmente incierta” en otra “probabil´ısticamente incierta”, simplemente a˜nadiendo una distribuci´on de probabilidad que se adec´ue a las relaciones de accesibilidad de la situaci´on inicial, pero no est´a claro que esto pueda hacerse siempre de manera satisfactoria4. 4Un ejemplo sencillo ser´ıa un modelo cuyos estados fueran los n´umeros naturales, y cuya relaci´on de accesibilidad fuese la total (cualquier estado es accesible desde cualquier otro). Sabemos que no existen medidas de probabilidad sobre los n´umeros naturales tales que a cada conjunto unitario se le asigne una medida no nula de forma equiprobable; por lo tanto, tendr´ıamos que prescindir de esta probabilidad y “privilegiar” a unos estados sobre otros, lo cual podr´ıa no ser deseable dependiendo de la situaci´on que estuviesemos tratando. 46 CAP´ ITULO 4. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA □ El ejemplo anterior nos muestra c´omo una situaci´on que en principio puede parecer sencilla ya se presta a bastantes consideraciones en cuanto a c´omo se deben asignar los espacios probabil´ısticos. En particular, el ejemplo nos permite ver que hay muchas situaciones en las que no es deseable tomar S(a,s)=Ra(s) (de hecho, el ´unico de los modelos anteriores en el que se satisfac´ıa esta propiedad, M0, es el ´unico para el que no hemos podido encontrar una interpretaci´on adecuada en el contexto de nuestro ejemplo, a pesar de que, inicialmente, lo planteamos como el candidato m´as “natural”). No obstante, podemos observar que una condici´on que s´ı satisface cada uno de los modelos anteriores es que S(a,s)⊆Ra(s). Esta es una propiedad que en la mayor´ıa de los contextos podr´ıamos considerar “bastante natural”, dado que, en ausencia de esta, un agente podr´ıa asignar probabilidades positivas sobre hechos que no considerase posibles. Podr´ıa decirse que un agente que asigna probabilidades positivas a hechos que considera imposibles es inconsistente; por lo tanto, bautizaremos esta propiedad como CONS (de consistencia). Definici´on 4.4. CONS. Decimos que un modelo de Kripke probabil´ıstico satisface la propiedad CONS si para todo a∈Ays∈S, se tiene S(a,s)⊆Ra(s). □ Obs´ervese que esta propiedad no implica s∈S(a,s), es decir, un agente no tiene por qu´e considerar que el estado en el que se encuentra forme parte del espacio muestral en su asignaci´on de probabilidad. Si bien esto puede parecer tambi´en un tanto extra˜no, hay situaciones en las que puede resultar apropiado. Para una discusi´on m´as pormenorizada de este tipo de situaciones, referimos al lector al art´ıculo de Halpern y Fagin [3] y a las fuentes que estos citan en el mismo en relaci´on con esta cuesti´on. Otra propiedad que podr´ıamos considerar deseable en ciertas situaciones es que las distribuciones de probabilidad sean “objetivas”, es decir, que sean compartidas por todos los agentes; esto es apropiado en muchas de las situaciones t´ıpicas que se estudian en teor´ıa de juegos, donde los “jugadores” deben conocer com´unmente un conjunto de hechos para que el “juego” tenga sentido. Regresando al ejemplo anterior, un motivo posible para considerar que el modelo M2 es “m´as adecuado” que el modelo M1 para representar la situaci´on tras el lanzamiento de la moneda ser´ıa precisamente este: si, adem´as de las asignaciones de probabilidad del nodo a, consideramos tambi´en las del b, no tendr´ıa ning´un sentido que este siguiese asignando probabilidad 1/2 al evento “se ha realizado la acci´on Act”; por lo tanto, si queremos hacer coincidir las asignaciones de probabilidad de ambos nodos, en principio parecer´ıa que este es el modelo que deber´ıamos elegir para representar la situaci´on. Definici´on 4.5. OBJ. Decimos que un modelo de Kripke probabil´ıstico satisface la propiedad OBJ si se tiene Π(a,s)= Π(b,s)para todo s∈Sya, b ∈A. □ Otras propiedades que pueden ser naturales en ciertos contextos tienen que ver con la relaci´on entre estados y asignaciones de probabilidad. Por ejemplo, podr´ıa interesarnos imponer que la asignaci´on de probabilidad de un agente asea la misma en 4.3. PROPIEDADES Y RESULTADOS B ´ ASICOS 47 todos los estados que el agente considera posibles desde un estado dado. Llamemos SDP (Space Determined Probability) a esta propiedad. Definici´on 4.6. SDP. Decimos que un modelo de Kripke probabil´ıstico satisface la propiedad SDP si para todo a∈Ays, t ∈S, si Rast entonces Π(a,s)= Π(a,t). □ De los tres modelos de nuestro ejemplo anterior, solo M0 satisface SDP. No obstante, M1 yM2 satisfacen una llamada uniformidad que, como veremos ahora, puede considerarse en cierto sentido como una relajaci´on de SDP. Definici´on 4.7. UNIF. Decimos que un modelo de Kripke probabil´ıstico satisface UNIF si para todo a∈A,s, t ∈S, si t∈S(a,s)entonces Π(a,s)= Π(a,t). □ Una forma de interpretar esta propiedad es que, si bien la asignaci´on de probabilidades para un agente ano es la misma en todos los estados que considera posible, al menos es posible particionar Ra(s) de forma que, para cada conjunto Ten la partici´on, todos los estados sen Ttengan una misma asignaci´on de probabilidades de tal forma que el espacio muestral S(a,s)asociado a dicha asignaci´on es el propio conjunto T. No obstante, esta interpretaci´on solo puede hacerse si, adem´as, tambi´en se satisface CONS (de lo contrario, no podemos asegurar que S(a,s)⊆Ra(s)). Proposici´on 4.1.Sea Mun modelo de Kripke probabil´ıstico satisfaciendo CONS y SDP; entonces, Msatisface UNIF. Demostraci´on. Sean a∈Ays, t ∈Sarbitrarios tales que t∈S(a,s). Por CONS, S(a,s)⊆Ra(s), y, por lo tanto, t∈Ra(s); por SDP, esto implica que Π(a,s)= Π(a,t), y, en particular, S(a,s)=S(a,t). Q.E.D. □ Una ´ultima propiedad, de car´acter m´as t´ecnico, que podr´ıamos pedir a un modelo es que todos sus conjuntos sean medibles; esta propiedad, como ya mencionamos en la observaci´on 4.1, simplifica de diversas formas los razonamientos probabil´ısticos. Definici´on 4.8. MEAS. Decimos que un modelo de Kripke probabil´ıstico satisface MEAS si para todo a∈A,s∈Syφ∈ LPK, el conjunto S(a,s)(φ)es medible (S(a,s)(φ)∈A(a,s)) □ Definici´on 4.9. PMEAS. Decimos que un modelo de Kripke probabil´ıstico satisface PMEAS si para todo a∈A,s∈Syp∈At, el conjunto S(a,s)(p)es medible. □ 48 CAP´ ITULO 4. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA No es dif´ıcil comprobar que si un modelo satisface PMEAS, entonces todas las f´ormulas puramente proposicionales definen conjuntos medibles. No obstante, no est´a claro que esto sea as´ı para proposiciones con componente modal o probabil´ıstica. A continuaci´on proporcionamos una condici´on suficiente para MEAS. Proposici´on 4.2.Sea Mun modelo satisfaciendo PMEAS,CONS,OBJ yUNIF. Entonces Msatisface MEAS. Demostraci´on. Procedemos por inducci´on estructural sobre las f´ormulas de LPK. Queremos probar que S(a,s)(φ) es medible, para todos a∈A,s∈Syφ∈ LPK. El caso base (p∈At) se tiene por hip´otesis, y los casos para los operadores proposicionales se comprueban f´acilmente. Operador modal. Sea φtal que S(a,s)(φ) es medible para todo a∈Ays∈S. Las propiedades CONS yOBJ juntas implican que para cualquier par de agentes a, b, S(a,s)=S(b,s)⊆Rb(s). De aqu´ı se sigue que S(a,s)(Kb(φ)) o bien es S(a,s)o bien es el vac´ıo (si Kbφse tiene en alg´un estado de S(a,s)=S(b,s)⊆Rb(s), entonces por definici´on de Rb(s) se tiene en todos); en ambos casos es medible. Operador probabil´ıstico. Sean φ1, ..., φktales que en todos los casos el conjunto S(a,s)(φi) es medible, para todo a∈Ays∈S. Dado b∈Aarbitrario, tenemos que probar que la f´ormula ψ:= Q1Prb(φ1) + ... +QkPrb(φk)≥Qdefine un conjunto medible S(a,s)(ψ) para a∈Ays∈Sarbitrarios. Sem´anticamente, M, t ⊨ψ⇐⇒ Q1Pr∗(b,t)(φ1) + ... +QkPr∗(b,t)(φk)≥Q. El lado izquierdo de la desigualdad anterior es un valor num´erico que depende de la distribuci´on de probabilidad para el agente ben el estado t; denomin´emoslo P(b,t). Entonces t∈S(a,s)(ψ) si y solo si t∈S(a,s)y P(b,t)≥Q. Ahora bien, por UNIF tenemos que si t∈S(a,s), entonces Π(a,s)= Π(a,t); en particular, esto implica que a todos los estados t∈S(a,s)les corresponde la misma asignaci´on de probabilidades. Por lo tanto, P(b,t)≥Qse tiene en un estado tsi y solo si se tiene en todos, o lo que es lo mismo, o bien S(a,s)(φ) = S(a,s)o bien S(a,s)(φ) = ∅. Q.E.D. □ Antes de pasar a otro orden de cosas, presentamos una ´ultima propiedad de interpretaci´on interesante que no se satisface en general, pero s´ı bajo ciertas condiciones. Dicha propiedad suele conocerse como “principio de Miller”, y representa una limitaci´on que se podr´ıa considerar natural sobre qu´e f´ormulas con probabilidades de orden superior (probabilidades sobre probabilidades) son ciertas. En particular, el principio de Miller puede expresarse a trav´es de la siguiente desigualdad: Pra(φ)≥b Pra(Pra(φ)≥b) (4.3) Proposici´on 4.3.UNIF y principio de Miller. Sea Mun modelo satisfaciendo UNIF. Entonces Msatisface el principio de Miller. Demostraci´on. Sean s∈S,a∈A,φ∈ LPKyb∈Qarbitrarios. Queremos probar: 5.2. PRE ´ AMBULO: LA PROPUESTA DE KOOI 55 La restricci´on por una f´ormula φde un modelo de Kripke probabil´ıstico Mse define como M|φ:= ⟨S′, R′, V ′,Π′⟩, con Π′ (a,s):= ⟨S′ (a,s),P(S′ (a,s)), Pr′ (a,s)⟩, donde S′:= S R′ a:= {(s, t)∈Ra|M, t ⊨φ} V′:= V S′ (a,s):= (S(a,s)si P(a,s)(φ) = 0 S(a,s)(φ)en otro caso P′ (a,s)(E) := (P(a,s)(E)si P(a,s)(φ)=0 P(a,s)(E(φ)) P(a,s)(φ)en otro caso Cualquier otra notaci´on que se haya definido en otro cap´ıtulo se define aqu´ı de la misma forma. □ Observaci´on 5.1.El lector podr´a apreciar de inmediato bastantes diferencias entre las filosof´ıas de la propuesta anterior y las que hemos estado haciendo a lo largo del resto de nuestro trabajo. Para empezar, no es dif´ıcil percatarse de que la familia S5 no es cerrada bajo la operaci´on de restricci´on tal y como aparece en esta propuesta; en efecto, no es dif´ıcil encontrar ejemplos de modelos en S5 cuyas restricciones seg´un esta definici´on ya no est´an en S5. En particular, esto hace que el enfoque de Kooi no sea del todo adecuado para tratar situaciones epist´emicas; de hecho, si nos fijamos solo en la parte no probabil´ıstica de esta definici´on de restricci´on, vemos que coincide con la que propone van Ditmarsch [1] en la secci´on 4.9 de su manual, donde discute precisamente sobre c´omo se podr´ıa relajar su concepto de anuncio p´ublico para adecuarlo mejor a modelos dox´asticos. Un aspecto de esta propuesta que podr´ıa verse como positivo es que nos permite prescindir de la medida interior para la cl´ausula sem´antica del operador probabil´ıstico, que algunos lectores podr´ıan considerar un tanto poco natural. No obstante, esto ocurre a costa de una gran p´erdida de generalidad, dado que lo que asegura que todos nuestros conjuntos sean medibles es que en todas las asignaciones de probabilidad se usa el “σ- ´algebra discreta”. Finalmente, otro de los aspectos que podr´ıan considerarse problem´aticos en esta propuesta es que la actualizaci´on de la asignaci´on de probabilidades en el caso de que la probabilidad de la f´ormula anunciada sea 0 no es del todo natural; de hecho, el propio Kooi discute esta cuesti´on brevemente en su art´ıculo. En la propuesta que ofrecemos en este cap´ıtulo hemos tratado de dar un sentido algo m´as natural a lo que ocurre en este caso. □ Kooi demuestra que su concepto de restricci´on est´a bien definido en el siguiente sentido: 56 CAP´ ITULO 5. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA DIN ´ AMICA Proposici´on 5.1.Si M, s es un modelo de Kripke probabil´ıstico en las condiciones de la definici´on 5.2, entonces M|φ, s tambi´en lo es. □ Nuestro reto, por tanto, es ofrecer una propuesta para la restricci´on que generalice a la anterior en el ´ambito probabil´ıstico, que mantenga el car´acter epist´emico de los modelos en el ´ambito modal, y que est´e “bien definida” en el sentido de la proposici´on anterior. En particular, un aspecto que s´ı nos parece fundamental preservar en nuestra propia propuesta es la forma en la que se actualiza la funci´on de probabilidad, dado que se corresponde con la definici´on cl´asica de probabilidad condicionada [5]: P(X|Y) := P(X∩Y) P(Y) 5.3. Sintaxis y sem´antica (de nuestra propuesta) Las f´ormulas de nuestro lenguaje LPK[ ] se definen de la misma forma que en 5.1; la principal diferencia est´a en su dimensi´on sem´antica. Definici´on 5.3. Sem´antica de LPK[ ].Sea M=⟨S, R, V, Π⟩un modelo de Kripke probabil´ıstico3con agentes Ay ´atomos At. La verdad de una f´ormula en LPK[ ] se interpreta seg´un las siguientes cl´ausulas sem´anticas: M, s ⊨p sii s ∈V(p), p ∈At M, s ⊨¬φ sii M, s ⊭φ M, s ⊨φ∧ψ sii M, s ⊨φ y M, s ⊨ψ M, s ⊨Kaφ sii Para todo t ∈S:Rast ⇒M, t ⊨φ M, s ⊨[φ]ψ sii M, s ⊨φ=⇒M|φ, s ⊨ψ( %) M, s ⊨Pn (k=0) QkPra(φk)≥Q sii Pn k=0 QkPr∗(a,s)(S(a,s)(φk)) ≥Q (5.3) Donde: La restricci´on por una f´ormula φtal que de un modelo de Kripke probabil´ıstico M se define como M|φ:= ⟨S′, R′, V ′,Π′⟩, con Π′ (a,s):= ⟨S′ (a,s),A′ (a,s), Pr′ (a,s)⟩, donde 3Como discutiremos m´as adelante, en realidad permitiremos tambi´en que la parte probabil´ıstica sea el “espacio cuasi-probabil´ıstico” resultante de considerar un “espacio muestral vac´ıo”. 5.3. SINTAXIS Y SEM ´ ANTICA 57 S′:= S(φ) R′ a:= Ra∩(S′×S′) V′:= V∩S′ S′ (a,s):= (S(a,s)(φ)si Pr∗ (a,s)(φ)>0 ∅e.o.c. A′ (a,s):= ({E(φ)|E∈A(a,s)}si Pr∗ (a,s)(φ)>0 {∅} e.o.c Pr′ (a,s)(E) :=        1si E =S(a,s)(φ) 0si E =∅ Pr∗ (a,s)(E) Pr∗ (a,s)(φ)e.o.c. La notaci´on (∗)en el punto anterior indica que se trata de la medida exterior (no confundir con la medida interior, indicada con la notaci´on (∗)). Esta se define an´alogamente a la medida interior: Pr∗ (a,s)(G) := inf{Pr(a,s)(E)|E∈A(a,s), E ⊇G} Cualquier otra notaci´on que se haya definido en otro cap´ıtulo se define aqu´ı de la misma forma. □ Nota 5.1.Con la definici´on de restricci´on anterior, pueden producirse casos degenerados en los que S′ (a,s)=∅. En estos casos, se entender´a que Pr′ (a,s)(∅) = 0, y no 1. Si bien esto va en contra de una de las propiedades t´ıpicas de las funciones de probabilidad, a saber, que Pr′ (a,s)(S′ (a,s)) = 1, nos parece un “parche” preferible a la otra posibilidad, dado que esta producir´ıa problemas todav´ıa m´as extra˜nos en su interacci´on con la propiedad de aditividad numerable (un ejemplo: 1 = Pr′ (a,s)(∅) = Pr′ (a,s)(∅⊔∅) = 1+1 = 2). Adem´as, como discutiremos m´as abajo, tambi´en nos parece una soluci´on mucho m´as filos´oficamente coherente. En particular, a partir de ahora nos tomaremos la licencia de decir que la terna ⟨∅,{∅}, P∅⟩=: Π∅, donde P∅es la funci´on que asigna al conjunto vac´ıo el valor 0, es un “espacio probabil´ıstico”. □ Antes de alabar las virtudes de nuestra propuesta, comprobemos que, efectivamente, satisface la propiedad de buena definici´on deseada: 58 CAP´ ITULO 5. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA DIN ´ AMICA Teorema 5.1. La restricci´on de un modelo probabil´ıstico es un modelo probabil´ıstico. Dado M=⟨S, R, V, Π⟩modelo de Kripke probabil´ıstico y φ∈ LPK[ ], la restricci´on M|φtal y como aparece en la definici´on 5.3 sigue siendo un modelo de Kripke probabil´ıstico. Demostraci´on. En los casos en que Pr∗ (a,s)(φ) = 0 (y, en particular, en los casos en que Π(a,s)= Π∅), esto se tiene trivialmente. Para el caso general: Hay que comprobar tres puntos: i)S′ (a,s)⊆S′ ii)A′ (a,s)es un σ-´algebra sobre S′ (a,s). iii)Pr′ (a,s)es una funci´on de probabilidad sobre ⟨A′ (a,s), S′ (a,s)⟩. El primer punto es obvio, solo lo hemos incluido en la enumeraci´on para que figure que no lo hemos olvidado. Probemos los dos puntos restantes. Prueba del punto II. Tenemos que comprobar tres condiciones: Conjunto unidad. S′ (a,s)∈A′ (a,s) Cerrada bajo complementario. Si E∈A′ (a,s), entonces S′ (a,s)\E∈A′ (a,s) Cerrada bajo uni´on numerable. Si {Ei}∞ i=1 es una sucesi´on de conjuntos en A′ (a,s), entonces S∞ i=1 Ei∈A′ (a,s) Conjunto unidad. Dado que S(a,s)∈A(a,s)en todos los casos y S′ (a,s)=S(a,s)(φ), tenemos el resultado. Cerrada bajo complementario. Sea E∈A′ (a,s). Entonces E=G(φ) para alg´un G∈A(a,s). Afirmamos que (S(a,s)\G)(φ) = S(a,s)(φ)\G(φ), y con esta afirmaci´on tenemos el resultado, pues S(a,s)\G∈A(a,s)por las propiedades del σ-´algebra. Justificamos esta afirmaci´on en la forma de un lema: Lema 5.1.Sea Aun σ-´algebra (no trivial4) asociada a alg´un par agente-estado en un modelo de Kripke probabil´ıstico, sean A, B ∈A, y sea φ∈ LPK[ ]. Entonces (A\B)(φ) = A(φ)\B(φ). Demostraci´on. Escribimos la definici´on de ambos conjuntos: (A\B)(φ) = {s∈A|s∈ B y M, s ⊨φ}=: (1) A(φ)\B(φ) = {s∈A|s∈ B(φ)y M, s ⊨φ}=: (2) Claramente la condici´on s∈ Bes m´as restrictiva que la condici´on s∈ B(φ), de modo que (1) ⊆(2). Para ver la contenci´on contraria, consideremos s∈(2); para ver que s∈(1), tenemos que comprobar que s∈ B. Sabemos que s∈ B(φ), de modo que la ´unica forma de que s∈Bes que s∈B\B(φ). Pero s∈B\B(φ)⇒M, s ⊭φ, lo 4Con esto queremos decir que es algo m´as que el conjunto {∅}. 5.3. SINTAXIS Y SEM ´ ANTICA 59 cual contradice el hecho de que s∈(2); por lo tanto, concluimos que s∈ B, y por lo tanto (2) ⊆(1). Q.E.D. □ Uni´on numerable. Sea {Ei}∞ i=1 una sucesi´on de conjuntos en A′ (a,s). Entonces, para cada uno de ellos, existe Gi∈A(a,s)tal que Gi(φ) = Ei. Veamos que (S∞ i=1 Gi)(φ) = S∞ i=1 Gi(φ): s∈( ∞ [ i=1 Gi)(φ)⇔s∈ ∞ [ i=1 Giy M, s ⊨φ⇔ ∃i t.q. s ∈Giy M, s ⊨φ ⇔ ∃i t.q. s ∈Gi(φ)⇔s∈ ∞ [ i=1 Gi(φ) (En las l´ıneas anteriores cuando hemos escrito ∃ise ha sobreentendido que i∈ {1,2,3, ...}.) Con esto tenemos el resultado, y con esto acabamos de probar tambi´en que A′ (a,s) es un σ-´algebra. Prueba del punto III. Tenemos que comprobar tres condiciones: Pr′ (a,s)(S′ (a,s)) = 1 Pr′ (a,s)(E)≥0 para todo E∈A′ (a,s) Aditividad numerable. Sea {Ei}∞ i=1 una familia de conjuntos disjuntos en A′ (a,s), entonces Pr′ (a,s)(S∞ i=1 Ei) = P∞ i=1 Pr′ (a,s)(Ei) Las dos primeras propiedades son obvias a partir de las definiciones. Para ver la “propiedad dif´ıcil” (aditividad numerable) basta comprobar que para {Ei}∞ i=1 disjuntos 2 a 2 se tiene Pr∗ (a,s)( ∞ [ i=1 Ei) = ∞ X i=1 Pr∗ (a,s)(Ei) Para probar la igualdad anterior, haremos uso de una serie de lemas auxiliares que probaremos a continuaci´on: Lema 5.2.Sean Aun σ-´algebra (no trivial) asociada a un par agente-estado en un modelo de Kripke probabil´ıstico, φ∈ LPK[ ],A′la restricci´on (no trivial) de Aaφ, E∈A′y¯ G∈A′tal que E⊆¯ G. Entonces existe G∈Atal que G⊆¯ GyG(φ) = E. Demostraci´on. Si ¯ G(φ) = E, tenemos el resultado tomando G=¯ G. Supongamos ahora que ¯ G(φ)⊋E. Entonces ¯ G(φ) = E⊔Kcon K:= ¯ G(φ)\E∈A′ (a,s). Por lo 60 CAP´ ITULO 5. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA DIN ´ AMICA tanto, existe L∈A(a,s)con L(φ) = K. Entonces, utilizando el lema 5.1, tenemos que G=¯ G\Lsatisface las condiciones del lema. Q.E.D. □ Lema 5.3.Sea Aun σ-´algebra (no trivial) asociada a un par agente-estado en un modelo de Kripke probabil´ıstico, φ∈ LPK[ ],A′la restricci´on (no trivial) de Aaφ, sean {Ei}∞ i=1 conjuntos en A′disjuntos 2 a 2, y sea G∈Atal que G(φ) = S∞ i=1. Entonces existen Gi∈Atales que Gi(φ) = Ei, los Gison disjuntos 2 a 2, y S∞ i=1 Gi⊆G. Demostraci´on. Empezamos tomando G0 i∈Apara cada ide forma que G0 i(φ) = Ei (esto se puede hacer por la definici´on de A′). A partir de estos construiremos otros conjuntos que satisfagan las condiciones del lema. Primero, para asegurar que los conjuntos finales estar´an todos contenidos en G, tomamos G1 i=G0 i∩G. No es dif´ıcil comprobar que (A∩B)(φ) = A(φ)∩B(φ), y por tanto G1 i(φ) = Ei. Ahora, para asegurar que son disjuntos 2 a 2, tomamos: G1=G1 1 G2=G1 2\G1 1 . . . Gk=G1 k\( k−1 [ i=1 G1 i) Dichos conjuntos son claramente disjuntos, siguen estando contenidos en G y, en todos los casos, por el lema 5.1, se comprueba que Gi(φ) = Ei(aqu´ı es donde se usa que los Eison disjuntos 2 a 2, pues gracias a esto tenemos que Ek\Sk−1 i=1 Ei=Eken todos los casos). Esto prueba el lema. Q.E.D. □ A partir de los dos lemas anteriores, se justifican todos los pasos que daremos a continuaci´on, teniendo adem´as en cuenta la monoton´ıa de la funci´on de probabilidad y la siguiente observaci´on: sea Aun subconjunto acotado inferiormente de R(por lo tanto tiene ´ınfimo en R), y sea A′⊆Atal que ∀a∈A, ∃a′∈A′:a′≤a; entonces, inf A =inf A′. Los pasos en cuesti´on son los siguientes: 5.3. SINTAXIS Y SEM ´ ANTICA 61 Pr∗ (a,s)( ∞ [ i=1 Ei) = inf{Pr(a,s)(G)|G⊇ ∞ [ i=1 Ei, G ∈A(a,s)}= inf{Pr(a,s)(G)|G∈A(a,s), G(φ) = ∞ [ i=1 Ei}= inf{Pr(a,s)( ∞ [ i=1 Gi)|Gi∈A(a,s), Gi∩Gj=∅si i =j, Gi(φ) = Ei, i ∈ {1,2,3, ...}} = (∗)inf{ ∞ X i=1 Pr(a,s)(Gi)|Gi∈A(a,s), Gi∩Gj=∅si i =j, Gi(φ) = Ei, i ∈ {1,2,3, ...}} = (∗∗)inf{ ∞ X i=1 Pr(a,s)(Gi)|Gi∈A(a,s), Gi(φ) = Ei, i ∈ {1,2,3, ...}} = ∞ X i=1 {Pr(a,s)(Gi)|Gi∈A(a,s), Gi(φ) = Ei}= ∞ X i=1 Pr∗ (a,s)(Ei) El paso (*) utiliza la aditividad numerable de la P(a,s) El paso (**) est´a justificado porque, haciendo una construcci´on similar a la del lema 5.3, podemos encontrar siempre conjuntos disjuntos que, por lo dem´as, satisfagan las mismas propiedades. Con esto tenemos el resultado, y terminamos tambi´en de probar el teorema. Q.E.D. □ Ahora que ya hemos visto que efectivamente nuestra propuesta “funciona”, vamos a tratar de enumerar sus principales puntos fuertes en comparaci´on con la propuesta original de Kooi. Para empezar, la principal ventaja que podemos observar es que no requiere de ning´un tipo de condici´on sobre los modelos de Kripke probabil´ısticos, lo cual significa una generalizaci´on enorme de la misma. Adem´as, nuestra propuesta s´ı preserva el car´acter epist´emico de los modelos, dado que, al menos en lo que a la parte modal se refiere, la definici´on es id´entica a la presentada en 3.2; esto la hace mucho m´as adecuada para lidiar, en principio, con el tipo de situaciones que se suelen tratar en el campo de la l´ogica epist´emica din´amica Otra ventaja importante que observamos en nuestra propuesta es su tratamiento de las “actualizaciones con probabilidad nula”. En la propuesta de Kooi, la consecuencia de actualizar con una f´ormula φde probabilidad 0 es que la parte probabil´ıstica del modelo permanece igual que antes; esto podr´ıa considerarse una soluci´on sencilla a los problemas derivados de dividir por 0 que aparecer´ıan de otra forma, pero que, filos´oficamente, no tiene una justificaci´on del todo s´olida. Nuestra propuesta tampoco es filos´oficamente impenetrable, pero creemos que se le puede dar una interpretaci´on algo m´as satisfactoria: ante el anuncio p´ublico de una f´ormula cuya probabilidad es 0, la 62 CAP´ ITULO 5. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA DIN ´ AMICA asignaci´on de probabilidad actualizada es la “vac´ıa”5. En cierto modo, esto es “an´alogo” a transformar un modelo de Kripke probabil´ıstico en uno puramente modal, dado que la parte probabil´ıstica deja de aportarnos informaci´on ´util; este comportamiento puede considerarse coherente, dado que, si bien la actualizaci´on con una f´ormula de probabilidad 0 “no tiene sentido” desde un punto de vista probabil´ıstico, s´ı puede tenerlo desde un punto de vista modal. No obstante, tambi´en reconocemos que esta forma de lidiar con las actualizaciones de probabilidad nula puede tener efectos secundarios no deseados, aunque en nuestro trabajo no hemos podido detectar ninguno; el ´unico problema que s´ı hemos podido predecir tiene que ver con las perspectivas de proporcionar una axiom´atica completa para este sistema generalizando los axiomas “t´ıpicos” ya conocidos; de esto hablaremos en el cap´ıtulo 7. En este trabajo tratamos la parte axiom´atica de manera muy superficial y especulativa, de modo que no podemos pronunciarnos definitivamente sobre esto; no obstante, al menos en calidad de conjetura, proporcionamos algunas intuiciones sobre posibles modificaciones a dichos axiomas que nos permitan reutilizarlos en este nuevo sistema. Sobre esta cuesti´on, por lo tanto, solo puedo sugerir mayores esfuerzos de investigaci´on en el futuro. Un ´ultimo apunte que queremos dejar por escrito sobre nuestra propuesta tiene que ver con los motivos para el uso selectivo de la medida exterior en algunas partes de la misma. El motivo principal es t´ecnico: el lector que haya seguido las demostraciones anteriores podr´a comprobar que “nada funcionar´ıa” si se estuviese utilizando la medida interior en la definici´on de la medida de probabilidad actualizada. No obstante, es cierto que la decisi´on de actualizar la parte probabil´ıstica del modelo con la “asignaci´on vac´ıa” cuando Pr∗ (a,s)(φ) = 0 es algo m´as arbitraria, y aqu´ı s´ı podr´ıamos haber elegido utilizar la medida interior. Se pueden proporcionar argumentos t´ecnicos a favor y en contra de ambas opciones; en nuestro caso, la raz´on por la que nos hemos acabado decantando por utilizar la medida exterior es que esto nos permite hacer razonamientos como en el ejemplo 5.4.2 que veremos m´as adelante. 5.4. Algunos ejemplos ilustrativos 5.4.1. Ejemplo: Al´ı Bab´a y los nladrones Antes de estudiar m´as propiedades de este nuevo formalismo, trataremos de ponerlo en pr´actica con un ejemplo cl´asico en el ´area de la criptograf´ıa; en particular, se trata de una ilustraci´on de la idea de prueba de conocimiento cero presentada por Jean-Jacques Quisquater [14] en la forma de un “cuento para ni˜nos”, donde los sucesivos ´exitos en los atracos de unos ladrones a Al´ı Bab´a constituyen una prueba de cero conocimiento de que o bien su mala suerte es de magnitudes c´osmicas, o bien existe un 5M´as a´un: seg´un una interpretaci´on filos´ofica radical, ante la actualizaci´on con una f´ormula de probabilidad 0, podr´ıa considerarse, por analog´ıa con ex falso quodlibet, que el nuevo espacio muestral ser´ıa “el conjunto de todas las cosas posibles e imposibles”, un conjunto tan inconmensurablemente enorme que no puede expresarse matem´aticamente. 5.4. ALGUNOS EJEMPLOS ILUSTRATIVOS 63 pasadizo secreto en la cueva6. Ejemplo 5.1.Al´ı Bab´a y los nladrones. Al´ı Bab´a se encontraba un buen d´ıa paseando por el bazar de Bagdad cuando, de improvisto, not´o un tir´on en el brazo: un ladr´on le hab´ıa robado su bolso y se hab´ıa dado a la fuga. Inmediatamente, Al´ı Bab´a empez´o a correr tras ´el; lo persigui´o y lo persigui´o hasta que, finalmente, lo vio esconderse en una cueva. Al´ı Bab´a trat´o de seguirlo all´ı, pero, poco despu´es de entrar, se dio cuenta de que la cueva se bifurcaba, y no hab´ıa alcanzado a ver cu´al de los dos caminos hab´ıa tomado el ladr´on, de modo que decidi´o seguir uno de ellos al azar. Al llegar al final del camino y ver que el ladr´on no estaba all´ı, simplemente pens´o: “Diantres, debo haber tenido mala suerte. Habr´a tomado el otro camino.” Al d´ıa siguiente, de nuevo mientras paseaba tranquilamente por el bazar, otro ladr´on le rob´o su nuevo bolso a Al´ı Bab´a, y, de nuevo, se escondi´o en la misma cueva, repiti´endose los acontecimientos del d´ıa anterior; cuando, de nuevo, Al´ı Bab´a se encontr´o con que el ladr´on no estaba al final del camino que hab´ıa elegido, pens´o una vez m´as: “¡Diantres! Debo haber tenido mala suerte otra vez. A ver si ma˜nana, y durante los pr´oximos (n−2) d´ıas, no me pasa esto de nuevo.” Pasaron nd´ıas, y, con ellos, fueron nlos ladrones que robaron su bolso a Al´ı Bab´a, refugi´andose despu´es en la cueva y desapareciendo siempre misteriosamente. Cada vez que ocurr´ıa esto, Al´ı Bab´a exclamaba: “¡Diantres! ¡Otra vez debo haber tenido mala suerte! ¡Y qu´e mal est´an las calles ´ultimamente!”. Pero, con cada d´ıa que pasaba, aumentaban tambi´en sus sospechas de que en aquella cueva ocurr´ıa algo extra˜no. De modo que, cuando lleg´o el d´ıa n, tras su rutinario atraco, decidi´o explorar detenidamente la cueva, y se percat´o de que esta ten´ıa una forma un tanto peculiar 5.1: era casi como un donut, salvo por una delgada pared que separaba sus dos extremos. Observando esta pared con algo m´as de detenimiento, se percat´o de algo m´as: a ambos lados de la pared hab´ıa un peque˜no teclado, un tanto anacr´onico en el Siglo XII, que permit´ıa introducir c´odigos de cuadro d´ıgitos en una peque˜na pantalla, y, junto a este extra˜no aparato, una nota que dec´ıa: “¡NO OLVIDAR: EL C´ ODIGO ES 1234!”. Las sospechas ya comenzaban a acumularse en la cabeza de Al´ı Bab´a, de modo que, astutamente, decidi´o introducir estos mismos cuatro d´ıgitos en el teclado; de repente, en la pared se abri´o un peque˜no pasadizo. Al´ı Bab´a comprendi´o finalmente por qu´e aquellos ladrones siempre lograban escap´arsele: aunque tomase el mismo camino que ellos, los ladrones simplemente pod´ıan usar el pasadizo para salir por el otro. Al d´ıa siguiente, cuando el (n+ 1)-´esimo ladr´on entr´o en la cueva y trat´o de usar el mismo truco, Al´ı Bab´a simplemente se qued´o esper´andolo fuera.7 Tratemos de modelar esta situaci´on en t´erminos de nuestro lenguaje, LPK[ ]. M´as concretamente, nuestro principal objetivo ser´a representar el hecho de que, con las sucesivas iteraciones del atraco diario, Al´ı Bab´a considerar´a cada vez m´as improbable la posibilidad de que la cueva no tenga ning´un pasadizo oculto (tras la n-´esima iteraci´on, 6El ejemplo explora de forma m´as concreta muchas de las propiedades que ha de tener una prueba para poder considerarse “de cero conocimiento”. Nosotros nos limitaremos, en un principio, a modelar lo fundamental de la situaci´on. 7Siempre me he preguntado por qu´e no permaneci´o esperando fuera desde el principio, pero esa es otra historia. 64 CAP´ ITULO 5. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA DIN ´ AMICA Figura 5.1: Una representaci´on, no demasiado art´ıstica, de la cueva de Al´ı Bab´a (o m´as bien, de la cueva de sus atracadores). Al´ı Bab´a considera que la improbabilidad de la situaci´on es lo suficientemente significativa como para examinarla con m´as detenimiento). En particular, haremos uso de las siguientes notaciones: El ´atomo prepresentar´a la afirmaci´on “Hay un pasadizo secreto en la cueva”. Los ´atomos I1, ..., In, ... representar´an, respectivamente, las afirmaciones “Se han producido al menos natracos”. El ´atomo Frepresenta la afirmaci´on “Se da al menos un intento de escape fallido”; su negaci´on, por tanto, representa el hecho de que el ladr´on logra escapar exitosamente en todos los intentos. Proponemos el modelo de la figura 5.2 para representar la situaci´on epist´emica. Para aligerar la notaci´on, hemos evitado escribir los casos en los que se tiene ¬Ii; debe sobreentenderse que, si no aparece expl´ıcitamente Ii, entonces se tiene su negaci´on. Formalmente el modelo se define como sigue (a, Al´ı Bab´a, es el ´unico agente): S:= S0∪S+∪S−, con •S0:= {s0 i, i ∈ {1,2, ...}} •S+:= {si, i ∈ {1,2, ...}} •S−:= {¯si, i ∈ {1,2, ...}} Ra:= S×S VF=S− VIi={s0 j, sj,¯sj|j≥i} Vp=S0 S(a,s0 i)={s0 i} 5.5. ALGUNAS PROPIEDADES DEL LENGUAJE LPK[ ] 71 Es f´acil ver que ambos conjuntos coinciden: en efecto, la cl´ausula M|φ, t ⊨pse puede reescribir como t∈V(p)y t ∈S(φ), lo cual nos permite reescribir el primer conjunto como: S′ (a,s)(p) = {t∈S′ (a,s)|M|φ, t ⊨p}={t∈S(a,s)|M, t ⊨φ, t ∈V(p)y t ∈S(φ)} Pero t∈S(φ) y M, t ⊨φest´an afirmando lo mismo, de modo que nos quedamos con el conjunto S(a,s)(φ, p). Q.E.D. □ Lema 5.4.Sea Mun modelo de Kripke probabil´ıstico, sea φ∈ LPK[ ], y sea M|φla restricci´on de Maφ. Sean a∈Ays∈Stales que tanto A(a,s)como A′ (a,s)son no triviales (es decir, Pr∗ (a,s)(φ)>0). Sea E∈A′ (a,s). Entonces, existe G∈A(a,s)tal que G(φ) = EyPr(a,s)(G) = Pr∗ (a,s)(E). Demostraci´on. Por el lema 5.2, sabemos que P:= Pr∗ (a,s)(E) = inf{Pr(a,s)(G)|G∈A(a,s)y G(φ) = E} En particular, dado ϵ > 0, existen Gitales que Gi(φ) = E y Pr(a,s)(Gi)≥P+ϵ 2i Sea G:= T∞ i=0 Gi. Entonces G(φ) = Ey, adem´as, Pr(a,s)(G)≥P+ϵ 2k∀k∈N Es decir, Pr(a,s)(G) = P. Q.E.D. □ Proposici´on 5.6.Definici´on de SIGNIF + SIGNIF se conserva mediante las restricciones. Decimos que un modelo Msatisface SIGNIF (de “no tiene conjuntos inSIGNIFicantes”) si, para todo a∈Ays∈S, para todo E∈A(a,s)se tiene que Pr(a,s)(E) = 0 ⇒E=∅. Sea Mun modelo satisfaciendo SIGNIF y sea φ∈ LPK[ ] una f´ormula arbitraria. Entonces M|φtambi´en satisface SIGNIF. 72 CAP´ ITULO 5. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA DIN ´ AMICA Demostraci´on. Sean a∈A,s∈S(φ). Si S′ (a,s)=∅, estamos en el caso trivial. Supongamos pues que S′ (a,s)=∅. Sea E∈A′ (a,s), y supongamos que E=∅; hay que ver entonces que Pr′ (a,s)(E)>0. Por el lema anterior, sabemos que existe G∈A(a,s)tal que G(φ) = Ey cuya medida coincide con la medida exterior de E. Dado que E=∅,Gtampoco es vac´ıo. Ahora bien, por SIGNIF, esto implica que la medida de Ges positiva. Por lo tanto, Pr′ (a,s)(E) = Pr(a,s)(G) Pr∗ (a,s)(S(a,s)(φ)) >0 Q.E.D. □ Teorema 5.2. Condici´on suficiente para MEAS-D en LPK[ ].Sea Mun modelo satisfaciendo CONS,OBJ,UNIF,PMEAS ySIGNIF, y sea φ∈ LPK[ ]. Entonces Msatisface MEAS-D. Demostraci´on. El caso base, as´ı como los casos para las conectivas proposicionales, el operador modal y el operador probabil´ıstico, se prueban como en la proposici´on 4.2. Veamos el caso para el operador de anuncio p´ublico (por inducci´on estructural sobre las f´ormulas de LPK[ ]). Sean φyψtales que, para cualquier modelo Msatisfaciendo CONS,OBJ, UNIF,PMEAS ySIGNIF y tales que, para cualquier a∈Ays∈S, los conjuntos S(a,s)(φ)yS(a,s)(ψ) son medibles. Tenemos que probar que S(a,s)([ψ]φ) es medible. Caso 1. El caso trivial: S(a,s)=∅. En tal caso, S(a,s)([ψ]φ) = ∅, que obviamente es medible. Caso 2. S(a,s)=∅. Entonces, S(a,s)([ψ]φ) = {t∈S(a,s)|M, t ⊨ψ⇒M|ψ, t ⊨φ}= {t∈S(a,s)|M, t ⊭ψ o (M, t ⊨ψ y M|ψ, t ⊨φ)}= {t∈S(a,s)|M, t ⊭ψ}∪{t∈S(a,s)|M, t ⊨ψ y M|ψ, t ⊨φ} El primer conjunto de la uni´on en la ´ultima l´ınea es S(a,s)(¬φ), y es f´acil comprobar que es medible usando la hip´otesis de inducci´on y las propiedades del σ-´algebra. El segundo conjunto de la uni´on podemos reescribirlo como: {t∈S(a,s)(ψ)|M|ψ, s ⊨φ}=: (2) Nuestro objetivo ser´a probar que (2) = S′ (a,s)(φ), dado que con esto obtendr´ıamos el resultado: en efecto, por los lemas anteriores, el modelo M|ψsatisface CONS,OBJ, 5.5. ALGUNAS PROPIEDADES DEL LENGUAJE LPK[ ] 73 UNIF,PMEAS ySIGNIF, y por hip´otesis de inducci´on esto implica que S′ (a,s)(φ) es medible. Probemos pues este objetivo. Caso 2.1. Pr(a,s)(ψ) = 0. Por SIGNIF, esto implica que S(a,s)(ψ) = ∅, y, por otra parte, por definici´on, S′ (a,s)(φ) = ∅. Por lo tanto, (2) = S(a,s)(ψ)(φ) = S′ (a,s)(φ), y tenemos el resultado. Caso 2.2. Pr(a,s)(ψ)>0. Entonces S′ (a,s)=S(a,s)(ψ), y, de la misma forma, tenemos el resultado. Q.E.D. □ Corolario 5.1.En particular, si Mes un modelo satisfaciendo CONS,OBJ,UNIF, PMEAS ySIGNIF, entonces tanto este como su restricci´on a cualquier f´ormula satisfacen MEAS-D. □ Un ´ultimo resultado que ser´ıa interesante tratar de probar ser´ıa algo an´alogo al teorema 3.1, que nos permite reescribir cualquier f´ormula de LK[ ] como una f´ormula de LK. En este caso, presentamos un resultado que por s´ı solo es mucho m´as d´ebil, pero que creemos que puede abrir el camino a otros resultados algo m´as interesantes. Proposici´on 5.7.Reescritura para el operador probabil´ıstico en MEAS-D. La siguiente equivalencia es cierta en modelos satisfaciendo MEAS-D: [ψ] n X i=1 QiPra(φi)≥Q↔ Pra(φ)>0∧ φ→ n X i=1 QiPra(φ∧[φ]φi)≥Q Pra(φ)!! ∨(Pra(φ)=0∧(φ→Pra(⊥)≥Q) Demostraci´on. La prueba de la validez de la ´ultima f´ormula es tediosa, pero f´acil de ver a partir de la sem´antica de LPK[ ], teniendo en cuenta que se eval´ua en modelos satisfaciendo MEAS-D. Q.E.D. □ Observaci´on 5.2.La subf´ormula Pra(⊥)≥Qb´asicamente expresa que 0 ≥Q. □ No hemos tratado de encontrar un contraejemplo a la “reescritura” del operador probabil´ıstico en el caso general (modelo no satisfaciendo MEAS-D), pero, en principio, conjeturamos que debe existir tal contraejemplo, dado que la condici´on Pr∗ (a,s)(φ) = Pr(a,s)(φ) = Pr∗(a,s)(φ) parecer´ıa un requisito natural para que dicha 74 CAP´ ITULO 5. L ´ OGICA EPIST´ EMICA PROBABIL´ ISTICA DIN ´ AMICA reescritura sea correcta en general8. No obstante, por supuesto, no podemos afirmar o negar nada sobre esta cuesti´on hasta que no se hayan encontrado resultados concluyentes a favor o en contra. Tampoco descartamos la posibilidad de encontrar una reescritura m´as compleja en el caso general, aunque nos decantamos m´as por la posibilidad de que, en el caso general, no sea posible hallar tal sistema de reescrituras. Por otra parte, la proposici´on anterior adquirir´ıa un peso mucho mayor si se lograse probar que, en adici´on a las reescrituras del teorema 3.1, proporciona una traducci´on de LPKaLPK[ ], al menos restringi´endonos a modelos que satisfacen MEAS-D. Una prueba as´ı requerir´ıa de la definici´on de algunas construcciones te´oricas adicionales que no hemos podido cubrir en este trabajo, pero que tampoco son excesivamente complejas; en particular, nosotros creemos que es posible, y que no es dif´ıcil (disponiendo de las herramientas adecuadas), probar este hecho. En el caso de tenerse dicho resultado, se tendr´ıa tambi´en el siguiente corolario: Conjetura 5.1.Bisimulaci´on en LPK[ ].Sean M1,M2dos modelos de Kripke probabil´ısticos satisfaciendo MEAS-D, y sean s1,s2dos estados en los respectivos modelos. Entonces M1, s1←→M2, s2=⇒M1, s1≡LPK[ ] M2, s2. □ 8Aunque tambi´en barajamos la conjetura de que sea suficiente imponer una condici´on m´as d´ebil sobre los modelos, como SIGNIF. Dicha propiedad asegura, en particular, que Pr∗(a,s)(φ) es nula si y solo si lo es P r∗ (a,s)(φ). 6. Conocimiento Com´un 6.1. Idea y motivaci´on Hasta ahora, los formalismos presentados solo nos permiten hacer afirmaciones sobre nociones que, en ´ultima instancia, son reducibles al conocimiento individual de cada uno de los agentes involucrados. El operador de conocimiento com´un CBque introducimos en este cap´ıtulo nos permite expresar, adicionalmente, propiedades epist´emicas del sistema en conjunto, o de un subconjunto del mismo. Halpern y Fagin [3] presentan en su art´ıculo una “versi´on probabil´ıstica” de este operador, que no cubriremos aqu´ı pero cuya inclusi´on en investigaciones futuras tambi´en ser´ıa de gran inter´es. La idea intuitiva del operador de conocimiento com´un puede expresarse en t´erminos de los operadores grupales presentados en la anotaci´on 2.7. Ya sabemos que la f´ormula EBφse leer´ıa “Todos los agentes en Bsaben φ”. Consideremos ahora las iteraciones sucesivas de este operador: por ejemplo, la f´ormula E2 Bφse leer´ıa “Todos los agentes en Bsaben que todos los agentes en Bsaben φ”, y la f´ormula Ek Bφ, k > 0 se leer´ıa “Todos los agentes en Bsaben que todos los agentes en Bsaben que (...) todos los agentes en Bsaben φ” (kveces). En este sentido, el operador de conocimiento com´un da el “salto al infinito”, pues una forma natural de interpretar la f´ormula CBφ es la siguiente: ∀k≥0, Ek Bφ(6.1) La introducci´on de este operador de conocimiento com´un a˜nade toda una dimen- si´on de complejidad te´orica a nuestros formalismos que, por desgracia, en este trabajo solo nos dar´a tiempo a sugerir de forma superficial – consideramos, por otra parte, que los principales aportes te´oricos de este trabajo ya se hicieron en el cap´ıtulo anterior. En particular, una de las consecuencias te´oricas m´as interesantes de la introducci´on de este operador es que el lenguaje LKC[ ] (LK+ Operador anuncio p´ublico + Operador conocimiento com´un) es m´as expresivo que LKC (LK+ Operador conocimiento com´un); una prueba de este hecho puede encontrarse en van Ditmarsch [1] (teorema 8.48). Esto es interesante porque, en cambio, el lenguaje LKes, como vimos (de manera incompleta) en el cap´ıtulo 3, igual de expresivo que el lenguaje LK[ ] (LK+ Operador anuncio p´ublico). Lo que esto indica es que la aportaci´on que hacen los operadores de anuncio p´ublico y de conocimiento com´un en conjunto es “mayor” que la que hacen por separado. En investigaciones futuras ser´ıa interesante estudiar qu´e es lo que ocurre si se a˜nade tambi´en el operador de anuncio p´ublico en toda esta mezcla. Por ´ultimo, la mayor´ıa de los ejemplos realmente sugerentes que podr´ıamos haber incluido en las secciones anteriores requer´ıan del concepto adicional de conocimiento com´un, dado que, a menudo, es importante mostrar que un sistema satisface una propiedad que no es reducible a ninguno de los agentes individuales, sino al conocimiento com´un que comparten; de modo que ser´a en esta secci´on donde presentaremos buena parte de estos ejemplos. 75 76 CAP´ ITULO 6. CONOCIMIENTO COM ´ UN 6.2. Sintaxis, sem´antica y propiedades b´asicas Como hemos comentado en la introducci´on, el plano “te´orico” quedar´a en un plano m´as bien secundario de este cap´ıtulo. Adem´as, el lector ya estar´a cansado de ver una y otra vez el mismo tipo de construcciones y definiciones, de modo que nos tomamos la licencia de ser algo m´as escuetos en esta ocasi´on. Definici´on 6.1. Sintaxis de los lenguajes LKC,LKC[ ],LPKC,LPKC[ ],LPKC[ ]Kooi. Para cualquiera de los lenguajes que hemos considerado a lo largo de este trabajo, el correspondiente lenguaje con conocimiento com´un es el generado por la BNF resultante de a˜nadir el constructor CBφa cualquiera de las BNFs originales, con B⊆A. □ Antes de presentar la sem´antica para poder interpretar este nuevo operador, es necesario introducir algunas construcciones te´oricas previas. Definici´on 6.2. Cierre transitivo reflexivo. Sea Sun conjunto numerable, A un conjunto finito no vac´ıo, y, para cada a∈A, sea Rauna relaci´on en el conjunto S. Sea B⊆A. Definimos: REB=RB:= Sb∈BRb RCB:= R∗ EB Donde: El cierre transitivo de una relaci´on Rse define como la menor relaci´on R+tal que: i)R⊆R+ ii) Para todos x, y, z ∈S, se tiene que (Rxy y Ryz)⇒Rxz. Si adem´as imponemos que para todo x∈Sse tenga R+xx, entonces decimos que es el cierre reflexivo transitivo de R, y lo denotamos R∗. En particular, si Rya es reflexiva, entonces R+=R∗. □ Observaci´on 6.1.Se comprueba f´acilmente que una forma de expresar la condici´on para la validez de la f´ormula EBφes la siguiente: M, s ⊨EBφ⇐⇒ ∀t∈S, REBst ⇒M, t ⊨φ □ La siguiente proposici´on nos proporciona una forma sencilla de manejar e interpretar el cierre transitivo de una relaci´on. 6.2. SINTAXIS, SEM ´ ANTICA Y PROPIEDADES B ´ ASICAS 77 Proposici´on 6.1.Sea Runa relaci´on sobre un conjunto S. Consideremos las siguientes relaciones auxiliares: R0xy ⇔x=y R1xy ⇔Rxy Rkxy ⇔O bien Rk−1xy o bien existe x1tal que Rxx1yRk−1x1y. Entonces se tiene: R+xy si y solo si existe k≥1 tal que Rkxy. R∗xy si y solo si existe k≥0 tal que Rkxy. □ Definici´on 6.3. Sem´antica del operador de conocimiento com´un. En cualquiera de los lenguajes estudiados m´as el operador CB, la sem´antica para interpretar este operador es la siguiente: M, s ⊨CBφ⇐⇒ ∀t∈S, RCBst ⇒M, t ⊨φ Recordemos que utilizamos la notaci´on RCB:= R∗ EB. □ Observaci´on 6.2.Obs´ervese que la proposici´on 6.1 nos permite reescribir f´acilmente la sem´antica del operador CBpara obtener la expresi´on de la ecuaci´on 6.1. □ A continuaci´on presentamos varias propiedades b´asicas sobre la interacci´on entre el operador de conocimiento com´un y el operador de anuncio p´ublico. Comenzamos observando que no se satisface la reescritura “natural” que podr´ıamos esperarnos por analog´ıa con el teorema 3.1, a saber, [φ]Kaψ↔(φ→Ka[φ]ψ), y de hecho no es dif´ıcil encontrar un contraejemplo. No obstante, s´ı se tiene la siguiente propiedad para “garantizar” el conocimiento p´ublico de una f´ormula tras un anuncio p´ublico: Proposici´on 6.2.Sean φ, ψ, χ ∈ LPKC[ ]. Entonces, si las f´ormulas χ→[φ]ψy (χ∧ φ)→EBχson v´alidas, tambi´en lo es χ→[φ]CBψ. Demostraci´on. Sea Mun modelo de Kripke probabil´ıstico, y sea sun estado en dicho modelo. Supongamos que M, s ⊨χ; tenemos que probar entonces que, bajo las condiciones del enunciado, M, s ⊨[φ]CBψ. Si M, s ⊭φ, esto siempre es cierto. Supongamos pues que M, s ⊨φ; tenemos que probar que M|φ, s ⊨CBψ, es decir, dado s∈S′,R′∗ Bst implica que M|φ, t ⊨ψ. Por la proposici´on 6.1,R′∗ Bst ⇔R′k Bst para alg´un k. Procedemos pues por inducci´on sobre k. Caso k= 0.Entonces s=t, y M|φ, s ⊨ψse tiene porque M, s ⊨χ, y por la validez de χ→[φ]ψ. 78 CAP´ ITULO 6. CONOCIMIENTO COM ´ UN Hip´otesis de inducci´on. Para i≤k, si s∈S′es un estado en el que se satisface M, s ⊨χyM, s ⊨φ, entonces R′ist ⇒M|φ, t ⊨ψ. Caso k+ 1.Sea ttal que (R′ B)k+1st. Si (R′ B)kst, entonces tenemos el resultado por hip´otesis de inducci´on. En otro caso, existe x∈S′tal que R′ Bsx y (R′ B)kxt. Dado que M, s ⊨φyM, s ⊨χ, y por la validez de la f´ormula (φ∧χ)→EBχ, tenemos M, x ⊨χ(pues R′ Bsx ⇒RBsx). Por otra parte, dado que x∈S′=S(φ), tenemos que M, x ⊨φ. Aplicando la hip´otesis de inducci´on en M, x, tenemos el resultado para t. Q.E.D. □ Corolario 6.1.[φ]ψes v´alida si y solo si lo es [φ]CBψ. □ Este ´ultimo resultado podr´ıa parecer contradictorio con la noci´on de que no se puede proporcionar una traducci´on de LKC[ ] aLKC, pues algunos lectores podr´ıan considerar que esto ya constituye la equivalencia que nos faltar´ıa para tal sistema de reescrituras. No obstante, tener un conjunto de equivalencias de este tipo no es suficiente para que constituyan una traducci´on adecuada (es decir, que las f´ormulas traducidas tomen el mismo valor de verdad para los mismos modelos en los mismos estados); por ejemplo, es posible construir modelos en los que la f´ormula χ→[φ]ψes v´alida pero χ→[φ]CBψno lo es. 6.3. Algunos ejemplos En esta secci´on estudiaremos algunos ejemplos cl´asicos que ponen en relieve la potencia conceptual de este operador de conocimiento com´un. En algunos casos, ofrecemos tambi´en “variaciones probabil´ısticas” de los mismos. 6.3.1. N´umeros Consecutivos Nuestro primer ejemplo es un problema sencillo de van Ditmarsch [1] que ilustra c´omo, incluso en las situaciones m´as triviales, alcanzar conocimiento com´un sobre un hecho resulta no ser posible; en particular, esta situaci´on distingue claramente la diferencia entre conocimiento compartido por un grupo (operador EB) y conocimiento com´un. Ejemplo 6.1.N´umeros consecutivos. Dos agentes, Asmodeo (a) y Belfegor (b), se encuentran cara a cara. Cada uno de ellos tiene dibujado un n´umero en su frente, de tal forma que asabe el n´umero de bybsabe el n´umero de a, pero ninguno de ellos conoce su propio n´umero (pero s´ı saben que tienen alg´un n´umero dibujado). Adem´as, tambi´en conocen comunmente que se tienen las siguientes condiciones sobre los n´umeros: Son naturales mayores que 0. 6.3. ALGUNOS EJEMPLOS 79 Son consecutivos Una pregunta que podemos hacernos inicialmente es la siguiente: ¿bajo qu´e circunstancias alguno de los agentes (o ambos) puede deducir el n´umero que tiene en su frente? Empezemos describiendo la situaci´on como un modelo de Kripke. El conjunto de estados ser´ıa S:= {(n, m)∈N2|n=m+ 1 o n =m−1}; esta representaci´on de los estados es autodescriptiva en cuanto a las proposiciones at´omicas que se satisfacen en cada uno de ellos, que representaremos como an(“el agente atiene el n´umero n”) y bm (“el agente btiene el n´umero m”). Las relaciones de accesibilidad pueden caracterizarse de la siguiente forma: Ra(m, n)(m′, n)⇐⇒ m=m′o(m=n+1 y m′=n−1) o(m=n−1y m′=n+1) Rb(m, n)(m, n′)⇐⇒ n=n′o(n=m+1 y n′=m−1) o(n=m−1y n′=m+1) La figura 6.1 es una representaci´on visual de este modelo. En particular, esta figura nos permite contestar r´apidamente a la pregunta que nos hicimos antes: los ´unicos estados donde alg´un agente puede conocer su propio n´umero son el (1,2), donde se tiene M, (1,2) ⊨Kbb2, y el (2,1), donde se tiene M, (2,1) ⊨Kaa2. En cualquier otro estado, ninguno de los agentes conoce su propio n´umero. Supongamos por ejemplo que nos encontramos en el estado (3,2); en tal caso, se tiene b2, pero bconsidera posible b4. En particular, se tiene M, (3,2) ⊨¬b4∧¬Ea,b¬b4. S´ı que se tiene M, (3,2) ⊨Ea,b¬a5: en efecto, en todos los estados accesibles desde (3,2) tanto para acomo para bse satisface la f´ormula ¬a5. No obstante, no se tiene Ea,bEa,b¬a5, puesto que tenemos la “cadena” de estados accesibles (3,2) ∼b(3,4) ∼a(5,4), por lo que ¬KbKa¬a5; por lo tanto, tenemos M, (3,2) ⊨Ea,b¬a5∧ ¬Ea,bEa,b¬a5. Razonando de manera similar para n´umeros cada vez mayores, tenemos M, (3,2) ⊨Ea,bEa,b¬b6∧ ¬Ea,bEa,bEa,b¬b6 M, (3,2) ⊨Ea,bEa,bEa,b¬a7∧ ¬Ea,bEa,bEa,bEa,b¬a7 y as´ı sucesivamente. En definitiva, para cualquier n´umero natural n, por inmenso que sea, no podemos afirmar que sea conocimiento com´un el hecho ¬ansi nes impar o¬bnsi nes par (supongamos que es par). M´as a´un: dado que un razonamiento absolutamente an´alogo podr´ıa hacerse en cualquier otro estado de la “rama superior” del modelo M– es decir, el conjunto R∗ a,b((3,2)) – el hecho de que esto no sea conocimiento com´un es conocimiento com´un, M, (3,2) ⊨¬Ca,b¬bn∧Ca,b¬Ca,b¬bn Esta situaci´on puede resultar un tanto sorprendente, porque, en un principio, podr´ıa esperarse que, en el estado (3,2), ambos agentes pudiesen suponer que ninguno de ellos considera posible que ninguno de ellos considera posible (...) algo tan alejado de la realidad como que el n´umero del agente bes el 666. Es precisamente por esto que 80 CAP´ ITULO 6. CONOCIMIENTO COM ´ UN Figura 6.1: Una representaci´on del modelo Men el ejemplo de los n´umeros consecutivos. Las l´ıneas continuas representan la relaci´on de accesibilidad del agente a, y las l´ıneas discontinuas representan la relaci´on de accesibilidad del agente b. este ejemplo es especialmente bueno para mostrar lo restrictivas que son las condiciones para que se tenga conocimiento com´un de alg´un hecho. □ 6.3.2. Ni˜nos con Barro La situaci´on de los ni˜nos con barro, o de los ni˜nos embarrados, es uno de los ejemplos cl´asicos estudiados en la l´ogica epist´emica. Se trata de un ejemplo sugerente, dado que plantea una situaci´on en la que, tras nrepeticiones de una misma frase, un conjunto de agentes logra obtener conocimiento com´un sobre un hecho que en las n−1 repeticiones anteriores desconoc´ıan. Ejemplo 6.2.Ni˜nos con barro. Una serie de ni˜nos, convenientemente llamados a1, ..., an, est´an jugando en un charco de barro fuera de su casa, ensuci´andose en el proceso; en particular, algunos de estos ni˜nos se han manchado la frente con barro. En cierto momento, escuchan que su padre los llama, de modo que se dirigen de vuelta a su casa; una vez que han llegado, su padre les pide que se coloquen en c´ırculo, de tal forma que cada uno de los ni˜nos puede ver si la frente de cualquiera de los otros ni˜nos est´a o no manchada (pero no sabe si est´a manchada o no su propia frente). Entonces el padre anuncia p´ublicamente la siguiente afirmaci´on: “Al menos uno de vosotros tiene la frente manchada de barro.” Acto seguido, les hace la siguiente petici´on: “Que den un paso hacia delante aquellos que sepan si su frente est´a o no manchada.” Si nadie da un paso hacia delante, el padre seguir´a repitiendo la petici´on (hasta que alguien d´e un paso hacia delante). Se puede probar entonces que, si mde los n ni˜nos tienen la frente manchada, entonces los mni˜nos con la frente manchada dar´an un paso hacia delante tras mrepeticiones de la petici´on. 6.3. ALGUNOS EJEMPLOS 87 •n= 0 •p0<1 2arbitrario, “probabilidad umbral” •p=1 n+2 =1 2 Protocolo para el general a: i)aenv´ıa un mensaje mcon las instrucciones de ataque a b ii) Si en un periodo inferior a 2Tllega una respuesta de la forma Kb(KaKb)n/2m: a) Hacer n:= n+ 2 b) Hacer pa:= 1 n+2 c) Hacer pb:= 1 n+1 d) Si pa< p0: 1) Si pb< p0, FINALIZAR PROTOCOLO 2) En otro caso, enviar (KaKb)(n/2)+1 y FINALIZAR PROTOCOLO e) En otro caso, enviar (KaKb)(n/2)+1 y volver al paso II iii) Si en un periodo mayor a 2Ttodav´ıa no ha llegado una respuesta de b, ABORTAR PROTOCOLO Protocolo para el general b: i)bespera indefinidamente un mensaje mcon las instrucciones de ataque de a. Si llega el mensaje: a) Hacer n:= n+ 1 b) Hacer pa:= 1 n+2 c) Si pb< p0, enviar el mensaje Kbm; FINALIZAR PROTOCOLO d) En otro caso, enviar el mensaje Kbmy continuar ii) Si en un periodo inferior a 2Tllega una respuesta de la forma Kb(KaKb)n/2m: a) Hacer n:= n+ 1 b) Hacer pb:= 1 n+2 c) Hacer pa:= 1 n+1 d) Si pb< p0: 1) Si pa< p0, FINALIZAR PROTOCOLO 2) En otro caso, enviar Kb(KaKb)(n−1)/2y FINALIZAR PROTOCOLO e) En otro caso, enviar Kb(KaKb)(n−1)/2y volver al paso II iii) Si en un periodo mayor a 2Ttodav´ıa no ha llegado una respuesta de b, ABORTAR PROTOCOLO 88 CAP´ ITULO 6. CONOCIMIENTO COM ´ UN □ A continuaci´on ofreceremos una explicaci´on detallada de lo que ocurre en este protocolo, aunque no se trata de algo excesivamente complejo. No obstante, como siempre, consideramos que la comprensi´on del mismo se hace mucho m´as sencilla si se tiene claro lo que se pretende conseguir con ´el. Informalmente, este protocolo, si se realiza “hasta el final”, garantiza (obviamente) que el general que ha recibido el ´ultimo mensaje (por ejemplo, b) sepa que lo ha recibido, pero tambi´en que el general que lo ha enviado (por ejemplo, a) sepa que la probabilidad de haberlo recibido de bes superior a 1−p0; m´as a´un, btambi´en sabe que asabe que la probabilidad de que bhaya recibido el mensaje es superior a 1 −p0, y atambi´en sabe que la probabilidad de que bconozca el hecho anterior tambi´en es superior a 1 −p0; y as´ı sucesivamente. En la descripci´on del protocolo anterior, paypbrepresentan en cada caso la probabilidad que cada general asigna al evento “I≡El mensajero es interceptado” en el momento en el que uno de ellos recibe un nuevo mensaje. El hecho de que ambas probabilidades tengan que ser menores que el “umbral” para detener el env´ıo de mensajes es crucial para que se cumplan las propiedades que expondremos a continuaci´on; por otra parte, si solo una de estas probabilidades (a saber, la del propio general y no la de su compa˜nero) es la que est´a por debajo de este umbral, dicho general env´ıa un ´ultimo mensaje pero no espera respuesta. Supongamos, por ejemplo, que el general aes el primero en asignar una probabilidad inferior al umbral al evento I. Entonces aenv´ıa un ´ultimo mensaje, sabiendo que la probabilidad de llegue a su destino es mayor que 1 −p0. Supongamos tambi´en que, efectivamente, el mensaje llega a su destino (en este caso el general b); entonces, btambi´en sabe que asabe que la probabilidad de que su mensaje haya llegado a su destino es mayor que 1 −p0. Por otra parte, ano sabe que el mensaje ha llegado a su destino, pero s´ı sabe que si el mensaje ha llegado a su destino, entonces bsabe que asabe que la probabilidad de que el mensaje haya llegado a su destino es mayor que 1−p0; es decir, asabe que la probabilidad de que bsepa que asepa que la probabilidad de que el mensaje haya llegado a su destino es mayor que 1−p0es mayor que 1−p0. El general b, por su parte, tambi´en conoce el hecho anterior, y podemos seguir iterando de esta forma. Formalmente, esto se traducir´ıa en la validez de las siguientes f´ormulas: Ka(Pa(˜ K(n+1) ab m)>1−p0) KbKa(Pa(˜ K(n+1) ab m)>1−p0) KaPa((KbKa(Pa(˜ K(n+1) ab m)>1−p0)) >1−p0) KbKa(Pa((KbKa(Pa(˜ K(n+1) ab m)>1−p0)) >1−p0)) . . . (KbKaP>1−p0 a)nm∀n∈N Ka(Pa((KbKaP>1−p0 a)nm)>1−p0)∀n∈N (6.2) El razonamiento informal expuesto en el ejemplo 6.4 excluye desde un primer momento la posibilidad de obtener conocimiento com´un sobre alg´un hecho que tenga que ser transmitido a trav´es de un mensaje; no obstante, las iteraciones sucesivas de 6.3. ALGUNOS EJEMPLOS 89 los operadores (KbKaP>1−p0 a) apuntan a posibles “generalizaciones probabil´ısticas” del mismo, en la l´ınea de la propuesta de Halpern y Fagin [3]. Si el protocolo se realiza hasta el pen´ultimo paso, es decir, uno de los generales (por continuar con el ejemplo anterior, a) llega a FINALIZAR PROTOCOLO pero el otro general ABORTA PROTOCOLO (porque no le llega el ´ultimo mensaje de confirmaci´on), entonces no son ciertas aquellas de las f´ormulas cuyo operador “m´as externo” es Kb; por lo tanto, el general atendr´ıa un problema, ya que acabar´ıa atacando la ciudad ´el solo. No obstante, lo que garantiza la parte probabil´ıstica del protocolo es precisamente que la probabilidad de que esto ocurra sea considerada “´ınfima”. Por otra parte, si alguno de los generales ABORTA PROTOCOLO antes de que tanto pacomo pbsean menores que p0, el otro tambi´en ABORTA PROTOCOLO, y simplemente decidir´ıan no atacar (y esperar otra oportunidad mejor, o algo as´ı). De hecho, t´ecnicamente ni siquiera es necesario que el protocolo hubiese sido acordado de antemano: en su primer mensaje, junto con las instrucciones para atacar la ciudad, el general apodr´ıa haber incluido tambi´en las directrices del protocolo (m´as a´un: si el general brecibe el mensaje y considera que la “probabilidad umbral” es demasiado grande, puede proponer un umbral menor en su primera respuesta). Evidentemente no estamos teniendo en cuenta otras consideraciones, como la de la confidencialidad o la autenticidad de los mensajes, o las posibles estrategias que podr´ıa seguir un potencial “interceptor antag´onico” que conociese los contenidos de los intercambios; no obstante, creemos que la sencillez de este ejemplo es parte de lo que lo hace sugerente y extrapolable a casos mucho m´as complejos. No descartamos la posibilidad de obtener otros protocolos similares que resuelvan este problema de forma todav´ıa m´as satisfactoria; la f´ormula general para la predicci´on a posteriori del par´ametro ptras la realizaci´on de nexperimentos bayesianos independientes sucesivos es y+1 n+2, donde yes el n´umero de ´exitos y nes el n´umero de realizaciones, de modo que los generales podr´ıan tener en cuenta tambi´en el n´umero de mensajes interceptados; simplemente habr´ıa que detallar algo m´as la cuesti´on de c´omo se llegar´ıa a un consenso, en el caso de que el mensajero fuese interceptado, sobre si lo ha sido “en el camino de ida” o “en el camino de vuelta”. Tambi´en podr´ıa estudiarse en este sentido la posibilidad de establecer un umbral superior para la “probabilidad de intercepci´on” a partir de la cual ambos generales se resignar´ıan a simplemente no atacar. 90 CAP´ ITULO 6. CONOCIMIENTO COM ´ UN 7. Sistemas axiom´aticos 7.1. Idea y motivaci´on La idea de interpretar la verdad de f´ormulas en relaci´on a modelos constituye un enfoque relativamente moderno en el desarrollo de la l´ogica como campo de estudio. Mucho m´as com´un, al menos en t´erminos hist´oricos (podemos remontarnos, de nuevo, hasta al menos Arist´oteles), es encontrarse con una concepci´on de los sistemas, teor´ıas y razonamientos l´ogicos como un conjunto de proposiciones que se obtienen aplicando unas determinadas reglas de deducci´on a una serie de premisas o axiomas – tal concepci´on es, adem´as, mucho m´as cercana a la que existe en el “imaginario colectivo”1. Que dicha idea sea m´as antigua no significa que de alguna forma est´e pasada de moda: por el contrario, podr´ıa decirse que es precisamente a partir del Siglo XX cuando vemos una enorme intensificaci´on cuantitativa, de la mano de un mayor refinamiento conceptual en las herramientas y t´ecnicas utilizadas, en los esfuerzos para tratar de desarrollar y estudiar tales sistemas de deducci´on oc´alculo l´ogico, con figuras tan colosales como David Hilbert sentando las bases y la direcci´on de esta nueva deriva. Se pueden citar muchos motivos para el inter´es en este tipo de cuestiones, pero la mayor´ıa puede trasladarse al contexto de nuestro trabajo como sigue: si bien el enfoque sem´antico en el que nos hemos centrado aqu´ı nos permite interpretar sin problemas si una determinada f´ormula es o no verdadera en un determinado estado de un modelo, no nos proporciona un procedimiento conveniente (en t´erminos computacionales, por ejemplo) para saber qu´e f´ormulas son verdaderas en dicho modelo, o m´as a´un, en una determinada familia de modelos. En este cap´ıtulo presentamos brevemente un conjunto de sistemas axiom´aticos, ya conocidos, para los lenguajes que hemos estudiado, sin proporcionar ejemplos y solo explicaciones muy breves de los mismos; en este sentido, este cap´ıtulo podr´ıa entenderse m´as bien como un anexo. S´ı que queremos observar, como “hecho curioso”, que muchos de los axiomas y reglas de deducci´on que aparecen aqu´ı tienen su an´alogo en cap´ıtulos anteriores como “f´ormulas v´alidas en una familia de modelos” – por ejemplo, algunas de las propiedades de omnisciencia l´ogica en LK(proposici´on 2.2). Para LPK[ ] yLPKC[ ], proporcionamos algunas propuestas a modo de conjetura, en aras de confirmarlas o refinar sus aspectos problem´aticos a trav´es de investigaciones posteriores. 7.2. Sistemas axiom´aticos Informalmente hablando, un sistema axiom´atico puede entenderse como una “forma sint´actica” de especificar una l´ogica (a diferencia de la “forma sem´antica” que hemos estudiado a lo largo de este trabajo). Consta de un conjunto de “f´ormulas b´asicas”, 1Si se me permite decir algo en tono personal, puedo atestiguar que, de hecho, esta es la imagen que yo mismo ten´ıa de la l´ogica antes de empezar a escribir este trabajo. 91 92 CAP´ ITULO 7. SISTEMAS AXIOM ´ ATICOS los axiomas2, y un conjunto de reglas de inferencia, que permitir´ıa deducir el resto de f´ormulas (v´alidas) a partir de los axiomas dados. M´as concretamente: Definici´on 7.1. Derivaci´on de una f´ormula en un sistema axiom´atico. Sea Xuna axiom´atica con axiomas Ax1, ..., Axny reglas Ru1, ..., Ruk, donde cada regla Rujes de la forma “de φ1, ..., φar(j), deducir φ”; decimos que ar(j)es la “aridad” de la regla. Una derivaci´on de φen Xes una sucesi´on finita φ1, ..., φmde f´ormulas tales que: φm=φ Para cada φien la sucesi´on se tiene: •O bien φies una instancia de uno de los axiomas en X •O bien es el resultado de aplicar alguna de las reglas Ruja una cantidad ar(j)de f´ormulas en la sucesi´on cuyo ´ındice sea menor que i. Si φtiene una derivaci´on en X, escribimos ⊢Xφ, o simplemente ⊢φsi Xest´a claro por el contexto. En tal caso decimos que φes un teorema de X. □ Las dimensiones sem´antica y axiom´atica de un lenguaje l´ogico se relacionan a trav´es de los siguientes conceptos: Definici´on 7.2. Solidez y completitud Sea Lun lenguaje l´ogico. En lo que sigue, Xser´a un sistema axiom´atico sobre L, y Xser´a una clase sem´antica tal que el lenguaje Lser´a interpretable sobre ella. Xes completo con respecto a Xpara Lsi para toda f´ormula φ∈ L, se tiene X⊨φ⇒⊢Xφ. Xes s´olido3con respecto a Xpara Lsi para toda f´ormula φ∈ L, se tiene ⊢Xφ⇒ X ⊨φ. □ Como apunte final sobre estas anotaciones te´oricas previas, en el contexto de la l´ogica modal existen conceptos m´as restrictivos de solidez y completitud, que b´asicamente restringen el uso de los operadores modales de necesitaci´on (como nuestro operador epist´emico Ka) a la hora de hacer derivaciones l´ogicas a partir de premisas (otro concepto que tampoco hemos estudiado aqu´ı). Como hemos comentado ya, el objetivo de esta secci´on es proporcionar lo m´as b´asico para que un lector no familiarizado con estos conceptos pueda sacar alguna conclusi´on aproximadamente ´util de los sistemas axiom´aticos que proporcionamos a continuaci´on. No obstante, si el lector desea profundizar sobre este asunto, lo referimos a las partes relevantes de van Ditmarsch 2Los axiomas suelen proporcionarse como especificaciones, y no como f´ormulas concretas. Por ejemplo: si un axioma es Ka(φ→ψ)→(Kaφ→Kaψ), esto indica que cualquier f´ormula de esta forma (con φyψf´ormulas arbitrarias) es v´alida en el sistema axiom´atico. Por otra parte, las implementaciones concretas de los axiomas ser´an llamadas instancias de los mismos. 3A menudo esta propiedad tambi´en se conoce con el nombre de adecuaci´on. 7.2. SISTEMAS AXIOM ´ ATICOS 93 [1] (para una introducci´on m´as completa que la nuestra recomendamos el cap´ıtulo 2, secci´on 2.2.3; para quien realmente quiera profundizar, recomendamos los cap´ıtulos 7 y 8). 7.2.1. LK Definici´on 7.3. Sistema axiom´atico K.Definimos Kcomo el sistema axiom´atico constituido por: Todas las instancias de tautolog´ıas proposicionales Distribuci´on de la implicaci´on a trav´es de Ka Ka(φ→ψ)→(Kaφ→Kaψ) Modus ponens. De φyφ→ψ, inferir ψ. Necesitaci´on de Ka.De φinferir Kaφ. □ Definici´on 7.4. Sistema axiom´atico S5.Definimos S5como el sistema axiom´atico resultante de a˜nadir a Klos siguientes axiomas: Verdad Kaφ→φ Introspecci´on positiva Kaφ→KaKaφ Introspecci´on negativa ¬Kaφ→Ka¬Kaφ □ Teorema 7.1. El sistema axiom´atico Kes s´olido y completo respecto a la clase sem´antica K(es decir, la de todos los modelos de Kripke) para LK. El sistema axiom´atico S5es s´olido y completo respecto a la clase sem´antica S5(modelos epist´emicos) para LK. □ 7.2.2. LKC 94 CAP´ ITULO 7. SISTEMAS AXIOM ´ ATICOS Definici´on 7.5. Sistema axiom´atico S5C.Definimos S5Ccomo el sistema axiom´atico resultante de a˜nadir a S5los siguientes axiomas y reglas: Distribuci´on de la implicaci´on a trav´es de CB CB(φ→ψ)→(CBφ→CBψ) Mix CBφ→(φ∧EBCBφ) Inducci´on del conocimiento com´un CB(φ→EBφ)→(φ→CBφ) Necesitaci´on de CB.De φ, inferir CBφ. □ Teorema 7.2. El sistema axiom´atico S5Ces s´olido y completo respecto a la clase sem´antica S5para LKC. □ 7.2.3. LK[ ] Definici´on 7.6. Sistema axiom´atico PA.Definimos PA como el sistema axiom´atico resultante de a˜nadir a S5los siguientes axiomas: Permanencia at´omica [φ]p↔φ→p Anuncios y conjunci´on [φ] (ψ∧χ)↔([φ]ψ∧[φ]χ) Anuncios y negaci´on [φ]¬ψ↔(φ→ ¬[φ]ψ) Anuncios y conocimiento [φ]Kaψ↔(φ→Ka[φ]ψ) Composici´on de anuncios [φ] [ψ]χ↔[φ∧[φ]ψ]χ □ 7.2. SISTEMAS AXIOM ´ ATICOS 95 Observaci´on 7.1.Obs´ervese que los nuevos axiomas de PA se corresponden con las reescrituras proporcionadas en el teorema 3.1. □ Teorema 7.3. El sistema axiom´atico PA es s´olido y completo respecto a la clase sem´antica S5para LK[ ]. □ 7.2.4. LKC[ ] Definici´on 7.7. Sistema axiom´atico PAC.Definimos PAC como el sistema axiom´atico resultante de a˜nadir las siguientes reglas a PA: Necesitaci´on de CB.De φinferir CBφ. Necesitaci´on de [ψ].De φinferir [ψ]φ. Anuncios y conocimiento com´un. De χ→[φ]ψyχ∧φ→EBχ, inferir χ→[φ]CBψ. □ Observaci´on 7.2.Obs´ervese que el axioma Anuncios y conocimiento com´un se corresponde con el teorema 6.2. □ Teorema 7.4. El sistema axiom´atico PAC es s´olido y completo respecto a la clase sem´antica S5para LKC[ ]. □ 7.2.5. LPK Definici´on 7.8. Sistema axiom´atico S5P(MEAS).Definimos S5P(MEAS) como el sistema axiom´atico resultante de a˜nadir a S5los siguientes axiomas y reglas: Axiomas para razonar sobre desigualdades lineales (consultar Halpern- Fagin [3]) No negatividad Pa(φ)≥0 Evento seguro Pa(⊤) = 1 Aditividad Pa(φ∧ψ) + Pa(φ∧ ¬ψ) = Pa(φ) 96 CAP´ ITULO 7. SISTEMAS AXIOM ´ ATICOS Distributividad. Si φ↔ψes una tautolog´ıa proposicional, entonces Pa(φ) = Pa(ψ) □ Definici´on 7.9. Sistema axiom´atico S5P.Definimos S5Pcomo el sistema axiom´atico resultante de cambiar en S5P(MEAS)el axioma Aditividad por los dos siguientes: Principio de inclusi´on-exclusi´on Pa(φ1∧... ∧φk)≥X I⊆{1,...,k},I=∅ (−1)#(I)+1Pa ^ i∈I φi! Evento imposible Pa(⊥) = 0 □ Teorema 7.5. El sistema axiom´atico S5Pes s´olido y completo para la clase sem´antica S5P(modelos de Kripke probabil´ısticos cuya “parte modal” est´a en S5) para LPK. El sistema axiom´atico S5P(MEAS)es s´olido y completo respecto a la clase sem´antica S5P(MEAS)(´ıdem pero solo los modelos que satisfacen MEAS) para LPK.□ Teorema 7.6. Propiedades adicionales en modelos probabil´ısticos. Sea Props un subconjunto de {CONS,OBJ,UNIF,SDP}, y sea Axiomas el correspondiente subconjunto de {Ax1, Ax2, Ax3, Ax4}, donde los Axison los axiomas que definiremos a continuaci´on. Entonces S5P∪Axiomas (resp. S5P(MEAS)∪Axiomas) constituye una axiomatizaci´on s´olida y completa respecto a la clase de los modelos epist´emicos probabil´ısticos satisfaciendo las propiedades en Props (resp. satisfaciendo las propiedades en Props yMEAS). Ax1 Kaφ→(Pa(Kaφ) = 1) Ax2 (Q1Pa(φ1) + ... +QkPa(φk)≥Q)→(Q1Pb(φ1) + ... +QkPb(φk)≥Q) Ax3Si φes una f´ormula de la forma Q1Pa(φ1)+...+QkPa(φk)≥Qo la negaci´on de una f´ormula de tal forma, entonces φ→(Pa(φ) = 1) Ax4Si φes una f´ormula de la forma Q1Pa(φ1)+...+QkPa(φk)≥Qo la negaci´on de una f´ormula de tal forma, entonces φ→Kaφ □ Bibliograf´ıa [1] Hans van Ditmarsch, Wiebe van der Hoek, y Barteld Kooi. Dynamic Epistemic Logic. Springer, 2008. [2] Johan van Benthem. Modal Logic for Open Minds. Center for the study of language and information, 2010. [3] Ronald Fagin y Joseph Y. Halpern. Reasoning about knowledge and probability. Journal of the Association for Computing Machinery, 41(2):340–367, 1994. [4] Barteld P. Kooi. Probabilistic dynamic epistemic logic. Journal of Logic, Language and Information, 12:381–408, 2003. [5] George G. Roussas. An Introduction to Probability and Statistical Inference. Academic Press, 2003. [6] Mordechai Ben-Ari. Mathematical Logic for Computer Science. Springer, 1993. [7] Stanford Encyclopedia of Philosophy. Modal logic. Disponible en https://plato. stanford.edu/entries/logic-modal/, (2023/04/29). [8] Stanford Encyclopedia of Philosophy. Intensional logic. Disponible en https: //plato.stanford.edu/entries/logic-intensional/, (2023/04/28). [9] Stanford Encyclopedia of Philosophy. Medieval theories of modality. Disponible en https://plato.stanford.edu/entries/modality-medieval/, (2023/06/15). [10] Immanuel Kant. Cr´ıtica de la Raz´on Pura. Taurus, 2005. Una traducci´on al espa˜nol de Pedro Ribas. Con fines comparativos, incluye varias de las ediciones originales y de algunas notas al pie de p´agina. [11] Edmund L. Gettier. Is justified true belief knowledge? Analysis, 23:121–123, 1963. Texto disponible en la p´agina web http://www.ditext.com/gettier/gettier. html (2023/06/01). [12] Joseph Y. Halpern. Lexicographic probability, conditional probability, and nonstandard probability, 2009. Disponible en https://arxiv.org/abs/cs/0306106v2 (2023/06/17). [13] Unifying zero-knowledge proofs of knowledge, 2009. Disponible en https:// crypto.ethz.ch/publications/files/Maurer09.pdf. [14] Jean-Jacques Quisquater, Louis Guillou, y Tom Berson. How to explain zeroknowledge protocols to your children. In Advances in Cryptology – CRYPTO ’89: Proceedings. Lecture Notes in Computer Science, volume 435, pages 628–631, 1990. [15] Andrew Gelman, John B. Carlin, Hal S. Stern, y Donald B. Rubin. Bayesian Data Analysis. Columbia University, 1995. Disponible en http://www.stat.columbia. edu/∼gelman/book/. 103 104 BIBLIOGRAF´ IA [16] Hans van Ditmarsch. Dynamics of lying, 2011. Disponible en https://personal. us.es/hvd/fpubs/f3KRA lyingNancy.pdf (07-11-2023).