bases formales de la computación - javeriana, cali

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Bases Formales de la Computacion

Gerardo M. Sarria M.

Pontificia Universidad Javeriana

3 de abril de 2009

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

LOGICAS MODALES

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Contenido

1 Logica Modal

2 Logica Temporal

3 Logica Temporal Lineal

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que es la logica Modal?

Variedad de diferentes sistemas

Dificultad para dar una definicion que cubra a todos

Respuesta superficial: una logica que tiene una modalidado muchas modalidades en ella.

Una modalidad es un conectivo que toma una formula (oformulas) y produce una nueva formula con un nuevosignificado.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que es la logica Modal?

Variedad de diferentes sistemas

Dificultad para dar una definicion que cubra a todos

Respuesta superficial: una logica que tiene una modalidado muchas modalidades en ella.

Una modalidad es un conectivo que toma una formula (oformulas) y produce una nueva formula con un nuevosignificado.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que es la logica Modal?

Similar los conectivos logicos clasicos: ¬ toma una formula A yproduce una nueva formula ¬A, o → toma dos formulas A y By produce una formula A→ B.

La unica diferencia es que en la logica clasica, el valor deverdad de ¬A esta determinado unicamente por el valor de A, yel valor de A→ B es una funcion de los valores de A y B.

¡Las modalidades no son funciones de verdad!

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Ejemplos (Modalidades Unarias)

◻A: “es necesario que A”

◇A: “es posible que A”

G A: “siempre en el futuro, A sera cierto”

F A: “en algun momento en el futuro, A sera cierto”

P A: “en algun momento en el pasado, A fue cierto”

Ki A: “el agente i sabe que A”

Bi A: “el agente i cree que A”

[prog]A: “despues de cualquier ejecucion del programaprog , el estado satisface la propiedad A”

⟨prog⟩A: “existe una ejecucion del programa prog , cuyoresultado en un estado satisface la propiedad A”

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Ejemplos (Modalidades Binarias)

A→ B

U(A, B): “hasta que A sea cierta, B es cierta”

t2t1B

A

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Modal Basica: Sintaxis

Alfabeto:

Un conjunto de variables proposicionalesProp = {p1, p2, . . . ,}Conectivos booleanos ¬ y → (∧, ∨ y ↔ se pueden definir)

Modalidad (unaria) ◻ (◇ se puede definir)

Una formula bien formada:

A, B, . . . ∶∶= p ∣ ¬A ∣ A→ B ∣ ◻A

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Definiciones

A ∨ B = ¬A→ B

A ∧ B = ¬(A→ ¬B)A ↔ B = (A→ B) ∧ (B → A)◇A = ¬ ◻ ¬A

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Semantica

¿Como describir axiomaticamente las formulas validas?

Respuesta: Las estructuras de los posibles mundos!

La idea es usar grafos (W , R), R ⊆ W ×W , como modelos parala logica modal y pensar en W como el conjunto de posiblesmundos y R como una relacion alternativa.

(W , R, x) ⊧ ◻A iff (W , R, y) ⊧ A ∀y . x R y

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Semantica

¿Como describir axiomaticamente las formulas validas?

Respuesta: Las estructuras de los posibles mundos!

La idea es usar grafos (W , R), R ⊆ W ×W , como modelos parala logica modal y pensar en W como el conjunto de posiblesmundos y R como una relacion alternativa.

(W , R, x) ⊧ ◻A iff (W , R, y) ⊧ A ∀y . x R y

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Semantica de Kripke

Una estructura de Kripke es una tupla M = ⟨W , R, V ⟩, donde

W es un conjunto no vacıo (posibles mundos)

R ⊆ W ×W es una relacion de accesibilidad

V ∶ (Prop ×W )→ {true,false} es una funcion devaluacion

El grafo proveera la informacion de cuales variablesproposicionales seran verdad en cuales vertices.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Ejemplo

w 4 w 5

w 2w 1 w 3

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Ejemplo

w 4 w 5

w 2w 1 w 3

V (p, w1) = true, V (q, w1) = falseV (p, w2) = true, V (q, w2) = true

V (p, w3) = true, V (q, w3) = falseV (p, w4) = false, V (q, w4) = trueV (p, w5) = false, V (q, w5) = true

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Ejemplo

w 4 w 5

