Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Unsound result with define-fun-rec and declare-const, reloaded #5541

Closed
Elarnon opened this issue Sep 9, 2021 · 2 comments
Closed

Unsound result with define-fun-rec and declare-const, reloaded #5541

Elarnon opened this issue Sep 9, 2021 · 2 comments

Comments

@Elarnon
Copy link

Elarnon commented Sep 9, 2021

With the following query:

(declare-const W Int)
(declare-const x Int)
(define-fun-rec sat ((x Int)) Int (ite (< x W) x W))

(assert (not (= (sat x) (ite (< x W) x W))))
(assert (= W 10))

(check-sat)

Z3 (tested on 4.8.11 and on current master) answers sat and generates an invalid model (this is caught by model_validate).
If I either remove the assertion (= W 10) or use (define-const W Int 10) instead, Z3 correctly answers unsat.

This looks like a variation on #5305.

@Elarnon
Copy link
Author

Elarnon commented Sep 13, 2021

This doesn't happen with (check-sat-using smt), and I narrowed it down to the solve-eqs call used by the default tactic. It looks like that solve-eqs does not rewrite within the body of the recursive function (and macro-finder doesn't look like it does either).

Simplified example:

(declare-const W Int)
(declare-const x Int)
(define-fun-rec rW ((x Int)) Int W)
(assert (distinct (rW x) W))
(assert (= W 10))

(check-sat-using (then solve-eqs smt))

@Elarnon
Copy link
Author

Elarnon commented Sep 21, 2021

Thank you for the fix @NikolajBjorner; I can confirm the issue is no longer present with a constant + solve-eqs in the current master. However it is still present when using a function + macro-finder instead, see example below. I should have included it in the previous message.

(declare-fun W (Int) Int)
(declare-const x Int)
(define-fun-rec rW ((x Int)) Int (W x))
(assert (distinct (rW x) (W x)))
(assert (forall ((y Int)) (= (W y) 10)))

(check-sat-using (then macro-finder smt))

master (2c266a9) currently still answers sat for this problem.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant