Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
@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').

share|cite|improve this answer

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

share|cite|improve this answer

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
share|cite|improve this answer

Your Answer


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.