= {p} w 2w 1 = {p}w 3

= {q} = {q}

= {p, q}

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Significado de las Formulas

Dado M = ⟨W , R, V ⟩ y w ∈ W , se define lo que significa parauna formula ser verdad (nocion de satisfacer) en un mundo wde un modelo M:

M, w ⊧ p sii V (p, w) = trueM, w ⊧ ¬A sii M, w ⊭ AM, w ⊧ A→ B sii M, w ⊭ A o M, w ⊧ BM, w ⊧ ◻A sii para todo v accesible desde w

(∀v t.q. R(w , v)), M, v ⊧ A

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Ejemplo

w 4 w 5

= {p} w 2w 1 = {p}w 3

= {q} = {q}

= {p, q}

M, w1 ⊧ ◻qM, w1 ⊧ ¬ ◻ p

M, w1 ⊧ ¬ ◻ ¬pM, w1 ⊧◇p

M, w1 ⊧◇◻ p

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Validez (y Satisfacibilidad)

Una formula A es cierta en un modelo M si se satisface entodos los mundos de M.

Una formula A es valida si es cierta en todos los modelos.

Una formula es satisfacible si su negacion no es valida (sise satisface en por lo menos un mundo de un modelo)

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Validez (y Satisfacibilidad)

Ejemplos:

◻p → ◻p es valido (tautologıa proposicional)

◻(p → p) es valido (porque p → p es verdad en todos lomundos accesibles, donde sea que se este)

◻p → p no es valido (el conjunto {◻p,¬p} es satisfacibleen algunos mundos).

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

Utilidades:

los posibles mundos son estados en una computacion,

R es una relacion de transicion,

V nos dice cuales propiedades son ciertas en cual estado.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

Ejemplo:

Suponga que se tienen dos procesos/agentes A y B.

Cada uno tiene una variable booleana local (A tiene a, Btiene b).

Todo lo que hacen es: cambian el valor de su variable; sesuspenden; luego vuelven a cambiar el valor de nuevo.

Se asume que sus acciones son intercaladas (no seejecutan simultaneamente)

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

Ejemplo:

b

b

a a

w2

w1w4

w3

b

a a

b

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que podemos afirmar de este sistema en la logica modal?

◇¬a ∧ ◇a

◇¬b ∧ ◇b

a ∧ b → ◻(¬a ∨ ¬b)a ∧ b →◇◇ (a ∧ b)

Basicamente, cuales estados se pueden alcanzar y en cuantospasos.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que podemos afirmar de este sistema en la logica modal?

◇¬a ∧ ◇a

◇¬b ∧ ◇b

a ∧ b → ◻(¬a ∨ ¬b)a ∧ b →◇◇ (a ∧ b)

Basicamente, cuales estados se pueden alcanzar y en cuantospasos.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que podemos afirmar de este sistema en la logica modal?

◇¬a ∧ ◇a

◇¬b ∧ ◇b

a ∧ b → ◻(¬a ∨ ¬b)a ∧ b →◇◇ (a ∧ b)

Basicamente, cuales estados se pueden alcanzar y en cuantospasos.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que podemos afirmar de este sistema en la logica modal?

◇¬a ∧ ◇a

◇¬b ∧ ◇b

a ∧ b → ◻(¬a ∨ ¬b)

a ∧ b →◇◇ (a ∧ b)

Basicamente, cuales estados se pueden alcanzar y en cuantospasos.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que podemos afirmar de este sistema en la logica modal?

◇¬a ∧ ◇a

◇¬b ∧ ◇b

a ∧ b → ◻(¬a ∨ ¬b)a ∧ b →◇◇ (a ∧ b)

Basicamente, cuales estados se pueden alcanzar y en cuantospasos.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que podemos afirmar de este sistema en la logica modal?

◇¬a ∧ ◇a

◇¬b ∧ ◇b

a ∧ b → ◻(¬a ∨ ¬b)a ∧ b →◇◇ (a ∧ b)

Basicamente, cuales estados se pueden alcanzar y en cuantospasos.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que NO podemos afirmar?

No podemos decir que algo es alcanzable en principio:tenemos que decir “alcanzable en n pasos”.

No podemos decir cual accion (por cual proceso) nollevara a cual estado.

No podemos decir “existe una ejecucion que empieza enw1 donde b es siempre falso”.

