Lógica Modal Computacional ¿De qué se trata esta materia?

Lógica Modal Computacional

¿De qué se trata esta materia?

Daniel Gorín & Sergio Mera

1er Cuatrimestre 2010,Buenos Aires, Argentina

Generalidades

I En esta materia vamos a hablar de lógicas modales.I La materia va a ser más que nada teórica, pero vamos a ver

también aplicaciones prácticas.I Como requisito para la cursada, hay que tener nociones básicas

de lógica de primer orden.I Se recomienda haber cursado Lógica y Computabilidad.

: Lógica Modal Computacional ¿De qué se trata esta materia? Daniel Gorín & Sergio Mera

Organización de la materia

I Horario: martes de 19.00 a 22.00hs.I Vamos a intentar dejar la primera media hora para consultas.

I Evaluación: un take home al final de la cursada.I La materia da 2 puntos.

I Vamos a tener guías de ejercicios al estilo del take home final.Algunos los vamos a ir resolviendo en el pizarrón.

I La página de la materia es

http://www.glyc.dc.uba.ar/lmc

Ahí vamos a subir las prácticas y las slides de las clases, así quechequeen cada tanto las novedades.

I Y la lista de mail es

[email protected]


http://www.glyc.dc.uba.ar/lmc

¿Qué es lo que vamos a ver?

I Usualmente hablamos de La Lógica: lógica de primer orden.

∀x.(madruga(x)→ ∃y.(dios(y) ∧ ayuda(y, x)))

I Aunque también sabemos que existe la lógica proposicional:

comerChicle→ ¬cruzarLaCalle

I ¿Cuántas lógicas hay? ¿Dos?


Estructuras simples para lenguajes simplesPensemos en un grafo coloreado:

SS

S

greenpink

green

S

SS

pink

greengreen

Sgreen S

)

pinkSgreen

