Lógica modal computacional

Algoritmos efectivos

Daniel Gorín y Sergio Mera

1er cuatrimestre de 2010

Repaso

Estuvimos viendo. . .Complejidad de distintas lógicas modalesEn particular, algoritmos óptimos, pero imprácticos!

Hoy vamos a verAlgoritmos con peor complejidadPero buen comportamiento empírico en casos promedio

Satisfacibilidad proposicionalCuestión de((((hhhhadivinar buscar modelos

Algoritmo NP para satisfacibilidad proposicionalDada una fórmula ϕ:

1 Adivinar una valuación v para las variables de ϕ2 Devolver 1 sii v |= ϕ

Obviamente, no sirve como algoritmo efectivo

Algoritmo DPLL (Davis-Putnam-Logemann-Loveland)Dada una fórmula ϕ en clause normal form

1 Buscar (“backtracking”) una valuación que satisfaga ϕ2 Devolver 1 sii se encuentra tal valuación

Es la base de todos los SAT Solvers modernosPero éstos agregan mucha “inteligencia”!

DPLL en más detalle

Clause Normal Form(CNF)Conjunción de disyunciones de literales (cláusulas)Ej. (p1 ∨ ¬p2 ∨ p3) ∧ (p2 ∨ p3 ∨ ¬p4) ∧ (¬p1 ∨ ¬p3)

Reglas de DPLL

Splitv‖S

v[p7→>]‖S | v[p7→⊥]‖S p indefinido en v

Unit>v‖S∧(C∨p)v[p7→>]‖S p indefinido en v y v 6|= C

Unit⊥v‖S∧(C∨¬p)

v[p7→⊥]‖S p indefinido en v y v 6|= C

Failv‖S∧C× v 6|= C

Ejemplo

EjercicioDecidir si ϕ = C1 ∧ C2 ∧ C3 ∧ C4 ∧ C5 ∧ C6 es sat., donde:

C1 = ¬p1 ∨ p2 ∨ p3

C2 = p1

C3 = ¬p2 ∨ p3

C4 = p2 ∨ ¬p3

C5 = p2 ∨ p3

C6 = ¬p2 ∨ ¬p3

Del dicho al hecho. . .

Detalles que hacen la diferencia al implementar DPLLSplit corresponde al backtracking, aplicarla poco!Tener buenas heurísticas sobre qué p elegir en cada SplitImplementar:

Conflict analysis: qué está forzando el backtracking?Learning: agregar cláusulas con estas nuevas restriccionesBackjumping: basado en esto, poder volver más de un paso

Usar estructuras de datos especialesImplementar otras heurísticas (restarting, etc.)

Transformaciones a CNF

Toda fórmula tiene una equivalente en CNFPor ejemplo, usar la siguiente reescritura:

¬¬ϕ ; ϕ¬(ϕ ∧ ψ) ; (¬ϕ ∨ ¬ψ)¬(ϕ ∨ ψ) ; (¬ϕ ∧ ¬ψ)

ϕ ∨ (ψ ∧ χ) ; (ϕ ∨ ψ) ∧ (ϕ ∨ χ)

Pero tenemos este. . . TeoremaNingún polinomio acota el tamaño de una equivalente en CNF.

Existen transformaciones a CNF que. . .Devuelven una fórmula no equivalente, pero equisatisfacibleSon polinomiales!Se basan en introducir nuevos símbolos; por ejemplo:

ϕ ∨ (ψ ∧ χ) ; (ϕ ∨ p) ∧ (¬p ∨ ψ) ∧ (¬p ∨ χ)

Satisfacibilidad de K via DPLL

Algoritmo NPSPACE para K-satisfacibilidadDada una fórmula ϕ

1 Adivinar un Hintikka set H que contenga a ϕ2 Devolver 1 sólamente si:

para cada 3ψ ∈ H, {ψ} ∪ {χ | 2χ ∈ H} es satisfacible

DPLL modalDada una fórmula ϕ en modal clause normal form (mCNF)

1 Obtener (via DPLL) un Hintikka set H que contenga a ϕ2 Si para cada 3ϕ ∈ H, {ϕ} ∪ {χ | 2χ ∈ H} es satisfacible

Devolver 13 Si no (i.e. si cierto {ϕ} ∪ {χ | 2χ ∈ H} no es satisfacible)

Obtener (via DPLL) una extensión de H que contenga a¬3ϕ ∨

_{¬2χ | 2χ ∈ H}

Volver al punto 2.4 Devolver 0 siempre que una búsqueda por DPLL falle

DPLL modalDetalles de implementación

Modal Clause Normal Form (mCNF)mCNF: Conjunción de cláusulas modalesCláusula modal: disyunción de literales modalesLiterales modales: p, ¬p, 2χ, ¬2χ (con χ cláusula modal)Valen las mismas observaciones hechas para CNF!

De modal a proposicional, ida y vueltaUsamos dos mappings ;p y ;m

pi ;p qpi qpi ;m pi

2χ ;p q2χ q2χ ;m 2χ

Dada ϕ, usamos ;p para obtener una fórmula prop. αDada una v |= α, v induce un único Hintikka set sobre ϕCon ;m recuperamos los literales modales elegidos por v.

Ejemplo

EjercicioDecidir si ϕ = C1 ∧ C2 ∧ C3 ∧ C4 ∧ C5 es sat., donde:

C1 = p1

C2 = ¬p1 ∨ ¬2(p1 ∨ p2)C3 = ¬p1 ∨ p2

C4 = ¬p2 ∨2p1

C5 = ¬p1 ∨2p2

DPLL modalOptimizaciones

No recomenzar de cero cada vezHay SAT solvers que dejan agregar cláusulas y continuarLuego, si obtuvimos una valuación v tal que:

Exige que {¬2χ,2ψ1, . . .2ψn} sea satisfaciblesPero probamos que {χ, ψ1, . . . ψn} no lo es

Debemos agregar la cláusula 2χ ∨ ¬2χ1 ∨ · · · ∨ ¬2χn

Y recontinuamos (salvando el “esfuerzo” en obtener v)

Caching1 Si vimos que {¬2χ,2ψ1, . . .2ψn} es satisfacible, recordarlo2 Si luego queremos ver si H = {¬2ϕ,2ϕ1, . . .2ϕk} es sat,

y sabemos que un H′ es sat., con H′ ⊇ H, entonces H es sat.

Satisfacibilidad modal ((((((((hhhhhhhhadivinando buscando modelosTableaux modales

Algoritmo NTIME(f ) para lógicas con modelos f -acotadosDada una fórmula ϕ:

1 Adivinar un modeloM de tamaño a lo sumo f (|ϕ|)2 Adivinar un w en el dominio deM3 Devolver 1 siiM,w |= ϕ

Obviamente, no sirve como algoritmo efectivo

Algoritmo de TableauxDada una fórmula ϕ

1 Buscar (“backtracking”) sistemáticamente un modelo de ϕ2 Devolver 1 sii se encuentra tal modelo

Es la base de muchos razonadores para lógicas modalesVarios tipos de tableaux, vamos a ver sólo tableauxetiquetados

¿Qué es un algoritmo de tableau (etiquetado)?

Reglas de tableaux: definen un árbol de posibilidades.Los nodos de un árbol son, en general:

Fórmulas “etiquetadas” w:ψ, donde w es una etiqueta.“Relaciones” Rwv donde w y v son etiquetas.

Cada rama del árbol codifica de alguna manera un modelo.Las reglas nos dicen:

1 Cómo detectar que una rama no nos sirve (reglas de clash).2 Cómo expandir una rama sin clash.

Algoritmo: Dada ϕ, explorar (backtracking) el árbol de w:ϕ.

Ejemplo de tableaux etiquetadoLógica modal con pasado

Reglas de expansión

∧ w:ϕ∧ψw:ϕ,w:ψ ∨ w:ϕ∨ψ

w:ϕ | w:ψ

3w:3ϕ

Rwv,v:ϕ (nuevo v) 3−1 w:3−1ϕRvw,v:ϕ (nuevo v)

2w:2ϕ,Rwv

v:ϕ 2−1 w:2−1ϕ,Rvwv:ϕ

Reglas de clash

clashw:p,w:¬p⊥

Asumimos fórmulas en negation normal form.Las reglas 3 y 3−1 se usan sólo si no existe tal v en la rama.

Ejemplo

Ejercicio

Decidir si ϕ = p1 ∧3p2 ∧32−12(¬p2 ∨2−1¬p1) es satisfacible.

Tableau etiquetado para la lógica modal con pasadoCompletitud

Teorema (Completitud)Si Γ es una rama abierta y saturada para ϕ, ϕ es satisfacible.

DemostraciónExtraemos un modelo de Γ. SeaMΓ = 〈WΓ,RΓ,VΓ〉 donde

WΓ = {w | w:ϕ ∈ Γ}RΓ = {(w, v) | Rwv ∈ Γ}

VΓ(p) = {w | w:p ∈ Γ}Sea ψ la mínima fórmula tal que w:ψ ∈ Γ yMΓ,w 6|= ψ.

ψ 6= p (porque en ese caso w ∈ V(p)) y ψ 6= ¬p (habría clash)ψ 6= ψ1 ∨ ψ2 porque tendríamos w:ψi ∈ Γ y no sería mínimaψ 6= ψ1 ∧ ψ2 por razones análogasψ 6= 3χ porque tendríamos Rwv,w:χ ∈ Γ y no sería mínimaψ 6= 2χ, ψ 6= 2−1χ y ψ 6= 3−1χ por razones análogas.

Luego, no existe tal fórmula; w:ψ ∈ Γ implicaM,w |= ψ

Tableau etiquetado para la lógica modal con pasadoTerminación

TeoremaToda rama saturada de un tableaux para ϕ es finita.

DemostraciónSea Γ una rama saturada y LABEL(w) = {ψ | w:ψ ∈ Γ}.

1 LABEL(w) es finito porque son todas subfórmulas de ϕ.2 Luego, {v | Rwv ∈ Γ} es finito (ver nota sobre 3 y 3−1).3 Entonces, Γ es infinito sii existe una cadena w1,w2, . . . tal

que wi generó a wi+1 usando la regla 3 ó la regla 3−1.4 Pero si w genera a v, d(LABEL(w)) > d(LABEL(v)) (sale por

inducción en la derivación de Γ, d es profundidad modal).5 Por lo tanto, para algún j, d(LABEL(wj)) = 0, absurdo.

Detalles de implementación

¿Importa el orden en que aplicamos las reglas?No afecta la terminación del algoritmo.Sí afecta el tamaño del árbol generado!

Considerar: (p1 ∨ p2) ∧ ((p3 ∨ p4) ∧ ((p5 ∨ p6) ∧ (p ∧ ¬p)))¿Qué sucede si siempre preferimos aplicar ∧ antes que ∨?¿Qué sucede si siempre preferimos aplicar ∨ antes que ∧?

Heurísticas básicasUsar reglas sin branching (e.g., ∧) antes que aquellas conbranching (como ∨)Usar reglas proposicionales (e.g., ∧ y ∨) antes que reglasmodales (como 3 y 2)

Optimizaciones

Las reglas ∧, ∨ y clash son un tableaux proposicionalPero es preferible DPLL para razonamiento proposicionalLos demostradores basados en tableaux incorporanelementos de DPLL:

Branching semántico (una forma de splitting)BackjumpingCaching

Terminación en casos más complejosUn tableaux para K sobre la clase de modelos transitivos (K4)

∧ w:ϕ∧ψw:ϕ,w:ψ ∨ w:ϕ∨ψ

w:ϕ | w:ψ clashw:p,w:¬p⊥

3w:3ϕ

Rwv,v:ϕ (nuevo v) 24w:2ϕ,Rwvv:ϕ,v:2ϕ

TeoremaEste tableaux es completo para K4.

DemostraciónDada Γ (abierta y saturada) armamosMΓ con

RΓ = {(w, v) | Rwv ∈ Γ}+

Sup. 2ϕ es la mínima tal que w:2ψ ∈ Γ yMΓ,w 6|= 2ψ.Luego, existe {Rwv1,Rv1v2, . . .Rv2vk} ⊂ Γ yM,w 6|= ϕ.Γ está saturada por 24, entonces {vi:ϕ, vi:2ϕ} ⊂ Γ (∀i ≤ k)

Luego vk:ϕ ∈ Γ y 2ϕ no sería mínima. El resto queda igual.

Terminación en casos más complejosBlocking

¿Podemos repetir el argumento de terminación?¿Qué sucede al ejecutar este tableaux sobre w:(3p ∧23p)?Conclusión: una rama abierta saturada puede no ser finita!

Técnicas de blockingSe usan para garantizar terminación en implementacionesIdea:

Algunas w:ϕ pueden “bloquearse” o “desbloquearse”Algunas reglas no se aplican sobre fórmulas bloqueadas

Muchos tipos de blockingsubset blockingdynamic blocking. . .

En cada caso se debe probar terminación. . . y completitud!