Boolean equation

Question

$$\text{Solve for}\space{x, y}$$ $${a_1, a_2, a_3, a_4, b_1, b_2} \; \text{ - variables}$$ $$\left\{ \begin{aligned} {a_1}\&x \oplus {a_2}\&y &= {b_1} \\ {a_3}\&x \oplus {a_4}\&y &= {b_2} \end{aligned} \right.$$ I think that $x$ should be expressed from the first equation and then put that expression into the second equation. I don't know how to do it in boolean algebra. Is it possible do solve in that way?

Answer 1

To be honest, a long time passed since I had to manipulate boolean functions, so take this more like a long comment than like an actual answer...

From a practical point of view, if I had to solve that system I would just try the $4$ possible combined values of $x$ and $y$, i.e., $(x,y)$ equal to $(0,0)$, $(0,1)$, $(1,0)$ and $(1,1)$ to see which are solutions of the system, given the current values of the parameters.

If this was a practical problem I would generate in advance the $2^6=64$ possible combination of the parameters $a_i$ and $b_j$, and I would solve the system for all the possibilities and store the result.

But I have to assume this is not a practical problem.

To search for a general solution, I suggest to convert this system in a linear system in $\Bbb Z_2$, i.e., roughly speaking to work modulo $2$.

In practice we can use all the common rules of arithmetic but working modulo $2$ we have that $1+1=2\equiv0\pmod2$.

It is easy to see that the XOR operation in boolean arithmetic is just the sum modulo 2 and the AND operation is just the multiplication modulo 2. A bonus of working modulo $2$ is the $-1\equiv 1\pmod 2$, thus doing $a+b$ or $a-b$ is the same. So we can just turn our subtractions into additions.

So we can just consider this system $$\left\{ \begin{array}{l} a_1\cdot x + a_2\cdot y = b_1 \\ a_3\cdot x + a_4\cdot y = b_2 \end{array} \right. $$ in $\Bbb Z_2$.

This is a linear system and we know everthing is fine if the determinant $$ a_1\cdot a_4-a_3\cdot a_2 = a_1\cdot a_4 + a_3\cdot a_2 = (a_1 \& a_4)\oplus(a_3\&a_2) $$ is different from $0$. So for the moment we assume that the determinant is $1$, i.e., that $(a_1 \& a_4)\oplus(a_3\&a_2) = \mathrm{true}$.

If the determinant $\Delta$ is different from $0$ then the general solution of the $2\times 2$ linear system above is $$ x = \frac{a_4\cdot b_1-a_2\cdot b_2}{\Delta}\,,\quad y = \frac{a_1\cdot b_2-a_3\cdot b_1}{\Delta} $$ Since here we are assuming that $\Delta=1$ and since difference is like addiction in $\Bbb Z_2$, we can say that if $(a_1 \& a_4)\oplus(a_3\&a_2) = \mathrm{true}$ the the solution is $$x=(a_4\&b_1)\oplus(a_2\&b_2)\,,\quad y=(a_1\&b_2)\oplus(a_3\&b_1).$$

Unfortunately only 6 of the $2^4=16$ possible values of $a_1,a_2,a_3,a_4$ lead to a nonzero determinant, in the other $10$ cases we can have $0$, $1$ or multiple solutions.

But I don't know if there is a way to treat the case where the determinant is equal to $0$ in a general way, without knowing the actual parameters, because the various cases can present also depending on the $b_j$.

For example, if the $a_i$ are all equal to $1$, then, if $b_1\neq b_2$ then there are no solutions, if $b_1=b_2=0$ then there are two solutions, namely $x=y=0$ and $x=y=1$. If $b_1=b_2=1$ then there are two solution, $(x,y)=(0,1)$ and $(x,y)=(1,0)$.

And so on, for the various combinations of the parameters.

Answer 2

The construct $z=x\cdot y = x \& y$ where $x,y,z \in \{0,1\}$ can be expressed as linear inequalities: $$\begin{align} &z \le x\\ & z \le y \\ & z \ge x+y-1 \end{align}$$ For $z = x <> y = x \text{ xor } y$ we have $$\begin{align} &z \le x+y\\ & z \ge x-y \\ & z \ge y-x \\ & z \le 2 -x - y \end{align}$$