Z3 Prover returns 错误解

Question

我正尝试在 Python 中使用 Z3 Thoerem Prover 求解方程。但是我得到的解决方案是错误的。

from z3 import *    
solv = Solver()
x = Int("x")
y = Int("y")
z = Int("z")
s = Solver()
s.add(x/(y+z)+y/(x+z)+z/(x+y)==10, x>0, y>0, z>0)
s.add()
print(s.check())
print(s.model())

我得到了这个解决方案：

[z = 60, y = 5, x = 1]

但是当您将这些值填入给定的等式时，结果是：10.09735182849937。但我想找到的是一个精确的解决方案。我做错了什么？

感谢您的帮助:)

Answer 1

我试过你的代码和一个修改后的代码，我将整个方程乘以 (x+y)*(x+z)*(y+z) 以消除除法：

solv = Solver()
x = Int("x")
y = Int("y")
z = Int("z")
s = Solver()
# s.add(x/(y+z)+y/(x+z)+z/(x+y)==10, x>0, y>0, z>0)
s.add(x*(x+z)*(x+y) + y*(y+z)*(x+y) + z*(y+z)*(x+z) == 10*(x+y)*(x+z)*(y+z), x > 0, y > 0, z > 0)
s.add()
print(s.check())
print(s.model())

我在 Windows 下使用 Z3 4.4.1。

修改代码returns"unknown"，因为Z3无法解决。正如 MiniZinc 和 Excel.

等其他求解器所证实的那样，可能没有解决方案

您的原始代码 returns [x=1, y=1, z=20] 是正确的，如果假定整数除法：

x/(y+z) = 1/(1+20) is 0 for integer division
y/(x+z) = 1/(1+20) is 0 for integer division
z/(x+y) = 20/(1+1) is 10

Answer 2

简短的回答是四舍五入，因此答案是正确的，但不是您所期望的。请注意，通过作业 Z3 发现您有：

1/65 + 5/61 + 60/6 = 10

因为前两项四舍五入为 0。您可以乘以公分母使等式变平，并将其设为 z3。但这也不太可能奏效，因为您将有一个非线性丢番图方程，而 Z3 没有针对该片段的决策程序。事实上，众所周知，非线性整数运算是不可判定的。详见希尔伯特第十题：https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem

事实上，人们对这种方程式了解很多：它定义了一条椭圆曲线。对于奇数N，已知无解。对于甚至 N（即您使用 N=10 的情况）解决方案可能存在也可能不存在，并且当它们存在时，它们可能非常大。当我说大的时候，我是认真的：对于 N=10 已知有一个解决方案，其中令人满意的值有 190 位！

这是一篇关于这个方程式的好文章，包含所有血淋淋的细节：http://ami.ektf.hu/uploads/papers/finalpdf/AMI_43_from29to41.pdf

还有一个绝对更容易理解的 quora 讨论：https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4

长话短说，z3（或与此相关的任何 SMT 求解器）根本不是 solve/approach 此类问题的正确工具。

Z3 Prover returns 错误解

Z3 Prover returns wrong solution

python

z3

z3py