Boolean algebra (structure)

Last updated February 24, 2024

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra (with involution).

Every Boolean algebra gives rise to a Boolean ring, and vice versa, with ring multiplication corresponding to conjunction or meet ∧, and ring addition to exclusive disjunction or symmetric difference (not disjunction ∨). However, the theory of Boolean rings has an inherent asymmetry between the two operators, while the axioms and theorems of Boolean algebra express the symmetry of the theory described by the duality principle.^[1]

History

The term "Boolean algebra" honors George Boole (1815–1864), a self-educated English mathematician. He introduced the algebraic system initially in a small pamphlet, The Mathematical Analysis of Logic, published in 1847 in response to an ongoing public controversy between Augustus De Morgan and William Hamilton, and later as a more substantial book, The Laws of Thought , published in 1854. Boole's formulation differs from that described above in some important respects. For example, conjunction and disjunction in Boole were not a dual pair of operations. Boolean algebra emerged in the 1860s, in papers written by William Jevons and Charles Sanders Peirce. The first systematic presentation of Boolean algebra and distributive lattices is owed to the 1890 Vorlesungen of Ernst Schröder. The first extensive treatment of Boolean algebra in English is A. N. Whitehead's 1898 Universal Algebra. Boolean algebra as an axiomatic algebraic structure in the modern axiomatic sense begins with a 1904 paper by Edward V. Huntington. Boolean algebra came of age as serious mathematics with the work of Marshall Stone in the 1930s, and with Garrett Birkhoff's 1940 Lattice Theory. In the 1960s, Paul Cohen, Dana Scott, and others found deep new results in mathematical logic and axiomatic set theory using offshoots of Boolean algebra, namely forcing and Boolean-valued models.

Definition

A Boolean algebra is a set $A$ , equipped with two binary operations $\land$ (called "meet" or "and"), $\lor$ (called "join" or "or"), a unary operation $\neg$ (called "complement" or "not") and two elements $0$ and $1$ in $A$ (called "bottom" and "top", or "least" and "greatest" element, also denoted by the symbols $⊥$ and $⊤$ , respectively), such that for all elements $a$ , $b$ and $c$ of $A$ , the following axioms hold:^[2]

$a \lor (b \lor c) = (a \lor b) \lor c$	$a \land (b \land c) = (a \land b) \land c$	associativity
$a \lor b = b \lor a$	$a \land b = b \land a$	commutativity
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	absorption
$a \lor 0 = a$	$a \land 1 = a$	identity
$a \lor (b \land c) = (a \lor b) \land (a \lor c)$	$a \land (b \lor c) = (a \land b) \lor (a \land c)$	distributivity
$a \lor \neg a = 1$	$a \land \neg a = 0$	complements

Note, however, that the absorption law and even the associativity law can be excluded from the set of axioms as they can be derived from the other axioms (see Proven properties).

A Boolean algebra with only one element is called a trivial Boolean algebra or a degenerate Boolean algebra. (In older works, some authors required $0$ and $1$ to be distinct elements in order to exclude this case.)^{[ citation needed ]}

It follows from the last three pairs of axioms above (identity, distributivity and complements), or from the absorption axiom, that

a = b \land a

if and only if

a \lor b = b

.

The relation $\leq$ defined by $a \leq b$ if these equivalent conditions hold, is a partial order with least element 0 and greatest element 1. The meet $a \land b$ and the join $a \lor b$ of two elements coincide with their infimum and supremum, respectively, with respect to ≤.

The first four pairs of axioms constitute a definition of a bounded lattice.

It follows from the first five pairs of axioms that any complement is unique.

The set of axioms is self-dual in the sense that if one exchanges $\lor$ with $\land$ and $0$ with $1$ in an axiom, the result is again an axiom. Therefore, by applying this operation to a Boolean algebra (or Boolean lattice), one obtains another Boolean algebra with the same elements; it is called its dual.^[3]

Examples

The simplest non-trivial Boolean algebra, the two-element Boolean algebra, has only two elements, $0$ and $1$ , and is defined by the rules:

$\land$	$0$	$1$
$0$	$0$	$0$
$1$	$0$	$1$

$\lor$	$0$	$1$
$0$	$0$	$1$
$1$	$1$	$1$

$a$	$0$	$1$
$\neg a$	$1$	$0$

It has applications in logic, interpreting $0$ as false, $1$ as true, $\land$ as and, $\lor$ as or, and $\neg$ as not. Expressions involving variables and the Boolean operations represent statement forms, and two such expressions can be shown to be equal using the above axioms if and only if the corresponding statement forms are logically equivalent.

The two-element Boolean algebra is also used for circuit design in electrical engineering;^{[note 1]} here 0 and 1 represent the two different states of one bit in a digital circuit, typically high and low voltage. Circuits are described by expressions containing variables, and two such expressions are equal for all values of the variables if and only if the corresponding circuits have the same input–output behavior. Furthermore, every possible input–output behavior can be modeled by a suitable Boolean expression.

