Formal Methods: Module I: Automated Reasoning Ch. 01: Reasoning in Propositional Logic

(1)

Formal Methods:

Module I: Automated Reasoning

Ch. 01: Reasoning in Propositional Logic

Roberto Sebastiani

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

Teaching assistant:Giuseppe Spallitta– giuseppe.spallitta@unitn.it

M.S. in Computer Science, Mathematics, & Artificial Intelligence Systems Academic year 2020-2021

last update: Tuesday 13^thApril, 2021

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.

1 / 173

(2)

Outline

1

Boolean Logics and SAT

2

Basic SAT-Solving Techniques Resolution

Tableaux DPLL

Stochastic Local Search for SAT

3

Ordered Binary Decision Diagrams – OBDDs

4

Modern CDCL SAT Solvers

Limitations of Chronological Backtracking Conflict-Driven Clause-Learning SAT solvers Further Improvements

SAT Under Assumptions & Incremental SAT

5

SAT Functionalities: proofs, unsat cores, interpolants, optimization

2 / 173

(3)

Outline

1

Boolean Logics and SAT

2

Basic SAT-Solving Techniques Resolution

Tableaux DPLL

Stochastic Local Search for SAT

3

Ordered Binary Decision Diagrams – OBDDs

4

Modern CDCL SAT Solvers

Limitations of Chronological Backtracking Conflict-Driven Clause-Learning SAT solvers Further Improvements

SAT Under Assumptions & Incremental SAT

5

SAT Functionalities: proofs, unsat cores, interpolants, optimization

3 / 173

(4)

Propositional Logic (aka Boolean Logic)

4 / 173

(5)

Basic Definitions

Propositional formula (aka Boolean formula)

>, ⊥ are formulas

a propositional atom A

1

, A

2

, A

3

, ... is a formula;

if ϕ

1

and ϕ

2

are formulas, then

¬ϕ

₁

, ϕ

1

∧ ϕ

₂

, ϕ

1

∨ ϕ

₂

, ϕ

1

→ ϕ

₂

, ϕ

1

← ϕ

₂

, ϕ

1

↔ ϕ

₂

, ϕ

1

⊕ ϕ

₂

are formulas.

Ex: ϕ

^def

= (¬(A

₁

→ A

2

)) ∧ (A

₃

↔ (¬A

1

⊕ (A

2

∨ ¬A

4

)))) Atoms(ϕ): the set {A

₁

, ..., A

_N

} of atoms occurring in ϕ.

Ex: Atoms(ϕ) = {A

1

, A

2

, A

3

, A

4

}

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 literals W

j

l

_j

(e.g., (A

₁

∨ ¬A

₂

∨ A

₃

∨ ...)) Cube: a conjunction of literals V

j

l

_j

(e.g., (A

₁

∧ ¬A

2

∧ A

3

∧ ...))

5 / 173

(6)

Semantics of Boolean operators

Truth Table

α β ¬α α∧β α∨β α → β α ← β α ↔ β α⊕β

⊥ ⊥ > ⊥ ⊥ > > > ⊥

⊥ > > ⊥ > > ⊥ ⊥ >

> ⊥ ⊥ ⊥ > ⊥ > ⊥ >

> > ⊥ > > > > > ⊥

6 / 173

(7)

Semantics of Boolean operators (cont.)

Note

∧, ∨, ↔ and ⊕ are commutative:

(α ∧ β) ⇐⇒ (β ∧ α) (α ∨ β) ⇐⇒ (β ∨ α) (α ↔ β) ⇐⇒ (β ↔ α) (α ⊕ β) ⇐⇒ (β ⊕ α)

∧, ∨, ↔ and ⊕ are associative:

((α ∧ β) ∧ γ) ⇐⇒ (α ∧ (β ∧ γ)) ⇐⇒ (α ∧ β ∧ γ) ((α ∨ β) ∨ γ) ⇐⇒ (α ∨ (β ∨ γ)) ⇐⇒ (α ∨ β ∨ γ) ((α ↔ β) ↔ γ) ⇐⇒ (α ↔ (β ↔ γ)) ⇐⇒ (α ↔ β ↔ γ) ((α ⊕ β) ⊕ γ) ⇐⇒ (α ⊕ (β ⊕ γ)) ⇐⇒ (α ⊕ β ⊕ γ)

→, ← are neither commutative nor associative:

(α → β) ⇐⇒ (β → α) 6 ((α → β) → γ) ⇐⇒ (α → (β → γ)) 6

7 / 173

(8)

Remark: Semantics of Implication “→” (aka “⇒”, “⊃”)

The semantics of Implication “α → β” may be counter-intuitive

α → β: “the antecedent (aka premise) α implies the consequent (aka conclusion) β” (aka “if α holds, then β holds” (but not vice versa))

does not require causation or relevance between α and β ex: “5 is odd implies Tokyo is the capital of Japan” is true in p.l.

(under standard interpretation of “5”, “odd”, “Tokyo”, “Japan”) relation between antecedent & consequent: they are both true is true whenever its antecedent is false

ex: “5 is even implies Sam is smart” is true (regardless the smartness of Sam)

ex: “5 is even implies Tokyo is in Italy” is true (!)

relation between antecedent & consequent: the former is false does not require temporal precedence of α wrt. β

ex: “the grass is wet implies it must have rained” is true (the consequent precedes temporally the antecedent)

8 / 173

(9)

Remark: Semantics of Implication “→” (aka “⇒”, “⊃”)

The semantics of Implication “α → β” may be counter-intuitive

α → β: “the antecedent (aka premise) α implies the consequent (aka conclusion) β” (aka “if α holds, then β holds” (but not vice versa))

does not require causation or relevance between α and β ex: “5 is odd implies Tokyo is the capital of Japan” is true in p.l.

(under standard interpretation of “5”, “odd”, “Tokyo”, “Japan”) relation between antecedent & consequent: they are both true is true whenever its antecedent is false

ex: “5 is even implies Sam is smart” is true (regardless the smartness of Sam)

ex: “5 is even implies Tokyo is in Italy” is true (!)

relation between antecedent & consequent: the former is false does not require temporal precedence of α wrt. β

ex: “the grass is wet implies it must have rained” is true (the consequent precedes temporally the antecedent)

8 / 173

(10)

