5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

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.