LÓGICA MODAL

Carlos Amores MFV 2013 - 2014Carlos Rubio

ÍndiceIntroducción a la lógica modalTipos de lógicas modales● Lógica temporal y Model Checking

○ Lógica temporal lineal (LTL)○ Lógica temporal computacional (CTL)○ CTL*

● Lógica epistémica○ Lógica KT45

● Lógica doxástica● Lógica deóntica

Introducción a la Lógica Modal

La lógica modal surgió para tratar las nociones de necesidad y posibilidad.

Nace con el objetivo de clarificar la relación entre implicación material y relación de consecuencia.

Lógica ModalLa lógica modal es tan antigua como el Organon (artículo que trata de la lógica) de Aristóteles, tuvo su gran desarrollo durante la Edad Media.Sin embargo la lógica modal contemporáneo surge a principios del siglo XX. Los trabajos de Saul Kripke " 1963: Semantical Analysis of Modal Logic, I: Normal Propositional Calculi; 1965: Semantical Analysis of Modal Logic, II: Non-Normal Modal Propositional Calculi; 1965: Semantical Analysis of Intuitionistic Logic I" fueron decisivos para el estudio de la lógica modal.

Lógica Modal

Kripke aporta la herramienta básica para el análisis semántico de la lógica modal: la semántica de mundos posibles. La semántica de mundos posibles es una herramienta para el análisis de una colección importante de expresiones: modales, temporales, doxástica, epistémica, deóntica, entre otras.

La Lógica Modal representa situaciones que son regidas por un esquema de modalidad.

Lógica Modal

Se diferencian de las lógicas convencionales en el sentido que una modalidad indica las condiciones en las que se hace cierta o falsa alguna afirmación.

Define modalidades, representadas, por ejemplo, por las siguientes palabras: ● Puede, podría, quizás, ha de, probablemente, a veces, posiblemente,

necesariamente, etc.

Lógica Modal

Tomemos las siguientes afirmaciones:

• “El PC va lento. Puede estar infectado con un virus.”• “De no haber sido por el filtro anti-spam, tu PC podría haberse infectado con un virus.”

Lógica Modal

Ambas hablan de la posibilidad que el PC se infecte con un virus. No obstante, en la primera, se habla de algo que puede pasar en nuestro mundo (posibilidad epistémica) y la segunda habla de algo que podría ocurrir en un mundo paralelo (sin afectar nuestro mundo, es una posibilidad metafísica).

Lógica ModalLa lógica modal sólo agrega dos símbolos al vocabulario de la lógica proposicional( ⊤, ⊥, p, ¬, ˄, ˅, →): el símbolo □ que representa la expresión del lenguaje natural "Siempre" y el símbolo ◊ representa la expresión "Es posible que o alguna vez". En la lógica modal clásica, ambos símbolos son interdefinibles por medio del otro y de la negación:

◊p == ¬□¬p□p == ¬◊¬p

Lógica ModalPROPIEDADES DE LA LÓGICA MODAL

Nombre Fórmula Nombre de la propiedad

T □ ɸ → ɸ Reflexiva

B ɸ → □ ◊ ɸ Simétrica

D □ ɸ → ◊ ɸ

4 □ ɸ → □ □ ɸ Transitiva

5 ◊ ɸ → □ ◊ ɸ Euclídea

□ ɸ ↔ ◊ ɸ Funcional

Lógica ModalDiferentes combinaciones de axiomas dan lugar a diferentes sistemas de lógica modal. Como por ejemplos la lógica modal KT45(S5) o la KT4(S4).Por ejemplo, el sistema S4, que incluye los axiomas T y B, es consistente y completo respecto a las interpretaciones en que R es reflexiva y transitiva.

Otros sistemas de lógica modal conocidos son la lógica deóntica, la lógica temporal, la lógica epistémica y la lógica doxástica.

Introducción a la lógica temporalBreve historia:● La lógica temporal es una extensión de la lógica modal, donde está

presente el tiempo. Se podría decir también que la lógica temporal extiende a la lógica clásica permitiendo especificar en qué momento del tiempo esta teniendo lugar un hecho o proposición.

● Inicialmente propuestas en los 50s para investigaciones filosóficas.● Pnueli (1977) fue el primero en proponerlas para verificación. El

sistema se especificaba como un sistema de axiomas y se probaban propiedades a partir de estos axiomas.

● Clarke y Emerson (1981) automatizan este proceso diseñando algoritmos de verificación eficientes para ciertas lógicas temporales.

● Luego comenzó a estudiarse la complejidad de verificación de estas lógicas (model-checking, parametrized complexity, etc).