Remark: Semantics of Implication “→” (aka “⇒”, “⊃”)

The semantics of Implication “α → β” may be counter-intuitive

α → β: “the antecedent (aka premise) α implies the consequent (aka conclusion) β” (aka “if α holds, then β holds” (but not vice versa))

does not require causation or relevance between α and β ex: “5 is odd implies Tokyo is the capital of Japan” is true in p.l.

(under standard interpretation of “5”, “odd”, “Tokyo”, “Japan”) relation between antecedent & consequent: they are both true is true whenever its antecedent is false

ex: “5 is even implies Sam is smart” is true (regardless the smartness of Sam)

ex: “5 is even implies Tokyo is in Italy” is true (!)

relation between antecedent & consequent: the former is false does not require temporal precedence of α wrt. β

ex: “the grass is wet implies it must have rained” is true (the consequent precedes temporally the antecedent)

8 / 173

(11)

Remark: Semantics of Implication “→” (aka “⇒”, “⊃”)

The semantics of Implication “α → β” may be counter-intuitive

α → β: “the antecedent (aka premise) α implies the consequent (aka conclusion) β” (aka “if α holds, then β holds” (but not vice versa))

does not require causation or relevance between α and β ex: “5 is odd implies Tokyo is the capital of Japan” is true in p.l.

(under standard interpretation of “5”, “odd”, “Tokyo”, “Japan”) relation between antecedent & consequent: they are both true is true whenever its antecedent is false

ex: “5 is even implies Sam is smart” is true (regardless the smartness of Sam)

ex: “5 is even implies Tokyo is in Italy” is true (!)

relation between antecedent & consequent: the former is false does not require temporal precedence of α wrt. β

ex: “the grass is wet implies it must have rained” is true (the consequent precedes temporally the antecedent)

8 / 173

(12)

Syntactic Properties of Boolean Operators

¬¬α ⇐⇒ α

(α ∨ β) ⇐⇒ ¬(¬α ∧ ¬β)

¬(α ∨ β) ⇐⇒ (¬α ∧ ¬β) (α ∧ β) ⇐⇒ ¬(¬α ∨ ¬β)

¬(α ∧ β) ⇐⇒ (¬α ∨ ¬β) (α → β) ⇐⇒ (¬α ∨ β)

¬(α → β) ⇐⇒ (α ∧ ¬β) (α ← β) ⇐⇒ (α ∨ ¬β)

¬(α ← β) ⇐⇒ (¬α ∧ β)

(α ↔ β) ⇐⇒ ((α → β) ∧ (α ← β))

⇐⇒ ((¬α ∨ β) ∧ (α ∨ ¬β))

¬(α ↔ β) ⇐⇒ (¬α ↔ β)

⇐⇒ (α ↔ ¬β)

⇐⇒ ((α ∨ β) ∧ (¬α ∨ ¬β)) (α ⊕ β) ⇐⇒ ¬(α ↔ β)

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

9 / 173

(13)

Syntactic Properties of Boolean Operators

¬¬α ⇐⇒ α

(α ∨ β) ⇐⇒ ¬(¬α ∧ ¬β)

¬(α ∨ β) ⇐⇒ (¬α ∧ ¬β) (α ∧ β) ⇐⇒ ¬(¬α ∨ ¬β)

¬(α ∧ β) ⇐⇒ (¬α ∨ ¬β) (α → β) ⇐⇒ (¬α ∨ β)

¬(α → β) ⇐⇒ (α ∧ ¬β) (α ← β) ⇐⇒ (α ∨ ¬β)

¬(α ← β) ⇐⇒ (¬α ∧ β)

(α ↔ β) ⇐⇒ ((α → β) ∧ (α ← β))

⇐⇒ ((¬α ∨ β) ∧ (α ∨ ¬β))

¬(α ↔ β) ⇐⇒ (¬α ↔ β)

⇐⇒ (α ↔ ¬β)

⇐⇒ ((α ∨ β) ∧ (¬α ∨ ¬β)) (α ⊕ β) ⇐⇒ ¬(α ↔ β)

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

9 / 173

(14)

Exercises

1

For every pair of formulas α ⇐⇒ β below, show that α and β can be rewritten into each other by applying the syntactic properties of the previous slide

(A

1

∧ A

₂

) ∨ A

3

⇐⇒ (A

1

∨ A

₃

) ∧ (A

2

∨ A

₃

) (A

₁

∨ A

₂

) ∧ A

₃

⇐⇒ (A

₁

∧ A

₃

) ∨ (A

₂

∧ A

₃

)

A

₁

→ (A

₂

→ (A

₃

→ A

₄

)) ⇐⇒ (A

₁

∧ A

₂

∧ A

₃

) → A

₄

A

₁

→ (A

₂

∧ A

₃

) ⇐⇒ (A

₁

→ A

₂

) ∧ (A

₁

→ A

₃

) (A

₁

∨ A

₂

) → A

₃

⇐⇒ (A

₁

→ A

₃

) ∧ (A

₂

→ A

₃

) A

₁

⊕ A

₂

⇐⇒ (A

₁

∨ A

₂

) ∧ (¬A

₁

∨ ¬A

₂

)

¬A

₁

↔ ¬A

₂

⇐⇒ A

₁

↔ A

₂

A

₁

↔ A

₂

↔ A

₃

⇐⇒ A

₁

⊕ A

₂

⊕ A

₃

10 / 173

(15)

Tree & DAG Representations of Formulas

Formulas can be represented either as trees or as DAGS (Directed Acyclic Graphs)

DAG representation can be up to exponentially smaller in particular, when ↔’s are involved

(A

₁

↔ A

₂

) ↔ (A

₃

↔ A

₄

)

⇓

(((A

₁

↔ A

2

) → (A

₃

↔ A

4

))∧ ((A

₃

↔ A

₄

) → (A

₁

↔ A

₂

)))

⇓

(((A

₁

→ A

2

) ∧ (A

₂

→ A

1

)) → ((A

₃

→ A

4

) ∧ (A

₄

→ A

3

))) ∧ (((A

₃

→ A

4

) ∧ (A

₄

→ A

3

)) → (((A

₁

→ A

2

) ∧ (A

₂

→ A

1

))))

11 / 173

(16)

Tree & DAG Representations of Formulas

