Importanza della specifica formale di un progetto (sviluppato in mesi, da diverse persone, modificato, ...)

(1)

Specifica formale (Peled, cap. 5)

Importanza della specifica formale di un progetto (sviluppato in mesi, da diverse persone, modificato, ...)

Correttezza di un programma rispetto alla specifica: verifica formale connessa a specifica A volte si usano formalismi simili per specificare il sistema e le sue propriet`a, ma spesso no Esistono anche formalismi visuali

Linguaggi di specifica

• Automi

• LTL: una specifica LTL si pu`o tradurre in un automa

• CTL (Computational Tree Logic)

Logica Temporale Lineare (LTL) (dispense in rete)

La logica classica `e statica: rappresenta stati.

Logiche Modali: descrivono relazioni tra stati.

Una logica modale estende la logica classica mediante:

• uno o pi`u operatori modali (sintassi)

(2)

Operatori modali Modalit` a : in che modo una proposizione `e vera?

E vera solo contingentemente, è necessariamente vera, è possibile che sia vera? Modalità ` aletiche:

• contingenza: piove

• necessit`a: 2piove

• possibilit`a: 3piove

Contingenza, necessit`a, possibilit`a sono concetti intensionali (non vero-funzionali):

2(piove ∨ ¬piove) Ma, anche se ¬piove `e vero, non `e vero 2¬piove

Quali sono le propriet`a di 2 e 3?

2(p ∧ q) → 2p ∧ 2q?

2p → p?

2p → 22p?

(Necessit`a logica, necessit`a fisica,...)

(3)

Semantica dei “mondi possibili” (semantica di Kripke)

p,q

p

p,r

p,q q,r

2p: in tutti i mondi visibili `e vero p

3¬r: esiste un mondo visibile in cui r `e falso

32r: esiste un mondo visibile tale che in tutti i mondi per esso visibili `e vero r 2A vero in un mondo w sse ∀w

^′

(se w vede w

^′

allora A vero in w

^′

) 2 ha un significato “universale”

3A vero in un mondo w sse ∃w

^′

tale che (w vede w

^′

e A vero in w

^′

)

3 ha un significato “esistenziale”

(4)

Semantica degli operatori modali

Secondo la semantica dei mondi possibili, alcune propriet`a degli operatori modali valgono sempre:

3A ≡ ¬2¬A

2(A ∧ B) → 2A ∧ 2B 2(A → B) → (2A → 2B) 2A se A `e classicamente valida

Altre propriet`a dipendono dall’interpretazione degli operatori. Ad esempio:

Interpretazione epistemica

2p: l’agente conosce p: K p 3p: p `e compatibile con le conoscenze dell’agente (l’agente non conosce la negazione di p): ¬K¬p

Insieme dei mondi “accessibili”: stati di cose compatibili con quello che l’agente conosce.

Conoscenza = opinione vera: 2p → p

Capacit`a introspettiva dell’agente: 2p → 22p (so di sapere)

3p → 23p (so di non sapere)

(5)

Interpretazione temporale

Il tempo è una sequenza lineare di stati: la relazione tra gli stati è transitiva e connessa (∀s, t(sRt ∨ s = t ∨ tRs)), cioè è un ordine lineare

L’insieme degli stati `e isomorfo a IN

LTL utilizzata per specificare propriet`a di interleaving sequences.

2p : p sar`a sempre vero

3p : p sar`a vero qualche volta in futuro Quindi:

2p → 3p perché il tempo è infinito nel futuro 2p → 22p perché il futuro è transitivo:

se p sarà sempre vero, allora sarà sempre vero che sarà sempre vero Ma non sempre, ad esempio:

3p → 23p

(6)

Operatori temporali del futuro (dove il futuro include il presente)

Always: 2A : A sar`a sempre vero nel futuro (stato attuale incluso)

Eventually: 3A : A sar`a vero in qualche stato futuro (oppure nello stato attuale) Next:

A : A `e vero nello stato successivo a quello attuale

Until: A U B : B sar`a vero in futuro e A vale da adesso al momento in cui sar`a vero B (escludendo tale stato)

Release: A R B : o B sar`a sempre vero, oppure sar`a vero fino a che il verificarsi di A non “libera” B dal vincolo di essere vero (ma B deve essere ancora vero quando vale A)

(nel libro di Peled la notazione per Release `e V)

Esempi 23A: A vale infinitamente spesso

32A: da un certo punto in poi, A `e sempre vera

(7)

LTL proposizionale: sintassi Dato un insieme P di lettere proposizionali:

1. ⊤ e ⊥ sono formule;

2. se p ∈ P allora p `e una formula;

3. se A `e una formula allora ¬A, 2A, 3A,

A sono formule;

4. se A e B sono formule, allora A ∧ B, A ∨ B, A → B, A U B, A R B sono formule.

Semantica formale

Interpretazione: sequenza infinita di interpretazioni classiche (stati).

Rappresentiamo un’interpretazione proposizionale classica mediante un insieme di atomi:

l’insieme degli atomi veri nell’interpretazione.

Se IN `e l’insieme dei numeri naturali, ordinati secondo l’abituale relazione <, allora:

Un’interpretazione temporale M del linguaggio P `e una funzione che associa a ogni k ∈ IN un sottoinsieme di P :

M : IN → 2

^P

Ogni k ∈ IN rappresenta uno stato. 0 `e lo stato iniziale.

Verit` a di un formula in uno stato di un’interpretazione M:

M

k

|= A

Verit`a di un formula in un’interpretazione:

(8)

Semantica 1. M

k

|= ⊤ e M

k

6|= ⊥;

2. M

k

|= p sse p ∈ M(k);

3. M

k

|= ¬A sse M

k

6|= A;

4. M

k

|= A ∧ B sse M

k

|= A e M

k

|= B;

5. M

k

|= A ∨ B sse M

k

|= A oppure M

k

|= B;

6. M

k

|= A → B sse M

k

6|= A oppure M

k

|= B;

Quindi se A ` e una formula proposizionale classica, M

k

|= A se e solo se M(k) |= A

7. M

k

|=

A sse M

k+1

|= A

A A

s

0

s

1

· · · s

k

s

_k+1

s

_k+2

· · ·

8. M

k

|= 2A sse per ogni i ≥ k M

ⁱ

|= A

2A

A A A A · · ·

s

0

s

1

· · · s

k

s

_k+1

s

_k+2

s

_k+3

· · · 9. M

k

|= 3A sse esiste i ≥ k tale che M

ⁱ

|= A 3A A

s

0

s

1

· · · s

k

s

k+1

· · · s

i

· · ·

(9)

Semantica (continua)

10. M

k

|= A U B sse esiste i ≥ k tale che M

i

|= B e per ogni j = k, ..., i − 1 (k ≤ j < i), M

j

|= A

A U B

A A · · · A A B

s

0

s

1

· · · s

k

s

k+1

s

_i−2

s

_i−1

s

i

s

i+1

11. M

k

|= A R B sse vale uno di questi due casi:

• per ogni i ≥ k, M

i

|= B (B vale per sempre);

A R B

B B B B · · ·

s

0

s

1

· · · s

_k

s

_k+1

s

_k+2

s

_k+3

· · ·

• esiste i ≥ k tale che M

_i

|= A e per ogni j = k, ..., i (k ≤ j ≤ i) si ha M

_j

|= B (B vale fino a un punto in cui valgono sia A che B).

A R B

B B · · · B B B, A

s

0

s

1

· · · s

k

s

k+1

s

_i−2

s

_i−1

s

i

s

i+1

O B `e sempre vera, oppure c’`e uno stato futuro s

i

in cui A `e vera, e in s

i

A “libera” B,

che deve comunque essere vera fino a s

i

.

(10)

Verit` a, validit` a, equivalenza logica

Una formula A è vera in un’interpretazione M (e M è un modello di A) sse A è vera nel suo stato iniziale:

M |= A sse M

0

