Is there a logic gate (NAND, OR, etc.) which forms a group under the set $\{0,1\}?$

Question

Many of the binary logic operators satisfy algebraic properties like associativity, closure, and having an inverse. I was wondering if you could form a group, or any other algebraic structure using one (or more) of these gates.

Answer 1

In fact you can form every algebraic structure the set $2 = \{ 0, 1 \}$ possesses using compositions of logic gates. This is because, by functional completeness, the standard logic gates can express every Boolean function $2^n \to 2$.

So it's natural to ask: what is the structure on $2$ given by all of the Boolean functions together? This is the "maximally general algebraic structure" that $2$ can possess. The answer is that it is equivalent to the structure of a Boolean algebra (using AND, OR, and NOT) or equivalently a Boolean ring (using XOR, NOT, and AND). Specializations of this structure include

• the structure of a lattice (using AND and OR)
• the structure of an idempotent commutative monoid (using either AND or OR)
• the structure of an abelian group, or more precisely a vector space over the finite field $\mathbb{F}_2$ (using XOR).

There are other more exotic specializations given by Post's lattice.

Another interesting question is: what algebraic structure do the logic gates themselves form? The answer is that they form what is called a Lawvere theory; see this blog post for some details.

Answer 2

The XOR gate corresponds to addition modulo 2, thus it forms a group.

Answer 3

Actually the set $\{0,1\}$ with AND, OR and NOT is an example (and the most basic nontrivial one) of a Boolean algebra. Its associated Boolean ring $(\{0,1\}, XOR, AND)$ is isomorphic in this case to $(\mathbb Z_2, +_2, \cdot_2)$.