Formulas can be represented either as trees or as DAGS (Directed Acyclic Graphs)

DAG representation can be up to exponentially smaller in particular, when ↔’s are involved

(A

₁

↔ A

₂

) ↔ (A

₃

↔ A

₄

)

⇓

(((A

₁

↔ A

2

) → (A

₃

↔ A

4

))∧

((A

₃

↔ A

₄

) → (A

₁

↔ A

₂

)))

⇓

(((A

₁

→ A

2

) ∧ (A

₂

→ A

1

)) → ((A

₃

→ A

4

) ∧ (A

₄

→ A

3

))) ∧ (((A

₃

→ A

4

) ∧ (A

₄

→ A

3

)) → (((A

₁

→ A

2

) ∧ (A

₂

→ A

1

))))

11 / 173

(17)

Tree & DAG Representations of Formulas

Formulas can be represented either as trees or as DAGS (Directed Acyclic Graphs)

DAG representation can be up to exponentially smaller in particular, when ↔’s are involved

(A

₁

↔ A

₂

) ↔ (A

₃

↔ A

₄

)

⇓

(((A

₁

↔ A

2

) → (A

₃

↔ A

4

))∧

((A

₃

↔ A

₄

) → (A

₁

↔ A

₂

)))

⇓

(((A

₁

→ A

2

) ∧ (A

₂

→ A

1

)) → ((A

₃

→ A

4

) ∧ (A

₄

→ A

3

))) ∧ (((A

₃

→ A

₄

) ∧ (A

₄

→ A

₃

)) → (((A

₁

→ A

₂

) ∧ (A

₂

→ A

₁

))))

11 / 173

(18)

Tree & DAG Representations of Formulas: Example

(((A

₁

→ A

₂

) ∧ (A

₂

→ A

₁

)) → ((A

₃

→ A

₄

) ∧ (A

₄

→ A

₃

))) ∧ (((A

₃

→ A

4

) ∧ (A

₄

→ A

3

)) → (((A

₁

→ A

2

) ∧ (A

₂

→ A

1

))))

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

A1 A2 A3 A4

Tree Representation

DAG Representation

12 / 173

(19)

Semantics: Basic Definitions

Total truth assignment µ for ϕ:

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

represents a possible world or a possible state of the world Partial Truth assignment µ for ϕ:

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

represents 2

^k

total assignments, k is # unassigned variables Notation: set and formula representations of an assignment

µ can be represented as a set of literals:

EX: {µ(A

₁

) := >, µ(A

2

) := ⊥} =⇒ {A

1

, ¬A

2

} µ can be represented as a formula (cube):

EX: {µ(A

₁

) := >, µ(A

2

) := ⊥} =⇒ (A

1

∧ ¬A

₂

)

13 / 173

(20)

Semantics: Basic Definitions [cont.]

A total truth assignment µ satisfies ϕ (µ is a model of ϕ, µ |= ϕ):

µ |= A

_i

⇐⇒ µ(A

_i

) = >

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

µ |= α ∧ β ⇐⇒ µ |= α and µ |= β µ |= α ∨ β ⇐⇒ µ |= α or µ |= β µ |= α → β ⇐⇒ if µ |= α, then µ |= β µ |= α ↔ β ⇐⇒ µ |= α iff µ |= β µ |= α ⊕ β ⇐⇒ µ |= α iff not µ |= β

M(ϕ)

^def

= {µ | µ |= ϕ} (the set of models of ϕ) A partial truth assignment µ satisfies ϕ iff all total assignments extending µ satisfy ϕ

Ex: {A

₁

} |= (A

₁

∨ A

₂

))

because both {A

₁

, A

2

} |= (A

₁

∨ A

₂

) and {A

₁

, ¬A

2

} |= (A

₁

∨ A

₂

) ϕ is satisfiable iff µ |= ϕ for some µ (i.e. M(ϕ) 6= ∅)

α entails β (α |= β): α |= β iff µ |= α =⇒ µ |= β for all µs (i.e., M(α) ⊆ M(β))

ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ forall µs (i.e., µ ∈ M(ϕ) forall µs)

14 / 173

(21)

Semantics: Basic Definitions [cont.]

A total truth assignment µ satisfies ϕ (µ is a model of ϕ, µ |= ϕ):

µ |= A

_i

⇐⇒ µ(A

_i

) = >

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

µ |= α ∧ β ⇐⇒ µ |= α and µ |= β µ |= α ∨ β ⇐⇒ µ |= α or µ |= β µ |= α → β ⇐⇒ if µ |= α, then µ |= β µ |= α ↔ β ⇐⇒ µ |= α iff µ |= β µ |= α ⊕ β ⇐⇒ µ |= α iff not µ |= β

M(ϕ)

^def

= {µ | µ |= ϕ} (the set of models of ϕ) A partial truth assignment µ satisfies ϕ iff all total assignments extending µ satisfy ϕ

Ex: {A

₁

} |= (A

₁

∨ A

₂

))

because both {A

₁

, A

2

} |= (A

₁

∨ A

₂

) and {A

₁

, ¬A

2

} |= (A

₁

∨ A

₂

) ϕ is satisfiable iff µ |= ϕ for some µ (i.e. M(ϕ) 6= ∅)

α entails β (α |= β): α |= β iff µ |= α =⇒ µ |= β for all µs (i.e., M(α) ⊆ M(β))

ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ forall µs (i.e., µ ∈ M(ϕ) forall µs)

14 / 173

(22)

Semantics: Basic Definitions [cont.]

A total truth assignment µ satisfies ϕ (µ is a model of ϕ, µ |= ϕ):

µ |= A

_i

⇐⇒ µ(A

_i

) = >

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

µ |= α ∧ β ⇐⇒ µ |= α and µ |= β µ |= α ∨ β ⇐⇒ µ |= α or µ |= β µ |= α → β ⇐⇒ if µ |= α, then µ |= β µ |= α ↔ β ⇐⇒ µ |= α iff µ |= β µ |= α ⊕ β ⇐⇒ µ |= α iff not µ |= β

M(ϕ)

^def

= {µ | µ |= ϕ} (the set of models of ϕ) A partial truth assignment µ satisfies ϕ iff all total assignments extending µ satisfy ϕ

Ex: {A

₁

} |= (A

₁

∨ A

₂

))

