如何在Python中求解多解二元布尔异或方程？

给定变量取值为0（假）和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

可改写为以“+”表示异或（XOR）的形式：

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，但未找到适用于布尔变量计数的函数。

当然有不用枚举所有可能的方法，这类问题本质是二元域GF(2)上的线性方程组求解，异或运算就是GF(2)里的加法，0和1是域内元素，直接用线性代数方法处理即可，无需暴力枚举。

具体步骤 #

• 转化为标准形式：
  GF(2)下的线性方程组标准形式为 Ax = b，其中A是系数矩阵，x是变量构成的列向量[X,Y,Z,V,W]^T，b是方程右侧常数项构成的列向量[1,1,1,1]^T。对应到本例的系数矩阵A和常数项b如下：

  A = [[1,0,1,0,0],
       [1,1,1,1,1],
       [0,0,0,1,1],
       [0,1,0,0,0]]
  b = [1,1,1,1]
  

• 用符号库求解：
  可以用sympy这类符号计算库直接在GF(2)域下求解，无需手动枚举：

  • 将矩阵和向量转换为GF(2)域的形式
  • 求解得到方程组的一个特解，再求出对应齐次方程组Ax=0的零空间（基础解系）
  • 所有解就是特解加上零空间中向量的所有线性组合（GF(2)里的组合运算就是异或）

示例代码（sympy实现） #

from sympy import Matrix, GF
from itertools import product

# 构造系数矩阵和常数项向量
A = Matrix([[1,0,1,0,0], [1,1,1,1,1], [0,0,0,1,1], [0,1,0,0,0]])
b = Matrix([1,1,1,1])

# 转换到GF(2)域
A_gf2 = A.applyfunc(lambda x: x % 2)
b_gf2 = b.applyfunc(lambda x: x % 2)

# 求解方程组，得到特解和零空间
particular_sol, null_space = A_gf2.gauss_jordan_solve(b_gf2)

# 生成所有解：零空间有2个向量，共2^2=4种组合
all_solutions = []
for coeffs in product([0,1], repeat=null_space.shape[1]):
    sol = particular_sol + sum(coeff * null_space[:,i] for i, coeff in enumerate(coeffs))
    all_solutions.append([int(val) for val in sol])

# 打印结果
print("所有解：")
for idx, sol in enumerate(all_solutions, 1):
    print(f"{idx}){sol[0]}, {sol[1]}, {sol[2]}, {sol[3]}, {sol[4]}")

运行这段代码会直接输出题目中的4组解，全程不需要枚举所有32种变量组合。

关于numpy的补充 #

numpy本身没有原生支持GF(2)域的线性方程组求解，但可以手动实现GF(2)下的高斯消元逻辑，或者对普通矩阵运算做模2处理。不过sympy的实现更简洁，适合快速解决这类问题。

内容的提问来源于stack exchange，提问作者zuiop play