CODEWITHSUNDEEP
z3
alias
alias

Reputation: 30450

mixing reals and bit-vectors

I've two SMT2-Lib scripts using reals, which are morally equivalent. The only difference is that one also uses bit-vectors while the other does not.

Here's the version that uses both reals and bit-vectors:

; uses both reals and bit-vectors
(set-option :produce-models true)
(define-fun s2 () Real (root-obj (+ (^ x 2) (- 2)) 2))
(define-fun s3 () Real 0.0)
(define-fun s6 () Real (/ 1.0 1.0))
(declare-fun s0 () (_ BitVec 1))
(declare-fun s1 () (_ BitVec 1))
(assert
   (let ((s4 (- s3 s2)))
   (let ((s5 (ite (= #b1 s1) s2 s4)))
   (let ((s7 (+ s5 s6)))
   (let ((s8 (- s5 s6)))
   (let ((s9 (ite (= #b1 s0) s7 s8)))
   (let ((s10 (ite (>= s9 s3) #b1 #b0)))
   (= s10 #b1))))))))

(check-sat)
(get-model)

Here's the morally equivalent script, using Bool instead of a bit-vector of size 1, otherwise it's essentially the same:

; uses reals only
(set-option :produce-models true)
(define-fun s2 () Real (root-obj (+ (^ x 2) (- 2)) 2))
(define-fun s3 () Real 0.0)
(define-fun s6 () Real (/ 1.0 1.0))
(declare-fun s0 () (Bool))
(declare-fun s1 () (Bool))
(assert
   (let ((s4 (- s3 s2)))
   (let ((s5 (ite s1 s2 s4)))
   (let ((s7 (+ s5 s6)))
   (let ((s8 (- s5 s6)))
   (let ((s9 (ite s0 s7 s8)))
   (let ((s10 (ite (>= s9 s3) #b1 #b0)))
   (= s10 #b1))))))))

(check-sat)
(get-model)

For the former I get unknown from z3 (v4.1 on Mac), while the latter nicely produces sat and a model.

While SMT-Lib2 doesn't allow mixing reals and bit-vectors, I thought Z3 handled these combinations just fine. Am I mistaken? Is there a workaround?

(Note that these are generated scripts, so just using Bool instead of (_ BitVec 1) is rather costly, as it requires quite a bit of changes elsewhere.)

Upvotes: 4

Views: 821

Answers (1)

Leonardo de Moura
Leonardo de Moura

Reputation: 21475

The new nonlinear solver is not integrated with other theories yet. It supports only real variables and Booleans. Actually, it also allows integer variables, but it is very limited support for them. It actually solves nonlinear integer problems as real problems, and just checks in the end whether each integer variable is assigned to an integer value. Moreover, this solver is the only complete procedure for nonlinear (real) arithmetic available in Z3.

Since your first problem contains Bit-vectors, the nonlinear solver is not used by Z3. Instead, Z3 uses a general purpose solver that combines many theories, but it is incomplete for nonlinear arithmetic.

That being said, I understand this is a limitation, and I'm working on that. In the (not so near) future, Z3 will have a new solver that integrates nonlinear arithmetic, arrays, bit-vectors, etc.

Finally, the bit-vector theory is a very special case, since we can easily reduce it to propositional logic in Z3. Z3 has tactic bit-blast that applies this reduction. This tactic can reduce any nonlinear+bit-vector problem into a problem that contains only reals and Booleans. Here is an example (http://rise4fun.com/Z3/0xl).

; uses both reals and bit-vectors
(set-option :produce-models true)
(define-fun s2 () Real (root-obj (+ (^ x 2) (- 2)) 2))
(define-fun s3 () Real 0.0)
(define-fun s6 () Real (/ 1.0 1.0))
(declare-fun s0 () (_ BitVec 1))
(declare-fun s1 () (_ BitVec 1))
(declare-fun v2 () (_ BitVec 8))
(assert
   (let ((s4 (- s3 s2)))
   (let ((s5 (ite (= #b1 s1) s2 s4)))
   (let ((s7 (+ s5 s6)))
   (let ((s8 (- s5 s6)))
   (let ((s9 (ite (= #b1 s0) s7 s8)))
   (let ((s10 (ite (>= s9 s3) #b1 #b0)))
   (= s10 #b1))))))))

(assert (or (and (not (= v2 #x00)) (not (= v2 #x01))) (bvslt v2 #x00)))
(assert (distinct (bvnot v2) #x00))
(check-sat-using (then simplify bit-blast qfnra))
(get-model)

Upvotes: 5

Related Questions