Course Formal Methods Module I: Automated Reasoning Ch. 03: Satisﬁability Modulo Theories

(1)

Course Formal Methods Module I: Automated Reasoning Ch. 03: Satisfiability Modulo Theories

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 / 136

(2)

Outline

1 Introduction

What is a Theory?

Satisfiability Modulo Theories Motivations and Goals of SMT

2 Efficient SMT solving

Combining SAT with Theory Solvers

Theory Solvers for Theories of Interest (hints) SMT for Combinations of Theories

3 Beyond Solving: Advanced SMT Functionalities Proofs and Unsatisfiable Cores

Interpolants

All-SMT & Predicate Abstraction (hints)

SMT with Optimization (Optimization Modulo Theories)

2 / 136

(3)

Outline

1 Introduction

What is a Theory?

Interpolants

3 / 136

(4)

Outline

1 Introduction

What is a Theory?

Interpolants

4 / 136

(5)

FOL Theories

Traditional Definition (FOL)

Given a FOL signature Σ, aΣ-Theory T (hereafter simply “theory”) is a (possibly infinite) set of FOL closed formulas (axioms)

Typically used to provide someintended interpretationto the symbols in the signature Σ

FOL formulas deduces from these axioms via inference rules Definition used by logicians,

Very low practical use in AR & Formal Verification

5 / 136

(6)

FOL Theories

5 / 136

(7)

FOL Theories

5 / 136

(8)

FOL Theories

5 / 136

(9)

FOL Theories

5 / 136

(10)

Example: A FOL Theory of Positive Integer Numbers (aka “Peano Arithmetic”, P)

Signature

(basic) unary predicate symbol:NatNum(“natural number”) (basic) unary function symbol:S(“successor”)

(basic) constant symbol:0

(derived) binary function symbols:+,*(infix) (derived) constant symbols:1,2,3,4,5,6,...

Axioms

1 NatNum(0)

2 ∀x.(NatNum(x) → NatNum(S(x)))

3 ∀x.(NatNum(x) → (0 6= S(x)))

4 ∀x, y .((NatNum(x) ∧ NatNum(y )) → ((x 6= y ) → (S(x) 6= S(y ))))

5 ∀x.(NatNum(x) → (x = (0 + x)))

6 ∀x, y .((NatNum(x) ∧ NatNum(y )) → (S(x) + y ) = S(x + y ))

7 1 = S(0), 2 = S(1), 3 = S(2), ...

Formulas deduced ex:P ` NatNum(25)

ex:P ` ∀x, y .((NatNum(x) ∧ NatNum(y )) → ((x + y ) = (y + x)))

6 / 136

(11)

Example: A FOL Theory of Positive Integer Numbers (aka “Peano Arithmetic”, P)

Signature

Axioms

1 NatNum(0)

3 ∀x.(NatNum(x) → (0 6= S(x)))

5 ∀x.(NatNum(x) → (x = (0 + x)))

7 1 = S(0), 2 = S(1), 3 = S(2), ...

6 / 136

(12)

Example: A FOL Theory of Positive Integer Numbers (aka “Peano Arithmetic”, P)

Signature

Axioms

1 NatNum(0)

3 ∀x.(NatNum(x) → (0 6= S(x)))

5 ∀x.(NatNum(x) → (x = (0 + x)))

7 1 = S(0), 2 = S(1), 3 = S(2), ...

6 / 136

(13)

Example: A FOL Theory of Positive Integer Numbers (aka “Peano Arithmetic”, P)

Signature

Axioms

1 NatNum(0)

3 ∀x.(NatNum(x) → (0 6= S(x)))

5 ∀x.(NatNum(x) → (x = (0 + x)))

7 1 = S(0), 2 = S(1), 3 = S(2), ...

6 / 136

(14)

FOL Theories (cont.)

SMT Definition

Given a FOL signature Σ, aΣ-Theory T (hereafter simply “theory”) is one (or more) model(s) constraining the interpretations of Σ

Provides anintended interpretationto the symbols in Σ constants mapped into domain elements

ex: “1” mapped into the number one

predicate symbols mapped into relations on domain elements ex: “. < .” mapped into the arithmetical relation “less then”

