0

I've been searching the square root functionality provided by z3. For example, for adding a constraint about a Real number x , that x*x = 2, what is the best way to encode that?

I tried:

(declare-const x Real)
(assert (= 2 (* x x))) 
(check-sat)

The result is unknown. The model is also, unavailable.

However, I am sure there should be a way to satisfy this. I am referring strictly to the extended version of smt-lib 2.0 language and not the python api.

Malte Schwerhoff
  • 12,684
  • 4
  • 41
  • 71
Madrugada
  • 1,261
  • 8
  • 24
  • 44

1 Answers1

4

You need to use the nonlinear solver. The reason your example did not autodetect and use this is because of the constant 2: this gets parsed into an integer and not a real, so it's technically in the combination theory of integers and reals, while the nonlinear solver may only involve reals unless you force it. To force its use, you can use check-sat-using and the nonlinear solver qfnra-nlsat (rise4fun link: http://rise4fun.com/Z3/fXDp ):

(declare-const x Real)

(push)
(assert (= 2 (* x x)))
(check-sat-using qfnra-nlsat) ; sat
(get-model)
; may have to play with printing options as this is irrational (or this may be a bug)
; (model 
;  (define-fun x () Real
;    (/ 5.0 4.0))
;)
(pop)

; the reason you need to use check-sat-using is because the 2 gets parsed into an integer; to force it to be a real, use a decimal:
(push)
(assert (= 2.0 (* x x)))

(check-sat) ; sat
(get-model) 
;(model 
;  (define-fun x () Real
;    (root-obj (+ (^ x 2) (- 2)) 1))
;)
(pop)

For general exponents (square roots, etc.), you can use ^ for exponentiation:

; you can also use ^ for exponentiation    
(push)
(assert (= 2.0 (^ x 2.0)))
(check-sat) ; sat
(get-model)
; (model 
;  (define-fun x () Real
;    (root-obj (+ (^ x 2) (- 2)) 1))
;)
(pop)

; to represent square root, etc., you may use fractional or decimal exponents
(push)
(assert (= 25.0 (^ x 0.5))) ; square root: 2 = sqrt(x)
(check-sat) ; sat
(get-model)
; maybe a bug or have to tune the model printer
;(model 
;  (define-fun x () Real
;    (- 1.0))
;)
(pop)

(push)
(assert (= 2.0 (^ x (/ 1.0 3.0))))
(check-sat) ; sat
(get-model)
;(model 
;  (define-fun x () Real
;    8.0)
;)
(pop)

(push)
(assert (= 10.0 (^ x 0.2)))
(check-sat) ; sat
(get-model)
;(model 
;  (define-fun x () Real
;    100000.0)
;)
(pop)

Here is an old, but related post: z3/python reals

Some of the printing issues, e.g., if you need decimal approximations, can be fixed by using:

(set-option :pp.decimal true)

Community
  • 1
  • 1
Taylor T. Johnson
  • 2,834
  • 16
  • 17