because both {A

₁

, A

2

} |= (A

₁

∨ A

₂

) and {A

₁

, ¬A

2

} |= (A

₁

∨ A

₂

) ϕ is satisfiable iff µ |= ϕ for some µ (i.e. M(ϕ) 6= ∅)

α entails β (α |= β): α |= β iff µ |= α =⇒ µ |= β for all µs (i.e., M(α) ⊆ M(β))

ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ forall µs (i.e., µ ∈ M(ϕ) forall µs)

14 / 173

(23)

Semantics: Basic Definitions [cont.]

A total truth assignment µ satisfies ϕ (µ is a model of ϕ, µ |= ϕ):

µ |= A

_i

⇐⇒ µ(A

_i

) = >

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

µ |= α ∧ β ⇐⇒ µ |= α and µ |= β µ |= α ∨ β ⇐⇒ µ |= α or µ |= β µ |= α → β ⇐⇒ if µ |= α, then µ |= β µ |= α ↔ β ⇐⇒ µ |= α iff µ |= β µ |= α ⊕ β ⇐⇒ µ |= α iff not µ |= β

M(ϕ)

^def

= {µ | µ |= ϕ} (the set of models of ϕ) A partial truth assignment µ satisfies ϕ iff all total assignments extending µ satisfy ϕ

Ex: {A

₁

} |= (A

₁

∨ A

₂

))

because both {A

₁

, A

2

} |= (A

₁

∨ A

₂

) and {A

₁

, ¬A

2

} |= (A

₁

∨ A

₂

) ϕ is satisfiable iff µ |= ϕ for some µ (i.e. M(ϕ) 6= ∅)

α entails β (α |= β): α |= β iff µ |= α =⇒ µ |= β for all µs (i.e., M(α) ⊆ M(β))

ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ forall µs (i.e., µ ∈ M(ϕ) forall µs)

14 / 173

(24)

Semantics: Basic Definitions [cont.]

A total truth assignment µ satisfies ϕ (µ is a model of ϕ, µ |= ϕ):

µ |= A

_i

⇐⇒ µ(A

_i

) = >

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

µ |= α ∧ β ⇐⇒ µ |= α and µ |= β µ |= α ∨ β ⇐⇒ µ |= α or µ |= β µ |= α → β ⇐⇒ if µ |= α, then µ |= β µ |= α ↔ β ⇐⇒ µ |= α iff µ |= β µ |= α ⊕ β ⇐⇒ µ |= α iff not µ |= β

M(ϕ)

^def

= {µ | µ |= ϕ} (the set of models of ϕ) A partial truth assignment µ satisfies ϕ iff all total assignments extending µ satisfy ϕ

Ex: {A

₁

} |= (A

₁

∨ A

₂

))

because both {A

₁

, A

2

} |= (A

₁

∨ A

₂

) and {A

₁

, ¬A

2

} |= (A

₁

∨ A

₂

) ϕ is satisfiable iff µ |= ϕ for some µ (i.e. M(ϕ) 6= ∅)

α entails β (α |= β): α |= β iff µ |= α =⇒ µ |= β for all µs (i.e., M(α) ⊆ M(β))

ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ forall µs (i.e., µ ∈ M(ϕ) forall µs)

14 / 173

(25)

Properties & Results

Property

ϕ is valid iff ¬ϕ is not satisfiable Deduction Theorem

α |= β iff α → β is valid (|= α → β)

Corollary

α |= β iff α ∧ ¬β is not satisfiable

Validity and entailment checking can be straightforwardly reduced to (un)satisfiability checking!

15 / 173

(26)

Properties & Results

Property

ϕ is valid iff ¬ϕ is not satisfiable Deduction Theorem

α |= β iff α → β is valid (|= α → β) Corollary

α |= β iff α ∧ ¬β is not satisfiable

Validity and entailment checking can be straightforwardly reduced to (un)satisfiability checking!

15 / 173

(27)

Properties & Results

Property

ϕ is valid iff ¬ϕ is not satisfiable Deduction Theorem

α |= β iff α → β is valid (|= α → β) Corollary

α |= β iff α ∧ ¬β is not satisfiable

Validity and entailment checking can be straightforwardly reduced to (un)satisfiability checking!

15 / 173

(28)

Properties & Results

Property

ϕ is valid iff ¬ϕ is not satisfiable Deduction Theorem

α |= β iff α → β is valid (|= α → β) Corollary

α |= β iff α ∧ ¬β is not satisfiable

Validity and entailment checking can be straightforwardly reduced to (un)satisfiability checking!

15 / 173

(29)

Equivalence and Equi-Satisfiability

α and β are equivalent iff, for every µ, µ |= α iff µ |= β (i.e., if M(α) = M(β)) α and β are equi-satisfiable iff

exists µ

₁

s.t. µ

₁

|= α iff exists µ

₂

s.t. µ

₂

|= β (i.e., if M(α) 6= ∅ iff M(β) 6= ∅)

α, β equivalent

⇓ 6⇑

α, β equi-satisfiable

EX: A

₁

∨ A

₂

and (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

) are equi-satisfiable, not equivalent.

{¬A

1

, A

₂

, A

₃

} |= (A

1

∨ A

2

), but

{¬A

₁

, A

₂

, A

₃

} 6|= (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

)

Typically used when β is the result of applying some transformation T to α: β

^def

= T (α):

T is validity-preserving [resp. satisfiability-preserving] iff T (α) and α are equivalent [resp. equi-satisfiable]

16 / 173

(30)

Equivalence and Equi-Satisfiability

α and β are equivalent iff, for every µ, µ |= α iff µ |= β (i.e., if M(α) = M(β)) α and β are equi-satisfiable iff

exists µ

₁

s.t. µ

₁

|= α iff exists µ

₂

s.t. µ

₂

|= β (i.e., if M(α) 6= ∅ iff M(β) 6= ∅)

α, β equivalent

⇓ 6⇑

α, β equi-satisfiable

EX: A

₁

∨ A

₂

and (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

) are equi-satisfiable, not equivalent.

{¬A

1

, A

₂

, A

₃

} |= (A

1

∨ A

2

), but

{¬A

₁

, A

₂

, A

₃

} 6|= (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

)

Typically used when β is the result of applying some transformation T to α: β

^def

= T (α):