function symbols mapped into functions on domain elements ex: “S(.)” mapped into the arithmetical function “successor of”

These symbols are calledinterpreted

Compliant with previous definition:model(s) satisfying all axioms Ad hoc “T -aware” decision procedures for reasoning on formulas Very effective in practical applications

7 / 136

(15)

FOL Theories (cont.)

SMT Definition

7 / 136

(16)

FOL Theories (cont.)

SMT Definition

7 / 136

(17)

FOL Theories (cont.)

SMT Definition

7 / 136

(18)

FOL Theories (cont.)

SMT Definition

7 / 136

(19)

Example: Linear Arithmetic on the Integers (LIA)

Domain: integer numbers

Numerical constants interpreted asnumbers

ex: “1”, “1346231” mapped directly into the corresponding number function and predicates interpreted asarithmetical operations

“+” as addiction, “*” as multiplication, “<” as less-then, . etc.

ILP solversused to do logical reasoning

ex:(3x − 2y ≤ 3) ∧ (4y − 2z < −7) |= (6x − 2z < −1)

8 / 136

(20)

Example: Linear Arithmetic on the Integers (LIA)

ex:(3x − 2y ≤ 3) ∧ (4y − 2z < −7) |= (6x − 2z < −1)

8 / 136

(21)

Example: Linear Arithmetic on the Integers (LIA)

ex:(3x − 2y ≤ 3) ∧ (4y − 2z < −7) |= (6x − 2z < −1)

8 / 136

(22)

Example: Linear Arithmetic on the Integers (LIA)

ex:(3x − 2y ≤ 3) ∧ (4y − 2z < −7) |= (6x − 2z < −1)

8 / 136

(23)

Satisfiability, Validity, Entailment (Modulo a Theory T )

Definitions

Idea: We restrict to models satisfying T (“T -models”)

A formula issatisfiable in T (aka “ϕ is T -satisfiable”)iff some model satisfying T satisfies also ϕ

ex:(x < 3)satisfiable in LIA

A formula ϕ isvalid in T (aka “ϕ is T -valid” or “|=T ϕ”)iff all models satisfying T satisfy also ϕ

ex:(x < 3) → (x < 4)valid in LIA

A formulaϕentails ψ in T (aka “ϕ T -entails ψ” or “ϕ |=T ψ”)iff all models satisfying T and ϕ satisfy also ψ

ex:(x < 3) |=LIA(x < 4)

Properties

ϕis T -valid iff ¬ϕ is T -unsatisfiable ϕ |=T ψiff ϕ → ψ is T -valid

=⇒ ϕ |=T ψiff ϕ ∧ ¬ψ T -unsatisfiable

9 / 136

(24)

Satisfiability, Validity, Entailment (Modulo a Theory T )

Definitions

ex:(x < 3) |=LIA(x < 4)

Properties

9 / 136

(25)

Satisfiability, Validity, Entailment (Modulo a Theory T )

Definitions

ex:(x < 3) |=LIA(x < 4)

Properties

9 / 136

(26)

Satisfiability, Validity, Entailment (Modulo a Theory T )

Definitions

ex:(x < 3) |=LIA(x < 4)

Properties

9 / 136

(27)

Satisfiability, Validity, Entailment (Modulo a Theory T )

Definitions

ex:(x < 3) |=LIA(x < 4)

Properties

9 / 136

(28)

Satisfiability, Validity, Entailment (Modulo a Theory T )

Definitions

ex:(x < 3) |=LIA(x < 4)

Properties

9 / 136

(29)

Satisfiability, Validity, Entailment (Modulo a Theory T )

Definitions

ex:(x < 3) |=LIA(x < 4)

Properties

9 / 136

(30)

Satisfiability, Validity, Entailment (Modulo a Theory T )

Definitions

ex:(x < 3) |=LIA(x < 4)

Properties

9 / 136

(31)

Outline

1 Introduction

What is a Theory?

Interpolants

10 / 136

(32)

Satisfiability Modulo Theories (SMT(T ))

The problem of deciding the satisfiability of (typically quantifier-free) formulas in some decidable first-order theory T

T can also be acombination of theoriesS

iT_i.

11 / 136

(33)

SMT(T ): Theories of Interest

Some theories of interest (e.g., for formal verification) Equality and Uninterpreted Functions (EU F ):

((x = y ) ∧ (y = f (z))) → (g(x ) = g(f (z)))

Difference logic (DL):((x = y ) ∧ (y − z ≤ 4)) → (x − z ≤ 6) UTVPI (U T VPI):((x = y ) ∧ (y − z ≤ 4)) → (x + z ≤ 6) Linear arithmetic over the rationals (LRA):

(T_δ → (s₁=s₀+3.4 · t − 3.4 · t₀)) ∧ (¬T_δ → (s₁=s₀)) Linear arithmetic over the integers (LIA):

(x = x_l+2¹⁶x_h) ∧ (x ≥ 0) ∧ (x ≤ 2¹⁶− 1)

Arrays (AR):(i = j) ∨ read (write(a, i, e), j) = read (a, j) Bit vectors (BV):

x_[16][15 : 0] = (y_[16][15 : 8] :: z_[16][7 : 0]) << w_[8][3 : 0]

Non-Linear arithmetic over the reals (N LA(R)):

((c = a · b) ∧ (a₁=a − 1) ∧ (b₁=b + 1)) → (c = a₁· b₁+1) ...

12 / 136

(34)

SMT(T ): Theories of Interest

((x = y ) ∧ (y = f (z))) → (g(x ) = g(f (z)))

(x = x_l+2¹⁶x_h) ∧ (x ≥ 0) ∧ (x ≤ 2¹⁶− 1)

x_[16][15 : 0] = (y_[16][15 : 8] :: z_[16][7 : 0]) << w_[8][3 : 0]

((c = a · b) ∧ (a₁=a − 1) ∧ (b₁=b + 1)) → (c = a₁· b₁+1) ...

12 / 136

(35)

SMT(T ): Theories of Interest

((x = y ) ∧ (y = f (z))) → (g(x ) = g(f (z)))

(x = x_l+2¹⁶x_h) ∧ (x ≥ 0) ∧ (x ≤ 2¹⁶− 1)

x_[16][15 : 0] = (y_[16][15 : 8] :: z_[16][7 : 0]) << w_[8][3 : 0]

((c = a · b) ∧ (a₁=a − 1) ∧ (b₁=b + 1)) → (c = a₁· b₁+1) ...

12 / 136

(36)

SMT(T ): Theories of Interest

((x = y ) ∧ (y = f (z))) → (g(x ) = g(f (z)))

(x = x_l+2¹⁶x_h) ∧ (x ≥ 0) ∧ (x ≤ 2¹⁶− 1)

x_[16][15 : 0] = (y_[16][15 : 8] :: z_[16][7 : 0]) << w_[8][3 : 0]

((c = a · b) ∧ (a₁=a − 1) ∧ (b₁=b + 1)) → (c = a₁· b₁+1) ...

12 / 136

(37)

SMT(T ): Theories of Interest

((x = y ) ∧ (y = f (z))) → (g(x ) = g(f (z)))

(x = x_l+2¹⁶x_h) ∧ (x ≥ 0) ∧ (x ≤ 2¹⁶− 1)

x_[16][15 : 0] = (y_[16][15 : 8] :: z_[16][7 : 0]) << w_[8][3 : 0]

((c = a · b) ∧ (a₁=a − 1) ∧ (b₁=b + 1)) → (c = a₁· b₁+1) ...

12 / 136

(38)

SMT(T ): Theories of Interest

((x = y ) ∧ (y = f (z))) → (g(x ) = g(f (z)))

(x = x_l+2¹⁶x_h) ∧ (x ≥ 0) ∧ (x ≤ 2¹⁶− 1)

x_[16][15 : 0] = (y_[16][15 : 8] :: z_[16][7 : 0]) << w_[8][3 : 0]

((c = a · b) ∧ (a₁=a − 1) ∧ (b₁=b + 1)) → (c = a₁· b₁+1) ...

12 / 136

(39)

SMT(T ): Theories of Interest

((x = y ) ∧ (y = f (z))) → (g(x ) = g(f (z)))

(x = x_l+2¹⁶x_h) ∧ (x ≥ 0) ∧ (x ≤ 2¹⁶− 1)