The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can be checked by a trivial brute force algorithm for small numbers of variables). This can for example be used to show that the following laws ( Consensus theorems ) are generally valid in all Boolean algebras:
- $(a \lor b) \land (\neg a \lor c) \land (b \lor c) \equiv (a \lor b) \land (\neg a \lor c)$
- $(a \land b) \lor (\neg a \land c) \lor (b \land c) \equiv (a \land b) \lor (\neg a \land c)$

The power set (set of all subsets) of any given nonempty set $S$ forms a Boolean algebra, an algebra of sets, with the two operations $\lor := \cup$ (union) and $\land := \cap$ (intersection). The smallest element 0 is the empty set and the largest element $1$ is the set $S$ itself.

After the two-element Boolean algebra, the simplest Boolean algebra is that defined by the power set of two atoms:

$\land$	$0$	$a$	$b$	$1$
$0$	$0$	$0$	$0$	$0$
$a$	$0$	$a$	$0$	$a$
$b$	$0$	$0$	$b$	$b$
$1$	$0$	$a$	$b$	$1$

$\lor$	$0$	$a$	$b$	$1$
$0$	$0$	$a$	$b$	$1$
$a$	$a$	$a$	$1$	$1$
$b$	$b$	$1$	$b$	$1$
$1$	$1$	$1$	$1$	$1$

$x$	$0$	$a$	$b$	$1$
$\neg x$	$1$	$b$	$a$	$0$

The set $A$ of all subsets of $S$ that are either finite or cofinite is a Boolean algebra and an algebra of sets called the finite–cofinite algebra. If $S$ is infinite then the set of all cofinite subsets of $S$ , which is called the Fréchet filter, is a free ultrafilter on $A$ . However, the Fréchet filter is not an ultrafilter on the power set of $S$ .
Starting with the propositional calculus with $κ$ sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo logical equivalence). This construction yields a Boolean algebra. It is in fact the free Boolean algebra on $κ$ generators. A truth assignment in propositional calculus is then a Boolean algebra homomorphism from this algebra to the two-element Boolean algebra.
Given any linearly ordered set $L$ with a least element, the interval algebra is the smallest Boolean algebra of subsets of $L$ containing all of the half-open intervals $[a, b)$ such that $a$ is in $L$ and $b$ is either in $L$ or equal to $\infty$ . Interval algebras are useful in the study of Lindenbaum–Tarski algebras; every countable Boolean algebra is isomorphic to an interval algebra.

For any natural number $n$ , the set of all positive divisors of $n$ , defining $a \leq b$ if $a$ divides $b$ , forms a distributive lattice. This lattice is a Boolean algebra if and only if $n$ is square-free. The bottom and the top elements of this Boolean algebra are the natural numbers $1$ and $n$ , respectively. The complement of $a$ is given by $n / a$ . The meet and the join of $a$ and $b$ are given by the greatest common divisor ( $gcd$ ) and the least common multiple ( $lcm$ ) of $a$ and $b$ , respectively. The ring addition $a + b$ is given by $lcm(a, b) / gcd(a, b)$ . The picture shows an example for $n = 30$ . As a counter-example, considering the non-square-free $n = 60$ , the greatest common divisor of 30 and its complement 2 would be 2, while it should be the bottom element 1.
Other examples of Boolean algebras arise from topological spaces: if $X$ is a topological space, then the collection of all subsets of $X$ that are both open and closed forms a Boolean algebra with the operations $\lor := \cup$ (union) and $\land := \cap$ (intersection).
If $R$ is an arbitrary ring then its set of central idempotents , which is the set

A=\left\{e\in R:e^{2}=e{\text{ and }}ex=xe\;{\text{ for all }}\;x\in R\right\},

becomes a Boolean algebra when its operations are defined by $e \lor f := e + f - ef$ and $e \land f := ef$ .

Homomorphisms and isomorphisms

A homomorphism between two Boolean algebras $A$ and $B$ is a function $f : A \to B$ such that for all $a$ , $b$ in $A$ :

f (a \lor b) = f (a) \lor f (b)

,

f (a \land b) = f (a) \land f (b)

,

f (0) = 0

,

f (1) = 1

.

It then follows that $f (\neg a) = \neg f (a)$ for all $a$ in $A$ . The class of all Boolean algebras, together with this notion of morphism, forms a full subcategory of the category of lattices.

An isomorphism between two Boolean algebras $A$ and $B$ is a homomorphism $f : A \to B$ with an inverse homomorphism, that is, a homomorphism $g : B \to A$ such that the composition $g \circ f : A \to A$ is the identity function on $A$ , and the composition $f \circ g : B \to B$ is the identity function on $B$ . A homomorphism of Boolean algebras is an isomorphism if and only if it is bijective.

Boolean rings

