在Python中求解具有多个解的二元方程

Question

您已经给出了方程，其中变量可以取值 0 和 1 (false = 0 true = 1)，并且方程的结果将始终为 1：

X  Y  Z  V  W
1, 0, 1, 0, 0
1, 1, 1, 1, 1
0, 0, 0, 1, 1
0, 1, 0, 0, 0

您可以将其重写为： （“+”=异或）

X + Z = 1
X + Y + Z + V + W = 1
V + W = 1
Y = 1

这个例子应该有 4 个解决方案：

  X  Y  Z  V  W
1)0, 1, 1, 0, 1 
2)0, 1, 1, 1, 0 
3)1, 1, 0, 0, 1 
4)1, 1, 0, 1, 0

有没有什么方法可以在不尝试所有选项的情况下计算这个值？

我尝试使用numpy，但没有找到任何使用布尔变量进行计数的函数。

Answer 1

也许您正在寻找这样的东西，不是很复杂，但可以完成工作。

在这里，您可以使用一组方程定义一个函数，以确保输入满足所有方程：

def xor_equations(x, y, z, v, w):
    equation1 = x ^ z
    equation2 = x ^ y ^ z ^ v ^ w
    equation3 = v ^ w
    equation4 = y

    return equation1==1 and equation2==1 and equation3==1 and equation4 ==1

^ 是异或运算符。 然后你只需尝试所有可能的组合..

def find_xor_solutions():
    solutions = []
    for x in range(2):
        for y in range(2):
            for z in range(2):
                for v in range(2):
                    for w in range(2):
                        if xor_equations(x, y, z, v, w):
                            solutions.append((x, y, z, v, w))
return solutions

# Find and print solutions
solutions = find_xor_solutions()
print(f"Solutions: {solutions}")

最后你应该有一个解决方案列表。

Answer 2

您可以像处理任何线性方程组一样获得所有解：

• 找到一个特定的解决方案（你已经有了

  0, 1, 1, 0, 1

  ）
• 然后求齐次方程的通解。

然后您可以将齐次方程的任何解添加到特定解中。

在你的情况下：方程组（写为矩阵）看起来像：

[1 0 1 0 0]
[1 1 1 1 1]
[0 0 0 1 1]
[0 1 0 0 0]

如果你应用高斯消去法，你会得到：

[1 0 1 0 0]
[0 1 0 0 0]
[0 0 0 1 1]
[0 0 0 0 0]

这现在意味着与变量的向量相乘。因此，对于齐次方程的通解，可以看出以下公式必须成立：

yh = 0
zh = xh
wh = vh

您可以自由选择

xh

和

vh

。

将其中任何一个添加到特定的解决方案中，您将获得所有解决方案：

from itertools import product

xp, yp, zp, vp, wp = (0, 1, 1, 0, 1)

yh = 0
for xh, vh in product(range(2), repeat=2):
    zh, wh = xh, vh
    x, y, z, v, w = (xp ^ xh, yp ^ yh, zp ^ zh, vp ^ vh, wp ^ wh)

    assert x ^ z == 1
    assert x ^ y ^ z ^ v ^ w == 1
    assert v ^ w == 1
    assert y == 1
    print(x, y, z, v, w)

获得：

0 1 1 0 1
0 1 1 1 0
1 1 0 0 1
1 1 0 1 0

没有不必要的循环。变量的所有设置都是方程的解。