x_[16][15 : 0] = (y_[16][15 : 8] :: z_[16][7 : 0]) << w_[8][3 : 0]

((c = a · b) ∧ (a₁=a − 1) ∧ (b₁=b + 1)) → (c = a₁· b₁+1) ...

12 / 136

(40)

SMT(T ): Theories of Interest

((x = y ) ∧ (y = f (z))) → (g(x ) = g(f (z)))

(x = x_l+2¹⁶x_h) ∧ (x ≥ 0) ∧ (x ≤ 2¹⁶− 1)

x_[16][15 : 0] = (y_[16][15 : 8] :: z_[16][7 : 0]) << w_[8][3 : 0]

((c = a · b) ∧ (a₁=a − 1) ∧ (b₁=b + 1)) → (c = a₁· b₁+1) ...

12 / 136

(41)

Satisfiability Modulo Theories (SMT(T )): Example

Example: SMT(LIA ∪ EU F ∪ AR) ϕ^def= (d ≥ 0) ∧ (d < 1)∧

((f (d ) = f (0)) → (read (write(V , i, x ), i + d ) = x + 1)) involves arithmetical, arrays, and uninterpreted function/predicate symbols, plus Boolean operators

Is it satisfiable?

No:

ϕ

=⇒_LIA (d = 0)

=⇒_{EU F} (f (d ) = f (0))

=⇒_Bool (read (write(V , i, x ), i + d ) = x + 1)

=⇒_LIA (read (write(V , i, x ), i) = x + 1)

=⇒_LIA ¬(read (write(V , i, x), i) = x)

=⇒_AR ⊥

13 / 136

(42)

Satisfiability Modulo Theories (SMT(T )): Example

Is it satisfiable?

No:

ϕ

=⇒_LIA (d = 0)

=⇒_{EU F} (f (d ) = f (0))

=⇒_AR ⊥

13 / 136

(43)

Satisfiability Modulo Theories (SMT(T )): Example

Is it satisfiable?

No:

ϕ

=⇒_LIA (d = 0)

=⇒_{EU F} (f (d ) = f (0))

=⇒_AR ⊥

13 / 136

(44)

SMT and SMT solvers

Common fact about SMT problems from various applications SMT requires capabilities forheavy Boolean reasoningcombined with capabilities forreasoning in expressive decidable F.O. theories

SAT alone not expressive enough

standard automated theorem proving inadequate (e.g., arithmetic)

may involve also numerical computation (e.g., simplex)

Modern SMT solvers

combineSAT solverswith T -specificdecision procedures (theory solversorT -solvers)

contributions from SAT, Automated Theorem Proving (ATP), formal verification (FV) and operational research (OR)

14 / 136

(45)

SMT and SMT solvers

Modern SMT solvers

14 / 136

(46)

SMT and SMT solvers

Modern SMT solvers

14 / 136

(47)

SMT and SMT solvers

Modern SMT solvers

14 / 136

(48)

SMT and SMT solvers

Modern SMT solvers

14 / 136

(49)

Notational remark (1): most/all examples in LRA

For better readability, in most/all the examples of this presentation we will use the theory of linear arithmetic on rational numbers (LRA) because of its intuitive semantics. E.g.:

(¬A₁∨ (3x₁− 2x₂− 3 ≤ 5)) ∧ (A₂∨ (−2x₁+4x₃+2 = 3)) Nevertheless, analogous examples can be built with all other theories of interest.

15 / 136

(50)

Notational remark (2): “constants” vs. “variables”

Consider, e.g., the formula:

(¬A₁∨ (3x₁− 2x₂− 3 ≤ 5)) ∧ (A₂∨ (−2x₁+4x₃+2 = 3)) How do we call A₁,A₂?:

(a) Boolean/propositionalvariables?

(b) uninterpreted0-ary predicates?

How do we call x₁,x₂,x₃?:

(a) domainvariables?

(b) uninterpreted Skolemconstants/0-ary uninterpreted functions?

Hint:

(a) typically used in SAT, CSP and OR communities (b) typically used in logic & ATP communities

