(Z3Py)检查方程的所有解

Question

在Z3Py中,如何检查给定约束的方程是否只有一个解？

如果有多个解决方案,我该如何枚举它们？

Answer 1

您可以通过添加阻止Z3返回的模型的新约束来实现.例如,假设在Z3返回的模型中我们有x = 0和y = 1.然后,我们可以通过添加约束来阻止此模型Or(x != 0, y != 1).以下脚本可以解决问题.您可以在线试用:http://rise4fun.com/Z3Py/4blB

请注意,以下脚本有一些限制.输入公式不能包含未解释的函数,数组或未解释的排序.

from z3 import *

# Return the first "M" models of formula list of formulas F 
def get_models(F, M):
    result = []
    s = Solver()
    s.add(F)
    while len(result) < M and s.check() == sat:
        m = s.model()
        result.append(m)
        # Create a new constraint the blocks the current model
        block = []
        for d in m:
            # d is a declaration
            if d.arity() > 0:
                raise Z3Exception("uninterpreted functions are not supported")
            # create a constant from declaration
            c = d()
            if is_array(c) or c.sort().kind() == Z3_UNINTERPRETED_SORT:
                raise Z3Exception("arrays and uninterpreted sorts are not supported")
            block.append(c != m[d])
        s.add(Or(block))
    return result

# Return True if F has exactly one model.
def exactly_one_model(F):
    return len(get_models(F, 2)) == 1

x, y = Ints('x y')
s = Solver()
F = [x >= 0, x <= 1, y >= 0, y <= 2, y == 2*x]
print get_models(F, 10)
print exactly_one_model(F)
print exactly_one_model([x >= 0, x <= 1, y >= 0, y <= 2, 2*y == x])

# Demonstrate unsupported features
try:
    a = Array('a', IntSort(), IntSort())
    b = Array('b', IntSort(), IntSort())
    print get_models(a==b, 10)
except Z3Exception as ex:
    print "Error: ", ex

try:
    f = Function('f', IntSort(), IntSort())
    print get_models(f(x) == x, 10)
except Z3Exception as ex:
    print "Error: ", ex

Answer 2

Himanshu Sheoran 给出的答案引用了论文https://theory.stanford.edu/%7Enikolaj/programmingz3.html#sec-blocking-evaluations

不幸的是，当时论文中给出的实现存在一个错误，该错误在该答案中被引用。此后该功能已得到更正。

对于后代，这是代码的正确版本：

def all_smt(s, initial_terms):
    def block_term(s, m, t):
        s.add(t != m.eval(t, model_completion=True))
    def fix_term(s, m, t):
        s.add(t == m.eval(t, model_completion=True))
    def all_smt_rec(terms):
        if sat == s.check():
           m = s.model()
           yield m
           for i in range(len(terms)):
               s.push()
               block_term(s, m, terms[i])
               for j in range(i):
                   fix_term(s, m, terms[j])
               yield from all_smt_rec(terms[i:])
               s.pop()   
    yield from all_smt_rec(list(initial_terms))