Question

Is there a way in Z3 to prove/show that a given model is unique and that no other solution exists?

A small example to demonstrate

(declare-const a1 Int)
(declare-const a2 Int)
(declare-const a3 Int)
(declare-const b1 Int)
(declare-const b2 Int)
(declare-const b3 Int)
(declare-const c1 Int)
(declare-const c2 Int)
(declare-const c3 Int)
(declare-const ra Int)
(declare-const rb Int)
(declare-const rc Int)
(declare-const r1 Int)
(declare-const r2 Int)
(declare-const r3 Int)
(assert (>= a1 0))
(assert (>= a2 0))
(assert (>= a3 0))
(assert (>= b1 0))
(assert (>= b2 0))
(assert (>= b3 0))
(assert (>= c1 0))
(assert (>= c2 0))
(assert (>= c3 0))
(assert (<= a1 9))
(assert (<= a2 9))
(assert (<= a3 9))
(assert (<= b1 9))
(assert (<= b2 9))
(assert (<= b3 9))
(assert (<= c1 9))
(assert (<= c2 9))
(assert (<= c3 9))
(assert (= ra 38))
(assert (= rb 1))
(assert (= rc 27))
(assert (= r1 55))
(assert (= r2 72))
(assert (= r3 6))
(assert (= ra (- (* a1 a2) a3)))
(assert (= rb (- (- b1 b2) b3)))
(assert (= rc (* (* c1 c2) c3)))
(assert (= r1 (- (* a1 b1) c1)))
(assert (= r2 (* (+ a2 b2) c2)))
(assert (= r3 (- (+ a3 b3) c3)))
(check-sat)
(get-model)

I know for a fact that the following model is unique, but can I ensure this using either some Z3 option or adding assertions?

(model 
  (define-fun c3 () Int
    3)
  (define-fun c2 () Int
    9)
  (define-fun c1 () Int
    1)
  (define-fun b3 () Int
    5)
  (define-fun b2 () Int
    2)
  (define-fun b1 () Int
    8)
  (define-fun a3 () Int
    4)
  (define-fun a2 () Int
    6)
  (define-fun a1 () Int
    7)
  (define-fun r3 () Int
    6)
  (define-fun r2 () Int
    72)
  (define-fun r1 () Int
    55)
  (define-fun rc () Int
    27)
  (define-fun rb () Int
    1)
  (define-fun ra () Int
    38)
)

For clarification, I'm using Z3 through de JAVA API

Was it helpful?

Solution

Yes: the idea is to assert that the values assigned by the found model are the only possible assignments, and hence it is unique. This can be done by adding one assertion that states that all the constants are NOT equal to their assigned model values.

For your example, this would be:

(assert (not (and
  (= c3 3)
  (= c2 9)
  (= c1 1)
  (= b3 5)
  (= b2 2)
  (= b1 8)
  (= a3 4)
  (= a2 6)
  (= a1 7)
  (= r3 6)
  (= r2 72)
  (= r1 55)
  (= rc 27)
  (= rb 1)
  (= ra 38))))
(check-sat) ; unsat => no other model exists

If you try changing any of the values (e.g., change c3 = 3 to c3 = 4) this will again become satisfiable. Here's a rise@fun link to your complete example: http://rise4fun.com/Z3/nD5n

For more details on how to do this programmatically using the APIs, see these questions and answers:

Z3: finding all satisfying models

(Z3Py) checking all solutions for equation

Note that as per comments in the second linked answer, you cannot do this programmatically using just the SMT-lib frontend, you have to use an API to traverse the found model if you want to automate this process.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top