Every Boolean algebra $(A, \land, \lor)$ gives rise to a ring $(A, +, \cdot)$ by defining $a + b := (a \land \neg b) \lor (b \land \neg a) = (a \lor b) \land \neg(a \land b)$ (this operation is called symmetric difference in the case of sets and XOR in the case of logic) and $a \cdot b := a \land b$ . The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the $1$ of the Boolean algebra. This ring has the property that $a \cdot a = a$ for all $a$ in $A$ ; rings with this property are called Boolean rings.

Conversely, if a Boolean ring $A$ is given, we can turn it into a Boolean algebra by defining $x \lor y := x + y + (x \cdot y)$ and $x \land y := x \cdot y$ .^[4]^[5] Since these two constructions are inverses of each other, we can say that every Boolean ring arises from a Boolean algebra, and vice versa. Furthermore, a map $f : A \to B$ is a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings. The categories of Boolean rings and Boolean algebras are equivalent;^[6] in fact the categories are isomorphic.

Hsiang (1985) gave a rule-based algorithm to check whether two arbitrary expressions denote the same value in every Boolean ring. More generally, Boudet, Jouannaud, and Schmidt-Schauß (1989) gave an algorithm to solve equations between arbitrary Boolean-ring expressions. Employing the similarity of Boolean rings and Boolean algebras, both algorithms have applications in automated theorem proving.

Ideals and filters

An ideal of the Boolean algebra $A$ is a nonempty subset $I$ such that for all $x$ , $y$ in $I$ we have $x \lor y$ in $I$ and for all $a$ in $A$ we have $a \land x$ in $I$ . This notion of ideal coincides with the notion of ring ideal in the Boolean ring $A$ . An ideal $I$ of $A$ is called prime if $I \neq A$ and if $a \land b$ in $I$ always implies $a$ in $I$ or $b$ in $I$ . Furthermore, for every $a \in A$ we have that $a \land - a = 0 \in I$ , and then if $I$ is prime we have $a \in I$ or $- a \in I$ for every $a \in A$ . An ideal $I$ of $A$ is called maximal if $I \neq A$ and if the only ideal properly containing $I$ is $A$ itself. For an ideal $I$ , if $a \notin I$ and $- a \notin I$ , then $I \cup {a}$ or $I \cup {- a}$ is contained in another proper ideal $J$ . Hence, such an $I$ is not maximal, and therefore the notions of prime ideal and maximal ideal are equivalent in Boolean algebras. Moreover, these notions coincide with ring theoretic ones of prime ideal and maximal ideal in the Boolean ring $A$ .

The dual of an ideal is a filter. A filter of the Boolean algebra $A$ is a nonempty subset $p$ such that for all $x$ , $y$ in $p$ we have $x \land y$ in $p$ and for all $a$ in $A$ we have $a \lor x$ in $p$ . The dual of a maximal (or prime) ideal in a Boolean algebra is ultrafilter . Ultrafilters can alternatively be described as 2-valued morphisms from $A$ to the two-element Boolean algebra. The statement every filter in a Boolean algebra can be extended to an ultrafilter is called the ultrafilter lemma and cannot be proven in Zermelo–Fraenkel set theory (ZF), if ZF is consistent. Within ZF, the ultrafilter lemma is strictly weaker than the axiom of choice. The ultrafilter lemma has many equivalent formulations: every Boolean algebra has an ultrafilter, every ideal in a Boolean algebra can be extended to a prime ideal, etc.

Representations

It can be shown that every finite Boolean algebra is isomorphic to the Boolean algebra of all subsets of a finite set. Therefore, the number of elements of every finite Boolean algebra is a power of two.

Stone's celebrated representation theorem for Boolean algebras states that every Boolean algebra $A$ is isomorphic to the Boolean algebra of all clopen sets in some (compact totally disconnected Hausdorff) topological space.

Axiomatics

Proven properties

UId₁		If x ∨ o = x for all x, then o = 0
Proof:		If x ∨ o = x, then
		0
	=	0 ∨ o	by assumption
	=	o ∨ 0	by Cmm₁
	=	o	by Idn₁

UId₂ [dual] If x ∧ i = x for all x, then i = 1

Idm₁		x ∨ x = x
Proof:		x ∨ x
	=	(x ∨ x) ∧ 1	by Idn₂
	=	(x ∨ x) ∧ (x ∨ ¬x)	by Cpl₁
	=	x ∨ (x ∧ ¬x)	by Dst₁
	=	x ∨ 0	by Cpl₂
	=	x	by Idn₁

Idm₂ [dual] x ∧ x = x

Bnd₁		x ∨ 1 = 1
Proof:		x ∨ 1
	=	(x ∨ 1) ∧ 1	by Idn₂
	=	1 ∧ (x ∨ 1)	by Cmm₂
	=	(x ∨ ¬x) ∧ (x ∨ 1)	by Cpl₁
	=	x ∨ (¬x ∧ 1)	by Dst₁
	=	x ∨ ¬x	by Idn₂
	=	1	by Cpl₁

