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.

  • 1
    $\begingroup$ I suspect you'll see the term "modular" for (x↔y)⊕z being equivalent to x↔(y⊕z). en.wikipedia.org/wiki/Modular_lattice $\endgroup$ – Doug Spoonwood Jun 15 '13 at 18:50
  • 2
    $\begingroup$ 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.) $\endgroup$ – Tunococ Jul 5 '13 at 9:16
  • $\begingroup$ @Tunococ, looks pretty sensible to me. $\endgroup$ – 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).

  • $\begingroup$ 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$. $\endgroup$ – 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.

  • 2
    $\begingroup$ Yep. We can also write $(x \oplus y) \oplus (x \leftrightarrow y),$ just to be cute! $\endgroup$ – goblin Jun 12 '13 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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