No podemos decir lo que el agente A conoce del agente B.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que NO podemos afirmar?

No podemos decir que algo es alcanzable en principio:tenemos que decir “alcanzable en n pasos”.

No podemos decir cual accion (por cual proceso) nollevara a cual estado.

No podemos decir “existe una ejecucion que empieza enw1 donde b es siempre falso”.

No podemos decir lo que el agente A conoce del agente B.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que NO podemos afirmar?

No podemos decir que algo es alcanzable en principio:tenemos que decir “alcanzable en n pasos”.

No podemos decir cual accion (por cual proceso) nollevara a cual estado.

No podemos decir “existe una ejecucion que empieza enw1 donde b es siempre falso”.

No podemos decir lo que el agente A conoce del agente B.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que NO podemos afirmar?

No podemos decir que algo es alcanzable en principio:tenemos que decir “alcanzable en n pasos”.

No podemos decir cual accion (por cual proceso) nollevara a cual estado.

No podemos decir “existe una ejecucion que empieza enw1 donde b es siempre falso”.

No podemos decir lo que el agente A conoce del agente B.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

¿Que se puede expresar en la logica modal?

¿Que NO podemos afirmar?

No podemos decir que algo es alcanzable en principio:tenemos que decir “alcanzable en n pasos”.

No podemos decir cual accion (por cual proceso) nollevara a cual estado.

No podemos decir “existe una ejecucion que empieza enw1 donde b es siempre falso”.

No podemos decir lo que el agente A conoce del agente B.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

El proposito de la logica temporal es razonar sobre el tiempo(en filosofıa), y sobre el comportamiento de sistemas queevolucionan en el tiempo (en ciencias de la computacion).

¿Cual es la estructura del tiempo?

Un flujo del tiempo es una pareja (T ,<), donde T es unconjunto no vacıo de puntos de tiempo, y < es una relacionbinaria e irreflexiva sobre T .

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

El proposito de la logica temporal es razonar sobre el tiempo(en filosofıa), y sobre el comportamiento de sistemas queevolucionan en el tiempo (en ciencias de la computacion).

¿Cual es la estructura del tiempo?

Un flujo del tiempo es una pareja (T ,<), donde T es unconjunto no vacıo de puntos de tiempo, y < es una relacionbinaria e irreflexiva sobre T .

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

El proposito de la logica temporal es razonar sobre el tiempo(en filosofıa), y sobre el comportamiento de sistemas queevolucionan en el tiempo (en ciencias de la computacion).

¿Cual es la estructura del tiempo?

Un flujo del tiempo es una pareja (T ,<), donde T es unconjunto no vacıo de puntos de tiempo, y < es una relacionbinaria e irreflexiva sobre T .

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

Decision fundamental: ¿lineal o ramificada?.

Lineal:(T ,<) es lineal si, para todo x , y ∈ T con x ≠ y , se tiene quex < y o y < x .

Propiedades:

Se puede limitar

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

Decision fundamental: ¿lineal o ramificada?.

Lineal:(T ,<) es lineal si, para todo x , y ∈ T con x ≠ y , se tiene quex < y o y < x .

Propiedades:

Se puede limitar

Al pasado: Existe un x ∈ T tal que x ≤ y para todo y ∈ T(genesis)

Al futuro: Existe un x ∈ T tal que x ≥ y para todo y ∈ T(dıa del juicio)

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

Decision fundamental: ¿lineal o ramificada?.

Lineal:(T ,<) es lineal si, para todo x , y ∈ T con x ≠ y , se tiene quex < y o y < x .

Propiedades:

Se puede limitar

Se puede discretizar

Si x ∈ T no es el genesis, entonces existe y ∈ T tal que y < x yy < z < x no se mantiene para ningun z ∈ T .

Si x ∈ T no es el dıa del juicio, entonces existe y ∈ T tal quex < y y x < z < y no se mantiene para ningun z ∈ T .

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

Decision fundamental: ¿lineal o ramificada?.

Lineal:(T ,<) es lineal si, para todo x , y ∈ T con x ≠ y , se tiene quex < y o y < x .

Propiedades:

Se puede limitar

Se puede discretizar

Tiene densidad

Para todo x , y ∈ T con x < y , existe un z ∈ T tal que x < z < y .

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

Decision fundamental: ¿lineal o ramificada?.

