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

Let $\mathbb{B} = \{0,1\}$ denote the Boolean domain.

Its well known that both exclusive OR and logical biconditional make $\mathbb{B}$ into an Abelian group (in the former case the identity is $0$, in the latter the identity is $1$).

Furthermore, I was playing around and noticed that these two operations 'associate' over each other, in the sense that $(x \leftrightarrow y) \oplus z$ is equivalent to $x \leftrightarrow (y \oplus z).$

This is easily seen via the following chain of equivalences.

  1. $(x \leftrightarrow y) \oplus z$
  2. $(x \leftrightarrow y) \leftrightarrow \neg z$
  3. $x \leftrightarrow (y \leftrightarrow \neg z)$
  4. $x \leftrightarrow (y \oplus z)$

Anyway, my question is, what are the major connections between the operations of negation, biconditional, and exclusive OR? Furthermore, does $(\mathbb{B},\leftrightarrow,\oplus,\neg)$ form any familiar structure? I know that the binary operations don't distribute over each other, so its not a ring.

share|cite|improve this question
I suspect you'll see the term "modular" for (x↔y)⊕z being equivalent to x↔(y⊕z). – Doug Spoonwood Jun 15 '13 at 18:50
I could be stupid here, but does it help to write $x \leftrightarrow y = x + y + 1$ and $\neg x = x + 1$? (At least this explains association and those equivalences, in my opinion.) – Tunococ Jul 5 '13 at 9:16
@Tunococ, looks pretty sensible to me. – goblin Jul 5 '13 at 9:47

You have defined a function $F(x,y,z)$ that is true if an even number of the arguments is true and false if an odd number of the arguments is true. None of your expressions make that obvious. The true ones form a subgroup of $\Bbb Z_8$ under addition, corresponding to the even elements in (one of) the obvious way(s).

share|cite|improve this answer
The most obvious way of showing this relationship is that $F(x,y,z)=\neg(x\oplus y\oplus z)$, and the OP's relation follows from the associativity of $\oplus$. – Mario Carneiro Jun 12 '13 at 7:06

You probably already know this, but the immediate connection between them is $(x\oplus y) \leftrightarrow \neg(x \leftrightarrow y)$. Then the exclusive OR reduces trivially to the biconditional, and vice versa.

share|cite|improve this answer
Yep. We can also write $(x \oplus y) \oplus (x \leftrightarrow y),$ just to be cute! – goblin Jun 12 '13 at 6:46

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.