Su estudio ha tenido importancia en gran parte de la informática hasta nuestros días.

Esta lógica se utiliza para describir propiedades que debe cumplir un sistema, para después comprobar que estas propiedades son correctas(Model Checking).

Lógica temporal y Model Checking

Lógica temporal y Model CheckingModel checking (MC) es una técnica automática para la verificación de sistemas finitos. En la actualidad una de las técnicas más populares de verificación formal. La verificación utilizando model checking exige la especificación del sistema y de las propiedades deseadas(expresan con conectivas especiales).

En el model checking, tanto el sistema de software como las propiedades deseadas del sistema (seguridad, alcanzabilidad, etc.) se modelan utilizando lenguajes de especificación formal(Maude), es decir, lenguajes basados en conceptos lógico-matemáticos.

Lógica temporal y Model Checking

Algunas de las propiedades típicas que suelen ser especificadas son:● Alcanzabilidad: es posible alcanzar una situación.● Seguridad: es seguro que una situación no sucederá.● Vivacidad: si empieza debe terminar.● Equidad: un número infinito de veces una situación se podrá dar,

se dará o no se dará nunca.Las propiedades son especificadas normalmente a través de lógica temporal.

El proceso MC consiste en la especificación de un modelo, especificación de propiedades y verificación. Esto significa que dada una propiedad deseada p y una estructura del modelo M con un estado inicial s decide si p cumple M; o más precisamente, decide si M, s |= p.

El modelo M es normalmente expresado como un sistema de transición, un grafo dirigido que conforma un árbol computacional (una estructura Kripke). Cada nodo tiene asociado un conjunto de proposiciones atómicas. Los nodos representan estados del sistema, los arcos posibles transiciones.

Lógica temporal y Model Checking

MC está basado en el cálculo y representación de todos los estados posibles alcanzables por el sistema. Una herramienta de model checking responde ‘true’, si el modelo satisface las especificaciones que establecen las propiedades o en caso contrario, genera un contraejemplo.

De esta forma los comprobadores de modelos son usados como debuggers para encontrar problemas, como así también para mostrar la correctitud una vez que se ha finalizado el debugging.

Lógica temporal y Model Checking

Algunos sistemas lógicos basados en lógica temporal son: Lógica computacional en árbol (Computational tree logic, CTL), lógica temporal lineal (Linear-Time temporal logic, LTL) y Lógica temporal de intervalos (Interval temporal logic, ITL).

LTL es una lógica temporal que nos permite referirnos al futuro, en la que el tiempo se modela como una secuencia infinita de estados. A esta secuencia de estados a veces se le llama ruta. LTL fue propuesto por primera vez para la verificación formal de programas de ordenador mediante Amir Pnueli en 1977.

Introducción lógica temporal lineal (LTL)

Unarias: ⊤, ⊥, ¬ɸ, p, (ɸ ˄ ɸ), (ɸ ˅ ɸ), (ɸ → ɸ), (ɸ ↔ ɸ) X ɸ, F ɸ, G ɸ

Binarias: (ɸ U ɸ ), ( ɸ R ɸ )

A X, F, G, U, W, R se les llama conectivas temporales.

● X : “NeXt state” (○), ● F : “Future state” (◊), ● G : “All future state”(Globally) (□)● U : “Until”● R : “Release”

Lógica temporal lineal (LTL)

Lógica temporal computacional (CTL)

CTL es la restricción de CTL* que satisface lo siguiente:

Cada fórmula de camino debe estar precedida por un cuantificador de caminos A o E.

Esta lógica se estudia porque combina buenas propiedades de expresividad y complejidad. Las fórmulas en CTL están dadas por la siguiente gramática:

Lógica temporal computacional (CTL)Algunos ejemplos:● Me va a gustar el chocolate de ahora en adelante

AG.P● Es posible que me guste el chocolate algún día

EF.P● Siempre es posible que de pronto empiece a tener gusto por el

chocolate para el resto de mi vidaAF.EG.P

Lógica temporal computacional (CTL) CTL es ampliamente utilizada en:

● Verificación: Tanto de sistemas hardware como sistemas software.

● Inteligencia Artificial: En particular, en sistemas de planificación de agentes, en los que cada agente planifica sus estrategias de acción teniendo en cuenta las diferentes opciones futuras.

● Formalización de especificaciones y comportamientos de sistemas

CTL*CTL* es un superconjunto de CTL y LTL. Combina diferentes cuantificadores con operadores temporales y combina expresividad de LTL y CTL.En 1981 EM Clarke y EA Emerson inventaron CTL y CTL para comprobación de modelos. CTL* fue definido por EA Emerson y Joseph Y. Halpern en 1986.LTL y CTL se han desarrollado de manera independiente antes de CTL*. Ambos han sido muy importantes en la comprobación de modelos, mientras que CTL* aún no tiene importancia en la práctica.

