Boolean algebras and Boolean rings

Logical conjunction, union of sets and multiplication of idempotent elements obey related algebraic laws. Boolean algebra makes that relationship precise. It is not the same as ordinary real arithmetic: repeating a logical proposition does not add a second copy, and Boolean-ring addition means exclusive-or rather than inclusive-or.

1 Lattice operations and complements

A Boolean algebra is a set $B$ with operations meet $a\wedge b$, join $a\vee b$, complement $\neg a$, and elements 0 and 1, satisfying commutativity, associativity, absorption, distributivity of each operation over the other, identity laws $a\vee0=a$, $a\wedge1=a$, and complement laws

$$a\vee\neg a=1,\qquad a\wedge\neg a=0.$$

Absorption means $a\wedge(a\vee b)=a$ and $a\vee(a\wedge b)=a$. Define $a\le b$ when $a\wedge b=a$. These laws make it a partial order; join and meet are least upper and greatest lower bounds.

For any set $X$, the power set $\mathcal P(X)$ is a Boolean algebra under intersection, union and complement relative to $X$, with 0 the empty set and 1 equal to $X$. Propositions modulo logical equivalence form another example using and, or and not. The two-element algebra $\{0,1\}$ is the truth-value model.

Complements are unique. If $b,c$ both complement $a$, then

$$b=b\wedge1=b\wedge(a\vee c)=(b\wedge a)\vee(b\wedge c)=b\wedge c,$$

and similarly $c=b\wedge c$, so $b=c$.

De Morgan laws. $\neg(a\vee b)=(\neg a)\wedge(\neg b)$ and $\neg(a\wedge b)=(\neg a)\vee(\neg b)$.

Proof. Distributivity and complement laws show $(\neg a)\wedge(\neg b)$ has meet 0 and join 1 with $a\vee b$. For example the meet expands into terms containing $a\wedge\neg a$ or $b\wedge\neg b$, and the join equals $[(a\vee b)\vee\neg a]\wedge[(a\vee b)\vee\neg b]=1$. Complement uniqueness proves the first identity; interchange meet and join for the second. $\square$

2 Boolean rings use a different addition

A Boolean ring here is a commutative unital ring in which every element is idempotent: $a^2=a$. It satisfies $2\cdot1=0$, since $(1+1)^2=1+1$ implies $4=2$, hence $2=0$. Thus a nonzero Boolean ring has characteristic 2, and $a+a=0$ for every $a$ even if the zero ring is allowed.

From such a ring define

$$a\wedge b=ab,\qquad a\vee b=a+b+ab,\qquad\neg a=1+a.$$

These operations give a Boolean algebra. The complement identities follow immediately: $a(1+a)=a+a^2=0$ and $a+(1+a)+a(1+a)=1$. Absorption follows from $a(a+b+ab)=a+ab+ab=a$. Meet distributivity over join follows by expanding both sides and using $a^2=a$; associativity of join expands both groupings to

$$a+b+c+ab+ac+bc+abc.$$

The other lattice laws follow by the same ring expansions or by complementation. Thus this construction is not a superficial analogy; the algebraic operations really satisfy the axioms.

For sets, Boolean-ring multiplication is intersection and addition is symmetric difference

$$A\triangle B=(A\setminus B)\cup(B\setminus A).$$

Membership at each point identifies these operations with multiplication and addition modulo 2, proving the ring laws pointwise. Inclusive union is instead $A\triangle B\triangle(A\cap B)$.

3 Atoms in a finite Boolean algebra

An atom is a minimal nonzero element under $\le$. In a finite Boolean algebra, every nonzero element has an atom below it by taking a minimal element from the finite nonempty set of its nonzero lower bounds. Distinct atoms have meet zero: a nonzero meet would force equality by minimality.

Every element $a$ is the join of the atoms below it. Let their join be $s\le a$. If $s\ne a$, then $a\wedge\neg s\ne0$; otherwise $a=a\wedge(s\vee\neg s)=a\wedge s\le s$. An atom below $a\wedge\neg s$ would be an atom below $a$ omitted from $s$, a contradiction. Thus the map sending $a$ to the set of atoms below it identifies a finite Boolean algebra with the power set of its atoms. In particular, it has $2^k$ elements for some $k$, not an arbitrary finite size.

Order, both ring constructions, and the finite representation

