Introduction to Formal Methods Chapter 03: Temporal Logics

(1)

Roberto Sebastiani

DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it URL: http://disi.unitn.it/rseba/DIDATTICA/fm2020/

Teaching assistant:Enrico Magnago– enrico.magnago@unitn.it

CDLM in Informatica, academic year 2019-2020

last update: Monday 18^thMay, 2020, 14:48

Copyright notice: some material (text, figures) displayed in these slides is courtesy of R. Alur, M. Benerecetti, A. Cimatti, M.

Di Natale, P. Pandya, M. Pistore, M. Roveri, and S.Tonetta, who detain its copyright. Some exampes displayed in these slides are taken from [Clarke, Grunberg & Peled, “Model Checking”, MIT Press], and their copyright is detained by the authors. All the other material is copyrighted by Roberto Sebastiani. Every commercial use of this material is strictly forbidden by the copyright laws without the authorization of the authors. No copy of these slides can be displayed in public

(2)

Outline

1 Some background on Boolean Logic

2 Generalities on temporal logics

3 Linear Temporal Logic – LTL

4 Some LTL Model Checking Examples

5 Computation Tree Logic – CTL

6 Some CTL Model Checking Examples

7 LTL vs. CTL

8 Fairness & Fair Kripke Models

9 Exercises

Roberto Sebastiani Ch. 03: Temporal Logics Monday 18^thMay, 2020 2 / 108

(3)

Some background on Boolean Logic

Boolean logic

(4)

Basic notation & definitions

Boolean formula

>, ⊥ are formulas

Apropositional atomA₁,A₂,A₃, ...is a formula;

if ϕ₁and ϕ₂are formulas, then

¬ϕ₁, ϕ₁∧ ϕ₂, ϕ₁∨ ϕ₂, ϕ₁→ ϕ₂, ϕ₁← ϕ₂, ϕ₁↔ ϕ₂ are formulas.

Atoms(ϕ): the set {A₁, ...,A_N} of atoms occurring in ϕ.

Literal: a propositional atom A_i (positive literal) or its negation ¬A_i (negative literal)

Notation: if l := ¬A_i, then ¬l := A_i Clause: a disjunction of literalsW

jl_j (e.g.,(A₁∨ ¬A₂∨ A₃∨ ...)) Cube:a conjunction of literalsV

jl_j(e.g.,(A₁∧ ¬A₂∧ A₃∧ ...))

(5)

Semantics of Boolean operators

Truth table:

ϕ1 ϕ2 ¬ϕ₁ ϕ1∧ ϕ₂ ϕ1∨ ϕ₂ ϕ1→ ϕ₂ ϕ1← ϕ₂ ϕ1↔ ϕ₂

⊥ ⊥ > ⊥ ⊥ > > >

⊥ > > ⊥ > > ⊥ ⊥

> ⊥ ⊥ ⊥ > ⊥ > ⊥

> > ⊥ > > > > >

Note

∧, ∨ and ↔ are commutative:

(ϕ₁∧ ϕ₂) ⇐⇒ (ϕ₂∧ ϕ₁) (ϕ₁∨ ϕ₂) ⇐⇒ (ϕ₂∨ ϕ₁) (ϕ1↔ ϕ₂) ⇐⇒ (ϕ₂↔ ϕ₁)

∧ and ∨ are associative:

((ϕ₁∧ ϕ₂) ∧ ϕ₃) ⇐⇒ (ϕ₁∧ (ϕ₂∧ ϕ₃)) ⇐⇒ (ϕ₁∧ ϕ₂∧ ϕ₃) ((ϕ1∨ ϕ₂) ∨ ϕ3) ⇐⇒ (ϕ1∨ (ϕ₂∨ ϕ₃)) ⇐⇒ (ϕ1∨ ϕ₂∨ ϕ₃)

(6)

Syntactic Properties of Boolean Operators

¬¬ϕ₁ ⇐⇒ ϕ₁

(ϕ₁∨ ϕ₂) ⇐⇒ ¬(¬ϕ₁∧ ¬ϕ₂)

