How to deal with recursive function in Z3?

Question

(set-option :smt.mbqi true)
(declare-fun R(Int) Int)
(declare-const a Int)
(assert (= (R 0) 0))
(assert (forall ((n Int)) (=> (> n 0) (= (R n ) (+ (R (- n 1)) 1)))))
(assert (not (= a 5)))
(assert (not (= (R a) 5)))
(check-sat)

I have tried the above code in Z3,But Z3 unable to answer.Can you please guide me where i have made the mistake ?

Answer 1

As a general pattern don't expect MBQI to produce models involving functions that only have an infinite range of different values. If you really must, then you can use the define-fun-rec construct to define a recursive function. Z3 currently trusts that the definition is well-formed (e.g., that the equation corresponding to the function definition is satisfiable).

(set-option :smt.mbqi true)
(declare-fun F (Int) Int)
(define-fun-rec R ((n Int)) Int
   (if (= n 0) 0
       (if (> n 0) (+ (R (- n 1)) 1)
            (F n))))

(declare-const a Int)
(assert (not (= a 5)))
(assert (not (= (R a) 5)))
(check-sat)
(get-model)

Z3 uses recursively defined functions passively during search: whenever there is a candidate model for the ground portion of the constraints, it checks that the function graph is adequately defined on the values of the candidate model. If it isn't, then the function definition is instantiated on the selected values until it is well defined on the values that are relevant to the ground constraints.