1

Is it possible to have Z3Py generate more counterexamples within reasonable time ?

I can generate one counterexample using z3.prove as follows:

import z3

x = z3.Real("x")

rule = x > 0
goal = x < 0
z3.prove(z3.Implies(rule, goal))

which gives the following output,

counterexample
[x = 1]

But what if I want to generate more counterexamples ?

Is the only way to do this by incrementally adding rules based on the counterexamples ?

For the above case, I can get a different counterexample by doing this,

z3.prove(z3.Implies(z3.And(rule, x!=1), goal))

but I believe this is slow when many rules are involved so I am hoping for a faster approach.

halfer
  • 19,824
  • 17
  • 99
  • 186
IssamLaradji
  • 6,637
  • 8
  • 43
  • 68
  • See [this answer](http://stackoverflow.com/questions/11867611/z3py-checking-all-solutions-for-equation). You could also use incremental solving. – Stanley Bak Aug 25 '16 at 14:49

1 Answers1

2

What you suggest is the "usual" recommendation for getting more than one counter-example. Z3 does not have methods for producing more than one counter-example because this is easy to do from the outside. However, it does have support for optimization, so if your goal is to find exactly one "best" or "at least as good" solution, then this may be a solution.

A simple optimization to the trivial counter-example addition is to check whether all the assignments in the counter-example are actually required. For instance, it may be the case that the counter-example is (x = 5, y = 0), but nothing depends on y = 0, so we can remove it, which makes the counter-example smaller (and thus there will be fewer of them).

Christoph Wintersteiger
  • 8,234
  • 1
  • 16
  • 30