¬(ϕ₁∨ ϕ₂) ⇐⇒ (¬ϕ₁∧ ¬ϕ₂) (ϕ₁∧ ϕ₂) ⇐⇒ ¬(¬ϕ₁∨ ¬ϕ₂)

¬(ϕ₁∧ ϕ₂) ⇐⇒ (¬ϕ₁∨ ¬ϕ₂) (ϕ1→ ϕ₂) ⇐⇒ (¬ϕ₁∨ ϕ₂)

¬(ϕ₁→ ϕ₂) ⇐⇒ (ϕ₁∧ ¬ϕ₂) (ϕ₁← ϕ₂) ⇐⇒ (ϕ₁∨ ¬ϕ₂)

¬(ϕ₁← ϕ₂) ⇐⇒ (¬ϕ₁∧ ϕ₂)

(ϕ₁↔ ϕ₂) ⇐⇒ ((ϕ₁→ ϕ₂) ∧ (ϕ₁← ϕ₂))

⇐⇒ ((¬ϕ₁∨ ϕ₂) ∧ (ϕ₁∨ ¬ϕ₂))

¬(ϕ₁↔ ϕ₂) ⇐⇒ (¬ϕ₁↔ ϕ₂)

⇐⇒ (ϕ₁↔ ¬ϕ₂)

⇐⇒ ((ϕ₁∨ ϕ₂) ∧ (¬ϕ₁∨ ¬ϕ₂))

Boolean logic can be expressed in terms of {¬, ∧} (or {¬, ∨}) only

(7)

TREE and DAG representation of formulas: example

Formulas can be represented either as trees or as DAGS:

DAG representation can be up to exponentially smaller (A₁↔ A₂) ↔ (A₃↔ A₄)

⇓

(((A₁↔ A2) → (A₃↔ A4))∧

((A₃↔ A₄) → (A₁↔ A₂)))

⇓

(((A₁→ A2) ∧ (A₂→ A1)) → ((A₃→ A4) ∧ (A₄→ A3)))∧

(((A₃→ A₄) ∧ (A₄→ A₃)) → (((A₁→ A₂) ∧ (A₂→ A₁))))

(8)

TREE and DAG representation of formulas: example (cont)

Tree Representation

DAG Representation

A1 A2 A2 A1 A3 A4 A4 A3 A3 A4 A4 A3 A1 A2 A2 A1

A2

A1 A3 A4

(9)

Basic notation & definitions (cont)

Total truth assignmentµfor ϕ:

µ :Atoms(ϕ) 7−→ {>, ⊥}.

Partial Truth assignmentµfor ϕ:

µ : A 7−→ {>, ⊥}, A ⊂ Atoms(ϕ).

Set and formula representation of an assignment:

µcan be represented as a set of literals:

EX:{µ(A₁) := >, µ(A₂) := ⊥} =⇒ {A₁, ¬A₂} µcan be represented as a formula (cube):

EX:{µ(A₁) := >, µ(A₂) := ⊥} =⇒ (A₁∧ ¬A₂)

(10)

Basic notation & definitions (cont)

atotaltruth assignmentµsatisfies ϕ(µ |= ϕ):

µ |=Ai ⇐⇒ µ(A_i) = >

µ |= ¬ϕ ⇐⇒not µ |= ϕ

µ |= ϕ₁∧ ϕ₂⇐⇒ µ |= ϕ₁and µ |= ϕ₂ µ |= ϕ₁∨ ϕ₂⇐⇒ µ |= ϕ₁or µ |= ϕ₂ µ |= ϕ₁→ ϕ₂⇐⇒ if µ |= ϕ₁, then µ |= ϕ₂ µ |= ϕ₁↔ ϕ₂⇐⇒ µ |= ϕ₁iff µ |= ϕ₂

apartialtruth assignmentµsatisfies ϕiff it makes ϕ evaluate to true (Ex: {A₁} |= (A₁∨ A₂))