Lineal:(T ,<) es lineal si, para todo x , y ∈ T con x ≠ y , se tiene quex < y o y < x .

Propiedades:

Se puede limitar

Se puede discretizar

Tiene densidad

Completitud (tiene un mınimo lımite superior)

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

Ramificada:

al futuro

al pasado

Opcion mas popular: lineal al pasado y ramificada al futuro, i.e.

para cada x ∈ T , el conjunto {y ∈ T ∣ y < x} es lineal ordenadopor <

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

Ramificada:

al futuro

al pasado

Opcion mas popular: lineal al pasado y ramificada al futuro, i.e.

para cada x ∈ T , el conjunto {y ∈ T ∣ y < x} es lineal ordenadopor <

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

¿Que flujo de tiempo tenemos que usar?

¡Depende de la aplicacion!

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Logica Temporal

¿Que flujo de tiempo tenemos que usar?

¡Depende de la aplicacion!

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Sistemas Reactivos

La aplicacion principal de la logica temporal en ciencias de lacomputacion es la verificacion de sistemas concurrentes yreactivos de estado finito.

Ejemplos: microprocesadores, sistemas operativos, protocolosde redes, software de aviacion.

La verificacion de dichos sistemas es una tarea importante ydifıcil.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Sistemas Reactivos

Estado-Finito. Un estado es una “foto” del sistema, quecaptura los valores de las variables en un instantede tiempo. Sistemas de estado-finito solo puedentener un numero finito de estados.

Sistema Reactivo. Interactua con el ambiente de manerafrecuente y usualmente no termina.

Sistema Concurrente. Consiste en multiples procesos queinteraccionan entre sı. Un proceso no conoce elestado interno de los otros. Puede ser visto comouna coleccion de sistemas reactivos.

Verificacion. Dada la descripcion (formal) de un sistema y sucomportamiento esperado, se chequea si elsistema de verdad cumple con estecomportamiento.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Sistemas Reactivos

Estado-Finito. Un estado es una “foto” del sistema, quecaptura los valores de las variables en un instantede tiempo. Sistemas de estado-finito solo puedentener un numero finito de estados.

Sistema Reactivo. Interactua con el ambiente de manerafrecuente y usualmente no termina.

Sistema Concurrente. Consiste en multiples procesos queinteraccionan entre sı. Un proceso no conoce elestado interno de los otros. Puede ser visto comouna coleccion de sistemas reactivos.

Verificacion. Dada la descripcion (formal) de un sistema y sucomportamiento esperado, se chequea si elsistema de verdad cumple con estecomportamiento.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Sistemas Reactivos

Estado-Finito. Un estado es una “foto” del sistema, quecaptura los valores de las variables en un instantede tiempo. Sistemas de estado-finito solo puedentener un numero finito de estados.

Sistema Reactivo. Interactua con el ambiente de manerafrecuente y usualmente no termina.

Sistema Concurrente. Consiste en multiples procesos queinteraccionan entre sı. Un proceso no conoce elestado interno de los otros. Puede ser visto comouna coleccion de sistemas reactivos.

Verificacion. Dada la descripcion (formal) de un sistema y sucomportamiento esperado, se chequea si elsistema de verdad cumple con estecomportamiento.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Sistemas Reactivos

Estado-Finito. Un estado es una “foto” del sistema, quecaptura los valores de las variables en un instantede tiempo. Sistemas de estado-finito solo puedentener un numero finito de estados.

Sistema Reactivo. Interactua con el ambiente de manerafrecuente y usualmente no termina.

Sistema Concurrente. Consiste en multiples procesos queinteraccionan entre sı. Un proceso no conoce elestado interno de los otros. Puede ser visto comouna coleccion de sistemas reactivos.

Verificacion. Dada la descripcion (formal) de un sistema y sucomportamiento esperado, se chequea si elsistema de verdad cumple con estecomportamiento.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Sea PL un conjunto finito de letras proposicionales. Unaestructura Kripke sobre PL es una tupla K = ⟨S , SI , R, V ⟩ con

S un conjunto no vacıo de estados,

SI ⊆ S un conjunto de estados iniciales,

R ⊆ S × S una relacion de transicion que es total, i.e. paracada estado s ∈ S , existe un estado s ′ ∈ S tal que s R s ′,