|= A Se S `e un insieme di formule e M un’interpretazione:

• M

k

|= S sse M

k

|= A per ogni formula A ∈ S;

• M `e un modello di S (M |= S) sse M |= A per ogni formula A ∈ S.

Una formula A `e valida (|= A) sse per ogni interpretazione M e ogni k ∈ IN, M

k

|= A.

Se S `e un insieme di formule e A una formula, A `e una conseguenza logica di S (e S implica logicamente A )

S |= A sse per ogni interpretazione M e k ∈ IN:

se M

k

|= S allora M

_k

|= A.

Due formule A e B sono logicamente equivalenti (A ↔ B) se per ogni interpretazione M e stato k ∈ IN, M

k

|= A se e solo se M

k

|= B.

Propriet` a della validit` a: una formula A `e valida sse per ogni interpretazione M, M

0

|= A.

(la verit`a in ogni interpretazione e la verit`a in ogni stato di ogni interpretazione coincidono)

(11)

Casi particolari

• Se M

k

|= A, allora M

k

|= 3A.

• Se M

k

|= B, allora M

k

|= A U B, per qualunque A.

• Se M

k

|= A ∧ B, allora M

k

|= A R B

Falsit` a di una formula in uno stato 1. M

k

6|=

A sse M

k+1

6|= A

2. M

k

6|= 2A sse esiste i ≥ k tale che M

ⁱ

6|= A 3. M

k

6|= 3A sse per ogni i ≥ k, M

ⁱ

6|= A

4. M

k

6|= A U B sse per ogni i ≥ k, se M

i

|= B, allora esiste j tale che k ≤ j < i e M

j

6|= A.

5. M

k

6|= A R B sse valgono entrambi i casi seguenti:

• esiste i ≥ k tale che M

i

6|= B, e

• per ogni i ≥ k, se M

i

|= A, allora esiste j tale che k ≤ j ≤ i e M

j

6|= B.

(12)

Propriet` a degli operatori temporali 3 `e un caso particolare di U : 3A ↔ true U A

3 e 2 sono duali: 2A ↔ ¬3¬A

3A ↔ ¬2¬A

U e R sono duali: A R B ↔ ¬(¬A U ¬B)

A U B ↔ ¬(¬A R ¬B) Il NEXT (

) `e duale di se stesso

A ↔ ¬

¬A

Poich´e ≤ `e riflessiva e transitiva: |= 2A → A

|= A → 3A

|= 2A → 22A Propriet`a del NEXT |= 2A →

A

|=

A → 3A

¬

A ↔

¬A

|=

(A → B) → (

A →

B ) Propriet`a di ALWAYS: |= 2(A → B) → (2A → 2B)

|= A ∧ 2(A →

A ) → 2A 2A ↔ A ∧

2A

Propriet`a di EVENTUALLY: 3A ↔ A ∨

3A Propriet`a di UNTIL: |= A U B → 3B

A U B ↔ B ∨ (A ∧

(A U B))

Propriet`a di RELEASE: A R B ↔ B ∧ (A ∨

(A R B))

(13)

Esercizi