=⇒ if µ satisfies ϕ, then all its total extensions satisfy ϕ (Ex:{A₁,A2} |= (A₁∨ A₂)and{A₁, ¬A2} |= (A₁∨ A₂)) ϕissatisfiableiff µ |= ϕ for some µ

Property

ϕis valid ⇐⇒ ¬ϕ is not satisfiable

(11)

Equivalence and equi-satisfiability

ϕ₁and ϕ₂areequivalent iff, for every µ, µ |= ϕ₁iff µ |= ϕ₂ ϕ₁and ϕ₂areequi-satisfiableiff

exists µ₁s.t. µ₁|= ϕ₁iff exists µ₂s.t. µ₂|= ϕ₂ ϕ₁, ϕ₂equivalent

⇓ 6⇑

ϕ₁, ϕ₂equi-satisfiable EX:ϕ1

def= ψ1∨ ψ₂andϕ2

def= (ψ1∨ ¬A3) ∧ (A₃∨ ψ₂)s.t.A₃not in ψ1∨ ψ₂, are equi-satisfiable but not equivalent:

µ |= (ψ₁∨ ¬A₃) ∧ (A₃∨ ψ₂)=⇒µ |= ψ₁∨ ψ₂

µ⁰|= ψ₁∨ ψ₂=⇒µ⁰∧ A₃|= (ψ₁∨ ¬A₃) ∧ (A₃∨ ψ₂)or µ⁰∧ ¬A₃|= (ψ₁∨ ¬A₃) ∧ (A₃∨ ψ₂)[ϕ₁, ϕ₂equi-satisfiable]

µ⁰6|= ψ₁andµ⁰|= ψ₂=⇒µ⁰∧ A₃|= ψ₁∨ ψ₂and

µ⁰∧ A₃6|= (ψ₁∨ ¬A₃) ∧ (A3∨ ψ₂)[ϕ1, ϕ₂not equivalent]

Typically used when ϕ₂is the result of applying some transformation T to ϕ₁: ϕ₂^def=T (ϕ₁):

we say that T isvalidity-preserving[satisfiability-preserving] iff

(12)

Complexity

For N variables, there are up to 2^N truth assignments to be checked.

The problem of deciding the satisfiability of a propositional formula isNP-complete

The most important logical problems (validity,inference,

entailment,equivalence, ...) can be straightforwardly reduced to satisfiability, and are thus(co)NP-complete.

⇓

No existing worst-case-polynomial algorithm.

(13)

POLARITY of subformulas

Positive/negative occurrences ϕoccurs positively in ϕ;

if ¬ϕ₁occurs positively [negatively] in ϕ, then ϕ1occurs negatively [positively] in ϕ

if ϕ1∧ ϕ₂or ϕ1∨ ϕ₂occur positively [negatively] in ϕ, then ϕ1and ϕ2occur positively [negatively] in ϕ;

if ϕ1→ ϕ₂occurs positively [negatively] in ϕ,

then ϕ1occurs negatively [positively] in ϕ and ϕ2occurs positively [negatively] in ϕ;

if ϕ1↔ ϕ₂occurs in ϕ,

then ϕ1and ϕ2occur positively and negatively in ϕ;

EX:

ϕ₁occurs positively in ¬(ϕ1→ ϕ₂) ϕ₂occurs negatively in ¬(ϕ1→ ϕ₂)

intuition: ϕ₁occurs positively [negatively] in ϕ iff it occurs under the scope of an (implicit) even [odd] number of negations.

=⇒ Polarity: the number of nested negations modulo 2.

(14)

Substitution

Properties

If ϕ₁is equivalent to ϕ₂, then ϕ[ϕ₁|ϕ₂]is equivalent to ϕ:

|= (ϕ₁↔ ϕ₂)

⇓

|= ϕ[ϕ₁|ϕ₂] ↔ ϕ

If ϕ₂entails ϕ₁and ϕ₁occurs only positively in ϕ, then ϕ[ϕ₁|ϕ₂] entails ϕ:

ϕ₂|= ϕ₁