V ∶ S → 2PL una funcion valuacion.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Ejemplo:Considere el siguiente protocolo de exclusion mutua:

task body ProcA isbeginloop

(0) Non Critical Section A;(1) loop exit when Turn = 0; end loop;(2) Critical Section A;(3) Turn := 1;

end loop;end ProcA;

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

task body ProcB isbeginloop

(0) Non Critical Section B;(1) loop exit when Turn = 1; end loop;(2) Critical Section B;(3) Turn := 0;

end loop;end ProcB;

Se asume que los procesos corren de manera asıncrona. Elorden de ejecucion es indeterminado.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Entonces definimos un conjunto de letras proposicionales:

PL ={(T = i) ∣ i ∈ {0, 1}}∪{(X = i) ∣ X ∈ {A, B} ∧ i ∈ {0, 1, 2, 3}}

Intuitivamente, (T = i) significa que Turn se le ha asignado i ,y (X = i) significa que el proceso X esta en la lınea i .

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Luego definimos una estructura Kripke K = ⟨S , SI , R, V ⟩ de lasiguiente manera:

S = {0, 1} × {0, 1, 2, 3} × {0, 1, 2, 3}SI = {(0, 0, 0), (1, 0, 0)}R = RA ∪ RB , donde

RA = {(t, pA, pB), (t ′, p′A, p′B) ∣ pB = p′B y

1 pA ∈ {0,2,3} Ô⇒ p′A = pA + 1 mod 4 ∧ t ′ = t2 t = 0 ∧ pA = 1 Ô⇒ p′A = 23 t = 1 ∧ pA = 1 Ô⇒ p′A = 14 pA = 3 Ô⇒ t ′ = 1}

RB es definido de la misma manera

V (t, pA, pB) = {(T = t), (A = pA),(B = pB)},∀(t, pA, pB) ∈ S

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Una computacion de K es una secuencia infinita s0s1⋯ deestados tal que s0 ∈ SI y si R si+1 para todo i ≥ 0.

Ejemplo:

(0, 0, 0), (0, 1, 0), (0, 1, 1), (0, 2, 1), (0, 3, 1), (1, 0, 1), (1, 0, 2), . . .

Dicha computacion corresponde a una ejecucion (asıncrona)del sistema concurrente con los procesos A y B.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Propiedades interesantes derivadas del ejemplo:

Exclusion mutua: ¿pueden A y B estar en la lınea (2) almismo tiempo?

(cierto)

Accesibilidad garantizada: si el proceso X ∈ {A, B} esta enla lınea (2), ¿se garantiza que finalmente llegara a la lınea(3)? (cierto, pero solo en computaciones que ejecutanambos procesos A y B de manera infinita)

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Propiedades interesantes derivadas del ejemplo:

Exclusion mutua: ¿pueden A y B estar en la lınea (2) almismo tiempo? (cierto)

Accesibilidad garantizada: si el proceso X ∈ {A, B} esta enla lınea (2), ¿se garantiza que finalmente llegara a la lınea(3)? (cierto, pero solo en computaciones que ejecutanambos procesos A y B de manera infinita)

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Propiedades interesantes derivadas del ejemplo:

Exclusion mutua: ¿pueden A y B estar en la lınea (2) almismo tiempo? (cierto)

Accesibilidad garantizada: si el proceso X ∈ {A, B} esta enla lınea (2), ¿se garantiza que finalmente llegara a la lınea(3)?

(cierto, pero solo en computaciones que ejecutanambos procesos A y B de manera infinita)

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Propiedades interesantes derivadas del ejemplo:

Exclusion mutua: ¿pueden A y B estar en la lınea (2) almismo tiempo? (cierto)

Accesibilidad garantizada: si el proceso X ∈ {A, B} esta enla lınea (2), ¿se garantiza que finalmente llegara a la lınea(3)? (cierto, pero solo en computaciones que ejecutanambos procesos A y B de manera infinita)

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

Las estructuras de Kripke pueden ser no deterministas, i.e. paraun s ∈ S , el conjunto {s ′∣s R s ′} puede tener una cardinalidadarbitraria.

En general hay mas de una computacion.

Podemos organizarlas todas en un arbol de computacion.

Informalmente, para s ∈ SI , el arbol (infinito) de computacionT (K , s) de K en s ∈ S es construido inductivamente ası:

use s como la raız;

para cada hoja s ′, agregue un sucesor {t ∈ S ∣s ′ R t}.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Estructuras de Kripke

El arbol de computacion para el ejemplo anterior que empiezaen (0, 0, 0) es:

(0,0,0)

(0,0,1)(0,1,0)

(0,2,0) (0,1,1)

(0,3,0) (0,2,1) (0,2,1) (0,1,1)

Para verificar propiedades se consideran las computacionessimples o el arbol entero.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Sintaxis

El conjunto de formulas en la logica temporal lineal (LTL) es elmenor conjunto donde

cada letra proposicional p ∈ PL es una formula,

si A y B son formulas, entonces A ∧ B y ¬A tambien loson,

si A y B son formulas, entonces ○A y AU B tambien loson.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Semantica

Una estructura LTL M es una secuencia infinita S0S1⋯ conSi ∈ 2PL para todo i ≥ 0.

Una formula LTL en M en un tiempo n ∈ N se satisface en lossiguientes casos:

M, n ⊧ p sii p ∈ Sn,∀p ∈ PLM, n ⊧ ¬A sii M, n ⊭ AM, n ⊧ A ∧B sii M, n ⊧ A y M, n ⊧ BM, n ⊧ ○A sii M, n + 1 ⊧ AM, n ⊧ AU B sii ∃m ≥ n ∶ M, m ⊧ A ∧

∀k ∈ {n, . . . , m − 1} ∶ M, k ⊧ B

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Abreviaciones

El Diamante futuro

◇A ∶= trueU A

M, n ⊧◇A sii ∃m ≥ n ∶ M, m ⊧ A

La caja futuro◻A ∶= ¬◇ ¬A

M, n ⊧ ◻A sii ∀m ≥ n ∶ M, m ⊧ A

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Abreviaciones

El Diamante futuro◇A ∶= trueU A

M, n ⊧◇A sii ∃m ≥ n ∶ M, m ⊧ A

La caja futuro◻A ∶= ¬◇ ¬A

M, n ⊧ ◻A sii ∀m ≥ n ∶ M, m ⊧ A

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Abreviaciones

El Diamante futuro◇A ∶= trueU A

M, n ⊧◇A sii ∃m ≥ n ∶ M, m ⊧ A

La caja futuro

◻A ∶= ¬◇ ¬A

M, n ⊧ ◻A sii ∀m ≥ n ∶ M, m ⊧ A

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Abreviaciones

El Diamante futuro◇A ∶= trueU A

M, n ⊧◇A sii ∃m ≥ n ∶ M, m ⊧ A

La caja futuro◻A ∶= ¬◇ ¬A

M, n ⊧ ◻A sii ∀m ≥ n ∶ M, m ⊧ A

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Abreviaciones

Ejercicio:¿Como se expresarıa el operador release R ?

ARB, significa que B siempre es cierto a menos que sealiberado (released) por A.

ARB ∶= ¬(¬AU ¬B)

M, n ⊧ ARB sii ∀m ≥ n ∶ M, k ⊧ A ∀k < m Ô⇒ M, m ⊧ B

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Abreviaciones

Ejercicio:¿Como se expresarıa el operador release R ?

ARB, significa que B siempre es cierto a menos que sealiberado (released) por A.

ARB ∶= ¬(¬AU ¬B)

M, n ⊧ ARB sii ∀m ≥ n ∶ M, k ⊧ A ∀k < m Ô⇒ M, m ⊧ B

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Abreviaciones

Ejercicio:¿Como se expresarıa el operador release R ?

ARB, significa que B siempre es cierto a menos que sealiberado (released) por A.

ARB ∶= ¬(¬AU ¬B)

M, n ⊧ ARB sii ∀m ≥ n ∶ M, k ⊧ A ∀k < m Ô⇒ M, m ⊧ B

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Equivalencias

Algunas equivalencias importantes:

¬○A ≡ ○¬A auto-dualidad del next◇◇A ≡ ◇A idempotencia del diamante○◇A ≡ ◇○A conmutacion de next con diamanteAU B ≡ ¬(¬AR¬B) until y release son dualesAU B ≡ B ∨ (A ∧ ○(AU B)) desarrollo del untilARB ≡ (A ∧B) ∨ (B ∧ ○(ARB)) desarrollo del release

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Propiedades Temporales