S(green pink


Estructuras simples para lenguajes simples

I Esto que vimos es un ejemplo de una lógica modal.I Aparentemente es un lenguaje muy cómodo para hablar de

grafos coloreados. ¿Servirá para algo más? Ya veremos...I Una primera ventaja:

I Decidir si una fórmula es cierta en lógica de primer orden esindecidible.

I En esta lógica modal, el problema es computable! (para los quesepan de qué se trata, es PSPACE-complete).


Una Familia de Lenguajes

I A veces, el lenguaje que acabamos de describir no es adecuado:

I La Lógica Modal investiga el espectro de posibles lenguajes quepueden usarse para describir estructuras relacionales.

I Algunas preguntas que uno se puede hacer son:I ¿Podemos definir algoritmos de inferencia para estos lenguajes?I ¿Cuán eficientes son?I ¿Cuáles son los límites de expresividad de estos lenguajes? Es

decir, ¿podemos decir más o menos cosas que con otras lógicas?I Otra perspectiva es mirarlos desde el punto de vista del diseño de

una lógica. Dado un problema en particular:I ¿Qué lenguaje lógico me resulta más cómodo de usar?I ¿Cuál tiene un buen algoritmo de inferencia?I ¿Qué operadores realmente necesito?


Posibles AplicacionesI Los lenguajes de la familia de las lógicas modales pueden usarse

en áreas muy diversas:I Verificación de Software y Hardware.I Representación de Conocimientos.I Linguística Computacional.I Inteligencia Artificial.I Filosofía.I Epistemología.I . . .

I ¿Por qué? Muchas cosas pueden ser representadas como grafos(i.e., estructuras relacionales).Y como vimos, los lenguajes modales fueron desarrolladosespecialmente para razonar sobre grafos y describir suspropiedades.


No Estamos Solos

I Aunque no parezca, estamos haciendo Lógica Clásica.I Los lenguajes que estuvimos discutiendo son fragmentos del

lenguaje de primer (o segundo) orden. Lo único que hicimos fueelegir sólo una parte del lenguaje que necesitábamos para unaaplicación dada.

I Esta es exactamente la forma en que vemos hoy por hoy a loslenguajes modales, como una forma de investigar fragmentosparticularmente interesantes de los lenguajes clásicos.

I Donde “interesantes” significaI Decidibles, expresivos, de “baja” complejidad, modulares, etc.


No Todo es Teoría en esta Vida

Además de ver propiedades teóricas de estos lenguajes, tambiénvamos a ver aplicaciones prácticas:

I Lógicas para la descripción: un juego de aventura de textoI Model checking.I Y varios demostradores automáticos en escena.


Clase #1

Temario:I Lógica de primer orden: sentencias y fórmulas.I El lenguaje modal visto como un lenguaje de grafos decorados.I Sintaxis y semántica del lenguaje modalI Extensiones: Operador inverso, modalidad universal, PDL,

lógicas híbridas.

Lógica de Primer OrdenI La noción de verdad en Lógica de Primer Orden tiene que ver

con sentencias, es decir, fórmulas sin variables libres.I Si pensamos en una sentencia ϕ cualquiera, y un modeloM, la

sentencia va a ser verdadera o falsa en todo el modelo. No vamosa poder hablar de una parte del modelo en particular.

M1

w1

w2

w3

w4

w5

w6

M2

w1

w2

w3

w4

w5

w6

I M1 |= ∀x.(red(x)→ (∃y.xRy ∧ red(y)))I M2 6|= ∀x.(red(x)→ (∃y.xRy ∧ red(y)))


Lógica de Primer OrdenI Esto significa que la extensión de una sentencia ϕ de LPO es o

bien vacío o bien todo el dominio.I ¿Cómo podemos hacer para hablar de partes del modelo?I Podemos usar fórmulas con variables libres:

M1

w1

w2

w3

w4

w5

w6

M2

w1

w2

w3

w4

w5

w6

I sRed(x) = red(x)→ (∃y.xRy ∧ red(y))I [sRed(x)]M1 = [red(x)→ (∃y.xRy∧ red(y))]M1 = {w1, . . . ,w6}I [sRed(x)]M2 = [red(x)→ (∃y.xRy∧ red(y))]M2 = {w2, . . . ,w6}


Perspectiva internaI De alguna manera, lo que estamos buscando es intentar expresar

una noción de perspectiva interna, en donde queremos ver laspropiedades de un elemento del modelo con respecto al resto.

I Con eso en mente, vamos a dejar por un momento LPO, y vamosa trabajar con un lenguaje especialmente diseñado para eso.

I Vamos a usar un lenguaje modalI Ahora, si queremos expresar la idea anterior, podemos decir:

w1

w2

w3

w4

w5w6

M,w1 |= red → 3redI Pareciera mucho más fácil de escribir así, ¿no?


Lenguaje Modal: un lenguaje para grafos decoradosVeamos otros ejemplos. Pensemos en un grafo orientado, con figurasdentro de cada nodo:

see

seesee

Queremos describir qué figu-ras un nodo puede “ver”.

Desde la perspectiva de un nodo n, el significado de los operadoresmodales va a ser:

I 〈see〉x: n puede ver la figura x en algún vecino.I [see]x: n puede ver la figura x en todos sus vecinos.


Lenguaje Modal: un lenguaje para grafos decorados

Ahora podemos hacerle “preguntas” al modelo:

w1

w2

w3

I Ve w1 un rectángulo?M,w1 |= 〈see〉rectangle

I ... y en dos “pasos”?M,w1 |= 〈see〉〈see〉rectangle

I Ve w1 un círculo y un triángulo?M,w1 |= 〈see〉circle ∧ 〈see〉triangle


Lenguaje Modal: un lenguaje para grafos decorados

Ahora podemos hacerle “preguntas” al modelo:

w2

w1

w3

I Ve w2 un círculo y un rectángulo?M,w2 |= 〈see〉circle ∧ 〈see〉rectangle

I ... y en el mismo vecino?M,w2 |= 〈see〉(circle ∧ rectangle)

I w2 ve sólo círculos?M,w2 |= [see]circle


Lenguaje Modal: un lenguaje para grafos decoradosTambién podemos verlo como un lenguaje para describir procesos.

I Esto significa ver a los elementos del modelo como un conjuntode estados computacionales.

I Y ver a las relaciones binarias como acciones que transformanun estado en otro.Veamos este modelo:

s

a

a b

b

t

I Esto muestra un autómata finito para el lenguaje anbm.I En este caso podemos trabajar con dos diamantes 〈a〉 y 〈b〉.I Está claro que todas las fórmulas con la forma

〈a〉 . . . 〈a〉〈b〉 . . . 〈b〉t

son satisfechas en el nodo s.


Lenguaje Modal: una perspectiva realmente internaMiremos este ejemplo:

I Hay varias habitaciones, pintadas de rojo y negro, y en cada una hay unteletransportador (wow!).

I Este transportador nos mueve entre algunas de las habitacionessiguiendo alguno de los posibles caminos (uno entra en eltransportador y aparece en alguna otra habitación al azar).

I ¿Podemos diferenciar entre estos dos ‘laberintos’?

I Aunque uno de los modelos tiene solo 2 elementos y el otro 4, no hayforma de notar esto ‘desde adentro’ de los modelos. Como vamos a ver,esta es una característica importante de las lógicas modales relacionadacon la expresividad.


Lenguaje Modal Básico: sintaxis y semánticaVamos a definir ahora la sintaxis formal del lenguaje modal básico.

I La signatura del lenguaje va a consistir de dos conjuntos infinitosnumerables, disjuntos entre sí:

I PROP = {p1, p2, . . . }, el conjunto de variables proposicionales.I REL = {R1,R2, . . . }, el conjunto de símbolos de relación.

I El conjunto de fórmulas FORM en la signatura 〈PROP, REL〉 estádefinido como:

FORM := p | ¬ϕ | ϕ ∧ ψ | 〈R〉ϕ

en donde p ∈ PROP,R ∈ REL y ϕ,ψ ∈ FORM.I El operador [R] se define como [R]ϕ = ¬〈R〉¬ϕ (de igual forma

que ∀x.ϕ es ¬∃x.¬ϕ)


Lenguaje Modal Básico: sintaxis y semánticaPara poder definir formalmente la semántica, vamos primero a ver quées un modelo de Kripke.

I Un modelo de Kripke es una estructura 〈W, {Ri},V〉 dondeI W es un conjunto no vacío de elementos.I {Ri} es un conjunto de relaciones binarias en W.I V : PROP → ℘(W) es una función de valuación (V(p) es el

conjunto de elementos donde vale p).I Intuitivamente, un modelo de Kripke es un grafo dirigido con

“decoraciones”.

p

pq

qr

R1

R1

R1


Lenguaje Modal Básico: sintaxis y semántica

Ahora sí, podemos definir la semántica de la lógica modal básica:

I Dado un modeloM = 〈W, {Ri},V〉 y un estado w ∈ W, larelación de satisfacibilidad es

M,w |= p iff w ∈ V(p), para p ∈ PROP

M,w |= ¬ϕ iff M,w 6|= ϕM,w |= ϕ ∧ ψ iff M,w |= ϕ yM,w |= ψM,w |= 〈R〉ϕ iff ∃w′ ∈ W tq R(w,w′) yM,w′ |= ϕ

I Vamos a decir que ϕ es válida en un modeloM sii en todos losestados w ∈ W valeM,w |= ϕ, y en ese caso escribimosM |= ϕ.


Extensiones

I Hasta ahora hicimos un repaso de lógica proposicional, lógica deprimer orden y vimos la lógica modal básica.

I Volviendo a la pregunta de cuántas lógicas había, ya sabemosque la respuesta no es dos.

I Como se podrán imaginar, tampoco es tres.I Así como existe el operador 〈R〉, tenemos un amplio “menú” de

operadores modales para usar.I Al combinar estos operadores, conseguimos diferentes lógicas


Extensiones: Operador InversoI Pensemos en la siguiente “línea temporal”

... ...t t t t1 2 3 n

I Claramente, esta estructura puede ser vista como un modelo deKripke.

I El operador 〈R〉 significa “en algún momento en el futuro”.I Y el operador [R] dice “en todo momento futuro”.I Con este lenguaje, ¿podremos decir “en algún momento en el

pasado”?I Más aún, esta idea la podemos querer usar en cualquier tipo de

modelo de Kripke, no sólo en los temporales.


Extensiones: Operador Inverso

I La necesidad de expresar esto, nos lleva a agregar el operadorinverso, que vamos a notar como 〈R〉−1.

I Para extender la lógica modal básica con este operador, primerotenemos que agregarlo a nuestra sintaxis:

FORM := p | ¬ϕ | ϕ ∧ ψ | 〈R〉ϕ | 〈R〉−1ϕ

I ¿Necesitamos hacer algún cambio en los modelos?I Parecería que no...I Ahora lo que nos falta es extender la semántica.


Extensiones: Operador Inverso

I La relación de satisfacibilidad que teníamos antes era:

M,w |= p iff w ∈ V(p), para p ∈ PROP

M,w |= ¬ϕ iff M,w 6|= ϕM,w |= ϕ ∧ ψ iff M,w |= ϕ yM,w |= ψM,w |= 〈R〉ϕ iff ∃w′ ∈ W tq R(w,w′) yM,w′ |= ϕ

I ¿Cómo podemos hacer para definir el comportamiento de estenuevo operador?

I Tenemos que agregar el caso del operador a la definición:

M,w |= 〈R〉−1ϕ iff ∃w′ ∈ W tq R(w′,w) yM,w′ |= ϕ


Extensiones: Modalidad Universal

I Otro “feature” que podemos querer es la capacidad de describiralguna propiedad global, que debe cumplirse en todo el modelo.

I Supongamos que estamos modelando un zoológico, y queestamos interesados en la alimentación de los osos y su relacióncon los cuidadores de osos.

I Queremos, por un lado, que estas fórmulas se satisfagan en todoel modelo:

oso ∨ humano oso → 〈MADRE〉osooso → ¬humano oso → [ALIMENTADO](cuidador ∨ madre)

I Y, por otro lado, poder preguntar si existirá algún estado donde:I oso ∧ 〈MADRE〉(oso ∧ humano)I oso ∧ 〈ALIMENTADO〉(¬madre ∧ ¬humano)


Extensiones: Modalidad Universal

I Para poder decir esto, tenemos que agregar la modalidaduniversal, que notamos como A.

I La fórmula Aϕ significa que ϕ es cierta en todos los puntos delmodelo.

I ¿Cómo es la definición formal de la semántica de este operador?I Y una pregunta (para pensar), ¿este operador es lo mismo que el∀ de LPO?


Extensiones: PDL (Propositional Dynamic Logic)

I Imaginemos que queremos modelar el comportamiento deprogramas.

I Para eso, para cada programa (no determinístico) π vamos atener una modalidad 〈π〉 (tenemos infinitas modalidades!).

I La interpretación de 〈π〉ϕ va a ser: ‘alguna ejecución que terminade π desde el estado actual nos lleva a un estado donde vale ϕ’.

I Lo que queremos también es hacer explícita la estructurainductiva de los programas: los programas se pueden componer,iterar, etc, formando nuevos programas.



Si tenemos programas ‘simples’ a, b, c, etc. (y por lo tanto tenemoslas modalidades 〈a〉, 〈b〉, 〈c〉, . . . ) podemos construir programas máscomplejos de la siguiente manera:

I (elección) Si π1 y π2 son programas, entonces π1 ∪ π2 es unprograma. El programa π1 ∪ π2 ejecuta no determinísticamenteπ1 ó π2.

I (composición) Si π1 y π2 son programas, entonces π1;π2 es unprograma. El programa π1;π2 ejecuta primero π1 y luego π2.

I (iteración) Si π es un programa, entonces π∗ es un programa. Elprograma π∗ ejecuta π un número finito (o quizás cero) de veces.

Esto significa que si 〈π1〉 y 〈π2〉 son modalidades, entonces tambiénlo son 〈π1 ∪ π2〉, 〈π1;π2〉 y 〈π∗〉.



I Tenemos que interpretar apropiadamente las modalidades paraque cada operador tenga el significado esperado.

I DefinamosRπ1∪π2 = Rπ1 ∪ Rπ2

Rπ1;π2 = Rπ1 ◦ Rπ2 (la composición de las relaciones)Rπ∗ = (Rπ1)

∗ (la clausura reflexo-transitiva de Rπ1)I Entonces,

M,w |= 〈π〉ϕ sii ∃w′.Rπ(w,w′) yM,w′ |= ϕ



I Con estas definiciones, ¿qué nos dice esta fórmula?

〈π∗〉ϕ↔ ϕ ∨ 〈π;π∗〉ϕ

I ¿Debería ser válida? Demostrarlo!I ¿Y esta?

[π∗](ϕ→ [π]ϕ)→ (ϕ→ [π∗]ϕ)

I Pensar en el esquema de inducción. . .


Extensiones: Lógica Híbrida

Volvamos al ejemplo de las figuras geométricas. ¿Cómo hacemos paradecir?

I ¿Puede w1 verse a sí mismo?I ¿Son realmente w1 y w2 estados

distintos?

I Lo que necesitamos para expresar esto es poder nombrarmundos, y una noción de igualdad.


Extensiones: Lógica HíbridaHL(@) es la extensión de la lógica modal básica con:

I nombres (nominales): son un nuevo conjunto de símbolosatómicos, que representan a los estados. La clave es que cadanominal tiene que ser cierto en un único estado. En general seescriben como i, j, k, . . .

I @: el operador ‘at’. @iϕ es verdadera sii ϕ es verdadera en elmundo denotado por i.

Ahora podemos expresar...

w1

w2

w3

i

j

k I ¿Puede w1 verse a sí mismo?@i〈see〉i

I ¿Son realmente w1 y w2 estadosdistintos?@i¬j


Extensiones: Lógica Híbrida

Entonces, la definición de la sintaxis es:I A la signatura 〈PROP, REL〉 que teníamos antes, le tenemos que

agregar un nuevo conjunto NOM = {i, j, k, . . . } de nominales.I Las fórmulas bien formadas ahora son:

FORM := p | i | ¬ϕ | ϕ ∧ ψ | 〈R〉ϕ | @iϕ

en donde p ∈ PROP,R ∈ REL, i ∈ NOM y ϕ,ψ ∈ FORM.I ¿Hay que hacer algún cambio en lo modelos? ¿Cómo es la

semántica deHL(@)?I Ejercicio!


Documents

Lógica Modal Computacional ¿De qué se trata esta materia?