⇓ ϕ[ϕ1|ϕ₂] |= ϕ dual case for negative occurrence

(15)

Negative normal form (NNF)

ϕis inNegative normal formiff it is given only by the recursive applications of ∧, ∨ to literals.

every ϕ can be reduced into NNF:

(i) substituting all →’s and ↔’s:

ϕ₁→ ϕ₂ =⇒ ¬ϕ₁∨ ϕ₂

ϕ1↔ ϕ₂ =⇒ (¬ϕ1∨ ϕ₂) ∧ (ϕ1∨ ¬ϕ₂) (ii) pushing down negations recursively:

¬(ϕ₁∧ ϕ₂) =⇒ ¬ϕ₁∨ ¬ϕ₂

¬(ϕ₁∨ ϕ₂) =⇒ ¬ϕ₁∧ ¬ϕ₂

¬¬ϕ₁ =⇒ ϕ1

The reduction islinearif a DAG representation is used.

Preserves theequivalenceof formulas.

(16)

NNF: example

(A₁↔ A2) ↔ (A₃↔ A4)

⇓

((((A₁→ A₂) ∧ (A₁← A₂)) → ((A₃→ A₄) ∧ (A₃← A₄)))∧

(((A₁→ A2) ∧ (A₁← A2)) ← ((A₃→ A4) ∧ (A₃← A4))))

⇓

((¬((¬A₁∨ A₂) ∧ (A₁∨ ¬A₂)) ∨ ((¬A₃∨ A₄) ∧ (A₃∨ ¬A₄)))∧

(((¬A₁∨ A2) ∧ (A₁∨ ¬A2)) ∨ ¬((¬A₃∨ A4) ∧ (A₃∨ ¬A4))))

⇓

((((A₁∧ ¬A₂) ∨ (¬A₁∧ A₂)) ∨ ((¬A₃∨ A₄) ∧ (A₃∨ ¬A₄)))∧

(((¬A₁∨ A2) ∧ (A₁∨ ¬A2)) ∨ ((A₃∧ ¬A4) ∨ (¬A₃∧ A4))))

(17)

NNF: example (cont)

A1 −A2 −A1 A2 −A3 A4A3 −A4 −A1 A2 A1 −A2 A3 −A4−A3 A4

−B1 B2 B1 −B2

A1 −A2 −A1 A2 −A3 A4A3 −A4

−B1 B2 B1 −B2

Tree Representation

DAG Representation

Note

For each non-literal subformula ϕ, ϕ and ¬ϕ have different representations =⇒ they are not shared.

(18)

Optimized polynomial representations

And-Inverter Graphs,Reduced Boolean Circuits,Boolean Expression Diagrams

Maximize the sharing in DAG representations:

{∧, ↔, ¬}-only, negations on arcs, sorting of subformulae, lifting of

¬’s over ↔’s,...

(19)

Conjunctive Normal Form (CNF)

ϕis inConjunctive normal formiff it is a conjunction of disjunctions of literals:

L

^

i=1 K_i

_

ji=1

l_j_i

the disjunctions of literalsWKi

j_i=1l_j_i are calledclauses Easier to handle: list of lists of literals.

=⇒no reasoning on the recursive structure of the formula

(20)

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNFby, e.g., (i) converting it into NNF (not indispensible);

(ii) applying recursively the DeMorgan’s Rule:

(ϕ1∧ ϕ₂) ∨ ϕ3 =⇒ (ϕ1∨ ϕ₃) ∧ (ϕ2∨ ϕ₃) Worst-caseexponential.

Atoms(CNF (ϕ)) = Atoms(ϕ).

CNF (ϕ) isequivalentto ϕ.

Rarely used in practice.

(21)

Labeling CNF conversion CNFlabel(ϕ)

Every ϕ can be reduced into CNFby, e.g., applying recursively bottom-up the rules:

ϕ =⇒ ϕ[(l_i∨ l_j)|B] ∧ CNF (B ↔ (l_i∨ l_j)) ϕ =⇒ ϕ[(l_i∧ l_j)|B] ∧ CNF (B ↔ (l_i∧ l_j)) ϕ =⇒ ϕ[(l_i ↔ lj)|B] ∧ CNF (B ↔ (l_i ↔ lj)) l_i,l_j being literals and B being a “new” variable.

Worst-caselinear.

Atoms(CNF_label(ϕ)) ⊇Atoms(ϕ).

CNF_label(ϕ)isequi-satisfiablew.r.t. ϕ.

More used in practice.

(22)

Labeling CNF conversion CNFlabel(ϕ) (cont.)

CNF (B ↔ (l_i∨ l_j)) ⇐⇒ (¬B ∨ l_i∨ l_j)∧

(B ∨ ¬l_i)∧

(B ∨ ¬l_j) CNF (B ↔ (l_i∧ lj)) ⇐⇒ (¬B ∨ li)∧

(¬B ∨ l_j)∧

(B ∨ ¬l_i¬l_j) CNF (B ↔ (l_i ↔ l_j)) ⇐⇒ (¬B ∨ ¬l_i∨ l_j)∧

(¬B ∨ l_i∨ ¬lj)∧

(B ∨ l_i∨ l_j)∧

(B ∨ ¬l_i∨ ¬l_j)

(23)

Labeling CNF conversion CNFlabel – example

−A3 A1 A5 −A4 −A3 A4 A2 −A6 A1 A4 A3 −A5 −A2 A6 A1 −A4

B1 B2 B3 B4 B5 B6 B7 B8

B9 B10 B11 B12

B13 B14

B15

CNF (B1↔ (¬A3∨ A1)) ∧

... ∧

CNF (B8↔ (A1∨ ¬A4)) ∧ CNF (B9↔ (B1↔ B2)) ∧

... ∧

CNF (B12↔ (B7∧ B8)) ∧ CNF (B13↔ (B9∨ B10)) ∧ CNF (B14↔ (B11∨ B12)) ∧ CNF (B15↔ (B13∧ B14)) ∧ B15

(24)

Labeling CNF conversion CNFlabel (variant)

As in the previous case, applying instead the rules:

ϕ =⇒ ϕ[(l_i∨ l_j)|B] ∧ CNF (B → (l_i∨ l_j)) if (l_i∨ l_j)pos.

ϕ =⇒ ϕ[(l_i∨ l_j)|B] ∧ CNF ((l_i∨ l_j) →B) if (l_i∨ l_j)neg.

ϕ =⇒ ϕ[(l_i∧ lj)|B] ∧ CNF (B → (li∧ lj)) if (l_i∧ lj)pos.

ϕ =⇒ ϕ[(l_i∧ l_j)|B] ∧ CNF ((l_i∧ l_j) →B) if (l_i∧ l_j)neg.

ϕ =⇒ ϕ[(l_i ↔ l_j)|B] ∧ CNF (B → (l_i ↔ l_j)) if (l_i ↔ l_j)pos.

ϕ =⇒ ϕ[(l_i ↔ lj)|B] ∧ CNF ((l_i ↔ lj) →B) if (l_i ↔ lj)neg.

Pro: smaller in size:

CNF (B → (l_i∨ l_j)) = (¬B ∨ l_i∨ l_j)

CNF (((l_i∨ lj) →B)) = (¬l_i∨ B) ∧ (¬lj∨ B) Con: looses backward propagation:

unlike with CNF (B ↔ (l_i∨ lj)), with CNF (B → (l_i∨ lj))we can no more infer that B is true from the fact that l_i is true or l_j is true.

(25)

Labeling CNF conversion CNFlabel(ϕ) (cont.)

CNF (B → (l_i∨ l_j)) ⇐⇒ (¬B ∨ l_i∨ l_j) CNF (B ← (l_i∨ l_j)) ⇐⇒ (B ∨ ¬l_i)∧

(B ∨ ¬l_j) CNF (B → (l_i∧ lj)) ⇐⇒ (¬B ∨ li)∧