Una propiedad temporal es un conjunto de estructuras LTL(aquellas en las cuales la propiedad es cierta).

Entonces una propiedad temporal P puede ser definida usandouna formula A:

P = {M ∣ M, 0 ⊧ A}

Dada una estructura de Kripke K que representa un sistemareactivo y una formula LTL A que representa una propiedadtemporal, K satisface A si M, 0 ⊧ A para todas las trazas M deK . Notacion: K ⊧ A.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Propiedades Temporales

Una propiedad temporal es un conjunto de estructuras LTL(aquellas en las cuales la propiedad es cierta).

Entonces una propiedad temporal P puede ser definida usandouna formula A:

P = {M ∣ M, 0 ⊧ A}

Dada una estructura de Kripke K que representa un sistemareactivo y una formula LTL A que representa una propiedadtemporal, K satisface A si M, 0 ⊧ A para todas las trazas M deK . Notacion: K ⊧ A.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Propiedades Temporales: Safety

Intuitivamente, una propiedad safety afirma que “nada malopasa”.

Exclusion mutua: E.g.

◻¬((A = 2) ∧ (B = 2))

No Deadlocks: En cualquier momento algun proceso debeestar activo:

◻(activo1 ∨ . . . ∨ activok)

Correctitud parcial: Si A se satisface cuando el programaempieza, entonces B sera satisfecho si el programa alcanzaun determinado estado:

A→ ◻(dist → B)

donde dist ∈ PL marque el determinado estado.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Propiedades Temporales: Liveness

Intuitivamente, una propiedad liveness afirma que “algo buenopasara”.

Accesibilidad Garantizada: E.g.

◻(A = 1→◇(A = 2)) ∧ ◻(B = 1→◇(B = 2))

Respuesta: Si se hace una peticion, sera otorgada:

◻(pet →◇(otorg))

Correctitud Total: Si A se satisface cuando el programaempieza, el programa termina en un determinado estadodonde B se satisface:

A→◇(dist ∧B)

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Propiedades Temporales: Fairness

Cuando se modelan sistemas concurrentes, usualmente esimportante hacer algunas suposiciones imparciales o justas.

Se asume que existen k procesos, que activoi ∈ PL es cierto enun estado s si el proceso #i esta activo en s, y que ejecutadoi

es cierto en un estado s si el proceso #i ha sido ejecutado paraalcanzar s.

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Model Checking

El problema de model checking en LTL es el siguiente:

Dada una estructura de Kripke K = (S , SI , R, V ) y una formulaLTL A, chequear cuando K ⊧ A. (Si todas las trazas M de Ksatisfacen M, 0 ⊧ A).

Ejemplo: La siguiente estructura de Kripke satisface◻(q → ○○○p). Pero no satisface ◻(p → pU q).

q q

p

p

p

q

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Model Checking

El problema de model checking en LTL es el siguiente:

Dada una estructura de Kripke K = (S , SI , R, V ) y una formulaLTL A, chequear cuando K ⊧ A. (Si todas las trazas M de Ksatisfacen M, 0 ⊧ A).

Ejemplo: La siguiente estructura de Kripke satisface◻(q → ○○○p). Pero no satisface ◻(p → pU q).

q q

p

p

p

q

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Satisfacibilidad

Una formula LTL A es satisfacible si existe una estructura LTLM tal que M, n ⊧ A, para algun n ∈ N.

Dicha estructura es llamada un modelo de A.

En verificacion, la satisfacibilidad es usada para detectarpropiedades contradictorias, i.e. propiedades que no sonsatisfechas por ninguna computacion en ningun sistemareactivo.

Ejercicio:p ∧ ◻(p → ○p) ∧◇¬p

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Satisfacibilidad

Una formula LTL A es satisfacible si existe una estructura LTLM tal que M, n ⊧ A, para algun n ∈ N.

Dicha estructura es llamada un modelo de A.

En verificacion, la satisfacibilidad es usada para detectarpropiedades contradictorias, i.e. propiedades que no sonsatisfechas por ninguna computacion en ningun sistemareactivo.

Ejercicio:p ∧ ◻(p → ○p) ∧◇¬p

Gerardo M.Sarria M.

Logica Modal

LogicaTemporal

LogicaTemporalLineal

Fin de la Presentacion