Solving binary equations with multiple solutions in Python

Question

You have given equations where the variables can take on the values 0 and 1 (false = 0 true = 1) and the result of the equation will always be 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

You can rewrite it as: (“+” = XOR)

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

This example should have 4 solutions:

  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

Is there any way to calculate this without trying all the options?

I tried to use numpy, but I didn't find any function for counting with boolean variables.

Answer 1

you get all the solutions the same way you would for any system of linear equations:

• find one particular solution (you already have 0, 1, 1, 0, 1)
• then find the general solution to the homogenous equation.

you can then add any solution of the homogenous equation to the particular solution.

in your case: the system of equations (written as matrix) looks like:

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

if you apply gaussian elimination to that you get:

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

this is now meant to be multiplied with the vector of the variables. so the for the general solution to the homogenous equation can read off that the following must hold:

yh = 0   # from [0 1 0 0 0]
zh = xh  # from [1 0 1 0 0]
wh = vh  # from [0 0 0 1 1]

and you are free to choose xh and vh.

add any of those to the particular solution and you get all the solutions:

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)

to get:

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

there are no unnecessary loops. all settings of the variables are solutions to your equations.

---

Update:

(disclaimer: none of this is really tested...)

in order to get the echelon form of your equations, you could install galois and sympy and use them like this:

for this you need to:

pip install galois numpy sympy

then:

from galois import GF2
from numpy import  hstack, dot
from numpy.linalg import solve, LinAlgError
from itertools import combinations

from sympy import Matrix, symbols
from sympy import solve_linear_system

A = GF2((
    (1, 0, 1, 0, 0,),
    (1, 1, 1, 1, 1),
    (0, 0, 0, 1, 1),
    (0, 1, 0, 0, 0),
))
b = GF2(((1, 1, 1, 1),)).T
Ab = hstack((A, b))
# GF([[1, 0, 1, 0, 0, 1],
#     [1, 1, 1, 1, 1, 1],
#     [0, 0, 0, 1, 1, 1],
#     [0, 1, 0, 0, 0, 1]], order=2)

gaussian elimination:

Ab_reduced = Ab.row_space()
# GF([[1, 0, 1, 0, 0, 1],
#     [0, 1, 0, 0, 0, 1],
#     [0, 0, 0, 1, 1, 1]], order=2)

A_reduced = Ab_reduced[:, :-1]
# GF([[1, 0, 1, 0, 0],
#     [0, 1, 0, 0, 0],
#     [0, 0, 0, 1, 1]], order=2)

b_reduced = Ab_reduced[:, -1:]
# GF([[1],
#     [1],
#     [1]], order=2)

i could not find a function in numpy that directly finds a particular solution. such a function might exist (?).

i counted the number of variables and the number of equations, set n_vars-n_eqs variables to zero and hoped to find a solution for the remaining variables using solve:

n_eqs, n_vars = A_reduced.shape

for idx in combinations(range(n_vars), r=n_eqs):
    try:
        sol = solve(A_reduced[:,idx], b_reduced)
        break
    except LinAlgError:
        pass

particular_solution = n_vars * [0]
for j, i in enumerate(idx):
    particular_solution[i] = int(b_reduced[j])
particular_solution = GF2(particular_solution)
# GF([1, 1, 0, 1, 0], order=2)

then, for the general solution i used sympy (which is unaware of GF(2) and might not always work as expected?)

zero_col = GF2((zeros(n_eqs, dtype=int), )).T
x, y, z, v, w = symbols("x y z v w")
A_homogenous = hstack((A_reduced, zero_col))
solve_linear_system(Matrix(A_homogenous), x, y, z, v, w)
# {x: -z, y: 0, v: -w}

the -z shows, that sympy does not know about GF(2). but in this case it works all the same.