(¬B ∨ l_j) CNF (B ← (l_i∧ l_j)) ⇐⇒ (B ∨ ¬l_i¬l_j) CNF (B → (l_i ↔ lj)) ⇐⇒ (¬B ∨ ¬li∨ lj)∧

(¬B ∨ l_i∨ ¬l_j) CNF (B ← (l_i ↔ l_j)) ⇐⇒ (B ∨ l_i∨ l_j)∧

(B ∨ ¬l_i∨ ¬l_j)

(26)

Labeling CNF conversion CNFlabel – example

−A3 A1 A5 −A4 −A3 A4 A2 −A6 A1 A4 A3 −A5 −A2 A6 A1 −A4

B1 B2 B3 B4 B5 B6 B7 B8

B9 B10 B11 B12

B13 B14

B15

Basic Improved

CNF (B1↔ (¬A3∨ A1)) ∧

... ∧

CNF (B8↔ (A1∨ ¬A4)) ∧ CNF (B9↔ (B1↔ B2)) ∧

... ∧

CNF (B12↔ (B7∧ B8)) ∧ CNF (B13↔ (B9∨ B10)) ∧ CNF (B14↔ (B11∨ B12)) ∧ CNF (B15↔ (B13∧ B14)) ∧ B15

CNF (B1↔ (¬A3∨ A1)) ∧

... ∧

CNF (B8→ (A1∨ ¬A4)) ∧ CNF (B9→ (B1↔ B2)) ∧

... ∧

CNF (B12→ (B7∧ B8)) ∧ CNF (B13→ (B9∨ B10)) ∧ CNF (B14→ (B11∨ B12)) ∧ CNF (B15→ (B13∧ B14)) ∧ B15

(27)

Labeling CNF conversion CNFlabel – further optimizations

Do not apply CNF_label when not necessary:

(e.g.,CNF_label(ϕ₁∧ ϕ₂) =⇒CNF_label(ϕ₁) ∧ ϕ₂, if ϕ₂already in CNF)