The order claim follows from the displayed axioms. Absorption gives $a\wedge a=a$ and $a\vee a=a$. Reflexivity of $\le$ follows; antisymmetry follows from commutativity, and if $a\wedge b=a$, $b\wedge c=b$, then $a\wedge c=(a\wedge b)\wedge c=a\wedge(b\wedge c)=a$. Thus the relation is transitive. The element $a\wedge b$ lies below both factors; any common lower bound $u$ satisfies $u\wedge(a\wedge b)=u$, so it is their greatest lower bound. Absorption makes $a\vee b$ an upper bound. If both $a,b\le c$, distributivity gives $(a\vee b)\wedge c=(a\wedge c)\vee(b\wedge c)=a\vee b$, proving leastness.

For the Boolean-ring-to-algebra direction, the remaining distributive law and absorption law are explicit identities:

$$(a\vee b)\wedge(a\vee c)=a+bc+abc=a\vee(b\wedge c), \qquad a\vee(a\wedge b)=a+ab+a^2b=a.$$

Meet is associative/commutative with identity 1 because ring multiplication is; join is commutative with identity 0 and is associative by the expansion already shown. Also $a\vee a=a$ and $a\wedge a=a$. Together with the two complement identities and the other distributive law proved above, this verifies every stated Boolean-algebra axiom.

Conversely, in any Boolean algebra define

$$a\oplus b=(a\wedge\neg b)\vee(\neg a\wedge b),\qquad a\cdot b=a\wedge b.$$

The first operation is commutative, has identity 0, and $a\oplus a=0$. To verify associativity rather than assume it, distribute either $(a\oplus b)\oplus c$ or $a\oplus(b\oplus c)$ using De Morgan's laws. Both give the join of precisely these four disjoint terms:

$$(a\wedge\neg b\wedge\neg c)\vee (\neg a\wedge b\wedge\neg c)\vee (\neg a\wedge\neg b\wedge c)\vee (a\wedge b\wedge c).$$

The eight terms obtained by choosing each of $a,\neg a$, each of $b,\neg b$ and each of $c,\neg c$ are pairwise disjoint and have join 1; this follows by distributing $(a\vee\neg a)\wedge(b\vee\neg b)\wedge(c\vee\neg c)$. This justifies the expansion without presuming a representation by sets. Distributing $a\wedge(b\oplus c)$ gives $(a\wedge b\wedge\neg c)\vee(a\wedge\neg b\wedge c)$; expanding $(a\wedge b)\oplus(a\wedge c)$ gives the same expression. Thus multiplication distributes over $\oplus$. Meet supplies associative commutative multiplication, identity 1 and idempotence. All ring axioms are now proved. The formulas $a\oplus b\oplus(a\wedge b)=a\vee b$ and $1\oplus a=\neg a$ recover the original operations.

Finally the finite atom map is an isomorphism, not only a count. For an atom $t$, each $t\wedge a$ is either $0$ or $t$. Therefore $t\le a\vee b$ holds exactly when $t\le a$ or $t\le b$, and $t\le\neg a$ holds exactly when $t\not\le a$. This proves preservation of join and complement; meet is immediate. Injectivity follows because every element is the join of its atoms. For any subset of the finite atom set, join exactly those atoms; disjointness shows its atoms are precisely the selected subset, proving surjectivity. If the degenerate algebra $0=1$ is allowed, there are no atoms and this argument gives the one-element power set of the empty set. No assertion that every infinite Boolean algebra is a full power set is being made.

4 Graded practice

E1 Foundation. For $X=\{1,2,3\}$, $A=\{1,2\}$ and $B=\{2,3\}$, calculate meet, join, Boolean-ring sum and complement of $A$.

E2 Algebra. Verify $a\vee a=a$ using the Boolean-ring formula. Compare it with $a+a$.

E3 Finite structure. Can a Boolean algebra have exactly six elements? How many atoms does a 16-element Boolean algebra have?

E4 Logic. Simplify $(p\wedge q)\vee(p\wedge\neg q)$ and explain why no probability assumption is involved.

5 Full solutions

S1. Meet is $\{2\}$, join is $X$, ring sum is $\{1,3\}$, and $\neg A=\{3\}$. Ring sum omits the shared element 2, while join includes it.

S2. $a\vee a=a+a+a^2=0+a=a$. In contrast, ring addition gives $a+a=0$. Using the same plus sign for both join and ring addition without a convention would therefore be ambiguous.

S3. No: a finite Boolean algebra has power-of-two size. Since $16=2^4$, it has four atoms.

S4. Distributivity gives $p\wedge(q\vee\neg q)=p\wedge1=p$. This is a logical identity valid for all truth assignments, not an independence statement or a probability calculation.

Summary

Boolean algebra abstracts set and logical operations. Boolean rings encode the same patterns using idempotent multiplication and characteristic-two addition. Inclusive-or and exclusive-or are different operations. Finite Boolean algebras are determined by their atoms and consequently have power-of-two sizes.