8
$\begingroup$

how can i solve this set of equations ? to get values of $x,y,z,w$ ?
$\begin{aligned} 1=x \oplus y \oplus z \end{aligned}$ $\begin{aligned}1=x \oplus y \oplus w \end{aligned}$ $\begin{aligned}0=x \oplus w \oplus z \end{aligned}$ $\begin{aligned}1=w \oplus y \oplus z \end{aligned}$

this is not a real example, the variables don't have to make sense, i just want to know the method.

  • 2
    As for every linear system. Recall that XOR is just addition modulo 2.2012-07-12

6 Answers 6

12

As I wrote in my comment, you can just use any method you know for solving linear systems, I will use Gauss:

$ \begin{array}{cccc|c||l} \hline x & y & z & w &\ & \\ \hline\hline 1 & 1 & 1 & 0 & 1 & \\ 1 & 1 & 0 & 1 & 1 & \text{$+$ I}\\ 1 & 0 & 1 & 1 & 0 & \text{$+$ I}\\ 0 & 1 & 1 & 1 & 1 & \\ \hline 1 & 1 & 1 & 0 & 1 & \\ 0 & 0 & 1 & 1 & 0 & \text{III}\\ 0 & 1 & 0 & 1 & 1 & \text{II}\\ 0 & 1 & 1 & 1 & 1 & \text{$+$ III}\\ \hline 1 & 1 & 1 & 0 & 1 & \\ 0 & 1 & 0 & 1 & 1 & \\ 0 & 0 & 1 & 1 & 0 & \\ 0 & 0 & 1 & 0 & 0 & \text{$+$ III}\\ \hline 1 & 1 & 1 & 0 & 1 & \\ 0 & 1 & 0 & 1 & 1 & \\ 0 & 0 & 1 & 1 & 0 & \\ 0 & 0 & 0 & 1 & 0 & \\\hline \end{array} $ Now we can conclude $w = 0$ from line 4, which gives $z = 0$ from 3 and $y = 1$ from 2, and finally $x = 0$. So $(x,y,z,w) = (0,1,0,0)$ is the only solution.

  • 0
    im having a hard time understanding how gaussian works when using binary, especially with multiplication and division.. can you explain to me using your own words? :)2012-07-14
9

I'll try it the 'artisanal way'.

These four rules should be enough : $\begin{align} &x\oplus 0=x\\ &x\oplus 1=\overline{x}\\ &x\oplus x=0\\ &x\oplus \overline{x}=1\\ \end{align}$

$\tag{1}1=x\oplus y\oplus z$
$\tag{2}1=x\oplus y\oplus w$
$\tag{3}0=x\oplus w\oplus z$
$\tag{4}1=w\oplus y\oplus z$

Applying $x\oplus$ on the three first equations and $w\oplus$ on the last gives :

$\tag{5}\overline{x}=y\oplus z$
$\tag{6}\overline{x}=y\oplus w$
$\tag{7}x= w\oplus z$
$\tag{8}\overline{w}=y\oplus z$