CTL*Los operadores son los mismos que en los CTL. Sin embargo, en CTL, cada operador temporal(X, F, G, U) tiene que ser precedido directamente por un cuantificador, mientras que en CTL* esto no es necesario.

El cuantificador universal puede definirse en CTL* de la misma manera que para el cálculo de predicados Aɸ == ¬E¬ɸ aunque esto no es posible en CTL.

LTL, CTL y CTL*Hay cosas que se pueden expresar en LTL pero no en CTL y viceversa y por eso se crea CTL* que combina la expresividad de las dos.● Fórmula en CTL * no es posible en LTL ni en CTL:

● Fórmula en LTL que no está en CTL:

● Fórmula de CTL que no está en LTL:

La lógica temporal tiene dos clases de operadores: operadores lógicos y operadores modales. Los operadores lógicos son ¬, ˄, ˅, → (Maude se escriben ¬, /\, \/ , ->) y los operadores modales usan el Linear-Time Temporal Logic (LTL) y Computation Tree Logic (CTL) son □, ○, ◊, U, R (Maude se escriben [], <>, O, R, U).

Gracias a estos operadores, podemos realizar MC para diferentes sistemas(Prácticas).

Lógica temporal y Model Checking

load model-checker.maude

mod PROPS is

pr LOCAL .pr SATISFACTION .

subsort Espacio < State .

op estaEnLaCola : String -> Prop [ctor] .op estaEnElLocal : String -> Prop [ctor] .

