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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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