Apply Demorgan’s rules where it is more effective: (e.g.,

CNF_label(ϕ₁∧(A → (B ∧C))) =⇒ CNFlabel(ϕ₁)∧(¬A∨B)∧(¬A∨C) exploit the associativity of ∧’s and ∨’s:

... (A₁∨ (A2∨ A3))

| {z }

B

... =⇒ ...CNF (B ↔ (A₁∨ A2∨ A3))...

before applying CNF_label, rewrite the initial formula so that to maximize the sharing of subformulas (RBC, BED)

...

(28)

Generalities on temporal logics

Computation tree vs. computation paths

Consider the following Kripke structure:

done

!done

Its execution can be seen as:

an infinite set of computation paths

done done done

!done

done done

done

!done !done

!done !done !done

!done

...

an infinite computation tree

done

done done done

done

!done

(29)

Generalities on temporal logics

Temporal Logics

Express properties of “Reactive Systems”

nonterminating behaviours, without explicit reference to time.

Linear Temporal Logic (LTL)

interpreted over each path of the Kripke structure linear model of time

temporal operators

“Medieval”: “since birth, one’s destiny is set”.

Computation Tree Logic (CTL)

interpreted over computation tree of Kripke model branching model of time

temporal operators plus path quantifiers

“Humanistic”: “one makes his/her own destiny step-by-step”.

(30)

Linear Temporal Logic – LTL

Linear Temporal Logic (LTL): Syntax

Anatomic propositionis a LTL formula;

ifϕ1andϕ2are LTL formulae, then¬ϕ₁, ϕ₁∧ ϕ₂, ϕ₁∨ ϕ₂, ϕ₁→ ϕ₂, ϕ₁↔ ϕ₂are LTL formulae;

ifϕ1andϕ2are LTL formulae, thenXϕ₁, ϕ₁Uϕ₂,Gϕ₁,Fϕ₁are LTL formulae, whereX, G, F, U are the “next”, “globally”,

“eventually”,“until” temporal operators respectively.

Another operatorR “releases” (the dual of U) is used sometimes.

(31)

LTL semantics: intuitions

LTL is given by the standard boolean logic enhanced with the following temporal operators, which operate throughpaths hs₀,s₁, ...,s_k, ...i:

“Next”X: Xϕ is true in st iff ϕ is true in s_t+1

“Finally” (or “eventually”)F: Fϕ is true in s_t iff ϕ is true insome s_t⁰ with t⁰≥ t

“Globally” (or “henceforth”)G: Gϕ is true in s_t iff ϕ is true inall s_t⁰ with t⁰≥ t

“Until”U: ϕUψ is true in s_t iff, for some state s_t⁰ s.t t⁰≥ t:

ψis true in s_t⁰ and

ϕis true in all states s_t⁰⁰s.t. t ≤ t⁰⁰<t⁰

“Releases”R: ϕRψ is true in s_t iff, for all states s_t⁰ s.t. t⁰ ≥ t:

ψis trueor

ϕis true in some states st⁰⁰with t ≤ t⁰⁰<t⁰

“ψ can become false only if ϕ becomes true first"

(32)

LTL semantics: intuitions finally P

F P

globally P

G P

X P

next P P until q

P U q

(33)

LTL: Some Noteworthy Examples

Safety: “it never happens that a train is arriving and the bar is up”

G(¬(train_arriving ∧ bar_up)) Liveness:“if input, then eventually output”

G(input → Foutput)

Releases:“the device is not working if you don’t first repair it”

(repair_deviceR ¬working_device) Fairness:“infinitely often send ”

GFsend

Strong fairness:“infinitely often send implies infinitely often recv.”

GFsend → GFrecv

(34)

LTL Formal Semantics

π,s_i |= a iff a ∈ L(s_i)

π,s_i |= ¬ϕ iff π,s_i 6|= ϕ

π,s_i |= ϕ ∧ ψ iff π,s_i |= ϕ and

π,s_i |= ψ

π,s_i |= Xϕ iff π,s_i+1 |= ϕ

for all k s.t. i ≤ k < j : π, s_k |= ϕ) π,s_i |= ϕRψ iff for all j ≥ i : (π, s_j |= ψ or

for some k s.t. i ≤ k < j : π, s_k |= ϕ)

(35)

LTL Formal Semantics (cont.)

LTL properties are evaluated over paths, i.e., over infinite, linear sequences of states: π =s₀→ s1→ · · · → st → st+1→ · · · Given an infinite sequence π = s₀,s₁,s₂, . . .

π,s_i |= φ if φ is true in state s_i of π.

π |= φif φ is true in the initial state s₀of π.

The LTL model checking problem M |= φ

check if π |= φ for every path π of the Kripke structure M (e.g., φ =Fdone)

done

!done ^!done ^done ^done ^done

!done

done done

done

!done !done

!done !done !done

!done

...

(36)

The LTL model checking problem M |= φ: remark

The LTL model checking problem M |= φ

π |= φfor every path πof the Kripke structure M

Important Remark M 6|= φ 6=⇒ M |= ¬φ(!!)

E.g. if φ is a LTL formula and two paths π₁and π₂are s.t. π₁|= φ and π₂|= ¬φ.

(37)

Example: M 6|= φ 6=⇒ M |= ¬φ

Let π₁^def= {s₁}^ω, π₂= {s^def ₂}^ω. M 6|= Gp, in fact:

π₁6|= Gp π₂|= Gp M 6|= ¬Gp, in fact:

π₁|= ¬Gp π₂6|= ¬Gp

pq s0

¬p¬q s₁

p¬q s₂

(38)

Syntactic properties of LTL operators

ϕ₁∨ ϕ₂ ⇐⇒ ¬(¬ϕ₁∧ ¬ϕ₂) ...

F ϕ₁ ⇐⇒ >Uϕ1

G ϕ₁ ⇐⇒ ⊥Rϕ₁ Fϕ₁ ⇐⇒ ¬G¬ϕ₁ Gϕ₁ ⇐⇒ ¬F¬ϕ1

¬Xϕ₁ ⇐⇒ X¬ϕ₁