Dare dimostrazioni semantiche di tutte le altre propriet`a riportate precedentemente.

Dimostrare inoltre che:

1. |= 3⊤

2. |= 2⊤

3. 3A 6|= 23A 4. 6|= 2A ∨ 2¬A

5. 3(A ∨ B) ↔ 3A ∨ 3B 6. 3A ∧ 3B 6|= 3(A ∧ B) 7. 3(A ∧ B) |= 3A ∧ 3B 8. 2(A ∧ B) ↔ 2A ∧ 2B 9. 2(A ∨ B) 6|= 2A ∨ 2B 10. 2A ∨ 2B |= 2(A ∨ B) 11. 2A ↔ ⊥ R A

12. ¬(A U B) ↔ ¬B ∧ (¬A ∨ ¬

(A U B)

13. ¬(A U B) ↔ 2¬B ∨ (¬B U (¬A ∧ ¬B))

14. A R B ↔ 2B ∨ (B U (A ∧ B))

(14)

Sistemi assiomatici per LTL

Assiomatizzazione di LTL (proposizionale): si considerano primitivi soltanto gli operatori temporali

, 2, 3, U .

A un qualsiasi sistema di assiomi per la logica proposizionale classica si aggiungono gli assiomi seguenti:

A1. ¬3A ≡ 2¬A

A2. 2(A → B) → (2A → 2B) A3. 2A → (A ∧

2A)

A4.

¬A ≡ ¬

A

A5.

(A → B) → (

A →

B ) A6. 2(A →

A ) → (A → 2A) A7. A U B ≡ B ∨ (A ∧

(A U B)) A8. A U B → 3B

e la regola di inferenza (regola di necessitazione):

A 2A

LTL con quantificatori: indecidibile (ovviamente) e non semi-decidibile (incompleta).

(15)

Approcci basati su LTL alla verifica di sistemi

Basati sulla deduzione: Il comportamento del sistema S `e descritto da un insieme S di formule di LTL e la propriet`a da verificare da una formula F :

S soddisfa la specifica F se e solo se S |= F

Basati sul “model checking”, o meglio semplicemente model based: il sistema S

`e modellato da una struttura di Kripke P (un grafo con stati iniziali, ai cui stati sono associati insiemi di formule proposizionali): ogni esecuzione del sistema corrisponde a un cammino massimale in P , cio`e a una interpretazione temporale.

Se identifichiamo P con l’insieme delle sue esecuzioni (i cammini in P ), diciamo che:

P |= A: tutte le esecuzioni di P soddisfano A, cio`e M |= A per ogni M ∈ P

P 6|= A: non tutte le esecuzioni di P soddisfano A, cio`e esiste M ∈ P tale che M 6|= A Quindi S soddisfa la specifica F se e solo se P |= F

Anche se questo approccio si dice “basato sul model checking”, in realt`a si sta sempre affrontando un problema di deduzione: se

• S `e il sistema,

• S una sua “assiomatizzazione” che descrive in modo corretto e completo il compor- tamento di S,

• P `e l’insieme dei modelli di S: P = {M | M |= S}

allora

(16)

Uso di LTL per la specifica di sistemi software

Assumiamo che il modello del sistema P sia descritto in modo corretto e completo da un insieme S di formule LTL, cio`e:

M ∈ P sse M |= S Ad esempio, consideriamo il programma

22: if N>10 then

23: N:=5

else

24: N:=6;

Esso pu`o essere descritto mediante un insieme di formule, contenenti ad esempio 2(at(22) → (N > 10 →

(at(23) ∧ N = 5))

∧(N ≤ 10 →

(at(24) ∧ N = 6)))

Allora, verificare che il programma P descritto dall’insieme di formule S soddisfa la propriet`a A, cio`e

P |= A equivale a verificare che

S |= A

(17)

Sistemi modellati da automi con vincoli di fairness

Assumiamo che il sistema sia modellato da una struttura di Kripke P con vincoli di fairness {F

1

, ..., F

_n

} (dove le F

i

sono formule).

Allora le esecuzioni del sistema sono rappresentate da tutte e solo le interpretazioni M ∈ P tali che M |= 23F

i

per ogni i = 1, ..., n:

F

_i

si verifica infinitamente spesso

Se S `e una descrizione corretta e completa di P (P = {M | M |= S}, allora S ∪ {23F

¹

, ..., 23F

n

} |= F equivale a P |= 23F

¹

∧ ... ∧ 23F

ⁿ

→ F

I vincoli di fairness semplici si possono esprimere mediante formule della forma 23F . In alcuni casi, comunque, i vincoli di fairness si possono esprimere mediante formule pi`u semplici.

s1 {work}

t2 s2

t1 {}

s3 {rich}

t3 t2

t4

3rich

(18)

