Boolean algebra (or Boolean lattice) is an algebraic structure capturing the essence of both mathematical logic and axiomatic set theory.

Huntington's axiomatization of Boolean algebra: [@Huntington1933]

Given a set $A$, a binary operator $\lor$ and a unary operator $\lnot$, the 3-tuple $(A, \lor, \lnot)$ is a Boolean algebra, if $\forall a, b, c \in A$:

  1. Commutativity: $a \lor b = b \lor a$;
  2. Associativity: $a \lor (b \lor c) = (a \lor b) \lor c$;
  3. Huntington axiom: $\lnot (\lnot a \lor b) \lor \lnot (\lnot a \lor \lnot b) = a$;

The binary operator $\lor$ is typically called logical OR or join; and the unary operator $\lnot$ is typically called logical NOT or complement.

For a Boolean algebra, two special elements and another binary operator can be defined as:

  1. top (unit): $1 \equiv a \lor \lnot a$
  2. bottom (zero): $0 \equiv \lnot 1$
  3. Logical AND (meet): $a \land b \equiv \lnot (\lnot a \lor \lnot b)$

Boolean algebra satisfies the Boolean laws:

  1. Idempotent: $a \lor a = a$;
  2. Commutative: $a \lor b = b \lor a$;
  3. Associative: $a \lor (b \lor c) = (a \lor b) \lor c$;
  4. Mutually Distributive: $a \land (b \lor c) = (a \land b) \lor (a \land c)$;
  5. Absorption: $a \land (a \lor b) = a$;
  6. Identity: $a \lor 0 = a,\quad 1 \lor a = 1$;
  7. Complements: $a \lor \lnot a = 1$;
  8. Duality: All these laws still hold if simultaneously exchange $\land$ with $\lor$, and $0$ with $1$.

A Boolean algebra is the partial order on subsets defined by inclusion $\subseteq$. A Boolean algebra also forms a complemented distributive lattice. The number of elements of every finite Boolean algebra is a power of two. Each of the elements of b(A) is called a Boolean function. There are $2^{2^n}$ Boolean functions in a Boolean algebra of order $n$.

🏷 Category=Algebra