Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
As for every linear system. Recall that XOR is just addition modulo 2. –  martini Jul 12 '12 at 13:04

6 Answers 6

up vote 8 down vote accepted

As I wrote in my comment, you can just use any method you now 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.

share|improve this answer
    
can you explain please martini ? :) –  Salma Nafady Jul 12 '12 at 13:25
    
@SalmaNafady Do you know Gauss' elemination method (see for example here)? –  martini Jul 12 '12 at 13:27
    
Thanks for the answer martini :) one more thing, what if the variables are matrices? ex: [1,0,0,1]=x⊕y⊕z [0,1,0,1]=x⊕y⊕w etc ? –  Salma Nafady Jul 12 '12 at 16:30
    
Just consider each component seperately ... –  martini Jul 12 '12 at 20:13
    
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? :) –  Salma Nafady Jul 14 '12 at 15:59

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...

share|improve this answer

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 & = & 0 \\ 0x & \oplus & 0y & \oplus & 1z & \oplus & 0w & = & 1 \\ 0x & \oplus & 0y & \oplus & 0z & \oplus & 1w & = & 0 \\ \end{array}$$

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

share|improve this answer

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$.

share|improve this answer

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

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.