Esempio: specifica delle propriet` a di un sistema

s1 {}

s2 {extended}

pull release

s3 {extended, malfunction}

release

Questo sistema ha infinite esecuzioni: tutte le sequenze infinite della forma s

1

s

2

(s

1

s

2

)

^∗

s

^ω₃

, oltre all’esecuzione (s

1

s

2

)

^ω

.

Sia M = s

¹

s

2

s

1

s

2

s

3

s

3

s

3

s

3

. . .

M 6|= extended M |=

extended

M 6|=

extended M |= 3extended

M 6|= 2extended M |= 32extended

M 6|= ¬extended U malf unction Se P `e il sistema illustrato sopra:

P |= 3extended

P |= 2(¬extended →

extended)

P 6|= 2(extended →

¬extended) (s

¹

s

2

s

3

s

3

s

3

. . .) P 6|= 32extended (s

¹

s

2

s

1

s

2

s

1

s

2

. . .) P 6|= ¬32extended (s

1

s

2

s

3

s

3

s

3

. . .) P 6|= 23¬extended

Esempio di fairness constraint: prima o poi l’elastico perde elasticit`a (3malfunction) Si esclude s

¹

s

2

s

1

s

2

s

1

s

2

. . .

Con questo vincolo il sistema soddisferebbe 32extended

(19)

Esempio 2: specifica delle propriet` a di un sistema

{green}

{yellow} {red}

Invariante: esattamente un colore alla volta 2(¬(green ∧ yellow) ∧ ¬(green ∧ red)∧

¬(yellow ∧ red) ∧ (green ∨ yellow ∨ red)) Se il semaforo `e verde, resta verde finch´e non diventa giallo:

2(green → green U yellow) Descrizione dei cambiamenti di colore:

2((green U yellow)∨(yellow U red)∨(red U green)) Modifichiamo ora il sistema: si passa per il giallo anche tra il verde e il rosso.

Se specifichiamo i cambiamenti di colore con:

2(((green ∨ red) U yellow) ∨ (yellow U (green ∨ red))) si ammette anche le sequenze green → red → green → . . . → yellow . . .

e green → yellow → green . . . Specifica corretta:

2( (green → green U (yellow ∧ (yellow U red)))∧

(red → red U (yellow ∧ (yellow U green)))∧

(20)

Propriet` a di programmi

Assumiamo che il programma sia modellato da un sistema di transizioni, e usiamo le notazioni seguenti:

en

_α

condizione che abilita la transizione α en

_P_i

=

def

_

α∈Pi

en

_α

almeno una transizione del processo P

i

`e abilitata init lo stato corrente `e uno stato iniziale (Φ)

f inish =

def

^

α∈T

¬en

α

lo stato corrente `e uno stato finale (T `e l’insieme di tutte le transizioni) Propriet` a di programmi sequenziali

Correttezza parziale rispetto alla condizione iniziale e alla specifica F che deve valere alla fine:

init ∧ 2(finish → F ) Terminazione rispetto alla condizione iniziale:

init ∧ 3finish

Correttezza totale rispetto alla condizione iniziale e all’asserzione finale F : init ∧ 3(finish ∧ F )

A `e un’invariante: 2A

(21)

Propriet` a di programmi concorrenti: esempio

Mutua esclusione: due processi con una risorsa condivisa. La risorsa si utilizza solo in una

“sezione critica”. Prima di entrare nella sezione critica, un processo entra in una trying section .

tryCS

_i

: P

i

`e nella trying section inCS

_i

: P

i

`e nella critical section Mutua esclusione:

2¬(inCS

¹

∧ inCS

2

) Responsiveness:

2(tryCS

ⁱ

→ 3inCS

i

)

Quando un processo `e nella trying section, vi resta finch´e non entra nella sezione critica:

2(tryCS

ⁱ

→ ((tryCS

i

U inCS

i

) ∨ 2tryCS

ⁱ

))

(22)

Esempio 2

0000 1111

00 11

0000 1111

00 11

0000 1111

00

1101 0101 00000000 00000000 11111111 11111111

00000000 0000 11111111 1111

00 0 11 1

00 0 11 1 00000000 0000 11111111 1111 00000000 0000 11111111 1111

000000 000000 111111 111111

B A

t1

t2

Verifica di correttezza del sistema: le formule seguenti devono essere verificate dal modello del sistema:

