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