T is validity-preserving [resp. satisfiability-preserving] iff T (α) and α are equivalent [resp. equi-satisfiable]

16 / 173

(31)

Equivalence and Equi-Satisfiability

α and β are equivalent iff, for every µ, µ |= α iff µ |= β (i.e., if M(α) = M(β)) α and β are equi-satisfiable iff

exists µ

₁

s.t. µ

₁

|= α iff exists µ

₂

s.t. µ

₂

|= β (i.e., if M(α) 6= ∅ iff M(β) 6= ∅)

α, β equivalent

⇓ 6⇑

α, β equi-satisfiable

EX: A

₁

∨ A

₂

and (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

) are equi-satisfiable, not equivalent.

{¬A

1

, A

₂

, A

₃

} |= (A

1

∨ A

2

), but

{¬A

₁

, A

₂

, A

₃

} 6|= (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

)

Typically used when β is the result of applying some transformation T to α: β

^def

= T (α):

T is validity-preserving [resp. satisfiability-preserving] iff T (α) and α are equivalent [resp. equi-satisfiable]

16 / 173

(32)

Equivalence and Equi-Satisfiability

α and β are equivalent iff, for every µ, µ |= α iff µ |= β (i.e., if M(α) = M(β)) α and β are equi-satisfiable iff

exists µ

₁

s.t. µ

₁

|= α iff exists µ

₂

s.t. µ

₂

|= β (i.e., if M(α) 6= ∅ iff M(β) 6= ∅)

α, β equivalent

⇓ 6⇑

α, β equi-satisfiable

EX: A

₁

∨ A

₂

and (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

) are equi-satisfiable, not equivalent.

{¬A

1

, A

₂

, A

₃

} |= (A

1

∨ A

2

), but

{¬A

₁

, A

₂

, A

₃

} 6|= (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

)

Typically used when β is the result of applying some transformation T to α: β

^def

= T (α):

T is validity-preserving [resp. satisfiability-preserving] iff T (α) and α are equivalent [resp. equi-satisfiable]

16 / 173

(33)

Equivalence and Equi-Satisfiability

α and β are equivalent iff, for every µ, µ |= α iff µ |= β (i.e., if M(α) = M(β)) α and β are equi-satisfiable iff

exists µ

₁

s.t. µ

₁

|= α iff exists µ

₂

s.t. µ

₂

|= β (i.e., if M(α) 6= ∅ iff M(β) 6= ∅)

α, β equivalent

⇓ 6⇑

α, β equi-satisfiable

EX: A

₁

∨ A

₂

and (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

) are equi-satisfiable, not equivalent.

{¬A

1

, A

₂

, A

₃

} |= (A

1

∨ A

2

), but

{¬A

₁

, A

₂

, A

₃

} 6|= (A

₁

∨ ¬A

₃

) ∧ (A

₃

∨ A

₂

)

Typically used when β is the result of applying some transformation T to α: β

^def

= T (α):

T is validity-preserving [resp. satisfiability-preserving] iff T (α) and α are equivalent [resp. equi-satisfiable]

16 / 173

(34)

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 is NP-complete

