# Boolean Algebra: Simplifying multiple XOR and XNOR

Is there any way to simplify a combination of XOR and XNOR gates in the following expression? I have tried multiple boolean theorems and I have not been able to simplify this any further:

The simplified version is XOR(A,B)*XNOR(C,D) + XOR(C,D)*XNOR(A,B)

The actual expression is: (A'B + AB')(CD + C'D') + (AB + A'B')(C'D + CD')

According to my lab, this expression can be simplified, but I don't know where to start.

I guess you could look at each element, such as (A'B + AB') as a single variable, such as X and then the equation would be XY' + X'Y, but I still don't see how to simplify that.

-
Note that XOR is boolean inequality, so that XNOR is actually just a very complicated way to write boolean equality. – Marnix Klooster Jan 11 '15 at 20:48

You're on the right track. Note that $X\bar Y + \bar X Y$ is exactly $X\oplus Y$ (where $\oplus$ is XOR), so you can simplify to $$(A\oplus B) \oplus (C\oplus D)$$ Since $\oplus$ is associative and commutative, this simplifies further to $$A\oplus B\oplus C\oplus D$$ which is particularly nice because it's a linear function of the inputs in the associated Boolean ring (whose multiplication is conjunction and addition is $\oplus$).

-
@miracle173: Good catch. I have no idea where I got the idea that $Y$ would be $\overline{C\oplus D}$ rather than just $C\oplus D$. – Henning Makholm Sep 20 '13 at 21:43
Could you please clarify what you mean by "linear function" in this context? it seems you that $$(Z \land A) \oplus (Z \land B) \oplus \dots \;=\; Z \land (A \oplus B \oplus \dots)$$ (since $\;\land\;$ distributes over $\;\oplus\;$, just like $\;\lor\;$ distributes over $\;\equiv\;$) and $$(A1 \oplus A2) \oplus (B1 \oplus B2) \oplus \dots \;=\; (A1 \oplus B1 \oplus \dots) \oplus (A2 \oplus B2 \oplus \dots)$$ (since $\;\oplus\;$ is associative and symmetric, just like $\;\equiv\;$). Am I correct? – Marnix Klooster Jan 12 '15 at 7:44
@MarnixKlooster: Your identities are correct. A "linear function" here, is just like any other linear function in linear algebra: $$f(x_1,x_2,\ldots,x_n) = a_1x_1+a_2x_2+\cdots+a_nx_n$$ In the Boolean ring of truth values the coefficients $a_i$ are either T (that is, 1 in the ring) or F (0 in the ring), so a linear function ends up simply being the XOR of some subset of the inputs. It is still nice to be able to use the tools of linear algebra to reason about it, though. – Henning Makholm Jan 12 '15 at 11:49

The definition (xor, xnor) of XOR(A,B)is A'B + AB' and of XNOR(C,D) is CD+C'D'. So XOR(A,B)*XNOR(C,D) + XOR(C,D)*XNOR(A,B) is a direct translation of (A'B + AB')(CD + C'D') + (AB + A'B')(C'D + CD').

-

In plain boolean algebra: XOR = (a || b) && !(a && b)

-

Keep in mind that XNOR is "XOR NOT" and as stated above: AB'+ A'B = A XOR B, AB + A'B' = A XNOR B = (A XOR B)'

So, the steps for (A'B + AB')(CD + C'D') + (AB + A'B')(C'D + CD')

              = (A XOR B)(C XNOR D) + (A XNOR B)(C XOR D)
= (A XOR B)(C XOR D)' + (A XOR B)'(C XOR D)
= (A XOR B) XOR (C XOR D)
= A XOR B XOR C XOR D

-