Hereafter we call A₁,A₂“Boolean/propositionalvariables” and x₁,x₂,x₃"domainvariables” (logic purists, please forgive me!)

16 / 136

(51)

Notational remark (2): “constants” vs. “variables”

Hint:

16 / 136

(52)

Notational remark (2): “constants” vs. “variables”

Hint:

16 / 136

(53)

Outline

1 Introduction

What is a Theory?

Interpolants

17 / 136

(54)

Some Motivating Applications

Interest in SMT triggered by some real-word applications Verification of Hybrid & Timed Systems

Verification of RTL Circuit Designs & of Microcode SW Verification

Planning with Resources Temporal reasoning Scheduling

Compiler optimization ...

18 / 136

(55)

Verification of Timed Systems

T12

T21 x<=3 x>=1

x:=0 x <= 2

a

b

l1 l2

Bounded/inductive model checking of Timed Systems[6, 33, 53], ...

Timed Automataencoded into T -formulas:

discrete information(locations, transitions, events) with Boolean vars.

timed information(clocks, elapsed time) with differences (t₃− x₃≤ 2), equalities(x₄=x₃)and linear constraints (t₈− x₈=t₂− x₂)on Q

=⇒ SMT on DL(Q) or LRA required

19 / 136

(56)

Verification of Hybrid Systems ...

w = 2. T12

Grow Steady

cruise

Stable

w >=L

L <= w<= U

Bounded model checking of Hybrid Systems[5],...

Hybrid Automataencoded into L-formulas:

discrete information(locs, trans., events) with Boolean vars.

timed information(clocks, elapsed time) with differences (t₃− x₃≤ 2), equalities(x₄=x₃)and linear constraints (t8− x₈=t2− x₂)on Q

Evolution of Physical Variables(e.g., speed, pressure) with linear (ω₄=2ω3)and non-linear constraints(P1V1=4T1)on Q

Undecidableunder simple hypotheses!

=⇒ SMT on DL(Q), LRA or N LA(R) required

20 / 136

(57)

Verification of HW circuit designs & microcode

CK CK

B2 CK

Adder B3

B1 g = 2*f

f’ = itea+2*e

itea’ = ITE(B1;a;0) c

a

g f

itea

e’ = ITE(B2;b;0)+2*ite(B3;c;0) e control

L−Shifter

L−Shifter b

L−Shifter Adder

data 1

0

1 1

0

SAT/SMT-basedModel Checking&Equiv. Checkingof RTL designs,symbolic simulationof µ-code [24, 21, 39]

Control pathshandled by Boolean reasoning

Data pathsinformation abstracted into theory-specific terms words(bit-vectors, integers, EU F vars, ... ):a[31 : 0],a word operations: (BV, EU F , AR, LIA, N LA(Z) operators) x_[16][15 : 0] = (y_[16][15 : 8] :: z_[16][7 : 0]) << w_[8][3 : 0], (a = aL+2¹⁶aH),(m1=store(m0,l0,v0)), ...

Tradesheavy Boolean reasoning(≈ 2⁶⁴ factors) withT -solving

=⇒ SMT on BV, EU F , AR, modulo-LIA [N LA(Z) ] required

21 / 136

(58)

Verification of SW systems

...

10. i = 0;

11. acc = 0.0;

12. while (i<dim) { 13. acc += V[i];

14. i++;

15. } ...

....

(pc = 10) → ((i⁰=0) ∧ (pc⁰=11)) (pc = 11) → ((acc⁰=0.0) ∧ (pc⁰=12)) (pc = 12) → ((i < dim) → ∧(pc⁰=13)) (pc = 12) → (¬(i < dim) → ∧(pc⁰=16))

(pc = 13) → ((acc⁰=acc + read (V , i)) ∧ (pc⁰=14)) (pc = 14) → (i⁰=i + 1) ∧ (pc⁰=15))

(pc = 15) → (pc⁰=16)) ...

Verification of SW code

BMC, K-induction, Check of proof obligations, interpolation-based model checking, symbolic simulation, concolic testing, ...

=⇒ SMT on BV, EU F , AR, (modulo-)LIA [N LA(Z) ] required

22 / 136

(59)

Planning with Resources [72]