2¬(on bridge t

¹

∧ on bridge t

2

) (mutual exclusion) 2(atA t

¹

→ 3on bridge t

¹

) (responsiveness) 2(atA t

²

→ 3on bridge t

²

) (responsiveness) 2(on bridge t

¹

→ 3atB t

¹

)

2(on bridge t

²

→ 3atB t

²

)

(23)

Tableaux per LTL (Wolper 85)

La chiave del metodo dei tableau per LTL con

`e la natura ricorsiva delle equivalenze:

2A ↔ A ∧

2A 3A ↔ A ∨

3A

A U B ↔ B ∨ (A ∧

(A U B))

Per semplicit`a, si trasformano inizialmente le formule in forma normale negativa, applicando le equivalenze:

¬¬A ↔ A

A → B ↔ ¬A ∨ B

¬(A → B) ↔ A ∧ ¬B

¬(A ∧ B) ↔ ¬A ∨ ¬B

¬(A ∨ B) ↔ ¬A ∧ ¬B

¬2A ↔ 3¬A

¬3A ↔ 2¬A

¬

A ↔

¬A

¬(A U B) ↔ ¬A R ¬B

¬(A R B) ↔ ¬A U ¬B

(24)

Regole di espansione

Un nodo di un tableau `e etichettato da un insieme di formule Regole classiche

A ∧ B, S A, B, S

A ∨ B, S A, S | B, S Regole temporali

2A, S A,

2A, S

3A, S

A, S |

3A, S A U B, S

B, S | A,

(A U B), S

A R B, S

A, B, S | B,

(A R B), S Λ,

A

1

, ...,

A

n

A

1

, ...., A

n

se Λ `e un insieme di letterali

Le regole per ∧, ∨, 2, 3, U e R sono statiche: analizzano uno stesso stato.

La regola per

`e dinamica: `e conclusa l’analisi di uno stato (rappresentato dai letterali

in Λ) e si passa ad analizzare lo stato successivo.

(25)

Terminazione 2p ∧ 3¬p

2p, 3¬p p,

2p, 3¬p

p,

2p, ¬p p,

2p,

3¬p 2p, 3¬p

...

Terminazione garantita da loop checking: se un figlio di un nodo n avrebbe etichetta S e gi`a esiste un nodo m con etichetta S, il nuovo nodo non viene creato, ma si aggiunge un arco da n a m (un tableau `e un grafo).

Sia S l’insieme iniziale di formule e

