Solving special boolean equation set I have boolean equation sets that look like this (where ^ means xor):

eq 1: x1^x3^x5^x6^x9^x10^x11^x13^x17^x18 = 0
eq 2: 1^x1^x3^x10^x12^x17 = 0
eq 3: 1^x2^x3^x5^x8^x10^x14^x16 = 0
eq 4: 1^x4^x5^x6^x7^x8^x10^x16^x17 = 0
eq 5: x2^x5^x8^x11^x13^x14^x17^x18 = 0

(This example has 18 vars and 5 equations, but imagine a thousand variables with a hundred equations).
I can easily find solutions for this by successive subtitutions, but is there any way to quickly generate solution(s) with the least number of variables set to true ?
Thanks!
 A: We can phrase the problem as follows:

Given $M \in \mathbb{F}_2^{m\times n}$ and $b \in \mathbb{F}_2^m$ with $n>m$, find the solution $x \in \mathbb{F}_2^n$ to $Mx=b$ for which $\sum_{i=1}^n x_i$ is minimized.

That is, this may be regarded as a "linear programming" problem, of sorts.  Below is my initial attempt at a solution, which was not particularly fruitful.

We can write this particular system as the matrix equality
$$
M\,x = b
$$
Where $M$ is the matrix of coefficients (either $1$ or $0$) of $x_1,\dots,x_{18}$, $x = \pmatrix{x_1&\dots&x_{18}}^T$, and $b = \pmatrix{0&1&1&1&0}^T$ (corresponding to whether the equation contains a "1^"). With row reduction, we can determine how many of $x_1,\dots,x_{18}$ are "free variables", i.e. variables that may be arbitrarily set to true or false.  The key here is to note that we define multiplication and addition over these elements/coefficients in $\{0,1\}$ as follows:
$$
a+b = a\text{ XOR } b\\
a\cdot b = a \text{ AND } b
$$
This is the definition of $\mathbb{F}_2$.

Let's take an example.  Suppose we have the system
x1 ^ x2 ^ x3 == 0
x2 ^ x3 ^ x4 == 1
x3 ^ x4 ^ x5 == 1

We can write this as
$$
\pmatrix{
1&1&1&0&0\\
0&1&1&1&0\\
0&0&1&1&1}
\pmatrix{x_1 \\ \vdots \\ x_5} =
\pmatrix{0 \\ 1 \\ 1}
$$
We can now row reduce the augmented matrix $(M\mid b)$ to get
$$
\pmatrix{
1&1&1&0&0&0\\
0&1&1&1&0&1\\
0&0&1&1&1&1}
\implies\\
\left(
\begin{array}{cccccc}
 1 & 0 & 0 & -1 & 0 & -1 \\
 0 & 1 & 0 & 0 & -1 & 0 \\
 0 & 0 & 1 & 1 & 1 & 1 \\
\end{array}
\right)=
\left(
\begin{array}{cccccc}
 1 & 0 & 0 & 1 & 0 & 1 \\
 0 & 1 & 0 & 0 & 1 & 0 \\
 0 & 0 & 1 & 1 & 1 & 1 \\
\end{array}
\right)
$$ 
That is, the system may be rewritten as
x1     ^     x4       == 1
    x2 ^           x5 == 0
         x3 ^ x4 ^ x5 == 1

So that $x_4,x_5$ may be freely chosen, and the values of $x_1,x_2,x_3$ may be solved for as
x1 == 1 ^ x4
x2 == x5
x3 == 1^x4^x5

Hope that makes sense.

NOTE: this may not be as useful for the particular problem as I originally thought.