SAT-bases planning augmented with numerical constraints Straightforward to encode into into SMT(LRA)

Example (sketch) [72]

(Deliver ) ∧ // goal

(MaxLoad ) ∧ // load constraint

(MaxFuel) ∧ // fuel constraint

(Move → MinFuel) ∧ // move requires fuel

(Move → Deliver ) ∧ // move implies delivery

(GoodTrip → Deliver ) ∧ // a good trip requires (GoodTrip → AllLoaded ) ∧ // a full delivery (MaxLoad → (load ≤ 30)) ∧ // load limit (MaxFuel → (fuel ≤ 15)) ∧ // fuel limit (MinFuel → (fuel ≥ 7 + 0.5load )) ∧ // fuel constraint (AllLoaded → (load = 45)) //

23 / 136

(60)

(Disjunctive) Temporal Reasoning [69, 2]

Temporal reasoning problems encoded as disjunctions of difference constraints

((x₁− x2≤ 6) ∨ (x3− x4≤ −2)) ∧ ((x₂− x₃≤ −2) ∨ (x₄− x5≤ 5)) ∧ ((x₂− x₁≤ 4) ∨ (x₃− x₇≤ −6)) ∧ ...

Straightforward to encode into into SMT(DL)

24 / 136

(61)

Goal

Provide an overview of standard “lazy” SMT:

foundations

SMT-solving techniques

beyond solving: advanced SMT functionalities ongoing research

We do notcover related approaches like:

Eager SAT encodings Rewrite-based approaches

We refer to [64, 10] for an overview and references.

25 / 136

(62)

Goal

Provide an overview of standard “lazy” SMT:

foundations

SMT-solving techniques

beyond solving: advanced SMT functionalities ongoing research

We do notcover related approaches like:

Eager SAT encodings Rewrite-based approaches

We refer to [64, 10] for an overview and references.

25 / 136

(63)

Outline

1 Introduction

What is a Theory?

Interpolants

26 / 136

(64)

Outline

1 Introduction

What is a Theory?

Interpolants

27 / 136

(65)

Modern “lazy” SMT(T ) solvers

A prominent “lazy” approach [42, 2, 72, 3, 8, 33] (aka “DPLL(T )”) aCDCL SAT solveris used to enumerate truth assignments µ_i for (the Boolean abstraction of) the input formula ϕ

a theory-specific solverT -solverchecks the T -satisfiability of the set of T -literalscorresponding to each assignment

Built on top of modern SAT CDCL solvers

benefit for free from all modern CDCL techniques

(e.g.,Boolean preprocessing, backjumping & learning, restarts,...) benefit for free from all state-of-the-art data structures and implementation tricks (e.g.,two-watched literals,...)

Many techniques to maximize the benefits of integration [64, 10]

Many lazy SMT tools available

(Barcelogic,CVC4,MathSAT,OpenSMT,Yices,Z3, . . . )

28 / 136

(66)

Modern “lazy” SMT(T ) solvers

A prominent “lazy” approach [42, 2, 72, 3, 8, 33] (aka “DPLL(T )”) aCDCL SAT solveris used to enumerate truth assignments µ_i for (the Boolean abstraction of) the input formula ϕ

a theory-specific solverT -solverchecks the T -satisfiability of the set of T -literalscorresponding to each assignment

Built on top of modern SAT CDCL solvers

benefit for free from all modern CDCL techniques

(e.g.,Boolean preprocessing, backjumping & learning, restarts,...) benefit for free from all state-of-the-art data structures and implementation tricks (e.g.,two-watched literals,...)

Many techniques to maximize the benefits of integration [64, 10]

Many lazy SMT tools available

(Barcelogic,CVC4,MathSAT,OpenSMT,Yices,Z3, . . . )

28 / 136

(67)

Basic schema: example

ϕ = ϕ^p=

c1: ¬(2v2− v3>2) ∨ A1

c2: ¬A2∨(v1− v5≤ 1) c3: (3v1− 2v2≤ 3) ∨A2

c4: ¬(2v3+v4≥ 5) ∨¬(3v1− v3≤ 6) ∨¬A1

c5: A1∨(3v1− 2v2≤ 3)

c6: (v2− v4≤ 6) ∨ (v5=5 − 3v4) ∨¬A1

