getting unsat core using Z3_solver_get_unsat_core

2019-05-26 03:23发布

问题:

suppose that here is the set of constraints on nonlinear real arithmetic like

pred1 = (> (- (* (- v2_x v0_x) (- v1_y v0_y)) (* (- v2_y v0_y) (- v1_x v0_x))) 0)
pred2 = (> (- (* (- v1_x v0_x) (- v2_y v0_y)) (* (- v1_y v0_y) (- v2_x v0_x))) 0)

In fact, if we do

Z3_solver_assert(ctx,solver,pred1);
Z3_solver_assert(ctx,solver,pred2);
b = Z3_solver_check(ctx, solver);

b would be unsat. I want to obtain the unsat core (for this example is trivial). So, for each of these predicates I defined a predicate variable. Lets say they are p1 and p2.

Z3_ast p1 = mk_bool_var(ctx, "P1");
assumptions[i] = Z3_mk_not(ctx, p1);
Z3_ast g[2] = { pred1, p1 };
Z3_solver_assert(ctx,solver,Z3_mk_or(ctx, 2, g));
Z3_ast p2 = mk_bool_var(ctx, "P2");
assumptions[i] = Z3_mk_not(ctx, p2);
Z3_ast g[2] = { pred2, p2 };
Z3_solver_assert(ctx,solver,Z3_mk_or(ctx, 2, g));

and then I call Z3_solver_check_assumptions(ctx, solver, 2 , assumptions);

but this returns Z3_L_UNDEF and the reason is (incomplete (theory arithmetic))

I am wondering where I am making a mistake and how this issue can be solved.

Here is how things are initialized:

  ctx = Z3_mk_context(cfg);
  Z3_symbol logic_symbol = Z3_mk_string_symbol(ctx, "QF_UFNRA");
  solver = Z3_mk_solver_for_logic((Z3_context)ctx, logic_symbol);
  Z3_solver_inc_ref(ctx, solver);
  Z3_params params = Z3_mk_params(ctx);
  Z3_symbol param_symbol = Z3_mk_string_symbol(ctx, "unsat_core");
  Z3_params_set_bool(ctx , params, param_symbol, Z3_L_TRUE);
  Z3_solver_set_params(ctx, solver, params); 

Thanks,

回答1:

Z3 contains many solvers. For nonlinear arithmetic problems it uses nlsat. The implementation of this solver is located in the directory src/nlsat, and the algorithm is explained here. However, the current nlsat implementation does not support unsat core extraction nor proof generation. When unsat core extraction is requested by the user, Z3 switches to a general purpose solver which is incomplete for nonlinear arithmetic. That is, it may return unknown for nonlinear arithmetic problems. The general purpose solver has support for many theories, quantifier, unsat core extraction, and proof generation. It is complete for linear arithmetic, but as I said it is not complete for the nonlinear fragment. In the plan, Z3 will have a new version of nlsat that is integrated with other theories and support unsat core extraction, but this is future work.



标签: z3