Bnd₂ [dual] x ∧ 0 = 0

Abs₁		x ∨ (x ∧ y) = x
Proof:		x ∨ (x ∧ y)
	=	(x ∧ 1) ∨ (x ∧ y)	by Idn₂
	=	x ∧ (1 ∨ y)	by Dst₂
	=	x ∧ (y ∨ 1)	by Cmm₁
	=	x ∧ 1	by Bnd₁
	=	x	by Idn₂

Abs₂ [dual] x ∧ (x ∨ y) = x

UNg		If x ∨ x_n = 1 and x ∧ x_n = 0, then x_n = ¬x
Proof:		If x ∨ x_n = 1 and x ∧ x_n = 0, then
		x_n
	=	x_n ∧ 1	by Idn₂
	=	x_n ∧ (x ∨ ¬x)	by Cpl₁
	=	(x_n ∧ x) ∨ (x_n ∧ ¬x)	by Dst₂
	=	(x ∧ x_n) ∨ (¬x ∧ x_n)	by Cmm₂
	=	0 ∨ (¬x ∧ x_n)	by assumption
	=	(x ∧ ¬x) ∨ (¬x ∧ x_n)	by Cpl₂
	=	(¬x ∧ x) ∨ (¬x ∧ x_n)	by Cmm₂
	=	¬x ∧ (x ∨ x_n)	by Dst₂
	=	¬x ∧ 1	by assumption
	=	¬x	by Idn₂

DNg		¬¬x = x
Proof:		¬x ∨ x = x ∨ ¬x = 1	by Cmm₁, Cpl₁
	and	¬x ∧ x = x ∧ ¬x = 0	by Cmm₂, Cpl₂
	hence	x = ¬¬x	by UNg

A₁		x ∨ (¬x ∨ y) = 1
Proof:		x ∨ (¬x ∨ y)
	=	(x ∨ (¬x ∨ y)) ∧ 1	by Idn₂
	=	1 ∧ (x ∨ (¬x ∨ y))	by Cmm₂
	=	(x ∨ ¬x) ∧ (x ∨ (¬x ∨ y))	by Cpl₁
	=	x ∨ (¬x ∧ (¬x ∨ y))	by Dst₁
	=	x ∨ ¬x	by Abs₂
	=	1	by Cpl₁

A₂ [dual] x ∧ (¬x ∧ y) = 0

B₁		(x ∨ y) ∨ (¬x ∧ ¬y) = 1
Proof:		(x ∨ y) ∨ (¬x ∧ ¬y)
	=	((x ∨ y) ∨ ¬x) ∧ ((x ∨ y) ∨ ¬y)	by Dst₁
	=	(¬x ∨ (x ∨ y)) ∧ (¬y ∨ (y ∨ x))	by Cmm₁
	=	(¬x ∨ (¬¬x ∨ y)) ∧ (¬y ∨ (¬¬y ∨ x))	by DNg
	=	1 ∧ 1	by A₁
	=	1	by Idn₂

B₂ [dual] (x ∧ y) ∧ (¬x ∨ ¬y) = 0

C₁		(x ∨ y) ∧ (¬x ∧ ¬y) = 0
Proof:		(x ∨ y) ∧ (¬x ∧ ¬y)
	=	(¬x ∧ ¬y) ∧ (x ∨ y)	by Cmm₂
	=	((¬x ∧ ¬y) ∧ x) ∨ ((¬x ∧ ¬y) ∧ y)	by Dst₂
	=	(x ∧ (¬x ∧ ¬y)) ∨ (y ∧ (¬y ∧ ¬x))	by Cmm₂
	=	0 ∨ 0	by A₂
	=	0	by Idn₁

C₂ [dual] (x ∧ y) ∨ (¬x ∨ ¬y) = 1

DMg₁		¬(x ∨ y) = ¬x ∧ ¬y
Proof:		by B₁, C₁, and UNg

DMg₂ [dual] ¬(x ∧ y) = ¬x ∨ ¬y

D₁		(x∨(y∨z)) ∨ ¬x = 1
Proof:		(x ∨ (y ∨ z)) ∨ ¬x
	=	¬x ∨ (x ∨ (y ∨ z))	by Cmm₁
	=	¬x ∨ (¬¬x ∨ (y ∨ z))	by DNg
	=	1	by A₁

D₂ [dual] (x∧(y∧z)) ∧ ¬x = 0

E₁		y ∧ (x∨(y∨z)) = y
Proof:		y ∧ (x ∨ (y ∨ z))
	=	(y ∧ x) ∨ (y ∧ (y ∨ z))	by Dst₂
	=	(y ∧ x) ∨ y	by Abs₂
	=	y ∨ (y ∧ x)	by Cmm₁
	=	y	by Abs₁

