Boolean Algebra · aiwiki.page

Boolean algebra is a branch of algebra concerned with operations that model conjunction, disjunction, and negation. Its simplest instance uses two values, 0 and 1, interpreted as false and true. More generally, a Boolean algebra is an abstract structure called a complemented bounded distributive lattice; its elements need not be numbers or truth values. Boolean algebra connects logic, set theory, and digital circuit design through a common system of identities. (boole.stanford.edu)

Historical development

The subject is named after George Boole, who developed algebraic methods for logical reasoning in The Mathematical Analysis of Logic (1847) and An Investigation of the Laws of Thought (1854). He represented classes and logical relationships symbolically, making deductions through algebraic manipulation. His original system differed in notation and interpretation from the modern presentation. (georgeboole.com)

A major engineering application appeared in Claude Shannon’s 1938 paper “A Symbolic Analysis of Relay and Switching Circuits.” Shannon demonstrated how an algebra of two-state variables could analyze switching networks and guide the construction of equivalent circuits. This connected symbolic reasoning with practical problems in electrical engineering. (tubes.mit.edu)

Operations and truth values

The two-element Boolean algebra has the underlying set $\{0,1\}$ . Its three standard operations are AND, written $a\land b$ ; OR, written $a\lor b$ ; and NOT, written $\neg a$ . AND produces 1 only when both inputs are 1. OR produces 1 when at least one input is 1, including when both are 1. NOT interchanges 0 and 1. A truth table records these operations explicitly: (csg.csail.mit.edu)

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

Engineering notation often writes AND as multiplication, OR as addition, and NOT with an overbar. These symbols do not denote ordinary arithmetic: Boolean $1+1=1$ . OR also differs from exclusive OR, which produces 1 exactly when its two inputs differ. (ocw.mit.edu)

Algebraic structure and laws

Formally, a Boolean algebra consists of a set $B$ , binary operations $\land$ and $\lor$ , a unary complement operation $\neg$ , and distinguished elements 0 and 1. Its axioms require a bounded distributive lattice in which every element has a complement. Both binary operations are commutative and associative. They satisfy absorption and distribute over one another: (boole.stanford.edu)

a\land(a\lor b)=a,\qquad a\lor(a\land b)=a,

a\land(b\lor c)=(a\land b)\lor(a\land c),

a\lor(b\land c)=(a\lor b)\land(a\lor c).

The bounds and complements obey

a\land1=a,\quad a\lor0=a,\quad a\land\neg a=0,\quad a\lor\neg a=1.

Consequences include idempotence, $a\land a=a$ and $a\lor a=a$ , and double negation, $\neg\neg a=a$ . De Morgan’s laws describe how complementation exchanges the two operations:

\neg(a\land b)=\neg a\lor\neg b,\qquad \neg(a\lor b)=\neg a\land\neg b.

These identities support systematic transformations of expressions without changing their values. (csg.csail.mit.edu)

Sets and representation

In set theory, the power set $\mathcal P(X)$ , containing every subset of a fixed set $X$ , forms a Boolean algebra. AND corresponds to intersection, OR to union, and NOT to complement relative to $X$ . The empty set is 0, and $X$ itself is 1. A family containing these bounds and closed under the three operations also forms a Boolean algebra, even when it contains only some subsets of $X$ . (boole.stanford.edu)

An associated partial order is defined by

a\leq b\quad\text{if and only if}\quad a\land b=a.

For sets, this is inclusion. Every finite Boolean algebra is isomorphic to the power set of its atoms, where an atom means a minimal nonzero element. Thus, a finite Boolean algebra has $2^n$ elements for some nonnegative integer $n$ . Stone’s representation theorem extends the set interpretation: every Boolean algebra is isomorphic to an algebra of sets. Its topological formulation connects Boolean algebras with special spaces in topology. (math.uwaterloo.ca)

Logical expressions and normal forms

In classical propositional logic, Boolean operations interpret the connectives “and,” “or,” and “not.” A Boolean function of $n$ variables maps $\{0,1\}^n$ to $\{0,1\}$ . Its truth table has $2^n$ input rows, so complete tabulation grows exponentially with the number of variables. Different expressions may describe the same function. (boole.stanford.edu)

Every Boolean function can be expressed in disjunctive normal form, an OR of AND terms. A canonical construction takes each truth-table row with output 1 and forms a term using every variable, negated when that row assigns it 0. OR joins these terms. Dually, conjunctive normal form is an AND of OR clauses. Canonical forms provide systematic representations but are not necessarily compact. (ocw.mit.edu)

Digital implementation

In digital systems, Boolean values represent abstract states carried by signals. A logic gate implements a Boolean operation, and interconnected gates implement more complicated functions. AND, OR, and NOT suffice to express every Boolean function. NAND alone, or NOR alone, also suffices; each is therefore functionally complete. (csg.csail.mit.edu)

Algebraic simplification can reduce the required circuit structure. For example,

(a\land b)\lor(a\land\neg b) =a\land(b\lor\neg b)=a.

However, Boolean equivalence describes logical behavior rather than all physical properties. Equivalent implementations may differ in propagation delay and gate arrangement. Circuit synthesis consequently combines algebraic manipulation with implementation constraints, including the number of inputs available on individual gates. (ocw.mit.edu)