subf (S) = {A | A `e una sottoformula di una formula in S}

La costruzione di un tableau per S termina sempre perch´e le formule nelle etichette appar- tengono all’insieme finito

subf (S) ∪ {

A | A ∈ subf (S)}

Un tableau T `e completo se nessun nodo di T pu`o essere espanso

(26)

Chiusura dei tableaux

In logica classica, un nodo è chiuso (e non viene più espanso) se contiene un atomo e la sua negazione; un ramo è chiuso se la sua foglia è chiusa; un tableau è chiuso se tutti i suoi rami sono chiusi.

Un ramo aperto rappresenta uno o pi` u modelli dell’insieme iniziale di formule.

In LTL?

1 : 2p ∧ 3¬p 2 : 2p, 3¬p 3 : p,

2p, 3¬p

4 : p,

2p, ¬p 5 : p,

2p,

3¬p 2

Il ramo 1, 2, 3, 4 `e chiuso.

Il cammino 1, 2, 3, 5, 2, 3, 5, ... dovrebbe rappresentare un modello di 2p ∧ 3¬p.

Quale? Quello in cui:

M

⁰

|= p (nodo 5) M

1

|= p (nodo 5)

...

Ma 3¬p non `e soddisfatta!

(27)

Eventualities e tableaux chiusi Una eventuality `e una formula della forma 3A oppure B U A.

Se n `e un nodo di un tableau, una eventuality 3A o B U A `e soddisfatta in n se esiste un cammino nel tableau da n a un nodo che contiene A.

Procedimento per controllare se un tableau (completo) ` e chiuso:

cancellazione di nodi

• se un nodo `e contraddittorio (contiene un atomo p e la sua negazione ¬p), viene cancellato;

• se un nodo contiene una eventuality che non `e soddisfatta nel nodo, viene cancellato;

• se tutti i figli di un nodo sono cancellati, il nodo stesso viene cancellato.

Un tableau ` e chiuso se la sua radice viene cancellata 1 : 2p ∧ 3¬p

2 : 2p, 3¬p 3 : p,

2p, 3¬p

4 : p,

2p, ¬p 5 : p,

2p,

3¬p

2

(28)

Esempio

(1) 2(¬p ∨ q) ∧ (3p ∧ 2¬q) (2) 2(¬p ∨ q), 3p ∧ 2¬q

(3) ¬p ∨ q,

2(¬p ∨ q), 3p ∧ 2¬q (4) ¬p ∨ q,

2(¬p ∨ q), 3p, 2¬q

(5) ¬p ∨ q,

2(¬p ∨ q), 3p , ¬q,

2¬q

(6) ¬p,

2(¬p ∨ q), 3p , ¬q,

2¬q

(7) ¬p,

2(¬p ∨ q), p, ¬q,

2¬q

(8) ¬p,

2(¬p ∨ q),

3p, ¬q,

2¬q (9) 2(¬p ∨ q), 3p, 2¬q (10) ¬p ∨ q,

2(¬p ∨ q),

3p, 2¬q

= (4)

(11) q,

2(¬p ∨ q),

3p, ¬q ,

2¬q

(29)

Come caratterizzare i cammini aperti?

Usando le regole dei tableaux introdotte fin qui, un tableau (completo) pu`o avere cammini finiti e cammini infiniti.

Generalizziamo l’uso fatto fin’ora della regola

, in modo da avere sempre solo cammini infiniti (nei tableaux completi).

Λ,

A

1

, ...,

A

_n

A

1

, ..., A

n

(

)

dove Λ `e un insieme di letterali e n ≥ 0

Quando n = 0, l’espansione `e l’insieme vuoto, che pu`o essere rappresentato da ⊤.

Qualsiasi nodo non contraddittorio `e espandibile.

Gli unici cammini finiti sono quelli che terminano con un nodo contraddittorio.

(1) p ∨ 2q

(2) p (3) 2q

(4) q,

2q 2q = (3)

(1) p ∨ 2q (2) p

(5) ⊤

⊤ = (5)

(3) 2q

(4) q,

2q

2q = (3)

(30)

Cammini e interpretazioni temporali

• Stato: nodo a cui `e applicata la regola

• Se n `e uno stato etichettato da S, n rappresenta tutte le interpretazioni classiche I tali che:

se p ∈ S allora p ∈ I se ¬p ∈ S allora p 6∈ I

Cio`e n rappresenta qualsiasi interpretazione classica in cui sia vera la congiunzione dei letterali in S.

• Se C = n

0

, n

1

, n

2

, , ... un cammino infinito in un tableau, la sequenza degli stati del cammino C `e la sottosequenza massimale di nodi del cammino costituita soltanto da stati: s

⁰

, s

1

, s

2

, ....

• Un cammino C rappresenta tutte le interpretazioni temporali M tali che, se s

0

, s

1

, s

2

, ... `e la sequenza degli stati di C, per ogni i ∈ IN, s

i

rappresenta M(i).

Uno stato pu`o rappresentare diverse interpretazioni classiche.

Quindi un cammino pu`o rappresentare diverse interpretazioni temporali.

(31)

Esempio (1) 23p (2) 3p,

23p

(3) p,

23p 23p = (1)

(4)

3p,

23p (5) 3p, 23p 3p,

23p = (2)

C = 1, 2, 3, 1, (2, 4, 5)

^ω

Sequenza di stati 3, 4

^ω

.

Linguaggio: P = {p}.

Lo stato 3 rappresenta solo l’interpretazione {p}, lo stato 4 rappresenta sia ∅ sia {p}.

Interpretazioni M rappresentate da C: tutte quelle tali che p ∈ M(0).

Interpretazioni rappresentate da C

^′

= 1, (2, 4, 5)

^ω

: tutte.

(32)

Regole di espansione con memoria delle formule espanse

Per caratterizzare i cammini aperti in un tableau completo, modifichiamo le regole di espansione.

Nell’applicazione delle regole statiche, teniamo traccia delle formule espanse, marcandole per evitare di espanderle ancora. Con l’applicazione della regola NEXT, le formule marcate scompaiono insieme ai letterali.

A ∧ B, S A, B, (A ∧ B)

^∗

, S

A ∨ B, S

A, (A ∨ B)

^∗

, S | B, (A ∨ B)

^∗

, S 2A, S

A,

2A, (2A)

^∗

, S

3A, S

A, (3A)

^∗

, S |

3A, (3A)

^∗

, S A U B, S

B, (A U B)

^∗

, S | A,

(A U B), (A U B)

^∗

, S A R B, S

A, B, (A R B)

^∗

, S | B,

(A R B), (A R B)

^∗

, S Λ,

A

1

, ...,

A

n

, B

₁^∗

, ..., B

_k^∗

A

1

, ...., A

_n

se Λ `e un insieme di letterali e n, k ≥ 0

e le formule B

1^∗

, ..., B

_k^∗

sono state tutte espanse (sono marcate)

(33)

Nota sul loop checking nel calcolo con formule marcate: le formule marcate non possono essere ignorate.

Il loop checking avviene soltanto su stati.

Concetto chiave per caratterizzare i cammini aperti:

Nodi di accettazione di una eventuality

Sia E = 3A o E = B U A una eventuality. Un nodo n etichettato da S `e un nodo di accettazione di E sse

E 6∈ S oppure A ∈ S (se S contiene E, allora contiene anche A)

Insieme dei nodi di accettazione di E:

f

_E

= {S | E 6∈ S oppure A ∈ S}

Nota: un nodo etichettato da {⊤}, o comunque da un insieme di letterali, `e un nodo di

accettazione per qualsiasi eventuality

(34)

Esempio (1) 23p

(2) 3p ,

23p, (23p)

^∗

(3) p,

23p, (23p)

^∗

, (3p)

^∗

23p = (1)

(4)

3p,

23p, (23p)

^∗

, (3p)

^∗

(5) 3p, 23p

(6) 3p ,

23p, (23p)

^∗

p,

23p, (23p)

^∗

, (3p)

^∗

= (3)

3p,

23p, (23p)

^∗

, (3p)

^∗

= (4) I nodi in f

_3p

(i nodi di accettazione di 3p) sono in blu

Gli altri nodi contengono l’eventuality 3p (in rosso) ma non contengono p

Il nodo 6, anche se ha la stessa etichetta del nodo 2, viene ancora espanso perch´e non `e

uno stato (il controllo di cicli avviene solo su stati)

(35)

Cammini aperti in un tableau completo

Un cammino (infinito) in un tableau completo soddisfa un’eventuality E sse contiene nodi di f

E

infinitamente spesso (almeno un nodo di f

E

occorre infinite volte nel cammino).

Se un cammino massimale non soddisfa E: da un certo punto in poi contiene solo nodi che non sono in f

E

, cioè contengono E ma non A, cioè A è richiesta ma non è mai soddisfatta.

Un cammino ` e aperto sse soddisfa tutte le eventualities.

Se C `e un cammino aperto in un tableau completo, allora ogni interpretazione rappresentata da C `e un modello dell’insieme iniziale di formule.

Viceversa, ogni modello di un insieme di formule S `e rappresentato da qualche cammino aperto in un tableau completo per S.

Un tableau `e chiuso se tutti i suoi rami sono chiusi.

Teorema. Se C `e un cammino aperto in un tableau completo, i cui stati sono s

0

, s

1

, s

2

, ..., e

M `e rappresentata da C allora per ogni i ∈ IN: M

i

|= A per ogni formula A che appartiene

all’etichetta di s

i