E₂ [dual] y ∨ (x∧(y∧z)) = y

F₁		(x∨(y∨z)) ∨ ¬y = 1
Proof:		(x ∨ (y ∨ z)) ∨ ¬y
	=	¬y ∨ (x ∨ (y ∨ z))	by Cmm₁
	=	(¬y ∨ (x ∨ (y ∨ z))) ∧ 1	by Idn₂
	=	1 ∧ (¬y ∨ (x ∨ (y ∨ z)))	by Cmm₂
	=	(y ∨ ¬y) ∧ (¬y ∨ (x ∨ (y ∨ z)))	by Cpl₁
	=	(¬y ∨ y) ∧ (¬y ∨ (x ∨ (y ∨ z)))	by Cmm₁
	=	¬y ∨ (y ∧ (x ∨ (y ∨ z)))	by Dst₁
	=	¬y ∨ y	by E₁
	=	y ∨ ¬y	by Cmm₁
	=	1	by Cpl₁

F₂ [dual] (x∧(y∧z)) ∧ ¬y = 0

G₁		(x∨(y∨z)) ∨ ¬z = 1
Proof:		(x ∨ (y ∨ z)) ∨ ¬z
	=	(x ∨ (z ∨ y)) ∨ ¬z	by Cmm₁
	=	1	by F₁

G₂ [dual] (x∧(y∧z)) ∧ ¬z = 0

H₁		¬((x∨y)∨z) ∧ x = 0
Proof:		¬((x ∨ y) ∨ z) ∧ x
	=	(¬(x ∨ y) ∧ ¬z) ∧ x	by DMg₁
	=	((¬x ∧ ¬y) ∧ ¬z) ∧ x	by DMg₁
	=	x ∧ ((¬x ∧ ¬y) ∧ ¬z)	by Cmm₂
	=	(x ∧ ((¬x ∧ ¬y) ∧ ¬z)) ∨ 0	by Idn₁
	=	0 ∨ (x ∧ ((¬x ∧ ¬y) ∧ ¬z))	by Cmm₁
	=	(x ∧ ¬x) ∨ (x ∧ ((¬x ∧ ¬y) ∧ ¬z))	by Cpl₂
	=	x ∧ (¬x ∨ ((¬x ∧ ¬y) ∧ ¬z))	by Dst₂
	=	x ∧ (¬x ∨ (¬z ∧ (¬x ∧ ¬y)))	by Cmm₂
	=	x ∧ ¬x	by E₂
	=	0	by Cpl₂

H₂ [dual] ¬((x∧y)∧z) ∨ x = 1

I₁		¬((x∨y)∨z) ∧ y = 0
Proof:		¬((x ∨ y) ∨ z) ∧ y
	=	¬((y ∨ x) ∨ z) ∧ y	by Cmm₁
	=	0	by H₁

I₂ [dual] ¬((x∧y)∧z) ∨ y = 1

J₁		¬((x∨y)∨z) ∧ z = 0
Proof:		¬((x ∨ y) ∨ z) ∧ z
	=	(¬(x ∨ y) ∧ ¬z) ∧ z	by DMg₁
	=	z ∧ (¬(x ∨ y) ∧ ¬z)	by Cmm₂
	=	z ∧ ( ¬z ∧ ¬(x ∨ y))	by Cmm₂
	=	0	by A₂

J₂ [dual] ¬((x∧y)∧z) ∨ z = 1