c7: A1∨ (v3=3v5+4) ∨ A2

true,false

¬B1∨ A1

¬A2∨B2

B3∨A2

¬B4∨¬B5∨¬A1

A1∨B3

B6∨ B7∨¬A1

A1∨ B8∨ A2

µ^p = {¬B5,B8,B6, ¬B1, ¬B3,A1,A2,B2}

µ = {¬(3v1− v3≤ 6), (v3=3v5+4), (v2− v4≤ 6),

¬(2v2− v3>2), ¬(3v1− 2v2≤ 3), (v1− v5≤ 1)}

=⇒unsatisfiable in LRA =⇒ backtrack

29 / 136

(68)

Basic schema: example

ϕ = ϕ^p=

c1: ¬(2v2− v3>2) ∨ A1

c2: ¬A2∨(v1− v5≤ 1) c3: (3v1− 2v2≤ 3) ∨A2

c4: ¬(2v3+v4≥ 5) ∨¬(3v1− v3≤ 6) ∨¬A1

c5: A1∨(3v1− 2v2≤ 3)

c6: (v2− v4≤ 6) ∨ (v5=5 − 3v4) ∨¬A1

c7: A1∨ (v3=3v5+4) ∨ A2

true,false

¬B1∨ A1

¬A2∨B2

B3∨A2

¬B4∨¬B5∨¬A1

A1∨B3

B6∨ B7∨¬A1

A1∨ B8∨ A2

µ^p = {¬B5,B8,B6, ¬B1, ¬B3,A1,A2,B2}

µ = {¬(3v1− v3≤ 6), (v3=3v5+4), (v2− v4≤ 6),

¬(2v2− v3>2), ¬(3v1− 2v2≤ 3), (v1− v5≤ 1)}

29 / 136

(69)

Basic schema: example

ϕ = ϕ^p=

c1: ¬(2v2− v3>2) ∨ A1

c2: ¬A2∨(v1− v5≤ 1) c3: (3v1− 2v2≤ 3) ∨A2

c4: ¬(2v3+v4≥ 5) ∨¬(3v1− v3≤ 6) ∨¬A1

c5: A1∨(3v1− 2v2≤ 3)

c6: (v2− v4≤ 6) ∨ (v5=5 − 3v4) ∨¬A1

c7: A1∨ (v3=3v5+4) ∨ A2

true,false

¬B1∨ A1

¬A2∨B2

B3∨A2

¬B4∨¬B5∨¬A1

A1∨B3

B6∨ B7∨¬A1

A1∨ B8∨ A2

¬B3

A1

A2

B2

T

¬B5

B8

B6

¬B1

µ^p = {¬B5,B8,B6, ¬B1, ¬B3,A1,A2,B2}

µ = {¬(3v1− v3≤ 6), (v3=3v5+4), (v2− v4≤ 6),

¬(2v2− v3>2), ¬(3v1− 2v2≤ 3), (v1− v5≤ 1)}

29 / 136

(70)

Basic schema: example

ϕ = ϕ^p=

c1: ¬(2v2− v3>2) ∨ A1

c2: ¬A2∨(v1− v5≤ 1) c3: (3v1− 2v2≤ 3) ∨A2

c4: ¬(2v3+v4≥ 5) ∨¬(3v1− v3≤ 6) ∨¬A1

c5: A1∨(3v1− 2v2≤ 3)

c6: (v2− v4≤ 6) ∨ (v5=5 − 3v4) ∨¬A1

c7: A1∨ (v3=3v5+4) ∨ A2

true,false

¬B1∨ A1

¬A2∨B2

B3∨A2

¬B4∨¬B5∨¬A1

A1∨B3

B6∨ B7∨¬A1

A1∨ B8∨ A2

¬B3

A1

A2

B2

T

¬B5

B8

B6

¬B1

µ^p = {¬B5,B8,B6, ¬B1, ¬B3,A1,A2,B2}

µ = {¬(3v1− v3≤ 6), (v3=3v5+4), (v2− v4≤ 6),

¬(2v2− v3>2), ¬(3v1− 2v2≤ 3), (v1− v5≤ 1)}

29 / 136