Introduction to Formal Methods Chapter 03: Temporal Logics

Introduction to Formal Methods Chapter 03: Temporal Logics

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

without containing this copyright notice.

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

Some background on Boolean Logic

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

Some background on Boolean Logic

Boolean logic

Some background on Boolean Logic

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₃∧ ...))

Some background on Boolean Logic

Semantics of Boolean operators

Truth table:

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

⊥ ⊥ > ⊥ ⊥ > > >

⊥ > > ⊥ > > ⊥ ⊥

> ⊥ ⊥ ⊥ > ⊥ > ⊥

> > ⊥ > > > > >

Note

∧, ∨ and ↔ are commutative: (ϕ₁∧ ϕ₂) ⇐⇒ (ϕ₂∧ ϕ₁) (ϕ₁∨ ϕ₂) ⇐⇒ (ϕ₂∨ ϕ₁) (ϕ₁↔ ϕ₂) ⇐⇒ (ϕ₂↔ ϕ₁)

∧ and ∨ are associative:

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

Some background on Boolean Logic

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∨ ϕ₂∨ ϕ₃)

Some background on Boolean Logic

Syntactic Properties of Boolean Operators

¬¬ϕ₁ ⇐⇒ ϕ₁

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

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

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

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

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

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

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

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

⇐⇒ (ϕ₁↔ ¬ϕ₂)

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

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

Some background on Boolean Logic

Syntactic Properties of Boolean Operators

¬¬ϕ₁ ⇐⇒ ϕ₁

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

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

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

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

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

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

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

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

⇐⇒ (ϕ₁↔ ¬ϕ₂)

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

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

Some background on Boolean Logic

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₁))))

Some background on Boolean Logic

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₁))))

Some background on Boolean Logic

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₁))))

Some background on Boolean Logic

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

Some background on Boolean Logic

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₂)

Some background on Boolean Logic

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 µ

ϕ1entails ϕ₂(ϕ₁|= ϕ₂): ϕ₁|= ϕ₂iff µ |= ϕ₁=⇒ µ |= ϕ2for every µ ϕis valid(|= ϕ): |= ϕ iff µ |= ϕ for every µ

Property

ϕis valid ⇐⇒ ¬ϕ is not satisfiable

Some background on Boolean Logic

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 µ

ϕ1entails ϕ₂(ϕ₁|= ϕ₂): ϕ₁|= ϕ₂iff µ |= ϕ₁=⇒ µ |= ϕ2for every µ ϕis valid(|= ϕ): |= ϕ iff µ |= ϕ for every µ

Property

ϕis valid ⇐⇒ ¬ϕ is not satisfiable

Some background on Boolean Logic

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 µ

ϕ1entails ϕ₂(ϕ₁|= ϕ₂): ϕ₁|= ϕ₂iff µ |= ϕ₁=⇒ µ |= ϕ2for every µ ϕis valid(|= ϕ): |= ϕ iff µ |= ϕ for every µ

Property

ϕis valid ⇐⇒ ¬ϕ is not satisfiable

Some background on Boolean Logic

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 µ

ϕ1entails ϕ₂(ϕ₁|= ϕ₂): ϕ₁|= ϕ₂iff µ |= ϕ₁=⇒ µ |= ϕ2for every µ

ϕis valid(|= ϕ): |= ϕ iff µ |= ϕ for every µ Property

ϕis valid ⇐⇒ ¬ϕ is not satisfiable

Some background on Boolean Logic

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 µ

ϕ1entails ϕ₂(ϕ₁|= ϕ₂): ϕ₁|= ϕ₂iff µ |= ϕ₁=⇒ µ |= ϕ2for every µ ϕis valid(|= ϕ): |= ϕ iff µ |= ϕ for every µ

Property

ϕis valid ⇐⇒ ¬ϕ is not satisfiable

Some background on Boolean Logic

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 µ

ϕ1entails ϕ₂(ϕ₁|= ϕ₂): ϕ₁|= ϕ₂iff µ |= ϕ₁=⇒ µ |= ϕ2for every µ ϕis valid(|= ϕ): |= ϕ iff µ |= ϕ for every µ

Property

ϕis valid ⇐⇒ ¬ϕ is not satisfiable

Some background on Boolean Logic

Equivalence and equi-satisfiability

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

ϕ1and ϕ₂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 ψ₁∨ ψ₂, are equi-satisfiable but not equivalent:

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

µ⁰|= ψ₁∨ ψ₂=⇒µ⁰∧ A₃|= (ψ₁∨ ¬A₃) ∧ (A₃∨ ψ₂)or µ⁰∧ ¬A₃|= (ψ₁∨ ¬A₃) ∧ (A3∨ ψ₂)[ϕ1, ϕ₂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 T (ϕ₁)and ϕ₁are equivalent [equi-satisfiable]

Some background on Boolean Logic

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 ψ₁∨ ψ₂, are equi-satisfiable but not equivalent:

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

µ⁰|= ψ₁∨ ψ₂=⇒µ⁰∧ A₃|= (ψ₁∨ ¬A₃) ∧ (A₃∨ ψ₂)or µ⁰∧ ¬A₃|= (ψ₁∨ ¬A₃) ∧ (A3∨ ψ₂)[ϕ1, ϕ₂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 T (ϕ₁)and ϕ₁are equivalent [equi-satisfiable]

Some background on Boolean Logic

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 ψ₁∨ ψ₂, are equi-satisfiable but not equivalent:

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

µ⁰|= ψ₁∨ ψ₂=⇒µ⁰∧ A₃|= (ψ₁∨ ¬A₃) ∧ (A₃∨ ψ₂)or µ⁰∧ ¬A₃|= (ψ₁∨ ¬A₃) ∧ (A3∨ ψ₂)[ϕ1, ϕ₂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 T (ϕ₁)and ϕ₁are equivalent [equi-satisfiable]

Some background on Boolean Logic

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₃) ∧ (A3∨ ψ₂)[ϕ1, ϕ₂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 T (ϕ₁)and ϕ₁are equivalent [equi-satisfiable]

Some background on Boolean Logic

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₃) ∧ (A3∨ ψ₂)[ϕ1, ϕ₂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 T (ϕ₁)and ϕ₁are equivalent [equi-satisfiable]

Some background on Boolean Logic

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 T (ϕ₁)and ϕ₁are equivalent [equi-satisfiable]

Some background on Boolean Logic

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 T (ϕ₁)and ϕ₁are equivalent [equi-satisfiable]