K₁		(x ∨ (y ∨ z)) ∨ ¬((x ∨ y) ∨ z) = 1
Proof:		(x∨(y∨z)) ∨ ¬((x ∨ y) ∨ z)
	=	(x∨(y∨z)) ∨ (¬(x ∨ y) ∧ ¬z)	by DMg₁
	=	(x∨(y∨z)) ∨ ((¬x ∧ ¬y) ∧ ¬z)	by DMg₁
	=	((x∨(y∨z)) ∨ (¬x ∧ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z)	by Dst₁
	=	(((x∨(y∨z)) ∨ ¬x) ∧ ((x∨(y∨z)) ∨ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z)	by Dst₁
	=	(1 ∧ 1) ∧ 1	by D₁,F₁,G₁
	=	1	by Idn₂

K₂ [dual] (x ∧ (y ∧ z)) ∧ ¬((x ∧ y) ∧ z) = 0

L₁		(x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z) = 0
Proof:		(x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z)
	=	¬((x∨y)∨z) ∧ (x ∨ (y ∨ z))	by Cmm₂
	=	(¬((x∨y)∨z) ∧ x) ∨ (¬((x∨y)∨z) ∧ (y ∨ z))	by Dst₂
	=	(¬((x∨y)∨z) ∧ x) ∨ ((¬((x∨y)∨z) ∧ y) ∨ (¬((x∨y)∨z) ∧ z))	by Dst₂
	=	0 ∨ (0 ∨ 0)	by H₁,I₁,J₁
	=	0	by Idn₁

L₂ [dual] (x ∧ (y ∧ z)) ∨ ¬((x ∧ y) ∧ z) = 1

Ass₁		x ∨ (y ∨ z) = (x ∨ y) ∨ z
Proof:		by K₁, L₁, UNg, DNg

Ass₂ [dual] x ∧ (y ∧ z) = (x ∧ y) ∧ z

Abbreviations
UId	Unique Identity
Idm	Idempotence
Bnd	Boundaries
Abs	Absorption law
UNg	Unique Negation
DNg	Double negation
DMg	De Morgan's Law
Ass	Associativity

Huntington 1904 Boolean algebra axioms

Idn₁

x ∨ 0 = x

Idn₂

x ∧ 1 = x

Cmm₁

x ∨ y = y ∨ x

Cmm₂

x ∧ y = y ∧ x

Dst₁

x ∨ (y∧z) = (x∨y) ∧ (x∨z)

Dst₂

x ∧ (y∨z) = (x∧y) ∨ (x∧z)

Cpl₁

x ∨ ¬x = 1

Cpl₂

x ∧ ¬x = 0

Abbreviations
Idn	Identity
Cmm	Commutativity
Dst	Distributivity
Cpl	Complements

The first axiomatization of Boolean lattices/algebras in general was given by the English philosopher and mathematician Alfred North Whitehead in 1898.^[7]^[8] It included the above axioms and additionally $x \lor 1 = 1$ and $x \land 0 = 0$ . In 1904, the American mathematician Edward V. Huntington (1874–1952) gave probably the most parsimonious axiomatization based on $\land$ , $\lor$ , $\neg$ , even proving the associativity laws (see box).^[9] He also proved that these axioms are independent of each other.^[10] In 1933, Huntington set out the following elegant axiomatization for Boolean algebra.^[11] It requires just one binary operation $+$ and a unary functional symbol $n$ , to be read as 'complement', which satisfy the following laws:

Commutativity: $x + y = y + x$ .
Associativity: $(x + y) + z = x + (y + z)$ .
Huntington equation: $n (n (x) + y) + n (n (x) + n (y)) = x$ .

Herbert Robbins immediately asked: If the Huntington equation is replaced with its dual, to wit:

Robbins Equation: $n (n (x + y) + n (x + n (y))) = x$ ,

do (1), (2), and (4) form a basis for Boolean algebra? Calling (1), (2), and (4) a Robbins algebra, the question then becomes: Is every Robbins algebra a Boolean algebra? This question (which came to be known as the Robbins conjecture) remained open for decades, and became a favorite question of Alfred Tarski and his students. In 1996, William McCune at Argonne National Laboratory, building on earlier work by Larry Wos, Steve Winker, and Bob Veroff, answered Robbins's question in the affirmative: Every Robbins algebra is a Boolean algebra. Crucial to McCune's proof was the computer program EQP he designed. For a simplification of McCune's proof, see Dahn (1998).

Further work has been done for reducing the number of axioms; see Minimal axioms for Boolean algebra.

Generalizations

Removing the requirement of existence of a unit from the axioms of Boolean algebra yields "generalized Boolean algebras". Formally, a distributive lattice $B$ is a generalized Boolean lattice, if it has a smallest element $0$ and for any elements $a$ and $b$ in $B$ such that $a \leq b$ , there exists an element $x$ such that $a \land x = 0$ and $a \lor x = b$ . Defining $a \ b$ as the unique $x$ such that $(a \land b) \lor x = a$ and $(a \land b) \land x = 0$ , we say that the structure $(B, ∧, ∨, \, 0)$ is a generalized Boolean algebra, while $(B, \lor, 0)$ is a generalized Boolean semilattice . Generalized Boolean lattices are exactly the ideals of Boolean lattices.

A structure that satisfies all axioms for Boolean algebras except the two distributivity axioms is called an orthocomplemented lattice. Orthocomplemented lattices arise naturally in quantum logic as lattices of closed linear subspaces for separable Hilbert spaces.

Notes

↑ Strictly, electrical engineers tend to use additional states to represent other circuit conditions such as high impedance - see IEEE 1164 or IEEE 1364.

Related Research Articles

In mathematics, the power set (or powerset) of a set $S$ is the set of all subsets of $S$ , including the empty set and $S$ itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is postulated by the axiom of power set. The powerset of $S$ is variously denoted as $P (S)$ , $𝒫 (S)$ , $P (S)$ , $,, or 2 S . The notation 2 S, meaning the set of all functions from S to a given set of two elements (e.g., {0, 1}), is used because the powerset of S can be identified with, is equivalent to, or bijective to the set of all the functions from S to the given two-element set.$

In mathematics, pointless topology, also called point-free topology and locale theory, is an approach to topology that avoids mentioning points, and in which the lattices of open sets are the primitive notions. In this approach it becomes possible to construct topologically interesting spaces from purely algebraic data.

In the mathematical field of order theory, an ultrafilter on a given partially ordered set $is a certain subset of namely a maximal filter on that is, a proper filter on that cannot be enlarged to a bigger proper filter on$

In mathematics, an algebraic structure consists of a nonempty set A, a collection of operations on A, and a finite set of identities, known as axioms, that these operations must satisfy.

In mathematics, an algebra over a field is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and addition and scalar multiplication by elements of a field and satisfying the axioms implied by "vector space" and "bilinear".

In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation a → b of implication such that (c ∧ a) ≤ b is equivalent to c ≤ (a → b). From a logical standpoint, A → B is by this definition the weakest proposition for which modus ponens, the inference rule A → B, A ⊢ B, is sound. Like Boolean algebras, Heyting algebras form a variety axiomatizable with finitely many equations. Heyting algebras were introduced by Arend Heyting (1930) to formalize intuitionistic logic.

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

In mathematics, the Boolean prime ideal theorem states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma. Other theorems are obtained by considering different mathematical structures with appropriate notions of ideals, for example, rings and prime ideals, or distributive lattices and maximal ideals. This article focuses on prime ideal theorems from order theory.

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion. Ideals are of great importance for many constructions in order and lattice theory.

In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a certain field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Marshall H. Stone. Stone was led to it by his study of the spectral theory of operators on a Hilbert space.

In mathematics, a join-semilattice is a partially ordered set that has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.

In abstract algebra, an interior algebra is a certain type of algebraic structure that encodes the idea of the topological interior of a set. Interior algebras are to topology and the modal logic S4 what Boolean algebras are to set theory and ordinary propositional logic. Interior algebras form a variety of modal algebras.

In mathematics, a field of sets is a mathematical structure consisting of a pair $consisting of a set and a family of subsets of called an algebra over that contains the empty set as an element, and is closed under the operations of taking complements in finite unions, and finite intersections.$

In abstract algebra, a residuated lattice is an algebraic structure that is simultaneously a lattice x ≤ y and a monoid x•y which admits operations x\z and z/y, loosely analogous to division or implication, when x•y is viewed as multiplication or conjunction, respectively. Called respectively right and left residuals, these operations coincide when the monoid is commutative. The general concept was introduced by Morgan Ward and Robert P. Dilworth in 1939. Examples, some of which existed prior to the general concept, include Boolean algebras, Heyting algebras, residuated Boolean algebras, relation algebras, and MV-algebras. Residuated semilattices omit the meet operation ∧, for example Kleene algebras and action algebras.

In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take values in some fixed complete Boolean algebra.

Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1. Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.

In mathematics, the congruence lattice problem asks whether every algebraic distributive lattice is isomorphic to the congruence lattice of some other lattice. The problem was posed by Robert P. Dilworth, and for many years it was one of the most famous and long-standing open problems in lattice theory; it had a deep impact on the development of lattice theory itself. The conjecture that every distributive lattice is a congruence lattice is true for all distributive lattices with at most ℵ₁ compact elements, but F. Wehrung provided a counterexample for distributive lattices with ℵ₂ compact elements using a construction based on Kuratowski's free set theorem.

In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets. Here, a lattice is an abstract structure with two binary operations, the "meet" and "join" operations, which must obey certain axioms; it is distributive if these two operations obey the distributive law. The union and intersection operations, in a family of sets that is closed under these operations, automatically form a distributive lattice, and Birkhoff's representation theorem states that every finite distributive lattice can be formed in this way. It is named after Garrett Birkhoff, who published a proof of it in 1937.

References

↑ Givant & Halmos 2009, p. 20.
↑ Davey & Priestley 1990, pp. 109, 131, 144.
↑ Goodstein 2012, p. 21ff.
↑ Stone 1936.
↑ Hsiang 1985, p. 260.
↑ Cohn 2003, p. 81.
↑ Padmanabhan & Rudeanu 2008, p. 73.
↑ Whitehead 1898, p. 37.
↑ Huntington 1904, pp. 292–293.
↑ Huntington 1904, p. 296.
↑ Huntington 1933a.

Works cited

Davey, B.A.; Priestley, H.A. (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press.
Cohn, Paul M. (2003), Basic Algebra: Groups, Rings, and Fields, Springer, pp. 51, 70–81, ISBN 9781852335878
Givant, Steven; Halmos, Paul (2009), Introduction to Boolean Algebras, Undergraduate Texts in Mathematics, Springer, ISBN 978-0-387-40293-2 .
Goodstein, R. L. (2012), "Chapter 2: The self-dual system of axioms", Boolean Algebra, Courier Dover Publications, pp. 21ff, ISBN 9780486154978
Hsiang, Jieh (1985). "Refutational Theorem Proving Using Term Rewriting Systems". Artificial Intelligence . 25 (3): 255–300. doi:10.1016/0004-3702(85)90074-8.
Huntington, Edward V. (1904). "Sets of Independent Postulates for the Algebra of Logic". Transactions of the American Mathematical Society . 5 (3): 288–309. doi: 10.1090/s0002-9947-1904-1500675-4 . JSTOR 1986459.
Padmanabhan, Ranganathan; Rudeanu, Sergiu (2008), Axioms for lattices and boolean algebras, World Scientific, ISBN 978-981-283-454-6 .
Stone, Marshall H. (1936). "The Theory of Representations for Boolean Algebra". Transactions of the American Mathematical Society . 40: 37–111. doi: 10.1090/s0002-9947-1936-1501865-8 .
Whitehead, A.N. (1898). A Treatise on Universal Algebra. Cambridge University Press. ISBN 978-1-4297-0032-0.

General references

Brown, Stephen; Vranesic, Zvonko (2002), Fundamentals of Digital Logic with VHDL Design (2nd ed.), McGraw–Hill, ISBN 978-0-07-249938-4 . See Section 2.5.
Boudet, A.; Jouannaud, J.P.; Schmidt-Schauß, M. (1989). "Unification in Boolean Rings and Abelian Groups". Journal of Symbolic Computation . 8 (5): 449–477. doi: 10.1016/s0747-7171(89)80054-9 .
Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3 . See Chapter 2.
Dahn, B. I. (1998), "Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem", Journal of Algebra , 208 (2): 526–532, doi: 10.1006/jabr.1998.7467 .

Halmos, Paul (1963), Lectures on Boolean Algebras, Van Nostrand, ISBN 978-0-387-90094-0 .
Halmos, Paul; Givant, Steven (1998), Logic as Algebra , Dolciani Mathematical Expositions, vol. 21, Mathematical Association of America, ISBN 978-0-88385-327-6 .
Huntington, E. V. (1933a), "New sets of independent postulates for the algebra of logic" (PDF), Transactions of the American Mathematical Society , American Mathematical Society, 35 (1): 274–304, doi:10.2307/1989325, JSTOR 1989325 .
Huntington, E. V. (1933b), "Boolean algebra: A correction", Transactions of the American Mathematical Society , 35 (2): 557–558, doi:10.2307/1989783, JSTOR 1989783
Mendelson, Elliott (1970), Boolean Algebra and Switching Circuits , Schaum's Outline Series in Mathematics, McGraw–Hill, ISBN 978-0-07-041460-0
Monk, J. Donald; Bonnet, R., eds. (1989), Handbook of Boolean Algebras , North-Holland, ISBN 978-0-444-87291-3 . In 3 volumes. (Vol.1: ISBN 978-0-444-70261-6, Vol.2: ISBN 978-0-444-87152-7, Vol.3: ISBN 978-0-444-87153-4)
Sikorski, Roman (1966), Boolean Algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag .
Stoll, R. R. (1963), Set Theory and Logic, W. H. Freeman, ISBN 978-0-486-63829-4 . Reprinted by Dover Publications, 1979.

External links

"Boolean algebra", Encyclopedia of Mathematics , EMS Press, 2001 [1994]
Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra", by J. Donald Monk.
McCune W., 1997. Robbins Algebras Are Boolean JAR 19(3), 263—276
"Boolean Algebra" by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.
Burris, Stanley N.; Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.
Weisstein, Eric W. "Boolean Algebra". MathWorld .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[4] Strictly, electrical engineers tend to use additional states to represent other circuit conditions such as high impedance - see IEEE 1164 or IEEE 1364.

[FOOTNOTEGivantHalmos200920-1] Givant & Halmos 2009, p. 20.

[FOOTNOTEDaveyPriestley1990109,_131,_144-2] Davey & Priestley 1990, pp. 109, 131, 144.

[FOOTNOTEGoodstein201221ff-3] Goodstein 2012, p. 21ff.

[FOOTNOTEStone1936-5] Stone 1936.

[FOOTNOTEHsiang1985260-6] Hsiang 1985, p. 260.

[FOOTNOTECohn2003[httpsbooksgooglecombooksidVESm0MJOiDQCpgPA81_81]-7] Cohn 2003, p. 81.

[FOOTNOTEPadmanabhanRudeanu2008[httpsbooksgooglecombooksidJlXSlpmlSv4CpgPA73_73]-8] Padmanabhan & Rudeanu 2008, p. 73.

[FOOTNOTEWhitehead189837-9] Whitehead 1898, p. 37.

[FOOTNOTEHuntington1904292–293-10] Huntington 1904, pp. 292–293.

[FOOTNOTEHuntington1904296-11] Huntington 1904, p. 296.

[FOOTNOTEHuntington1933a-12] Huntington 1933a.

[1]

[2]

[3]

[note 1]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types ( list )	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Ordered vector space Partially ordered Positive cone Riesz space Upper set Young's lattice