Download Lógicas Modales Computacionales Clase # 6: Decidibilidad

Lógicas Modales Computacionales
Clase # 6: Decidibilidad
Carlos Areces / Daniel Gorín / Sergio Mera
2do Cuatrimestre 2006,
Buenos Aires, Argentina
Propiedad de modelos finitos. . . ¿para qué?
I
Usando el método de selección vimos que la lógica modal básica
tiene la propiedad de modelos finitos
I
Tener esta propiedad y ser decidible, ¿es lo mismo?
I
No necesariamente. . . pero ayuda
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Propiedad de modelos finitos y satisfacibilidad
El problema de la satisfacibilidad
I
Sea ϕ una fórmula de alguna lógica L con signatura S
I
Y sea C alguna clase de modelos (e.g. todos los modelos)
I
Problema: ¿Es ϕ satisfacible (respecto a C)?
Supongamos que. . .
I
L tiene la propiedad de modelos finitos
I
Para todo modelo finito M, es decidible si M está en C
I
En ese caso, podemos proponer el siguiente algoritmo:
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Modelos finitos ≈ semi-decidibilidad
funcion buscarModelo(ϕ, C)
1. S ← símbolos que aparecen en ϕ
2. para n ← 1, 2, 3, . . .
3.
4.
para M ← modelos de S de tamaño n
si M está en C y M |= ϕ
devolver ¡SI!
Fig. 1 – buscarModelo.java
I
Observar que para cada n, hay finitos M posibles
I
Y cada M es finito y tiene finitos símbolos para interpretar
I
Siempre que ϕ sea satisfacible va a responder que sí
I
Pero nunca responde que no!
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Modelos finitos + Axiomatización ≈ Decidibilidad
I
Si L además tiene una axiomatización consistente y completa A
I
(Y es decidible si ψ es axioma de A, lo cual es razonable!)
I
Entonces podemos escupir uno por uno los teoremas de L
I
¡Y usar eso para semi-decidir si ϕ es insatisfacible!
funcion buscarContradiccion(ϕ)
1. para ψ ← todos los teoremas de L enumerados con A
2.
si ψ == ¬ϕ
devolver ¡NO!
Fig. 2 – buscarContradiccion.java
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Modelos finitos + Axiomatización ≈ Decidibilidad
I
Dado ϕ podemos correr ambos programas en paralelo!
buscarModelo.java & buscarContradiccion.java
Fig. 3 – decidirSatisfacibilidad.sh
I
Si ϕ es satisfacible, buscarModelo.java da la respuesta
I
Si ϕ es insatisfacible, la da buscarContradiccion.java
I
Y una de las dos cosas tiene que pasar!
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
¿Prueba esto que la lógica modal básica es decidible?
I
Sabemos que la lógica modal básica tiene modelos finitos
I
La clase de todos los modelos es trivialmente decidible
I
¿Tenemos una axiomatización consistente, completa y decidible?
I
En la Práctica 2 presentamos una que es consistente y
decidible. . .
I
Y pronto veremos que además es completa
I
Hasta que eso pase. . . sigue el acto de fé
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
¿Y qué pasa si tomamos otras clases de modelos?
I
Tomemos una signatura S con un único símbolo de relación R
I
Y sea CT la clase de los modelos donde R es transitiva
I
¿Cómo vemos si la lógica modal básica sobre CT es decidible?
Si pudiéramos ver que
I
1. Tiene la propiedad de modelos finitos
2. Es axiomatizable
entonces ya está!
I
Pregunta ¿y cómo vemos si tiene modelos finitos?
I
Posible respuesta ¿Igual que hicimos con la lógica modal básica?
I
Pero los modelos que obtenemos por selección son árboles. . .
I
¡y los árboles no están en CT !
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Aparecen las filtraciones
I
I
Otro método de probar la propiedad de modelos finitos
Idea:
I
I
I
I
Ventajas:
I
I
I
Nos va a dar margen para jugar con las relaciones
Prueba un resultado más fuerte (modelo acotado)
Aclaración:
I
I
: Bisimulaciones
No se seleccionan finitos sucesores (en un árbol)
En cambio, se cocientan todos los elementos del modelo
El criterio para cocientar es: “cosas que ϕ no puede distinguir”
En lo que sigue asumimos que hay una única relación
Pero la generalización es trivial
Carlos Areces / Daniel Gorín / Sergio Mera
Preliminares
Definición (Conjunto cerrado por subfórmulas)
Un conjunto de fórmulas Σ está cerrado por subfórmulas si para todo
par de fórmulas ϕ y ψ, si ϕ ∈ Σ y ψ es subfórmula de ϕ, entonces
ψ∈Σ
Definición
Sea Σ un conjunto cerrado por subfórmulas, y sea M = hW, R, Vi.
Llamamos !Σ a la relación de equivalencia sobre W dada por
!Σ := {(w, v) | para todo ϕ ∈ Σ, M, w |= ϕ sii M, v |= ϕ}
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Con ustedes, las filtraciones
Definición (Filtración)
Sea M = hW, R, Vi y sea Σ un conjunto cerrado por subfórmulas. Se
llama filtración de M vía Σ a cualquier modelo Mf = hW f , Rf , V f i
que cumpla
I.
II .
W f = W/ !Σ
Si Rwv, entonces Rf [w][v]
III .
Si Rf [w][v] y 3ϕ ∈ Σ, entonces M, v |= ϕ implica M, w |= 3ϕ
IV .
V f (p) = {[w] | M, w |= p} para todo p ∈ Σ
I
I
: Bisimulaciones
Las condiciones II y III tienen algo de zig y zag
Intuitivamente, nos dicen qué pares tiene que tener Rf como
mínimo (II) y como máximo (III).
Carlos Areces / Daniel Gorín / Sergio Mera
Filtraciones. . . ¿para que?
Teorema (Filtration Theorem)
Sea Mf la filtración vía Σ de M, donde Σ es un conjunto de fórmulas
de la lógica modal básica, cerrado por subfórmulas. Para toda
fórmula ϕ ∈ Σ y todo elemento w de M, M, w |= ϕ sii Mf , [w] |= ϕ
Demostración.
Inducción en ϕ. Caso base, por definición de V f . Booleanos, por HI.
I Si 3ψ ∈ Σ y M, w |= 3ψ
I
I
I
I
Si 3ψ ∈ Σ y Mf , [w] |= 3ψ
I
I
: Bisimulaciones
Existe v tal que Rwv y M, v |= ψ
Por II, Rf [w][v] y como ψ ∈ Σ, por HI Mf , [v] |= ψ
Con lo cual Mf , [w] |= 3ψ
Para algún [v], Rf [w][v] y Mf , [v] |= ψ
Como ψ ∈ Σ, por HI, M, v |= ψ; luego, por III M, w |= 3ψ
Carlos Areces / Daniel Gorín / Sergio Mera
Filtraciones, mito o realidad
I
I
Si Mf cumple ciertas condiciones, vale el Filtration Theorem
Preguntas:
I
I
: Bisimulaciones
¿Serán condiciones que se pueden cumplir?
O sea, dado M y Σ, existirá siempre una filtración de M vía Σ
Carlos Areces / Daniel Gorín / Sergio Mera
Filtraciones, ¡realidad!
Teorema
Sea M = hW, R, Vi y sea Σ un conjunto cerrado por subfórmulas.
Llamemos W f a W/ !Σ , y V f a la valuación que cumple con IV.
Entonces, Ms = hW f , Rs , V f i y Ml = hW f , Rl , V f i son filtraciones de
M vía Σ, donde
Rs [w][v]
sii
∃w0 ∈ [w] y ∃v0 ∈ [v] tal que Rw0 v0
Rl [w][v]
sii
para toda 3ϕ ∈ Σ, M, v |= ϕ implica M, w |= 3ϕ
Además, si Mf = hW f , Rf , V f i es una filtración de M vía Σ,
entonces Rs ⊆ Rf ⊆ Rl
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Filtraciones, ¡realidad!
Demostración.
Veamos que Ms = hW f , Rs , V f i es una filtración (el
resto. . . ejercicio!). Alcanza con ver que Rs cumple con II y III.
I
Rs cumple II por definición
I
Para III, supongamos que Rs [w][v] y que M, v |= ϕ para 3ϕ ∈ Σ
I
Necesitamos ver que M, w |= 3ϕ
I
Como Rs [w][v], existen w0 ∈ [w] y v0 ∈ [v] tales que Rwv
I
Pero ϕ ∈ Σ, y v0 !Σ v, con lo cual M, v0 |= ϕ
I
Luego, M, w0 |= 3ϕ
I
Pero como w0 !Σ w y 3ϕ ∈ Σ, M, w |= 3ϕ
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Propiedad de modelos finitos vía filtraciones
Teorema
Sea ϕ una fórmula de la lógica modal básica. Si ϕ es satisfacible, es
satisfacible en un modelo finito, que contiene a lo sumo 2m nodos,
donde m es la cantidad de subfórmulas de ϕ (m ≤ |ϕ|)
Demostración.
I
Supongamos que ϕ es satisfacible, i.e., M, w |= ϕ
I
Sea Σ := {ψ | ψ es subfórmula de ϕ}. Observar que Σ es finito
I
Sea, además, Mf una filtración de M vía Σ.
I
Vale Mf , [w] |= ϕ
I
¿Cuántos elementos tiene Mf ?
I
¡A lo sumo 2|Σ| !
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Filtraciones =⇒ propiedad de modelo acotado
I
Probamos una propiedad más fuerte que “modelo finito”
I
Porque podemos dar una cota para el tamaño del modelo
I
Y si podemos hacer eso, ya no necesitamos una axiomatización
para tener decidibilidad
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
Propiedad de modelo acotado ≈ decidibilidad
funcion buscarModeloAcotado(ϕ, C)
1. S ← símbolos que aparecen en ϕ
2. k ← cota para el tamaño de un modelo para ϕ
3. para n ← 1, 2, 3, . . . , k
4.
5.
para M ← modelos de S de tamaño n
si M está en C y M |= ϕ
devolver ¡SI!
6. devolver ¡NO!
Fig. 4 – buscarModeloAcotado.java
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera
¿Y cómo se usa esto con otras clases de modelos?
I
Vimos que hay al menos dos filtraciones posibles (la que usa Rs
y la que usa Rl )
I
Es fácil ver que, por ejemplo, ni Rs ni Rl preservan la
transitividad de R
I
¡Pero veremos que hay otras Rf que sí!
: Bisimulaciones
Carlos Areces / Daniel Gorín / Sergio Mera