$(6)\oplus(7)\ $ gives $\ \tag{6'}1=y\oplus z$ so that from $(8)$ $w=0$
from $(7)$ and $(6)$ $\ x=z$ and $\ \overline{x}=y$
from $(5)$ $\ \overline{x}=1$ and the final conclusion :
$(w,x,y,z)=(0,0,1,0)$ as found (earlier) by martini...

5

As others have noted, all the usual methods of solving systems of linear equations (such as Gaussian elimination) in the field of real numbers work just as well in the finite field of integers modulo 2, also known as $GF(2)$.

In this field, addition corresponds to the XOR operation, while multiplication corresponds to AND (as it does in the reals, if the operands are restricted to $0$ and $1$). As both $0$ and $1$ are their own additive inverses in $GF(2)$ (since $0 \oplus 0 = 1 \oplus 1 = 0$), subtraction is also equivalent to XOR, while division is trivial (dividing by $1$ does nothing, dividing by $0$ is undefined).


So, let's try solving your example equations. Since martini already did Gaussian elimination, let me do Gauss–Jordan:

$\begin{array}{rcrcrcrcr} 1x & \oplus & 1y & \oplus & 1z & \oplus & 0w & = & 1 \\ 1x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 1x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 1y & \oplus & 1z & \oplus & 1w & = & 1 \\ \end{array}$

The first coefficient of the first equation is already $1$, so we just subtract (XOR) that equation from the second and the third:

$\begin{array}{rcrcrcrcr} 1x & \oplus & 1y & \oplus & 1z & \oplus & 0w & = & 1 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 0x & \oplus & 1y & \oplus & 1z & \oplus & 1w & = & 1 \\ \end{array}$

Now the second coefficient of the second equation is $0$, so we need to choose some later row that has a $1$ for that coefficient and swap those rows:

$\begin{array}{rcrcrcrcr} 1x & \oplus & 1y & \oplus & 1z & \oplus & 0w & = & 1 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 1y & \oplus & 1z & \oplus & 1w & = & 1 \\ \end{array}$

... and then subtract that row from all the others with a non-zero second coefficient:

$\begin{array}{rcrcrcrcr} 1x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 0w & = & 0 \\ \end{array}$

Then we subtract the third row from those with a non-zero third coefficient:

$\begin{array}{rcrcrcrcr} 1x & \oplus & 0y & \oplus & 0z & \oplus & 0w & = & 0 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 1w & = & 1 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 1w & = & 0 \\ 0x & \oplus & 0y & \oplus & 0z & \oplus & 1w & = & 0 \\ \end{array}$

... and finally the fourth row from those with a non-zero fourth coefficient:

$\begin{array}{rcrcrcrcr} 1x & \oplus & 0y & \oplus & 0z & \oplus & 0w & = & 0 \\ 0x & \oplus & 1y & \oplus & 0z & \oplus & 0w & = & 1 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 0w & = & 0 \\ 0x & \oplus & 0y & \oplus & 0z & \oplus & 1w & = & 0 \\ \end{array}$

And now we can read out the result: $x = 0$, $y = 1$, $z = 0$, $w = 0$.

  • 1
    @Alexander: Uh... magic? Definitely magic. Or I guess I just might have made a typo there...2017-02-01
2

The other answers are fine, but you can use even more elementary (if somewhat ad hoc) methods, just as you might with an ordinary system of linear equations over $\Bbb R$. You have this system:

$\left\{\begin{align*} 1&=x\oplus y\oplus z\\ 1&=x\oplus y\oplus w\\ 0&=x\oplus w\oplus z\\ 1&=w\oplus y\oplus z \end{align*}\right.$

Add the first two equations:

$\begin{align*} (x\oplus y\oplus z)\oplus(x\oplus y\oplus w)&=(z\oplus w)\oplus\Big((x\oplus y)\oplus(x\oplus y)\Big)\\ &=z\oplus w\oplus 0\\ &=z\oplus w\;, \end{align*}$

and $1\oplus 1=0$, so you get $z+w=0$. Substitue this into the last two equations to get $0=x\oplus 0=x$ and $1=y\oplus 0=y$. Now you know that $x=0$ and $y=1$ so $x\oplus y=1$. Substituting this into the first two equations, we find that $1=1\oplus z$ and $1=1\oplus w$. Add $1$ to both sides to get $0=z$ and $0=w$. The solution is therefore $x=0,y=1,z=0,w=0$.

0

Fast Walsh–Hadamard Transform used to solve system of boolean linear equations with distorted right-hand sides. See implementation on https://fwht.codeplex.com/

0

as stated:

$(x \oplus y) \oplus z = 1 = (x \oplus y) \oplus w \Longrightarrow z = w$

as stated:

$x \oplus ( y \oplus w ) = 1 = ( w \oplus y ) \oplus z \Longrightarrow x = z$ (AS $a \oplus b = b \oplus a$ ) SO $x = z = w$

substitute our 2nd conclusion:

$0 = x \oplus w \oplus z = x \oplus x \oplus z = 0 \oplus z = z \Longrightarrow x = z = w = 0$ (AS $a \oplus a = 0$)

substitute our 3rd conclusion:

$1 = x \oplus y \oplus w = 0 \oplus y \oplus 0 = 0 \oplus y = y \Longrightarrow y = 1$