The refutation that Z3 produces for HORN logic problems is in the form of a tree of unit-resulting resolution steps. The counterexample you're looking for is hiding in the conclusions of the unit-resolution steps. These conclusions (the last arguments of the rules) are ground facts that correspond to program states...

Z3 supports the distinct function, which in C++ is available as expr expr::distinct(expr_vector const & args).

Self Answer based on the comment summary of Christoph Wintersteiger when running python example.py this access violation error WindowsError: [Error 998] Invalid access to memory location was raised because as noted in the query and as commented by Christoph the operating system Windows xp doesn't support Thread local Storage in...

For sign extension: Z3_ast Z3_API Z3_mk_sign_ext(__in Z3_context c, __in unsigned i, __in Z3_ast t1); https://github.com/Z3Prover/z3/blob/master/src/api/z3_api.h#L2826 For unsigned extension: Z3_ast Z3_API Z3_mk_zero_ext(__in Z3_context c, __in unsigned i, __in Z3_ast t1); https://github.com/Z3Prover/z3/blob/master/src/api/z3_api.h#L2838 These functions are also available in bindings for Python, C#, Java...

The issue can be followed on Z3's GitHub page: https://github.com/Z3Prover/z3/issues/32.

I'm not sure that I understand the question, but in general we cannot expect Z3 to solve all formulas with quantifiers. In this particular case it might help to enable the macro-finder, which propagates function definitions like the (forall ... (= (try ...) def ))) which replaces all occurrences of...

There is no equivalent to function definitions because they aren't necessary, just like the define-fun macro. The equivalent thing to do in the API is to build an expression for the function and then for every application of the function, just substitute the argument values for the input values, e.g.,...