ϕ₁Rϕ₂ ⇐⇒ ¬(¬ϕ₁U¬ϕ₂) ϕ₁Uϕ₂ ⇐⇒ ¬(¬ϕ₁R¬ϕ₂) Note

LTL can be defined in terms of ∧, ¬,X, U only

Exercise

Prove that ϕ₁Rϕ₂⇐⇒ Gϕ2∨ ϕ₂U(ϕ₁∧ ϕ₂)

(39)

Proof of ϕRψ ⇔ (Gψ ∨ ψU(ϕ ∧ ψ))

[Solution proposed by the student Samuel Valentini, 2016]

(All state indexes below are implicitly assumed to be ≥ 0.)

⇒: Let π be s.t. π, s₀|= ϕRψ

If ∀j, π, s_j |= ψ, then π, s₀|= Gψ.

Otherwise, let s_k be thefirststate s.t. π, s_k 6|= ψ.

Thus, π, s0|= Gψ ∨ ψU(ϕ ∧ ψ)

⇐: Let π be s.t. π, s₀|= Gψ ∨ ψU(ϕ ∧ ψ)

If π, s₀|= Gψ, then ∀j, π, s_j |= ψ, so that π, s₀|= ϕRψ.

Otherwise, π, s₀|= ψU(ϕ ∧ ψ).

Let s_k be thefirststate s.t. π, s_k 6|= ψ.

by construction, ∃k⁰such that π, S_k⁰ |= ϕ ∧ ψ

by the definition of k , we have that k⁰ <k and ∀w < k , π, S_w|= ψ.

Thus π, s |= ϕRψ

(40)

Strength of LTL operators

Gϕ |= ϕ |= Fϕ Gϕ |= Xϕ |= Fϕ Gϕ |= XX...Xϕ |= Fϕ ϕUψ |= Fψ

Gψ |= ϕRψ

(41)

LTL tableaux rules

Let ϕ1 and ϕ2 be LTL formulae:

Fϕ1 ⇐⇒ (ϕ₁∨ XFϕ₁) Gϕ1 ⇐⇒ (ϕ₁∧ XGϕ₁)

ϕ₁Uϕ2 ⇐⇒ (ϕ₂∨ (ϕ₁∧ X(ϕ₁Uϕ2))) ϕ₁Rϕ₂ ⇐⇒ (ϕ₂∧ (ϕ₁∨ X(ϕ₁Rϕ₂)))

If applied recursively, rewrite an LTL formula in terms of atomic andX-formulas:

(pUq) ∧ (G¬p) =⇒ (q ∨ (p ∧ X(pUq))) ∧ (¬p ∧ XG¬p)

(42)

Tableaux rules: a quote

“After all... tomorrow is another day."

[Scarlett O’Hara, “Gone with the Wind”]

(43)

Some LTL Model Checking Examples

Example 1: mutual exclusion (safety)

N1, N2 turn=0

turn=1 C1, T2

turn=1 T1, T2 T1, N2

turn=1

C1, N2 turn=1

T1, T2 turn=2 N = noncritical, T = trying, C = critical User 1 User 2

N1, T2 turn=2

T1, C2 turn=2

turn=2 N1, C2

M |=G¬(C₁∧ C2)?

YES: There is no reachable state in which (C₁∧ C₂)holds!

(44)

Example 2: liveness

N1, N2 turn=0

turn=1 C1, T2

turn=1 T1, T2 T1, N2

turn=1

C1, N2 turn=1

N1, T2 turn=2

T1, C2 turn=2

turn=2 N1, C2

M |=FC₁?

NO: there is an infinite cyclic solution in which C₁never holds!

(45)

Example 3: liveness

N1, N2 turn=0

turn=1 C1, T2

turn=1 T1, T2 T1, N2

turn=1

C1, N2 turn=1

N1, T2 turn=2

T1, C2 turn=2

turn=2 N1, C2

M |=G(T₁→ FC₁)?

YES: every path starting from each state where T₁holds passes through a state where C₁holds.