Course “An Introduction to SAT and SMT”
Chapter 1: Propositional Satisfiability (SAT)
Roberto Sebastiani
DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it URL: http://disi.unitn.it/rseba/DIDATTICA/SAT_SMT2020/
Int. Graduate School on ICT, University of Trento, Academic year 2019-2020
last update: Friday 22ndMay, 2020
Copyright notice: some material contained in these slides is courtesy of Alessandro Cimatti, Alberto Griggio and Marco Roveri, who detain its copyright. All the other material is copyrighted by Roberto Sebastiani. Any 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 Basics on SAT
2 Basic SAT-Solving techniques
3 Modern CDCL SAT Solvers
Conflict-Driven Clause-Learning SAT solvers Further Improvements
4 Tractable subclasses of SAT
5 Random k-SAT and Phase Transition
6 Advanced Functionalities: proofs, unsat cores, interpolants, optimization
7 Some Applications
Appl. #1: (Bounded) Planning
Appl. #2: Bounded Model Checking
Outline
1 Basics on SAT
2 Basic SAT-Solving techniques
3 Modern CDCL SAT Solvers
Conflict-Driven Clause-Learning SAT solvers Further Improvements
4 Tractable subclasses of SAT
5 Random k-SAT and Phase Transition
6 Advanced Functionalities: proofs, unsat cores, interpolants, optimization
7 Some Applications
Appl. #1: (Bounded) Planning
Appl. #2: Bounded Model Checking
Boolean logic
Basic notation & definitions
Boolean formula
>, ⊥ are formulas
A propositional atom A
1, A
2, A
3, ... is a formula;
if ϕ
1and ϕ
2are formulas, then
¬ϕ
1, ϕ
1∧ ϕ
2, ϕ
1∨ ϕ
2, ϕ
1→ ϕ
2, ϕ
1← ϕ
2, ϕ
1↔ ϕ
2are formulas.
Atoms(ϕ): the set {A 1 , ..., 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
iClause: a disjunction of literals W
j l j (e.g., (A 1 ∨ ¬A 2 ∨ A 3 ∨ ...)) Cube: a conjunction of literals V
j l j (e.g., (A 1 ∧ ¬A 2 ∧ A 3 ∧ ...))
Semantics of Boolean operators
Truth table:
ϕ 1 ϕ 2 ¬ϕ 1 ϕ 1 ∧ ϕ 2 ϕ 1 ∨ ϕ 2 ϕ 1 → ϕ 2 ϕ 1 ← ϕ 2 ϕ 1 ↔ ϕ 2
⊥ ⊥ > ⊥ ⊥ > > >
⊥ > > ⊥ > > ⊥ ⊥
> ⊥ ⊥ ⊥ > ⊥ > ⊥
> > ⊥ > > > > >
Note
∧, ∨ and ↔ are commutative:
(ϕ 1 ∧ ϕ 2 ) ⇐⇒ (ϕ 2 ∧ ϕ 1 ) (ϕ 1 ∨ ϕ 2 ) ⇐⇒ (ϕ 2 ∨ ϕ 1 ) (ϕ 1 ↔ ϕ 2 ) ⇐⇒ (ϕ 2 ↔ ϕ 1 )
∧ and ∨ are associative:
((ϕ 1 ∧ ϕ 2 ) ∧ ϕ 3 ) ⇐⇒ (ϕ 1 ∧ (ϕ 2 ∧ ϕ 3 )) ⇐⇒ (ϕ 1 ∧ ϕ 2 ∧ ϕ 3 )
((ϕ 1 ∨ ϕ 2 ) ∨ ϕ 3 ) ⇐⇒ (ϕ 1 ∨ (ϕ 2 ∨ ϕ 3 )) ⇐⇒ (ϕ 1 ∨ ϕ 2 ∨ ϕ 3 )
Semantics of Boolean operators
Truth table:
ϕ 1 ϕ 2 ¬ϕ 1 ϕ 1 ∧ ϕ 2 ϕ 1 ∨ ϕ 2 ϕ 1 → ϕ 2 ϕ 1 ← ϕ 2 ϕ 1 ↔ ϕ 2
⊥ ⊥ > ⊥ ⊥ > > >
⊥ > > ⊥ > > ⊥ ⊥
> ⊥ ⊥ ⊥ > ⊥ > ⊥
> > ⊥ > > > > >
Note
∧, ∨ and ↔ are commutative:
(ϕ 1 ∧ ϕ 2 ) ⇐⇒ (ϕ 2 ∧ ϕ 1 ) (ϕ 1 ∨ ϕ 2 ) ⇐⇒ (ϕ 2 ∨ ϕ 1 ) (ϕ 1 ↔ ϕ 2 ) ⇐⇒ (ϕ 2 ↔ ϕ 1 )
∧ and ∨ are associative:
((ϕ 1 ∧ ϕ 2 ) ∧ ϕ 3 ) ⇐⇒ (ϕ 1 ∧ (ϕ 2 ∧ ϕ 3 )) ⇐⇒ (ϕ 1 ∧ ϕ 2 ∧ ϕ 3 )
((ϕ 1 ∨ ϕ 2 ) ∨ ϕ 3 ) ⇐⇒ (ϕ 1 ∨ (ϕ 2 ∨ ϕ 3 )) ⇐⇒ (ϕ 1 ∨ ϕ 2 ∨ ϕ 3 )
Syntactic Properties of Boolean Operators
¬¬ϕ 1 ⇐⇒ ϕ 1
(ϕ 1 ∨ ϕ 2 ) ⇐⇒ ¬(¬ϕ 1 ∧ ¬ϕ 2 )
¬(ϕ 1 ∨ ϕ 2 ) ⇐⇒ (¬ϕ 1 ∧ ¬ϕ 2 ) (ϕ 1 ∧ ϕ 2 ) ⇐⇒ ¬(¬ϕ 1 ∨ ¬ϕ 2 )
¬(ϕ 1 ∧ ϕ 2 ) ⇐⇒ (¬ϕ 1 ∨ ¬ϕ 2 ) (ϕ 1 → ϕ 2 ) ⇐⇒ (¬ϕ 1 ∨ ϕ 2 )
¬(ϕ 1 → ϕ 2 ) ⇐⇒ (ϕ 1 ∧ ¬ϕ 2 ) (ϕ 1 ← ϕ 2 ) ⇐⇒ (ϕ 1 ∨ ¬ϕ 2 )
¬(ϕ 1 ← ϕ 2 ) ⇐⇒ (¬ϕ 1 ∧ ϕ 2 )
(ϕ 1 ↔ ϕ 2 ) ⇐⇒ ((ϕ 1 → ϕ 2 ) ∧ (ϕ 1 ← ϕ 2 ))
⇐⇒ ((¬ϕ 1 ∨ ϕ 2 ) ∧ (ϕ 1 ∨ ¬ϕ 2 ))
¬(ϕ 1 ↔ ϕ 2 ) ⇐⇒ (¬ϕ 1 ↔ ϕ 2 )
⇐⇒ (ϕ 1 ↔ ¬ϕ 2 )
⇐⇒ ((ϕ 1 ∨ ϕ 2 ) ∧ (¬ϕ 1 ∨ ¬ϕ 2 ))
Boolean logic can be expressed in terms of {¬, ∧} (or {¬, ∨}) only
Syntactic Properties of Boolean Operators
¬¬ϕ 1 ⇐⇒ ϕ 1
(ϕ 1 ∨ ϕ 2 ) ⇐⇒ ¬(¬ϕ 1 ∧ ¬ϕ 2 )
¬(ϕ 1 ∨ ϕ 2 ) ⇐⇒ (¬ϕ 1 ∧ ¬ϕ 2 ) (ϕ 1 ∧ ϕ 2 ) ⇐⇒ ¬(¬ϕ 1 ∨ ¬ϕ 2 )
¬(ϕ 1 ∧ ϕ 2 ) ⇐⇒ (¬ϕ 1 ∨ ¬ϕ 2 ) (ϕ 1 → ϕ 2 ) ⇐⇒ (¬ϕ 1 ∨ ϕ 2 )
¬(ϕ 1 → ϕ 2 ) ⇐⇒ (ϕ 1 ∧ ¬ϕ 2 ) (ϕ 1 ← ϕ 2 ) ⇐⇒ (ϕ 1 ∨ ¬ϕ 2 )
¬(ϕ 1 ← ϕ 2 ) ⇐⇒ (¬ϕ 1 ∧ ϕ 2 )
(ϕ 1 ↔ ϕ 2 ) ⇐⇒ ((ϕ 1 → ϕ 2 ) ∧ (ϕ 1 ← ϕ 2 ))
⇐⇒ ((¬ϕ 1 ∨ ϕ 2 ) ∧ (ϕ 1 ∨ ¬ϕ 2 ))
¬(ϕ 1 ↔ ϕ 2 ) ⇐⇒ (¬ϕ 1 ↔ ϕ 2 )
⇐⇒ (ϕ 1 ↔ ¬ϕ 2 )
⇐⇒ ((ϕ 1 ∨ ϕ 2 ) ∧ (¬ϕ 1 ∨ ¬ϕ 2 ))
Boolean logic can be expressed in terms of {¬, ∧} (or {¬, ∨}) only
Basics on SAT
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 1 ↔ A 2 ) ↔ (A 3 ↔ A 4 )
(((A 1 ↔ A 2 ) → (A 3 ↔ A 4 ))∧ ((A 3 ↔ A 4 ) → (A 1 ↔ A 2 )))
⇓
(((A 1 → A 2 ) ∧ (A 2 → A 1 )) → ((A 3 → A 4 ) ∧ (A 4 → A 3 )))∧
(((A 3 → A 4 ) ∧ (A 4 → A 3 )) → (((A 1 → A 2 ) ∧ (A 2 → A 1 ))))
Basics on SAT
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 1 ↔ A 2 ) ↔ (A 3 ↔ A 4 )
⇓
(((A 1 ↔ A 2 ) → (A 3 ↔ A 4 ))∧
((A 3 ↔ A 4 ) → (A 1 ↔ A 2 )))
(((A 1 → A 2 ) ∧ (A 2 → A 1 )) → ((A 3 → A 4 ) ∧ (A 4 → A 3 )))∧
(((A 3 → A 4 ) ∧ (A 4 → A 3 )) → (((A 1 → A 2 ) ∧ (A 2 → A 1 ))))
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 1 ↔ A 2 ) ↔ (A 3 ↔ A 4 )
⇓
(((A 1 ↔ A 2 ) → (A 3 ↔ A 4 ))∧
((A 3 ↔ A 4 ) → (A 1 ↔ A 2 )))
⇓
(((A 1 → A 2 ) ∧ (A 2 → A 1 )) → ((A 3 → A 4 ) ∧ (A 4 → A 3 )))∧
(((A 3 → A 4 ) ∧ (A 4 → A 3 )) → (((A 1 → A 2 ) ∧ (A 2 → A 1 ))))
Tree and DAG repres. of formulas: example (cont)
A1 A2 A2 A1 A3 A4 A4 A3 A3 A4 A4 A3 A1 A2 A2 A1
A1 A2 A3 A4
Tree Representation
DAG Representation
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
1) := >, µ(A
2) := ⊥} =⇒ {A
1, ¬A
2} µ can be represented as a formula (cube):
EX: {µ(A
1) := >, µ(A
2) := ⊥} =⇒ (A
1∧ ¬A
2)
Basic notation & definitions (cont)
a total truth assignment µ satisfies ϕ (µ |= ϕ):
µ |= A
i⇐⇒ µ(A
i) = >
µ |= ¬ϕ ⇐⇒ not µ |= ϕ
µ |= ϕ
1∧ ϕ
2⇐⇒ µ |= ϕ
1and µ |= ϕ
2µ |= ϕ
1∨ ϕ
2⇐⇒ µ |= ϕ
1or µ |= ϕ
2µ |= ϕ
1→ ϕ
2⇐⇒ if µ |= ϕ
1, then µ |= ϕ
2µ |= ϕ
1↔ ϕ
2⇐⇒ µ |= ϕ
1iff µ |= ϕ
2a partial truth assignment µ satisfies ϕ iff it makes ϕ evaluate to true (Ex: {A 1 } |= (A 1 ∨ A 2 ))
=⇒ if µ satisfies ϕ, then all its total extensions satisfy ϕ (Ex: {A
1, A
2} |= (A
1∨ A
2) and {A
1, ¬A
2} |= (A
1∨ A
2)) ϕ is satisfiable iff µ |= ϕ for some µ
ϕ 1 entails ϕ 2 (ϕ 1 |= ϕ 2 ): ϕ 1 |= ϕ 2 iff µ |= ϕ 1 =⇒ µ |= ϕ 2 for every µ ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ for every µ
Property
ϕ is valid ⇐⇒ ¬ϕ is not satisfiable
Basic notation & definitions (cont)
a total truth assignment µ satisfies ϕ (µ |= ϕ):
µ |= A
i⇐⇒ µ(A
i) = >
µ |= ¬ϕ ⇐⇒ not µ |= ϕ
µ |= ϕ
1∧ ϕ
2⇐⇒ µ |= ϕ
1and µ |= ϕ
2µ |= ϕ
1∨ ϕ
2⇐⇒ µ |= ϕ
1or µ |= ϕ
2µ |= ϕ
1→ ϕ
2⇐⇒ if µ |= ϕ
1, then µ |= ϕ
2µ |= ϕ
1↔ ϕ
2⇐⇒ µ |= ϕ
1iff µ |= ϕ
2a partial truth assignment µ satisfies ϕ iff it makes ϕ evaluate to true (Ex: {A 1 } |= (A 1 ∨ A 2 ))
=⇒ if µ satisfies ϕ, then all its total extensions satisfy ϕ (Ex: {A
1, A
2} |= (A
1∨ A
2) and {A
1, ¬A
2} |= (A
1∨ A
2)) ϕ is satisfiable iff µ |= ϕ for some µ
ϕ 1 entails ϕ 2 (ϕ 1 |= ϕ 2 ): ϕ 1 |= ϕ 2 iff µ |= ϕ 1 =⇒ µ |= ϕ 2 for every µ ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ for every µ
Property
ϕ is valid ⇐⇒ ¬ϕ is not satisfiable
Basic notation & definitions (cont)
a total truth assignment µ satisfies ϕ (µ |= ϕ):
µ |= A
i⇐⇒ µ(A
i) = >
µ |= ¬ϕ ⇐⇒ not µ |= ϕ
µ |= ϕ
1∧ ϕ
2⇐⇒ µ |= ϕ
1and µ |= ϕ
2µ |= ϕ
1∨ ϕ
2⇐⇒ µ |= ϕ
1or µ |= ϕ
2µ |= ϕ
1→ ϕ
2⇐⇒ if µ |= ϕ
1, then µ |= ϕ
2µ |= ϕ
1↔ ϕ
2⇐⇒ µ |= ϕ
1iff µ |= ϕ
2a partial truth assignment µ satisfies ϕ iff it makes ϕ evaluate to true (Ex: {A 1 } |= (A 1 ∨ A 2 ))
=⇒ if µ satisfies ϕ, then all its total extensions satisfy ϕ (Ex: {A
1, A
2} |= (A
1∨ A
2) and {A
1, ¬A
2} |= (A
1∨ A
2)) ϕ is satisfiable iff µ |= ϕ for some µ
ϕ 1 entails ϕ 2 (ϕ 1 |= ϕ 2 ): ϕ 1 |= ϕ 2 iff µ |= ϕ 1 =⇒ µ |= ϕ 2 for every µ ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ for every µ
Property
ϕ is valid ⇐⇒ ¬ϕ is not satisfiable
Basic notation & definitions (cont)
a total truth assignment µ satisfies ϕ (µ |= ϕ):
µ |= A
i⇐⇒ µ(A
i) = >
µ |= ¬ϕ ⇐⇒ not µ |= ϕ
µ |= ϕ
1∧ ϕ
2⇐⇒ µ |= ϕ
1and µ |= ϕ
2µ |= ϕ
1∨ ϕ
2⇐⇒ µ |= ϕ
1or µ |= ϕ
2µ |= ϕ
1→ ϕ
2⇐⇒ if µ |= ϕ
1, then µ |= ϕ
2µ |= ϕ
1↔ ϕ
2⇐⇒ µ |= ϕ
1iff µ |= ϕ
2a partial truth assignment µ satisfies ϕ iff it makes ϕ evaluate to true (Ex: {A 1 } |= (A 1 ∨ A 2 ))
=⇒ if µ satisfies ϕ, then all its total extensions satisfy ϕ (Ex: {A
1, A
2} |= (A
1∨ A
2) and {A
1, ¬A
2} |= (A
1∨ A
2)) ϕ is satisfiable iff µ |= ϕ for some µ
ϕ 1 entails ϕ 2 (ϕ 1 |= ϕ 2 ): ϕ 1 |= ϕ 2 iff µ |= ϕ 1 =⇒ µ |= ϕ 2 for every µ ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ for every µ
Property
ϕ is valid ⇐⇒ ¬ϕ is not satisfiable
Basic notation & definitions (cont)
a total truth assignment µ satisfies ϕ (µ |= ϕ):
µ |= A
i⇐⇒ µ(A
i) = >
µ |= ¬ϕ ⇐⇒ not µ |= ϕ
µ |= ϕ
1∧ ϕ
2⇐⇒ µ |= ϕ
1and µ |= ϕ
2µ |= ϕ
1∨ ϕ
2⇐⇒ µ |= ϕ
1or µ |= ϕ
2µ |= ϕ
1→ ϕ
2⇐⇒ if µ |= ϕ
1, then µ |= ϕ
2µ |= ϕ
1↔ ϕ
2⇐⇒ µ |= ϕ
1iff µ |= ϕ
2a partial truth assignment µ satisfies ϕ iff it makes ϕ evaluate to true (Ex: {A 1 } |= (A 1 ∨ A 2 ))
=⇒ if µ satisfies ϕ, then all its total extensions satisfy ϕ (Ex: {A
1, A
2} |= (A
1∨ A
2) and {A
1, ¬A
2} |= (A
1∨ A
2)) ϕ is satisfiable iff µ |= ϕ for some µ
ϕ 1 entails ϕ 2 (ϕ 1 |= ϕ 2 ): ϕ 1 |= ϕ 2 iff µ |= ϕ 1 =⇒ µ |= ϕ 2 for every µ ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ for every µ
Property
ϕ is valid ⇐⇒ ¬ϕ is not satisfiable
Basic notation & definitions (cont)
a total truth assignment µ satisfies ϕ (µ |= ϕ):
µ |= A
i⇐⇒ µ(A
i) = >
µ |= ¬ϕ ⇐⇒ not µ |= ϕ
µ |= ϕ
1∧ ϕ
2⇐⇒ µ |= ϕ
1and µ |= ϕ
2µ |= ϕ
1∨ ϕ
2⇐⇒ µ |= ϕ
1or µ |= ϕ
2µ |= ϕ
1→ ϕ
2⇐⇒ if µ |= ϕ
1, then µ |= ϕ
2µ |= ϕ
1↔ ϕ
2⇐⇒ µ |= ϕ
1iff µ |= ϕ
2a partial truth assignment µ satisfies ϕ iff it makes ϕ evaluate to true (Ex: {A 1 } |= (A 1 ∨ A 2 ))
=⇒ if µ satisfies ϕ, then all its total extensions satisfy ϕ (Ex: {A
1, A
2} |= (A
1∨ A
2) and {A
1, ¬A
2} |= (A
1∨ A
2)) ϕ is satisfiable iff µ |= ϕ for some µ
ϕ 1 entails ϕ 2 (ϕ 1 |= ϕ 2 ): ϕ 1 |= ϕ 2 iff µ |= ϕ 1 =⇒ µ |= ϕ 2 for every µ ϕ is valid (|= ϕ): |= ϕ iff µ |= ϕ for every µ
Property
ϕ is valid ⇐⇒ ¬ϕ is not satisfiable
Equivalence and equi-satisfiability
ϕ 1 and ϕ 2 are equivalent iff, for every µ, µ |= ϕ 1 iff µ |= ϕ 2
ϕ 1 and ϕ 2 are equi-satisfiable iff
exists µ 1 s.t. µ 1 |= ϕ 1 iff exists µ 2 s.t. µ 2 |= ϕ 2 ϕ 1 , ϕ 2 equivalent
⇓ 6⇑
ϕ 1 , ϕ 2 equi-satisfiable
EX: A 1 ∨ A 2 and (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 ) are equi-satisfiable, not equivalent.
{¬A 1 , A 2 , A 3 } |= (A 1 ∨ A 2 ), but
{¬A 1 , A 2 , A 3 } 6|= (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 )
Typically used when ϕ 2 is the result of applying some transformation T to ϕ 1 : ϕ 2
def= T (ϕ 1 ):
we say that T is validity-preserving [satisfiability-preserving] iff
T (ϕ 1 ) and ϕ 1 are equivalent [equi-satisfiable]
Equivalence and equi-satisfiability
ϕ 1 and ϕ 2 are equivalent iff, for every µ, µ |= ϕ 1 iff µ |= ϕ 2
ϕ 1 and ϕ 2 are equi-satisfiable iff
exists µ 1 s.t. µ 1 |= ϕ 1 iff exists µ 2 s.t. µ 2 |= ϕ 2 ϕ 1 , ϕ 2 equivalent
⇓ 6⇑
ϕ 1 , ϕ 2 equi-satisfiable
EX: A 1 ∨ A 2 and (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 ) are equi-satisfiable, not equivalent.
{¬A 1 , A 2 , A 3 } |= (A 1 ∨ A 2 ), but
{¬A 1 , A 2 , A 3 } 6|= (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 )
Typically used when ϕ 2 is the result of applying some transformation T to ϕ 1 : ϕ 2
def= T (ϕ 1 ):
we say that T is validity-preserving [satisfiability-preserving] iff
T (ϕ 1 ) and ϕ 1 are equivalent [equi-satisfiable]
Equivalence and equi-satisfiability
ϕ 1 and ϕ 2 are equivalent iff, for every µ, µ |= ϕ 1 iff µ |= ϕ 2
ϕ 1 and ϕ 2 are equi-satisfiable iff
exists µ 1 s.t. µ 1 |= ϕ 1 iff exists µ 2 s.t. µ 2 |= ϕ 2 ϕ 1 , ϕ 2 equivalent
⇓ 6⇑
ϕ 1 , ϕ 2 equi-satisfiable
EX: A 1 ∨ A 2 and (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 ) are equi-satisfiable, not equivalent.
{¬A 1 , A 2 , A 3 } |= (A 1 ∨ A 2 ), but
{¬A 1 , A 2 , A 3 } 6|= (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 )
Typically used when ϕ 2 is the result of applying some transformation T to ϕ 1 : ϕ 2
def= T (ϕ 1 ):
we say that T is validity-preserving [satisfiability-preserving] iff
T (ϕ 1 ) and ϕ 1 are equivalent [equi-satisfiable]
Equivalence and equi-satisfiability
ϕ 1 and ϕ 2 are equivalent iff, for every µ, µ |= ϕ 1 iff µ |= ϕ 2
ϕ 1 and ϕ 2 are equi-satisfiable iff
exists µ 1 s.t. µ 1 |= ϕ 1 iff exists µ 2 s.t. µ 2 |= ϕ 2 ϕ 1 , ϕ 2 equivalent
⇓ 6⇑
ϕ 1 , ϕ 2 equi-satisfiable
EX: A 1 ∨ A 2 and (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 ) are equi-satisfiable, not equivalent.
{¬A 1 , A 2 , A 3 } |= (A 1 ∨ A 2 ), but
{¬A 1 , A 2 , A 3 } 6|= (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 )
Typically used when ϕ 2 is the result of applying some transformation T to ϕ 1 : ϕ 2
def= T (ϕ 1 ):
we say that T is validity-preserving [satisfiability-preserving] iff
T (ϕ 1 ) and ϕ 1 are equivalent [equi-satisfiable]
Equivalence and equi-satisfiability
ϕ 1 and ϕ 2 are equivalent iff, for every µ, µ |= ϕ 1 iff µ |= ϕ 2
ϕ 1 and ϕ 2 are equi-satisfiable iff
exists µ 1 s.t. µ 1 |= ϕ 1 iff exists µ 2 s.t. µ 2 |= ϕ 2 ϕ 1 , ϕ 2 equivalent
⇓ 6⇑
ϕ 1 , ϕ 2 equi-satisfiable
EX: A 1 ∨ A 2 and (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 ) are equi-satisfiable, not equivalent.
{¬A 1 , A 2 , A 3 } |= (A 1 ∨ A 2 ), but
{¬A 1 , A 2 , A 3 } 6|= (A 1 ∨ ¬A 3 ) ∧ (A 3 ∨ A 2 )
Typically used when ϕ 2 is the result of applying some transformation T to ϕ 1 : ϕ 2
def= T (ϕ 1 ):
we say that T is validity-preserving [satisfiability-preserving] iff
T (ϕ 1 ) and ϕ 1 are equivalent [equi-satisfiable]
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 satisfiability, and are thus (co)NP-complete.
⇓
No existing worst-case-polynomial algorithm.
POLARITY of subformulas
Polarity: the number of nested negations modulo 2.
Positive/negative occurrences ϕ occurs positively in ϕ;
if ¬ϕ
1occurs positively [negatively] in ϕ, then ϕ
1occurs negatively [positively] in ϕ
if ϕ
1∧ ϕ
2or ϕ
1∨ ϕ
2occur positively [negatively] in ϕ, then ϕ
1and ϕ
2occur positively [negatively] in ϕ;
if ϕ
1→ ϕ
2occurs positively [negatively] in ϕ,
then ϕ
1occurs negatively [positively] in ϕ and ϕ
2occurs positively [negatively] in ϕ;
if ϕ
1↔ ϕ
2occurs in ϕ,
then ϕ
1and ϕ
2occur positively and negatively in ϕ;
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:
ϕ 1 → ϕ 2 =⇒ ¬ϕ 1 ∨ ϕ 2
ϕ 1 ↔ ϕ 2 =⇒ (¬ϕ 1 ∨ ϕ 2 ) ∧ (ϕ 1 ∨ ¬ϕ 2 ) (ii) pushing down negations recursively:
¬(ϕ 1 ∧ ϕ 2 ) =⇒ ¬ϕ 1 ∨ ¬ϕ 2
¬(ϕ 1 ∨ ϕ 2 ) =⇒ ¬ϕ 1 ∧ ¬ϕ 2
¬¬ϕ 1 =⇒ ϕ 1
The reduction is linear if a DAG representation is used.
Preserves the equivalence of formulas.
Basics on SAT
NNF: example
(A 1 ↔ A 2 ) ↔ (A 3 ↔ A 4 )
((((A 1 → A 2 ) ∧ (A 1 ← A 2 )) → ((A 3 → A 4 ) ∧ (A 3 ← A 4 )))∧ (((A 1 → A 2 ) ∧ (A 1 ← A 2 )) ← ((A 3 → A 4 ) ∧ (A 3 ← A 4 ))))
⇓
((¬((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 )))∧ (((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ¬((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 ))))
⇓
((((A 1 ∧ ¬A 2 ) ∨ (¬A 1 ∧ A 2 )) ∨ ((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 )))∧
(((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ((A 3 ∧ ¬A 4 ) ∨ (¬A 3 ∧ A 4 ))))
Basics on SAT
NNF: example
(A 1 ↔ A 2 ) ↔ (A 3 ↔ A 4 )
⇓
((((A 1 → A 2 ) ∧ (A 1 ← A 2 )) → ((A 3 → A 4 ) ∧ (A 3 ← A 4 )))∧
(((A 1 → A 2 ) ∧ (A 1 ← A 2 )) ← ((A 3 → A 4 ) ∧ (A 3 ← A 4 ))))
((¬((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 )))∧ (((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ¬((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 ))))
⇓
((((A 1 ∧ ¬A 2 ) ∨ (¬A 1 ∧ A 2 )) ∨ ((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 )))∧
(((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ((A 3 ∧ ¬A 4 ) ∨ (¬A 3 ∧ A 4 ))))
Basics on SAT
NNF: example
(A 1 ↔ A 2 ) ↔ (A 3 ↔ A 4 )
⇓
((((A 1 → A 2 ) ∧ (A 1 ← A 2 )) → ((A 3 → A 4 ) ∧ (A 3 ← A 4 )))∧
(((A 1 → A 2 ) ∧ (A 1 ← A 2 )) ← ((A 3 → A 4 ) ∧ (A 3 ← A 4 ))))
⇓
((¬((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 )))∧
(((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ¬((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 ))))
((((A 1 ∧ ¬A 2 ) ∨ (¬A 1 ∧ A 2 )) ∨ ((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 )))∧
(((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ((A 3 ∧ ¬A 4 ) ∨ (¬A 3 ∧ A 4 ))))
NNF: example
(A 1 ↔ A 2 ) ↔ (A 3 ↔ A 4 )
⇓
((((A 1 → A 2 ) ∧ (A 1 ← A 2 )) → ((A 3 → A 4 ) ∧ (A 3 ← A 4 )))∧
(((A 1 → A 2 ) ∧ (A 1 ← A 2 )) ← ((A 3 → A 4 ) ∧ (A 3 ← A 4 ))))
⇓
((¬((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 )))∧
(((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ¬((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 ))))
⇓
((((A 1 ∧ ¬A 2 ) ∨ (¬A 1 ∧ A 2 )) ∨ ((¬A 3 ∨ A 4 ) ∧ (A 3 ∨ ¬A 4 )))∧
(((¬A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 )) ∨ ((A 3 ∧ ¬A 4 ) ∨ (¬A 3 ∧ A 4 ))))
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.
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.
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,...
Conjunctive Normal Form (CNF)
ϕ is in Conjunctive normal form iff it is a conjunction of disjunctions of literals:
L
^
i=1 K
i_
j
i=1
l j
ithe disjunctions of literals W K
ij
i=1 l j
iare called clauses Easier to handle: list of lists of literals.
=⇒ no reasoning on the recursive structure of the formula
Classic CNF Conversion CNF (ϕ)
Every ϕ can be reduced into CNF by, e.g., (i) converting it into NNF (not indispensible);
(ii) applying recursively the DeMorgan’s Rule:
(ϕ 1 ∧ ϕ 2 ) ∨ ϕ 3 =⇒ (ϕ 1 ∨ ϕ 3 ) ∧ (ϕ 2 ∨ ϕ 3 ) Worst-case exponential.
Atoms(CNF (ϕ)) = Atoms(ϕ).
CNF (ϕ) is equivalent to ϕ.
Rarely used in practice.
Classic CNF Conversion CNF (ϕ)
Every ϕ can be reduced into CNF by, e.g., (i) converting it into NNF (not indispensible);
(ii) applying recursively the DeMorgan’s Rule:
(ϕ 1 ∧ ϕ 2 ) ∨ ϕ 3 =⇒ (ϕ 1 ∨ ϕ 3 ) ∧ (ϕ 2 ∨ ϕ 3 ) Worst-case exponential.
Atoms(CNF (ϕ)) = Atoms(ϕ).
CNF (ϕ) is equivalent to ϕ.
Rarely used in practice.
Classic CNF Conversion CNF (ϕ)
Every ϕ can be reduced into CNF by, e.g., (i) converting it into NNF (not indispensible);
(ii) applying recursively the DeMorgan’s Rule:
(ϕ 1 ∧ ϕ 2 ) ∨ ϕ 3 =⇒ (ϕ 1 ∨ ϕ 3 ) ∧ (ϕ 2 ∨ ϕ 3 ) Worst-case exponential.
Atoms(CNF (ϕ)) = Atoms(ϕ).
CNF (ϕ) is equivalent to ϕ.
Rarely used in practice.
Classic CNF Conversion CNF (ϕ)
Every ϕ can be reduced into CNF by, e.g., (i) converting it into NNF (not indispensible);
(ii) applying recursively the DeMorgan’s Rule:
(ϕ 1 ∧ ϕ 2 ) ∨ ϕ 3 =⇒ (ϕ 1 ∨ ϕ 3 ) ∧ (ϕ 2 ∨ ϕ 3 ) Worst-case exponential.
Atoms(CNF (ϕ)) = Atoms(ϕ).
CNF (ϕ) is equivalent to ϕ.
Rarely used in practice.
Labeling CNF conversion CNF label (ϕ)
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 w.r.t. ϕ.
More used in practice.
Labeling CNF conversion CNF label (ϕ)
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 w.r.t. ϕ.
More used in practice.
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 )
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
15Labeling 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)
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)
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 )
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 (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
15CNF (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
15Labeling CNF conversion CNF label – further optimizations
Do not apply CNF label when not necessary:
(e.g., CNF label (ϕ 1 ∧ ϕ 2 ) =⇒ CNF label (ϕ 1 ) ∧ ϕ 2 , if ϕ 2 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 1 ∨ (A 2 ∨ A 3 ))
| {z }
B
... =⇒ ...CNF (B ↔ (A 1 ∨ A 2 ∨ A 3 ))...
before applying CNF label , rewrite the initial formula so that to maximize the sharing of subformulas (RBC, BED)
...
Outline
1 Basics on SAT
2 Basic SAT-Solving techniques
3 Modern CDCL SAT Solvers
Conflict-Driven Clause-Learning SAT solvers Further Improvements
4 Tractable subclasses of SAT
5 Random k-SAT and Phase Transition
6 Advanced Functionalities: proofs, unsat cores, interpolants, optimization
7 Some Applications
Appl. #1: (Bounded) Planning
Appl. #2: Bounded Model Checking
Truth Tables
Exhaustive evaluation of all subformulas:
ϕ 1 ϕ 2 ϕ 1 ∧ ϕ 2 ϕ 1 ∨ ϕ 2 ϕ 1 → ϕ 2 ϕ 1 ↔ ϕ 2
⊥ ⊥ ⊥ ⊥ > >
⊥ > ⊥ > > ⊥
> ⊥ ⊥ > ⊥ ⊥
> > > > > >
Requires polynomial space (draw one line at a time).
Requires analyzing 2 |Atoms(ϕ)| lines.
Never used in practice.
Resolution [49, 15]
Search for a refutation of ϕ
ϕ is represented as a set of clauses
Applies iteratively the resolution rule to pairs of clauses containing a conflicting literal, until a false clause is generated or the
resolution rule is no more applicable
Many different strategies
Resolution Rule
Resolution of a pair of clauses with exactly one incompatible variable:
(
common
z }| {
l
1∨ ... ∨ l
k∨
resolvent
z}|{ l ∨
C0
z }| {
l
k +10∨ ... ∨ l
m0) (
common
z }| {
l
1∨ ... ∨ l
k∨
resolvent
z}|{ ¬l ∨
C00
z }| {
l
k +100∨ ... ∨ l
n00) ( l
1∨ ... ∨ l
k| {z }
common
∨ l
k +10∨ ... ∨ l
m0| {z }
C0
∨ l
k +100∨ ... ∨ l
n00| {z }
C00
)
EXAMPLE:
( A ∨ B ∨ C ∨ D ∨ E ) ( A ∨ B ∨ ¬C ∨ F ) ( A ∨ B ∨ D ∨ E ∨ F )
NOTE: many standard inference rules subcases of resolution:
A → B B → C
A → C (Transit.) A A → B
B (M. Ponens) ¬B A → B
¬A (M. Tollens)
Resolution Rules [15, 14]: unit propagation
Unit resolution:
Γ 0 ∧ (l) ∧ (¬l ∨ W
i l i ) Γ 0 ∧ (l) ∧ ( W
i l i ) Unit subsumption:
Γ 0 ∧ (l) ∧ (l ∨ W
i l i ) Γ 0 ∧ (l)
Unit propagation = unit resolution + unit subsumption
“Deterministic” rule: applied before other “non-deterministic” rules!
Resolution: basic strategy [15]
function DP(Γ)
if ⊥ ∈ Γ /* unsat */
then return False;
if (Resolve() is no more applicable to Γ) /* sat */
then return True;
if {a unit clause (l) occurs in Γ} /* unit */
then Γ := Unit_Propagate(l, Γ));
return DP(Γ)
A := select-variable(Γ); /* resolve */
Γ = Γ ∪ S
A∈C
0,¬A∈C
00{Resolve(C 0 , C 00 )} \ S
A∈C
0,¬A∈C
00{C 0 , C 00 }};
return DP(Γ)
Hint: drops one variable A ∈ Atoms(Γ) at a time
Resolution: Examples
(A 1 ∨ A 2 ) (A 1 ∨ ¬A 2 ) (¬A 1 ∨ A 2 ) (¬A 1 ∨ ¬A 2 )
⇓
(A 2 ) (A 2 ∨ ¬A 2 ) (¬A 2 ∨ A 2 ) (¬A 2 )
⇓
⊥
=⇒ UNSAT
Resolution: Examples
(A 1 ∨ A 2 ) (A 1 ∨ ¬A 2 ) (¬A 1 ∨ A 2 ) (¬A 1 ∨ ¬A 2 )
⇓
(A 2 ) (A 2 ∨ ¬A 2 ) (¬A 2 ∨ A 2 ) (¬A 2 )
⇓
⊥
=⇒ UNSAT
Resolution: Examples
(A 1 ∨ A 2 ) (A 1 ∨ ¬A 2 ) (¬A 1 ∨ A 2 ) (¬A 1 ∨ ¬A 2 )
⇓
(A 2 ) (A 2 ∨ ¬A 2 ) (¬A 2 ∨ A 2 ) (¬A 2 )
⇓
⊥
=⇒ UNSAT
Resolution: Examples
(A 1 ∨ A 2 ) (A 1 ∨ ¬A 2 ) (¬A 1 ∨ A 2 ) (¬A 1 ∨ ¬A 2 )
⇓
(A 2 ) (A 2 ∨ ¬A 2 ) (¬A 2 ∨ A 2 ) (¬A 2 )
⇓
⊥
=⇒ UNSAT
Resolution: Examples (cont.)
(A ∨ B ∨ C) (B ∨ ¬C ∨ ¬F ) (¬B ∨ E)
⇓
(A ∨ C ∨ E) (¬C ∨ ¬F ∨ E)
⇓ (A ∨ E ∨ ¬F )
=⇒ SAT
Resolution: Examples (cont.)
(A ∨ B ∨ C) (B ∨ ¬C ∨ ¬F ) (¬B ∨ E)
⇓
(A ∨ C ∨ E) (¬C ∨ ¬F ∨ E)
⇓ (A ∨ E ∨ ¬F )
=⇒ SAT
Resolution: Examples (cont.)
(A ∨ B ∨ C) (B ∨ ¬C ∨ ¬F ) (¬B ∨ E)
⇓
(A ∨ C ∨ E) (¬C ∨ ¬F ∨ E)
⇓ (A ∨ E ∨ ¬F )
=⇒ SAT
Resolution: Examples (cont.)
(A ∨ B ∨ C) (B ∨ ¬C ∨ ¬F ) (¬B ∨ E)
⇓
(A ∨ C ∨ E) (¬C ∨ ¬F ∨ E)
⇓ (A ∨ E ∨ ¬F )
=⇒ SAT
Resolution: Examples
(A ∨ B) (A ∨ ¬B) (¬A ∨ C) (¬A ∨ ¬C)
⇓
(A) (¬A ∨ C) (¬A ∨ ¬C)
⇓ (C) (¬C)
⇓
⊥
=⇒ UNSAT
Resolution: Examples
(A ∨ B) (A ∨ ¬B) (¬A ∨ C) (¬A ∨ ¬C)
⇓
(A) (¬A ∨ C) (¬A ∨ ¬C)
⇓ (C) (¬C)
⇓
⊥
=⇒ UNSAT
Resolution: Examples
(A ∨ B) (A ∨ ¬B) (¬A ∨ C) (¬A ∨ ¬C)
⇓
(A) (¬A ∨ C) (¬A ∨ ¬C)
⇓ (C) (¬C)
⇓
⊥
=⇒ UNSAT
Resolution – summary
Requires CNF Γ may blow up
=⇒ May require exponential space
Not very much used in Boolean reasoning (unless integrated with
DPLL procedure in recent implementations)
Semantic tableaux [55]
Search for an assignment satisfying ϕ
applies recursively elimination rules to the connectives If a branch contains A i and ¬A i , (ψ i and ¬ψ i ) for some i, the branch is closed, otherwise it is open.
if no rule can be applied to an open branch µ, then µ |= ϕ;
if all branches are closed, the formula is not satisfiable;
Tableau elimination rules
ϕ 1 ∧ ϕ 2 ϕ 1
ϕ 2
¬(ϕ 1 ∨ ϕ 2 )
¬ϕ 1
¬ϕ 2
¬(ϕ 1 → ϕ 2 ) ϕ 1
¬ϕ 2 (∧-elimination)
¬¬ϕ
ϕ (¬¬-elimination)
ϕ 1 ∨ ϕ 2 ϕ 1 ϕ 2
¬(ϕ 1 ∧ ϕ 2 )
¬ϕ 1 ¬ϕ 2
ϕ 1 → ϕ 2
¬ϕ 1 ϕ 2 (∨-elimination) ϕ 1 ↔ ϕ 2
ϕ 1 ¬ϕ 1 ϕ 2 ¬ϕ 2
¬(ϕ 1 ↔ ϕ 2 ) ϕ 1 ¬ϕ 1
¬ϕ 2 ϕ 2 (↔ -elimination).
Semantic Tableaux – example
ϕ = (A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 ) ∧ (¬A 1 ∨ A 2 ) ∧ (¬A 1 ∨ ¬A 2 )
Semantic Tableaux – example
ϕ = (A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 ) ∧ (¬A 1 ∨ A 2 ) ∧ (¬A 1 ∨ ¬A 2 )
A1 A2
A1 −A2 A1 −A2
−A1 A2 −A1 A2 −A1 A2
−A1 −A2 −A1 −A2
Tableau algorithm
function Tableau(Γ)
if A i ∈ Γ and ¬A i ∈ Γ /* branch closed */
then return False;
if (ϕ 1 ∧ ϕ 2 ) ∈ Γ /* ∧-elimination */
then return Tableau(Γ ∪ {ϕ 1 , ϕ 2 }\{(ϕ 1 ∧ ϕ 2 )});
if (¬¬ϕ 1 ) ∈ Γ /* ¬¬-elimination */
then return Tableau(Γ ∪ {ϕ 1 }\{(¬¬ϕ 1 )});
if (ϕ 1 ∨ ϕ 2 ) ∈ Γ /* ∨-elimination */
then return Tableau(Γ ∪ {ϕ 1 }\{(ϕ 1 ∨ ϕ 2 )}) or Tableau(Γ ∪ {ϕ 2 }\{(ϕ 1 ∨ ϕ 2 )});
...
return True; /* branch expanded */
Semantic Tableaux – summary
Handles all propositional formulas (CNF not required).
Branches on disjunctions
Intuitive, modular, easy to extend
=⇒ loved by logicians.
Rather inefficient
=⇒ avoided by computer scientists.
Requires polynomial space
DPLL [15, 14]
Davis-Putnam-Longeman-Loveland procedure (DPLL) Tries to build an assignment µ satisfying ϕ;
At each step assigns a truth value to (all instances of) one atom.
Performs deterministic choices first.
DPLL rules
ϕ 1 ∧ (l)
ϕ 1 [l|>] (Unit) ϕ
ϕ[l|>] (l Pure) ϕ
ϕ[l|>] ϕ[l|⊥] (split) (l is a pure literal in ϕ iff it occurs only positively).
Split applied if and only if the others cannot be applied.
Richer formalisms described in [57, 44, 45]
DPLL – example
ϕ = (A 1 ∨ A 2 ) ∧ (A 1 ∨ ¬A 2 ) ∧ (¬A 1 ∨ A 2 ) ∧ (¬A 1 ∨ ¬A 2 )
A1 −A1
A2 A2
DPLL Algorithm
function DPLL(ϕ, µ)
if ϕ = > /* base */
then return True;
if ϕ = ⊥ /* backtrack */
then return False;
if {a unit clause (l) occurs in ϕ} /* unit */
then return DPLL(assign(l, ϕ), µ ∧ l);
if {a literal l occurs pure in ϕ} /* pure */
then return DPLL(assign(l, ϕ), µ ∧ l);
l := choose-literal(ϕ); /* split */
return DPLL(assign(l, ϕ), µ ∧ l) or
DPLL(assign(¬l, ϕ), µ ∧ ¬l);
DPLL – summary
Handles CNF formulas (non-CNF variant known [2, 25]).
Branches on truth values
=⇒ all instances of an atom assigned simultaneously Postpones branching as much as possible.
Mostly ignored by logicians.
(The grandfather of) the most efficient SAT algorithms
=⇒ loved by computer scientists.
Requires polynomial space Choose_literal() critical!
Many very efficient implementations [61, 54, 4, 43].
Ordered Binary Decision Diagrams (OBDDs) [12]]
Canonical representation of Boolean formulas
“If-then-else” binary direct acyclic graphs (DAGs) with one root and two leaves: 1, 0 (or >,⊥; or T, F)
Variable ordering A 1 , A 2 , ..., A n imposed a priori.
Paths leading to 1 represent models
Paths leading to 0 represent counter-models Note
Some authors call them Reduced Ordered Binary Decision Diagrams
(ROBDDs)
Ordered Binary Decision Diagrams (OBDDs) [12]]
Canonical representation of Boolean formulas
“If-then-else” binary direct acyclic graphs (DAGs) with one root and two leaves: 1, 0 (or >,⊥; or T, F)
Variable ordering A 1 , A 2 , ..., A n imposed a priori.
Paths leading to 1 represent models
Paths leading to 0 represent counter-models Note
Some authors call them Reduced Ordered Binary Decision Diagrams
(ROBDDs)
OBDD - Examples
F T
b3 a3
b3 b2 a2
b2
b1 b1
a1 a1
a2
a3 a3 a3
a2
a3
b1 b1 b1 b1 b1 b1
b2 b2 b2 b2
b3 b3
b1 b1
T F