=⇒ The most important logical problems (validity, inference,

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

⇓

No existing worst-case-polynomial algorithm.

17 / 173

(35)

POLARITY of subformulas

Polarity: the number of nested negations modulo 2.

Positive/negative occurrences ϕ occurs positively in ϕ;

if ¬ϕ

1

occurs positively [negatively] in ϕ, then ϕ

1

occurs negatively [positively] in ϕ

if ϕ

1

∧ ϕ

₂

or ϕ

1

∨ ϕ

₂

occur positively [negatively] in ϕ, then ϕ

1

and ϕ

2

occur positively [negatively] in ϕ;

if ϕ

1

→ ϕ

₂

occurs positively [negatively] in ϕ,

then ϕ

1

occurs negatively [positively] in ϕ and ϕ

2

occurs positively [negatively] in ϕ;

if ϕ

₁

↔ ϕ

₂

or ϕ

₁

⊕ ϕ

₂

occurs in ϕ,

then ϕ

₁

and ϕ

₂

occur positively and negatively in ϕ;

18 / 173

(36)

Negative Normal Form (NNF)

ϕ is in Negative normal form iff it is given only by the recursive applications of ∧, ∨ to literals.

every ϕ can be reduced into NNF:

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

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

The reduction is linear if a DAG representation is used.

Preserves the equivalence of formulas.

19 / 173

(37)

Negative Normal Form (NNF)

ϕ is in Negative normal form iff it is given only by the recursive applications of ∧, ∨ to literals.

every ϕ can be reduced into NNF:

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

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

The reduction is linear if a DAG representation is used.

Preserves the equivalence of formulas.

19 / 173

(38)

Negative Normal Form (NNF)

ϕ is in Negative normal form iff it is given only by the recursive applications of ∧, ∨ to literals.

every ϕ can be reduced into NNF:

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

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

The reduction is linear if a DAG representation is used.

Preserves the equivalence of formulas.

19 / 173

(39)

Negative Normal Form (NNF)

ϕ is in Negative normal form iff it is given only by the recursive applications of ∧, ∨ to literals.

every ϕ can be reduced into NNF:

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

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

The reduction is linear if a DAG representation is used.

Preserves the equivalence of formulas.

19 / 173

(40)

NNF: Example

(A

₁

↔ A

₂

) ↔ (A

₃

↔ A

₄

)

⇓

((((A

₁

→ A

₂

) ∧ (A

₁

← A

₂

)) → ((A

₃

→ A

₄

) ∧ (A

₃

← A

₄

)))∧ (((A

₁

→ A

₂

) ∧ (A

₁

← A

₂

)) ← ((A

₃

→ A

₄

) ∧ (A

₃

← A

₄

))))

⇓

((¬((¬A

₁

∨ A

2

) ∧ (A

₁

∨ ¬A

2

)) ∨ ((¬A

₃

∨ A

4

) ∧ (A

₃

∨ ¬A

4

)))∧ (((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ¬((¬A

₃

∨ A

₄

) ∧ (A

₃

∨ ¬A

₄

))))

⇓

((((A

₁

∧ ¬A

2

) ∨ (¬A

₁

∧ A

2

)) ∨ ((¬A

₃

∨ A

4

) ∧ (A

₃

∨ ¬A

4

)))∧ (((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ((A

₃

∧ ¬A

₄

) ∨ (¬A

₃

∧ A

₄

))))

20 / 173

(41)

NNF: Example

(A

₁

↔ A

₂

) ↔ (A

₃

↔ A

₄

)

⇓

((((A

₁

→ A

₂

) ∧ (A

₁

← A

₂

)) → ((A

₃

→ A

₄

) ∧ (A

₃

← A

₄

)))∧

(((A

₁

→ A

₂

) ∧ (A

₁

← A

₂

)) ← ((A

₃

→ A

₄

) ∧ (A

₃

← A

₄

))))

⇓

((¬((¬A

₁

∨ A

2

) ∧ (A

₁

∨ ¬A

2

)) ∨ ((¬A

₃

∨ A

4

) ∧ (A

₃

∨ ¬A

4

)))∧ (((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ¬((¬A

₃

∨ A

₄

) ∧ (A

₃

∨ ¬A

₄

))))

⇓

((((A

₁

∧ ¬A

2

) ∨ (¬A

₁

∧ A

2

)) ∨ ((¬A

₃

∨ A

4

) ∧ (A

₃

∨ ¬A

4

)))∧ (((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ((A

₃

∧ ¬A

₄

) ∨ (¬A

₃

∧ A

₄

))))

20 / 173

(42)

NNF: Example

(A

₁

↔ A

₂

) ↔ (A

₃

↔ A

₄

)

⇓

((((A

₁

→ A

₂

) ∧ (A

₁

← A

₂

)) → ((A

₃

→ A

₄

) ∧ (A

₃

← A

₄

)))∧

(((A

₁

→ A

₂

) ∧ (A

₁

← A

₂

)) ← ((A

₃

→ A

₄

) ∧ (A

₃

← A

₄

))))

⇓

((¬((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ((¬A

₃

∨ A

₄

) ∧ (A

₃

∨ ¬A

₄

)))∧

(((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ¬((¬A

₃

∨ A

₄

) ∧ (A

₃

∨ ¬A

₄

))))

⇓

((((A

₁

∧ ¬A

2

) ∨ (¬A

₁

∧ A

2

)) ∨ ((¬A

₃

∨ A

4

) ∧ (A

₃

∨ ¬A

4

)))∧ (((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ((A

₃

∧ ¬A

₄

) ∨ (¬A

₃

∧ A

₄

))))

20 / 173

(43)

NNF: Example

(A

₁

↔ A

₂

) ↔ (A

₃

↔ A

₄

)

⇓

((((A

₁

→ A

₂

) ∧ (A

₁

← A

₂

)) → ((A

₃

→ A

₄

) ∧ (A

₃

← A

₄

)))∧

(((A

₁

→ A

₂

) ∧ (A

₁

← A

₂

)) ← ((A

₃

→ A

₄

) ∧ (A

₃

← A

₄

))))

⇓

((¬((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ((¬A

₃

∨ A

₄

) ∧ (A

₃

∨ ¬A

₄

)))∧

(((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ¬((¬A

₃

∨ A

₄

) ∧ (A

₃

∨ ¬A

₄

))))

⇓

((((A

₁

∧ ¬A

2

) ∨ (¬A

₁

∧ A

2

)) ∨ ((¬A

₃

∨ A

4

) ∧ (A

₃

∨ ¬A

4

)))∧

(((¬A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

)) ∨ ((A

₃

∧ ¬A

₄

) ∨ (¬A

₃

∧ A

₄

))))

20 / 173

(44)

NNF: Example [cont.]

Note

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

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

21 / 173

(45)

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,...

22 / 173

(46)

Conjunctive Normal Form (CNF)

ϕ is in Conjunctive normal form iff it is a conjunction of disjunctions of literals:

L

^

i=1 Ki

_

j_i=1

l

_j_i

the disjunctions of literals W

K_i

ji=1

l

_j_i

are called clauses Easier to handle: list of lists of literals.

=⇒ no reasoning on the recursive structure of the formula

23 / 173

(47)

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNF by, e.g., (i) expanding implications and equivalences:

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

(iii) applying recursively the DeMorgan’s Rule:

(α ∧ β) ∨ γ =⇒ (α ∨ γ) ∧ (β ∨ γ) Resulting formula worst-case exponential:

ex: ||CNF( W

N

i=1

(l

i1

∧ l

_i2

)|| =

||(l

₁₁

∨l

₂₁

∨...∨l

_N1

)∧(l

12

∨l

₂₁

∨...∨l

_N1

)∧...∧(l

12

∨l

₂₂

∨...∨l

_N2

)|| = 2

^N

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

CNF (ϕ) is equivalent to ϕ.

Rarely used in practice.

24 / 173

(48)

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNF by, e.g., (i) expanding implications and equivalences:

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

(iii) applying recursively the DeMorgan’s Rule:

(α ∧ β) ∨ γ =⇒ (α ∨ γ) ∧ (β ∨ γ) Resulting formula worst-case exponential:

ex: ||CNF( W

N

i=1

(l

i1

∧ l

_i2

)|| =

||(l

₁₁

∨l

₂₁

∨...∨l

_N1

)∧(l

12

∨l

₂₁

∨...∨l

_N1

)∧...∧(l

12

∨l

₂₂

∨...∨l

_N2

)|| = 2

^N

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

CNF (ϕ) is equivalent to ϕ.

Rarely used in practice.

24 / 173

(49)

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNF by, e.g., (i) expanding implications and equivalences:

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

(iii) applying recursively the DeMorgan’s Rule:

(α ∧ β) ∨ γ =⇒ (α ∨ γ) ∧ (β ∨ γ) Resulting formula worst-case exponential:

ex: ||CNF( W

N

i=1

(l

i1

∧ l

_i2

)|| =

||(l

₁₁

∨l

₂₁

∨...∨l

_N1

)∧(l

12

∨l

₂₁

∨...∨l

_N1

)∧...∧(l

12

∨l

₂₂

∨...∨l

_N2

)|| = 2

^N

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

CNF (ϕ) is equivalent to ϕ.

Rarely used in practice.

24 / 173

(50)

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNF by, e.g., (i) expanding implications and equivalences:

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

(iii) applying recursively the DeMorgan’s Rule:

(α ∧ β) ∨ γ =⇒ (α ∨ γ) ∧ (β ∨ γ) Resulting formula worst-case exponential:

ex: ||CNF( W

N

i=1

(l

i1

∧ l

_i2

)|| =

||(l

₁₁

∨l

₂₁

∨...∨l

_N1

)∧(l

12

∨l

₂₁

∨...∨l

_N1

)∧...∧(l

12

∨l

₂₂

∨...∨l

_N2

)|| = 2

^N

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

CNF (ϕ) is equivalent to ϕ.

Rarely used in practice.

24 / 173

(51)

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNF by, e.g., (i) expanding implications and equivalences:

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

(iii) applying recursively the DeMorgan’s Rule:

(α ∧ β) ∨ γ =⇒ (α ∨ γ) ∧ (β ∨ γ) Resulting formula worst-case exponential:

ex: ||CNF( W

N

i=1

(l

i1

∧ l

_i2

)|| =

||(l

₁₁

∨l

₂₁

∨...∨l

_N1

)∧(l

12

∨l

₂₁

∨...∨l

_N1

)∧...∧(l

12

∨l

₂₂

∨...∨l

_N2

)|| = 2

^N

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

CNF (ϕ) is equivalent to ϕ.

Rarely used in practice.

24 / 173

(52)

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNF by, e.g., (i) expanding implications and equivalences:

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

(iii) applying recursively the DeMorgan’s Rule:

(α ∧ β) ∨ γ =⇒ (α ∨ γ) ∧ (β ∨ γ) Resulting formula worst-case exponential:

ex: ||CNF( W

N

i=1

(l

i1

∧ l

_i2

)|| =

||(l

₁₁

∨l

₂₁

∨...∨l

_N1

)∧(l

12

∨l

₂₁

∨...∨l

_N1

)∧...∧(l

12

∨l

₂₂

∨...∨l

_N2

)|| = 2

^N

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

CNF (ϕ) is equivalent to ϕ.

Rarely used in practice.

24 / 173

(53)

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNF by, e.g., (i) expanding implications and equivalences:

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

(iii) applying recursively the DeMorgan’s Rule:

(α ∧ β) ∨ γ =⇒ (α ∨ γ) ∧ (β ∨ γ) Resulting formula worst-case exponential:

ex: ||CNF( W

N

i=1

(l

i1

∧ l

_i2

)|| =

||(l

₁₁

∨l

₂₁

∨...∨l

_N1

)∧(l

12

∨l

₂₁

∨...∨l

_N1

)∧...∧(l

12

∨l

₂₂

∨...∨l

_N2

)|| = 2

^N

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

CNF (ϕ) is equivalent to ϕ.

Rarely used in practice.

24 / 173

(54)

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNF by, e.g., (i) expanding implications and equivalences:

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

(iii) applying recursively the DeMorgan’s Rule:

(α ∧ β) ∨ γ =⇒ (α ∨ γ) ∧ (β ∨ γ) Resulting formula worst-case exponential:

ex: ||CNF( W

N

i=1

(l

i1

∧ l

_i2

)|| =

||(l

₁₁

∨l

₂₁

∨...∨l

_N1

)∧(l

12

∨l

₂₁

∨...∨l

_N1

)∧...∧(l

12

∨l

₂₂

∨...∨l

_N2

)|| = 2

^N

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

CNF (ϕ) is equivalent to ϕ.

Rarely used in practice.

24 / 173

(55)

Labeling CNF conversion CNF _label (ϕ)

Labeling CNF conversion CNF

_label

(ϕ) (aka Tseitin’s CNF-ization) Every ϕ can be reduced into CNF by, 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

↔ l

_j

)|B] ∧ CNF (B ↔ (l

_i

↔ l

_j

)) l

_i

, l

_j

being literals and B being a “new” variable.

Worst-case linear!

Atoms(CNF

_label

(ϕ)) ⊇ Atoms(ϕ)

CNF

_label

(ϕ) is equi-satisfiable (but not equivalent) to ϕ.

Much more used than classic conversion in practice.

25 / 173

(56)

Labeling CNF conversion CNF _label (ϕ)

Labeling CNF conversion CNF

_label

(ϕ) (aka Tseitin’s CNF-ization) Every ϕ can be reduced into CNF by, 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

↔ l

_j

)|B] ∧ CNF (B ↔ (l

_i

↔ l

_j

)) l

_i

, l

_j

being literals and B being a “new” variable.

Worst-case linear!

Atoms(CNF

_label

(ϕ)) ⊇ Atoms(ϕ)

CNF

_label

(ϕ) is equi-satisfiable (but not equivalent) to ϕ.

Much more used than classic conversion in practice.

25 / 173

(57)

Labeling CNF conversion CNF _label (ϕ) (cont.)

CNF (B ↔ (l

_i

∨ l

_j

)) ⇐⇒ (¬B ∨ l

_i

∨ l

_j

)∧

(B ∨ ¬l

_i

)∧

(B ∨ ¬l

_j

) CNF (B ↔ (l

_i

∧ l

j

)) ⇐⇒ (¬B ∨ l

i

)∧

(¬B ∨ l

_j

)∧

(B ∨ ¬l

_i

¬l

_j

) CNF (B ↔ (l

_i

↔ l

_j

)) ⇐⇒ (¬B ∨ ¬l

_i

∨ l

_j

)∧

(¬B ∨ l

_i

∨ ¬l

_j

)∧

(B ∨ l

_i

∨ l

j

)∧

(B ∨ ¬l

_i

∨ ¬l

_j

)

26 / 173

(58)

Labeling CNF Conversion CNF _label – 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 (B

1

↔ (¬A

3

∨ A

1

))∧

...∧

CNF (B

8

↔ (A

1

∨ ¬A

4

))∧

CNF (B

9

↔ (B

1

↔ B

2

))∧

...∧

CNF (B

12

↔ (B

7

∧ B

8

))∧

CNF (B

13

↔ (B

9

∨ B

10

))∧

CNF (B

14

↔ (B

11

∨ B

12

))∧

CNF (B

15

↔ (B

13

∧ B

14

))∧

B

15

=

(¬B

1

∨ ¬A

3

∨ A

1

) ∧ (B

1

∨ A

3

) ∧ (B

1

∨ ¬A

1

)∧

...∧

(¬B

8

∨ A

1

∨ ¬A

4

) ∧ (B

8

∨ ¬A

1

) ∧ (B

8

∨ A

4

)∧

(¬B

9

∨ ¬B

1

∨ B

2

) ∧ (¬B

9

∨ B

1

∨ ¬B

2

)∧

(B

9

∨ B

1

∨ B

2

) ∧ (B

9

∨ ¬B

1

∨ ¬B

2

)∧

...∧

(B

12

∨ ¬B

7

∨ ¬B

8

) ∧ (¬B

12

∨ B

7

) ∧ (¬B

12

∨ B

8

)∧

(¬B

13

∨ B

9

∨ B

10

) ∧ (B

13

∨ ¬B

9

) ∧ (B

13

∨ ¬B

10

)∧

(¬B

14

∨ B

11

∨ B

12

) ∧ (B

14

∨ ¬B

11

) ∧ (B

14

∨ ¬B

12

)∧

(B

15

∨ ¬B

13

∨ ¬B

14

) ∧ (¬B

15

∨ B

13

) ∧ (¬B

15

∨ B

14

)∧

B

15

27 / 173

(59)

Labeling CNF conversion CNF _label (improved)

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

∧ 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

↔ 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.

Smaller in size:

CNF (B → (l

_i

∨ l

j

)) = (¬B ∨ l

_i

∨ l

j

)

CNF (((l

_i

∨ l

_j

) → B)) = (¬l

_i

∨ B) ∧ (¬l

_j

∨ B)

28 / 173

(60)

Labeling CNF conversion CNF _label (improved)

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

∧ 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

↔ 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.

Smaller in size:

CNF (B → (l

_i

∨ l

j

)) = (¬B ∨ l

_i

∨ l

j

)

CNF (((l

_i

∨ l

_j

) → B)) = (¬l

_i

∨ B) ∧ (¬l

_j

∨ B)

28 / 173

(61)

Labeling CNF conversion CNF _label (ϕ) (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

∧ l

_j

)) ⇐⇒ (¬B ∨ l

_i

)∧

(¬B ∨ l

_j

) CNF (B ← (l

_i

∧ l

j

)) ⇐⇒ (B ∨ ¬l

i

¬l

j

) CNF (B → (l

_i

↔ l

j

)) ⇐⇒ (¬B ∨ ¬l

i

∨ l

j

)∧

(¬B ∨ l

_i

∨ ¬l

_j

) CNF (B ← (l

_i

↔ l

_j

)) ⇐⇒ (B ∨ l

_i

∨ l

_j

)∧

(B ∨ ¬l

_i

∨ ¬l

_j

)

29 / 173

(62)

Labeling CNF conversion CNF _label – 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 (B

1

↔ (¬A

3

∨ A

1

)) ∧

... ∧

CNF (B

8

→ (A

1

∨ ¬A

4

)) ∧ CNF (B

9

→ (B

1

↔ B

2

)) ∧

... ∧

CNF (B

12

→ (B

7

∧ B

8

)) ∧ CNF (B

13

→ (B

9

∨ B

10

)) ∧ CNF (B

14

→ (B

11

∨ B

12

)) ∧ CNF (B

15

→ (B

13

∧ B

14

)) ∧ B

15

30 / 173

(63)

Labeling CNF conversion CNF _label – 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

(ϕ

1

∧(A → (B∧C))) =⇒ CNF

label

(ϕ

1

)∧(¬A∨B)∧(¬A∨C) exploit the associativity of ∧’s and ∨’s:

... (A

₁

∨ (A

₂

∨ A

₃

))

| {z }

B

... =⇒ ...CNF (B ↔ (A

₁

∨ A

₂

∨ A

₃

))...

before applying CNF

_label

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

...

31 / 173

(64)

Exercises

1

Consider the following Boolean formula ϕ:

¬(((¬A

1

→ A

₂

) ∧ (¬A

₃

→ A

₄

)) ∨ (( A

₅

→ A

₆

) ∧ ( A

₇

→ ¬A

8

))) Compute the Negative Normal Form of ϕ

2

Consider the following Boolean formula ϕ:

((¬A

₁

∧ A

₂

) ∨ ( A

₇

∧ A

₄

) ∨ (¬A

₃

∧ ¬A

₂

) ∨ ( A

₅

∧ ¬A

₄

))

1

Produce the CNF formula CNF (ϕ).

2

Produce the CNF formula CNF

label

(ϕ).

3

Produce the CNF formula CNF

label

(ϕ) (improved version)

32 / 173

(65)

Outline

1

Boolean Logics and SAT

2

Basic SAT-Solving Techniques Resolution

Tableaux DPLL

Stochastic Local Search for SAT

3

Ordered Binary Decision Diagrams – OBDDs

4

Modern CDCL SAT Solvers

Limitations of Chronological Backtracking Conflict-Driven Clause-Learning SAT solvers Further Improvements

SAT Under Assumptions & Incremental SAT

5

SAT Functionalities: proofs, unsat cores, interpolants, optimization

33 / 173

(66)

Propositional Reasoning: Generalities

Automated Reasoning in Propositional Logic fundamental task AI, formal verification, circuit synthesis, operational research,....

Important in AI: KB |= α: entail fact α from knowledge base KR (aka Model Checking: M(KB) ⊆ M(α))

typically KB >> α

All propositional reasoning tasks reduced to satisfiability (SAT) KR |= α =⇒ SAT(KR ∧ ¬α)=false

input formula CNF-ized and fed to a SAT solver Current SAT solvers dramatically efficient:

handle industrial problems with 10

⁶

− 10

⁷

variables & clauses!

used as backend engines in a variety of systems

34 / 173

(67)

Propositional Reasoning: Generalities

Automated Reasoning in Propositional Logic fundamental task AI, formal verification, circuit synthesis, operational research,....

Important in AI: KB |= α: entail fact α from knowledge base KR (aka Model Checking: M(KB) ⊆ M(α))

typically KB >> α

All propositional reasoning tasks reduced to satisfiability (SAT) KR |= α =⇒ SAT(KR ∧ ¬α)=false

input formula CNF-ized and fed to a SAT solver Current SAT solvers dramatically efficient:

handle industrial problems with 10

⁶

− 10

⁷

variables & clauses!

used as backend engines in a variety of systems

34 / 173