If all you want is to encode is that an element v is in a finite set {e1, ..., en} (with sort U), you can do this using smtlib2 as follows: (declare-fun v () U) (declare-fun p1 () Bool) ... (assert (= p1 (= v e1))) (assert (= p2 (=...

The easiest is to encode cardinality constraints using arithmetic. So if you want to say a + b + c <= 2, where a, b, c are Bool, then you can formulate it as (if a 1 0) + (if b 1 0) + (if c 1 0) >= 2....

Disclaimer: If your problem is solely that you are struggling with encoding the problem using Z3py, then my suggestions won't help you since they are not about Z3py. However, I assume that your problem is actually more fundamental. Answer: Axiomatising the lists in Z3/SMTLIB is not at all straight-forward, in...

Those changes to the build system are right, but all that is needed to get a proper 32-bit binary, e.g., the AMD64 macro needs to be removed. I've now added the option --x86 to mk_make.py (in the unstable branch), which I hope will get all the settings right.

From the description it's not clear which solving method Z3 employs in the end, but in general non-linear integer arithmetic is undecidable and Z3 can only handle simple cases of exponentials. See also Leo's answers to similar questions: How does Z3 handle non-linear integer arithmetic? Z3 supports for nonlinear arithmetics...

It also seemed not to return for me using that, but it seems to work as: z3 -in -smt2 Followed by pasting the query, so I think it may need the -smt2 parameter. I tried it on Windows with 4.3.3 (I thought I had 4.3.2, but it seems I updated...

In addition to dejvuth's answer: The SMT language is well documented (see smt-lib.org), for this particular issue the FixedSizeBitVectors theory and the QF_BV logic definition are relevant. The latter contains the definition for repeat: ((_ repeat i) (_ BitVec m) (_ BitVec i*m)) - ((_ repeat i) x) means concatenate...

I am obtaining (using iZ3, Z3 unstable branch) sat (model (define-fun f ((x!1 Int) (x!2 Int)) Int (ite (and (= x!1 1) (= x!2 1)) 1 (ite (and (= x!1 2) (= x!2 2)) 2 (ite (and (= x!1 1) (= x!2 2)) 2 (ite (and (= x!1 2) (=...

The second call to Z3_parse_smtlib2_string does not know about the declaration in the first call: Z3_ast parsed2 = Z3_parse_smtlib2_string(c1, testing.c_str(), 0,0,0,0,0,0); The bunch of zero's in the end means "do not assume anything else", so it doesn't know that p0 exists. For more details see the Z3_parse_smtlib2_string in the API...

By default Z3 solves the objectives one at a time and finds the lexicographically best solution. First it tries to satisfy as many soft constraints from "first". The weight you associate with the soft constraints is a penalty for not satisfying the constraint. That is, it is not an award,...

Actually, I have figured it out: using substitute with a further call to simplify seems to do the trick.

Thanks for catching that! There was indeed a bug that caused the random seed not to be passed through to the arithmetic theory. This is now fixed in the unstable branch (fix here). This example: (set-option :smt.arith.random_initial_value true) (declare-const x Int) (declare-const y Int) (assert (> (+ x y) 0))...

configuration,z3,usage-statistics

All theories have final checks, but smt.arith.nl.rounds is only for the non-linear arithmetic solver (old; not NLSAT). There may be lots of final checks, none of which involve any non-linear arithmetic, or they use other methods to solve those parts.

There is currently no separate documentation for the Java API (other than the comments in the API itself). Large parts of this API where however automatically translated from the .NET API, so it is virtually the same as that one, as bovoi said. The .NET API is in turn based...

The `Distinct' function only creates a term, it doesn't add itself to the solver. Here's an example that works for me: x = Int('x') y = Int('y') d = Distinct(x, y) s = Solver() s.add(d) # SAT without this one, UNSAT with s.add(x == y) print s print s.check() ...

arrays,z3,smt,z3py,microsoft-research

Disclaimer: I've hardly ever used Z3py before, but I've used Z3 quite a bit. I have the feeling that you are somewhat new to encoding logical problems as well - could that be? There are several (odd) things going on in your problem. You put constraints on x and y,...

exception,z3,smt,java-api,tactic

The command Goal g = ctx.mkGoal(true, true, false); asks for unsat core extraction to be enabled (the second true) for the goal g, but the propagate-ineqs tactic does not support that feature, so it throws an exception....

This may well be a bug, but it's very unlikely that it has anything to do with mbqi; the reason you get less warnings when it is set to false, is that it simply gives up much earlier, never reaching the parts that throw the additional warnings. There've been a...

There is currently no function for this purpose, but it is easy to get the declarations by traversing the expressions. This has previously been asked for C/C++, but the answer applies to Java as well: Z3 4.3.1 C-API parse_smtlib2_string: Where to get declarations from? Additionally, these posts may be of...

Here're some encodings, the syntax for ite requires 3 parameters, the first of which is the conditional, the second is the true case, and the third is the false case (rise4fun link: http://rise4fun.com/Z3/qW3B ): ; original example for { x< 40 } x :=x+10 { x < 50} (push) (declare-const...

The extract function only takes numerals as arguments, not arbitrary expressions. However, we can shift the expression to one direction and then extract the first or last four bits, e.g. along the lines of ((_ extract 11 8) (bvshl l (bvmul idx four))) (where idx and four are bit-vector expressions...

The define-fun construct behaves like a macro, so all occurrences of max2 will be replaced with the function definition. Alternatively, we could use quantifiers and the macro-finder (see e.g., Equivalent of define-fun in Z3 API), or we can just replace all occurrences of the function ourselves. In general it is...

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...

Those particular utilities are an external contribution to Z3 and only available for the Python API. It should be possible to follow the same ideas in Java though. The Solver object has a function called getStatistics() that returns Statistics object, which is essentially a collection of key/value pairs. Note that...

The int2bv function is essentially handled as uninterpreted (as stated in the documentation), so the semantics are not precise. There have previously been a few questions about those conversion functions, they might be helpful here too: Z3: an exception with int2bv Check overflow with Z3 bv-enable-int2bv-propagation option...

Reduction-And, Reduction-Or were not added to the Python API yet. Note that Reduction-And is quite different from 'normal and'. I have now added those to the unstable branch. For reference and future use, we can add functions that exist in the C-API but not in the Python API from the...

For this example, the macro finder will be useful (I think often with forall quantifiers with implications), you can enable it with: (set-option :macro-finder true) Here's your updated example that gets sat quickly (rise4fun link: http://rise4fun.com/Z3/Ux7gN ): (set-option :macro-finder true) (declare-const a (Array Int Bool)) (declare-const sz Int) (declare-const n...

For true don't-cares, the model will not assign any value. Consequently, calls to eval or Z3_model_eval with model_completion set to false will keep the original constants untouched and only replace those for which a model value is assigned (and it will potentially simplify the expression). Here's an example: context c;...

No, Z3 does not have facilities that achieve all those goals already built in. Z3 goal and solver objects can be serialized to a string in SMT2 format via the Z3_goal_to_string and Z3_solver_to_string functions; these could be used for check-pointing, but they will not save any learnt clauses that weren't...

Z3 is not particularly tuned for proving theorems in universal algebra. Theorem provers with super-position, such as E, Spass, Vampire, are traditionally well suited for such theorems. That said, the version of Z3 in the unstable branch has no problems. Here is what I get: z3.exe ua.smt2 /v:10 (simplifier :num-exprs...

Well, it turns out I used brackets where I shouldn't - the reference to the custom data type "Bool" needs no call: BoolList.declare('bCONS', ('hd', Bool), ('tail', BoolList)) works just fine :)...

Sure you can store expressions of different sorts. Based on your description you are running into a C++ overloading "experience". THe operator < is overloaded to exprs. Instead you want to use comparison on expressions as abstract syntax trees. The expressions expose a unique identifier, which is an unsigned. You...

It may, but switching solvers or building a specialized tactic will probably have a greater influence.

If you represent your problem in a bit vector formula, e.g. QF_ABV, it will be automatically flattened into propositional formula, and solved using a SAT solver. For example, you can represent your less-than-100 integer variables as a bit vectors of 7 bits. Apart from bit vector, conversion from SMT to...

There are several C-Functions that allow you to extract different types of values, depending on the expected size of the numerals: Z3_get_numeral_int, Z3_get_numeral_uint, Z3_get_numeral_uint64, Z3_get_numeral_int64. For numbers that don't fit into those basic types, we can use the Z3_get_numeral_string function to get a string representation that can be parsed into...

My golden rule for reference counting is: Whenever my program receives a pointer to a Z3 object, I immediately increment the ref count and I save the object somewhere safe (i.e., I now own 1 reference to that object). Only when I'm absolutely sure that I will not need the...

You use ! incorrectly. The exclamation point is used for naming formulae (not asserts). See section 3.9.8 from the Tutorial. This should fix it: (assert (! (bvslt ...) :named ?U0))....

The documentation for the parameters is obtained by running z3 -p. More information about a particular option is obtained by running z3 -pp:option_name. The parameter infrastructure has seen major changes in 4.3.2; there are now parameter modules and the soft_timeout resides in the smt module, i.e., the proper name is...

I'm not exactly sure whether this is an observation or a question? Yes, Z3 will behave differently for different inputs and push/pop are not "innocent", i.e., they will have a major impact on the performance. This is most obvious if they can be removed completely, because that allows Z3 to...

For Q1: No, you'd have to add your own timers on that and I would expect this to be nontrivial as it's not clear what exactly should and shouldn't be counted. Q2: Yes, you can build your own custom strategies/tactics. Note that par-or means parallel or, i.e., it will try...

I did a quick search and it appears that no obj::reset_statistics() is called between check-sat calls for various objs. There are a few re-initializations happening though, so no guarantee that any of this is precise enough for your purpose.

Even Z3 has multiple solvers, e.g., BMC, PDR (the default?), CLP (prolog-style reasoning), Datalog, and Duality. Choose with fixedpoint.engine=xx. There's also another engine coming soonish which is a port of HSF to Z3. (the original HSF is also available and is very reliable) There are other solvers out there, but...

I have just updated the ml-ng branch with a new set of build rules that should build and install a package that also works in the ocaml toplevel. See also the following discussion on codeplex: OCaml bindings status and compilation

Timeout through the API is definitely supported. Maybe 100ms on your Linux box is too much? Can you try with a smaller timeout? If it still fails, could you file a bug report with a short, self-contained, reproducing test case? Thanks!...

That is indeed correct. SMTLib uses a many-sorted first-order logic; so in your example A can be any sort, but it has to be a known sort; not a type-parameter. Having said that, SMTLib does allow uninterpreted sorts; that is, you can introduce new sorts with no underlying representation. (Just...

There isn't much more to it. For soft constraints the number on the right of "|->" is given as follows. Suppose we assert (assert-soft F1 :weight w1 :id first) (assert-soft F2 :weight w2 :id first) (assert-soft F3 :weight w3 :id first) And suppose M is a model maximal assignment that...

Here's a trick you might enjoy by parsing the SMT2 string via the Python API with parse_smt2_string ( http://research.microsoft.com/en-us/um/redmond/projects/z3/z3.html#-parse_smt2_string ): from z3 import * s = SolverFor("BV") #s.set(':pp.bv_literals', True) # gives error for some reason mask = BitVec('mask', 64) multiplicand = BitVec('multiplicand', 64) x = BitVec('x', 64) y = BitVec('y',...

The nlsat solver does not expose incrementality, so when you create multiple queries it will start from scratch. For your shorter formulas it may be the case that the search space is much bigger.

That sort of reasoning is indeed possible, through the use of uninterpreted sorts and functions. Be warned, however, that reasoning about such structures typically requires quantified axioms, and SMT-solvers are usually not terribly good at reasoning with quantifiers. Having said that, here's how I would go about it, using SBV....

sorting,z3,z3py,theorem-proving

This example is not well-formed SMT2, functions can not return multiple objects. The Z3 Guide for examples of how to use datatypes as well as quantifiers.

This is not necessarily a bug. The Groebner-basis computation solves the problem, so the unsat result is found quickly (it's good, so it's enabled by default). Further, disabling auto_config also means that a host of other options is not set up depending on the problem (but it doesn't make a...

Actually, interpolation for bit vector arithmetic is not supported. It's interesting that it works on the web version. That version is quite old, however, and I think it predates the source-available version of Z3. I can think of two possible reasons why it works: 1) That version of interpolating Z3...

so I couldn't get rid of the multiplications without restructuring the whole approach so what I did instead was moving the block with all the conditions (uc=1 or uc=1 and sum = 1) below the forAll block. This worked in most cases but there were still a few tests where...

You already have everything in place, but the constants 1 and 0 are not Boolean values; the corresponding values are true and false, i.e., this should work: (assert (= (not (ite (< t0 10) true false)) true)) ...

There may be some bug, but the following returns a model of x = 0 and z = 1, even though it gives unknown. Assuming the Python API also shows this model, you could create a simple hack to extract the model and add it to the assertions to check,...

The parser (Z3_parse_smtlib2_string) parses SMT-LIB2 benchmarks. Benchmarks in this format define a logical formula. This formula is "true" if the input does not contain any assertions. This is why the parser returns "true" in your case. Z3 doesn't expose parsing facilities for terms. You can work around this by creating...

The solver for non-linear constraints does not support core extraction so you will not be able to retrieve a core directly. You can implement a bisection search (quick-explain) on top of Z3 for a (minimal) core. It will require several calls so it depends on your application if it is...

The problem was with the concept of ownership of the expr and func_decl objects I created. As it happened with other solvers I worked with, once you give the object to the context, I supposed that the context took ownership of the object, so I could forget about it. It...

z3,topology,z3py,theorem-proving

It is possible that both a formula and the negation of the formula is consistent with respect to a background theory T. In particular, when T is not complete, then there are sentences that are neither consequences of T nor inconsistent with T. In your case the theory T is...

By default, Z3 uses the simplex engine and sometimes a Floyd Marshall engine to solve your constraints even when the logic is QF_IDL. In this case it uses the simplex engine, and the size of rows grows quadratically for this example. You can force the sparce difference logic solver by...

The expr class derive from ast which has a bool() operator that can be used for this purpose. This means we can simply write if (exp) cout << exp; (Internally expressions and ASTs are simply pointers, and they should be valid whenever the pointer is non-zero, so the bool() operator...

No, this is not possible, expr_vectors are just like normal vectors with fixed size and explicit indexing. That said, it may be possible to express your problem by the use of arrays (see e.g., the Arrays section in the tutorial); this may come at the cost of performance however, because...

I tried replicating this problem, but the substitution works fine for me. Here's the code I used: Symbol xs = ctx.mkSymbol("xs"); EnumSort xSort = ctx.mkEnumSort(xs, ctx.mkSymbol("A"),ctx.mkSymbol("B")); SetSort xSet = ctx.mkSetSort(xSort); Expr x = ctx.mkConst("x",xSet); Expr z = ctx.mkConst("z",xSet); Expr f_old = ctx.mkEq(x, z); System.out.println("old: " + f_old); Expr y =...

Apparently it is an issue with the precedence of the ^ operator. Using lhs = (x ^ y) + (2*(x&y)) makes the example work for me....

The example given in the answer to the question referred to is slightly out of date. A Solver() will pick a suitable tactic to solve the problem, and it appears that it picks a different one now. We can still get that behavior by using a SimpleSolver() (at a possibly...