Course “Introduction to SAT & SMT” TEST

(1)

Roberto Sebastiani

DISI, Universit` a di Trento, Italy June 11

^th

, 2020

769857918 Name (please print):

Surname (please print):

i

(2)

1 Let φ be a generic Boolean formula, and let φ

^tree_nnf ^def

= N N F

^tree

(φ) and φ

^dag_nnf ^def

= N N F

^dag

(φ), s.c.

N N F ()

^tree

and N N F ()

^dag

are the conversion into negative normal form using a tree and a DAG representation of the formulas respectively.

Let |φ|, |φ

^treennf

| and |φ

^dag_nnf

| denote the size of φ, φ

^treennf

and φ

^dag_nnf

respectively.

For each of the following sentences, say if it is true or false.

(a) |φ

^tree_nnf

| is in worst-case polynomial in size wrt. |φ|.

(b) |φ

^dag_nnf

| is in worst-case polynomial in size wrt. |φ|.

(c) φ

^dag_nnf

has the same number of distinct Boolean variables as φ has.

(d) A model for φ

^dag_nnf

(if any) is also a model for φ, and vice versa.

1

(3)

Using the variable ordering “ A

₁

, A

₂

, A

₃

, A

₄

”, draw the OBDD corresponding to the following formulas:

A

₁

∧ (¬A

1

∨ ¬A

2

) ∧ ( A

2

∨ A

3

) ∧ (¬A

3

∨ A

4

)

2

(4)

3 Using the semantic tableaux algorithm, decide whether the following formula is satisﬁable or not.

(Write the search tree.)

( ¬A

1

) ∧ ( A

₁

∨ ¬A

2

) ∧ ( A

₁

∨ A

₂

∨ A

₃

) ∧ ( A

₄

∨ ¬A

3

∨ A

₆

) ∧ ( A

₄

∨ ¬A

3

∨ ¬A

6

) ∧ ( ¬A

3

∨ ¬A

4

∨ A

7

) ∧ ( ¬A

3

∨ ¬A

4

∨ ¬A

7

) (Literal-selection criteria to your choice.)

3

(5)

Consider the following piece of a much bigger formula, which has been fed to a CDCL SAT solver:

c

₁

: ¬A

7

∨ A

2

c

₂

: A

₄

∨ A

1

∨ A

₁₁

c

₃

: A

₈

∨ ¬A

6

∨ ¬A

4

c

₄

: ¬A

5

∨ ¬A

1

c

₅

: A

₇

∨ ¬A

8

c

₆

: A

₇

∨ A

6

∨ A

₉

c

₇

: ¬A

7

∨ A

3

∨ ¬A

12

c

₈

: A

₄

∨ A

5

∨ A

₁₀

...

Suppose the solver has decided, in order, the following literals (possibly interleaved by others not occurring in the above clauses):

{..., ¬A

9

, ... ¬A

10

, ... ¬A

11

, ... A

₁₂

, ... A

₁₃

, ..., ¬A

7

}

(a) List the sequence of unit-propagations following after the last decision, each literal tagged (in square brackets) by its antecedent clause

(b) Derive the conﬂict clause via conﬂict analysis by means of the 1st-UIP technique

(c) Using the 1st-UIP backjumping strategy, update the list of literals above after the backjumping step and the unit-propagation of the UIP

4

(6)

5 Consider the following CNF formula:

( A

₇

) ∧

( A

₈

∨ ¬A

7

) ∧

( ¬A

4

∨ ¬A

7

∨ ¬A

5

) ∧ ( ¬A

8

∨ ¬A

6

∨ A

₁

) ∧ ( A

₂

∨ ¬A

7

∨ ¬A

6

) ∧ ( ¬A

8

∨ A

₆

∨ ¬A

2

) ∧ ( ¬A

1

∨ ¬A

5

∨ ¬A

2

) ∧ ( A

₂

∨ ¬A

6

∨ ¬A

8

) ∧ ( ¬A

1

∨ ¬A

5

∨ A

₈

) ∧ ( A

₂

∨ A

₇

∨ ¬A

6

) ∧ ( ¬A

6

∨ A

₄

∨ ¬A

6

) ∧ ( A

₃

∨ A

₈

∨ ¬A

7

) Decide quickly if it is satisﬁable or not, and brieﬂy explain why.

5

(7)

Consider the following Boolean formulas:

φ

₁ ^def

= ( ¬A

7

∨ ¬A

3

) ∧ ( A

₇

∨ ¬A

3

) ∧

( A

₂

) ∧

( ¬A

2

∨ ¬A

4

) φ

2

def

= ( A

3

∨ A

5

) ∧ ( A

₄

∨ ¬A

1

) ∧ ( ¬A

5

∨ A

1

)

which are such that φ

₁

∧ φ

2

|= ⊥. For each of the following formulas, say if it is a Craig interpolant for (φ

₁

, φ

₂

) or not.

(a)

( ¬A

7

∨ ¬A

3

) ∧ ( A

₇

∨ ¬A

3

) ∧ ( ¬A

4

)

(b)

( ¬A

4

) (c)

( ¬A

3

∧ ¬A

4

)

6

(8)

7 Consider the following formula in the theory EUF of linear arithmetic on the Rationals.

φ = {(f(x) = f(f(y))) ∨ A

2

} ∧

{¬(h(x, f(y)) = h(g(x), y)) ∨ ¬(h(x, g(z) = h(f(x), y))) ∨ ¬A

1

} ∧ {A

1

∨ (h(x, y) = h(y, x))} ∧

{(x = f(x)) ∨ A

3

∨ ¬A

1

} ∧ {¬(w(x) = g(f(y))) ∨ A

1

} ∧ {¬A

2

∨ (w(g(x)) = w(f(x)))} ∧ {A

1

∨ (y = g(z)) ∨ A

2

}

and consider the partial truth assignment µ given by the underlined literals above:

{¬(w(x) = g(f(y))), ¬A

2

, ¬(h(x, g(z) = h(f(x), y))), (x = f(x)), (y = g(z))}.

1. Does (the Boolean abstraction of) µ propositionally satisfy (the Boolean abstraction of) φ?

2. Is µ satisﬁable in EUF?

(a) If no, find a minimal conflict set for µ and the corresponding conflict clause C.

(b) If yes, show one unassigned literal which can be deduced from µ, and show the corresponding deduction clause C.

7

(9)

Consider the following set of clauses φ in the theory of linear arithmetic on the Integers EUF.

 

 

 



( ¬(x = y) ∨ (f(x) = f(y))), ( ¬(x = y) ∨ ¬(f(x) = f(y))), ( (x = y) ∨ (f(x) = f(y))), ( (x = y) ∨ ¬(f(x) = f(y)))

 

 

 



Say which of the following sets is a EUF-unsatisﬁable core of φ and which is not. For each one, explain why.

(a) 





( ¬(x = y) ∨ ¬(f(x) = f(y))), ( (x = y) ∨ (f(x) = f(y))), ( (x = y) ∨ ¬(f(x) = f(y)))

 



(b) 





( ¬(x = y) ∨ (f(x) = f(y))), ( (x = y) ∨ (f(x) = f(y))), ( (x = y) ∨ ¬(f(x) = f(y)))

 



(c) 

 



 



( ¬(x = y) ∨ ¬(f(x) = f(y))), ( (x = y) ∨ (f(x) = f(y))), ( (x = y) ∨ ¬(f(x) = f(y))), ((x = f (y)))

 

 

 



8

(10)

9 Let LRA be the logic of linear arithmetic over the rationals and EUF be the logic of equality and uninterpreted functions. Consider the following pure formula φ in the combined logic LRA ∪ EUF:

(x = 1.0) ∧ (h = 1.0) ∧ (k = 1.0) ∧ (y = 2h − k) ∧ (z < w) (1)

(z = f (x)) ∧ (w = f(y)) (2)

Say which variables are interface variables, list the interface equalities for this formula (modulo symmetry), and decide whether this formulas is LRA ∪ EUF-satisﬁable or not, using either Nelson- Oppen or Delayed Theory Combination.

9

(11)

Consider the following formulas in diﬀerence logic ( DL):

φ

₁ ^def

= (x

₂

− x

3

≤ −4) ∧ (x

₃

− x

4

≤ −6) ∧ (x

₅

− x

6

≤ 4) ∧ (x

₆

− x

1

≤ 2) ∧ (x

₆

− x

7

≤ −2) ∧ (x

₇

− x

8

≤ 1) φ

₂ ^def

= (x

₄

− x

9

≤ 2) ∧

(x

9

− x

5

≤ 0) ∧ (x

₁

− x

2

≤ 1)

which are such that φ

1

∧φ

2

|=

DL

⊥. For each of the following formulas, say if it is a Craig interpolant in DL for (φ

1

, φ

₂

), and explain why.

(a) (x

₂

− x

3

+ x

₆

− x

1

≤ −2) (b) (x

₂

− x

4

≤ −10)

(c) (x

₂

− x

4

≤ −10) ∧ (x

₅

− x

1

≤ 6)

10