eq ([ A | C' persona(S, E, T, O) C | B | N | M ] L) |= estaEnLaCola(S) = true .eq ([ A | C | (persona(S, E, T, O), B) | N | M ] L) |= estaEnElLocal(S) = true .

endm

Lógica temporal y Model Checking

mod TEST ispr PROPS .pr MODEL-CHECKER .

pr LTL-SIMPLIFIER .

*** p1 : “Carlos”, 20, VIP, 0 *** p2 : “Victoria”, 17, noVIP, 0

op initial : -> Espacio . eq initial = [ (p1, p2) | cola-vacia | manager | 5 | 6 ] 4 .endm

Maude> red modelCheck(initial, [] (estaEnLaCola("Carlos") -> <> estaEnElLocal("Carlos"))) .result Bool: true

Maude> red modelCheck(initial, [] (estaEnLaCola("Victoria") -> <> estaEnElLocal("Victoria"))) .CONTRAEJEMPLO!!!

Lógica temporal y Model Checking

CONCLUSIONESA medida que el model checking ha crecido en popularidad, se ha incrementado la importancia de la lógica temporal dentro de la Informática.La lógica temporal sirve para expresar propiedades de sistemas software o hardware y así evitar errores.Por ejemplo, en sistemas de software críticos como sistemas de control de vuelo de aviones o sistemas de control de ascensores, los errores de software deben ser evitados.

Lógica temporal y Model Checking

La lógica epistémica es un campo de la lógica modal que se ocupa del razonamiento sobre el conocimiento. Mientras que la epistemología posee una larga tradición filosófica que se origina en la Grecia Antigua, la lógica epistémica es un desarrollo mucho más reciente con aplicaciones en numerosos campos, tales como filosofía, ciencia computacional teórica, inteligencia artificial, economía y lingüística.

Como otras lógicas, esta también tiene sus orígenes de las fuentes de Aristóteles.

Introducción a la lógica epistémica

La Edad Media a juicio de los historiadores, el periodo más activo de la lógica epistémica, que se desarrolla sobre todo en universidades del norte de Italia donde destacan figuras como Paolo de Venecia, su discípulo Paolo da Pergola o Gaetano de Thiene.

Pero en la Edad Moderna se produce un descrédito de la misma, hace que se abandone temas de gran interés y habrá que esperar hasta el siglo XX para volver a tratar a la lógica epistémica de nuevo.

Lógica epistémica

Durante la década de 1950 se publicaron numerosos trabajos acerca del tema, pero es reciente trabajo del finlandés Georg Heinrik Von Wright, titulado An Essay in Modal Logic publicado en 1951 el que es reconocido como el documento fundacional de la lógica epistémica.

No fue sino hasta 1962 en que Hintikka, escribe Knowledge and Belief, el primer trabajo extenso en que sugiere utilizar modalidades para capturar la semántica del conocimiento en vez de utilizar las premisas aléticas con que típicamente se desarrolla la lógica modal y desde entonces se han realizado numerosas investigaciones y avances.

Lógica epistémica

El operador modal básico de la lógica epistémica, normalmente escrito con el símbolo K , se puede interpretar como significando "se sabe que". Si está representando el conocimiento de uno o más actores se representa con el subíndice i, ( K

i ) .

De tal manera si ponemos Ka ɸ significa “El agente a sabe ɸ ” , o si

pongo ¬ Ka ¬ ɸ significa “El agente a no sabe que no ɸ ”

Lógica epistémica

Ejemplos de proposiciones epistémicasj ==Juan

Q == Cervantes escribió el QuijoteH == Shakespeare escribió Hamlet

Proposiciones epistémicas❖ K j Q: ‘Juan sabe que Cervantes escribió El Quijote’❖ ¬ K j H: ‘Juan no sabe que Shakespeare escribió Hamlet’

K j(Q /\ H)

Lógica epistémica

Algunas propiedades del conocimiento son:● El axioma de distribución: más conocido como K. En términos

epistémicos, establece que si un agente sabe φ y sabe que φ => Ψ , entonces el agente debe saber Ψ.

● La regla de generalización del conocimiento: si φ es válido, entonces lo es K

i φ . Quiere decir que si φ es verdadero en todo mundo que un agente considere mundo posible, entonces el agente i debe conocer φ en todos los mundos posibles.

Lógica epistémica

● El axioma de la verdad o el conocimiento(T): Si un agente conoce hechos, estos deben ser verdaderos. Principal característica que diferencia al conocimiento de la creencia.

● El axioma de la introspección positiva(4): Los agentes saben que es lo que conocen.

● El axioma de la introspección negativa(5): Los agentes saben que es lo que no saben.

Lógica epistémica

Se pueden derivar diferentes lógicas tomando distintos subconjuntos de los anteriores axiomas. La lógica KT45 (S5) resulta de combinar K, T, 4, 5 y la Regla de Generalización del Conocimiento. Por estos las anteriores propiedades se les sabe llamar propiedades S5.

En esta lógica vamos a usar la conectiva modal de la epistémica.A = {1,2,3,….n} K

i p == “El agente i sabe p”

Ejemplo: K 1

p ˄ K 1 ¬ K

2 K

1 p

El agente 1 sabe p, pero el agente 2 no sabe lo que él sabe.

Introducción a la lógica KT45

Una fórmula ɸ de la lógica KT45 se define por la siguiente gramática:ɸ == ⊤ | ⊥ | ¬ɸ | p | (ɸ ˄ ɸ) | (ɸ ˅ ɸ) | (ɸ → ɸ) | (ɸ ↔ ɸ) | K

i ɸ | E

G ɸ | C

G ɸ |

DG

ɸ

● La conectiva modal EG

p, donde G es un subconjunto de A, EG

p quiere decir “Todos miembros de G saben p ”

Si G = {1,2,3,...,n}E

G p equivale a K

1 p ˄ K

2 p ˄ … ˄ K

n p

La lógica KT45

● La conectiva modal CG ɸ quiere decir que “ ɸ es un conocimiento en

posesión de todo agente de G”C

G p equivale a K

1 ɸ ˅ K

2 ɸ ˅ … ˅ K

n ɸ

● La conectiva modal DG ɸ quiere decir que “El conocimiento ɸ está

distribuido entre el grupo G ”Ψ ˄

ɸ ; K

1 Ψ ˄ K

2 ɸ == D

{ 1, 2 } ( Ψ ˄

ɸ )

La lógica KT45

EJEMPLOS DE LOS 3 SABIOS Y LOS 5 SOMBREROS (2 BLANCOS Y 3 NEGROS)

p i

: “Sabio i tiene el sombrero negro”¬ p

i : “Sabio i tiene el sombrero blanco”

T = {C( p1 ˅ p

2 ˅ p

3 ),

C( p1

→ K 2

p 1

), C( ¬ p1

→ K 2

¬ p 1

), C( p

1 → K

3 p

1 ), C( ¬ p

1 → K

3 ¬ p

1 ),

C( p2

→ K 1

p 2

), C( ¬ p2

→ K 1

¬ p 2 ),

C( p2

→ K 3

p 2

), C( ¬ p 2

→ K 3

¬ p 2 ),

C( p3

→ K 1

p 3 ), C( ¬ p

3 → K

1 ¬ p

3 ),

C( p3

→ K 2

p 3 ), C( ¬ p

3 → K

2 ¬ p

3 ) }.

La lógica KT45

EJEMPLOS DE LOS 3 SABIOS Y LOS 5 SOMBREROS (2 BLANCOS Y 3 NEGROS)

C( ¬ K 1

p1

˄ ¬ K 1

¬ p1

)

T, C( ¬ K 1

p1

˄ ¬ K 1

¬ p1

),

C( ¬ K 2

p2

˄ ¬ K 2

¬ p2

) ├ K 3

p3

La lógica KT45

Lógica epistémica y lógica KT45CONCLUSIONES

Este tipo de lógica se utiliza para chequear sistemas de agentes inteligentes utilizados en aplicación como bibliotecas digitales o mercados virtuales.

Introducción a la lógica doxásticaLa lógica doxástica (del griego antiguo δόξα, doxa, "creencia") es una lógica modal que se ocupa del razonamiento acerca de las creencias.Esta lógica utiliza la expresión Bcp que quiere decir “El razonador ‘c’ cree que ‘p’ es verdadero” y el conjunto Bc se refiere al conjunto de creencia de ‘c’.Existe un paralelismo completo entre los razonadores que creen en proposiciones y los sistemas matemáticos que demuestran proposiciones. Utilizando la lógica doxástica, se puede expresar el equivalente epistémico del teorema de la incompletitud de Gödel, como también el teorema de Löb.

TIPOS DE RAZONADORES● Razonador preciso: Un razonador c es preciso si no cree en

ninguna proposición falsa (axioma modal T).

● Razonador impreciso: Un razonador c es impreciso si existe al menos una proposición en la que cree y que no es verdadera

Lógica doxástica

● Razonador presumido: Un razonador c es presumido, si cree que no es impreciso. Un razonador presumido necesariamente incurre en una imprecisión.

● Razonador consistente: Un razonador c es consistente si no cree en una proposición y su negación (axioma modal D).

Lógica doxástica

Lógica doxástica● Razonador normal: Un razonador c es normal si siempre que cree

p, cree también que cree p.

● Razonador peculiar: Un razonador c es peculiar si existe alguna proposición p en la que cree, pero también cree que no cree p. Se dice que un razonador peculiar es necesariamente impreciso pero no necesariamente inconsistente.

Introducción a la lógica deóntica“Deóntico” se deriva del griego δέον "debido" + λόγος "tratado", así pues la Lógica Deóntica (LD) trata acerca de las normas.

El nombre de “lógica deóntica” fue considerada a partir del ensayo de Georg Heinrik Von Wright, “Deontic Logic” publicado en 1951.Von Wright propuso que los conceptos deónticos de obligación, permisividad, prohibición e indiferencia correspondía a los operadores modales de necesidad, posibilidad, imposibilidad y contingencia.

Los operadores deónticos y algunas de sus interpretaciones más comunes son las siguientes:● El operador O qué puede significar “Es obligatorio que..”, “Es

indispensable que ...”, “Es necesario que ...”, etc. ○ Por ejemplo:

El acto de “pagar impuestos”, representamos con el símbolo q, para nosotros es obligatorio y seria :

OqA partir del operador de obligación y de la negación lógica (¬) , es posible definir los operadores de permisión y de prohibición.

Lógica deóntica

● El operador P qué puede significar “Está permitido que ..”, “Es válido que ...”, “Es correcto que ...”, “Es posible que ...”, etc.○ Por ejemplo:

El acto “poder silbar” -> qPq ¬Pq

● El operador Ph que puede significar “Está prohibido que ...”, “El ilícito que ...”, “Es incorrecto que ...”, etc.○ Por ejemplo:

El acto de “conducir borracho” -> qPhq

Lógica deóntica

Lógica deónticaSe puede hacer una tabla de equivalencia entre los operadores mencionados antes:

Oq == Ph¬q == ¬P¬qO¬q == Phq == ¬Pq

¬O¬q == ¬Phq == Pq¬Oq == ¬Ph¬q == P¬q

● El operador F puede significar “Da lo mismo que ...”, “Es facultativo que ...”, etc.

El campo de aplicación de la LD lo constituyen sobre todo discursos discursos argumentativos de tipo moral, ético y jurídico.También se puede usar la LD en el campo de la informática.● Programacion legal o normativa: leyes o normas aplicables para

todos programadores.● En sistemas de alta disponibilidad: aplicar unas normas

obligatoria que deben cumplir estos sistemas como la especificación de un número determinado de excepciones en un periodo de tiempo finito.

● Comportamiento deseado por los usuarios en un sistema.

Lógica deóntica

CONCLUSIONES

El uso de la lógica deóntica sirve para unir dos áreas que se creían separadas cómo son las leyes y la informática, formalizando unas normas jurídicas y estableciendo reglas para la creación programas que sirvan de apoyo para la aplicación de las leyes.

Lógica deóntica

Preguntas