Boolean Algebra

Boolean algebra is the branch of algebra in which the values of the variables are the truth values true ($1$) and false ($0$). It is fundamental to computer science, digital logic circuits, and set theory.

Basic Operators & Logic Gates

The primary operations of Boolean algebra are conjunction (AND), disjunction (OR), and negation (NOT). These operations are implemented in hardware as logic gates.

AND ($\wedge$, $\cdot$): Outputs true only if all inputs are true. Corresponds to the AND gate.
OR ($\vee$, $+$): Outputs true if at least one input is true. Corresponds to the OR gate.
NOT ($\neg$, $\bar{}$, $'$): Inverts the input; true becomes false, and vice versa. Corresponds to the NOT gate (inverter).

Derived operators include:

XOR ($\oplus$): Exclusive OR. Outputs true if exactly one input is true (inputs are different). Corresponds to the XOR gate.
NAND: NOT AND. Outputs false only if all inputs are true. Corresponds to the NAND gate (Universal gate).
NOR: NOT OR. Outputs true only if all inputs are false. Corresponds to the NOR gate (Universal gate).

Truth Tables

A truth table is a mathematical table used in logic to compute the functional values of logical expressions on each of their functional arguments.

$A$	$B$	AND ($A \wedge B$)	OR ($A \vee B$)	XOR ($A \oplus B$)	NAND	NOR
0	0	0	0	0	1	1
0	1	0	1	1	1	0
1	0	0	1	1	1	0
1	1	1	1	0	0	0

$A$	NOT ($\neg A$)
0	1
1	0

Laws and Theorems

Boolean algebra obeys several fundamental laws, allowing us to simplify complex logical expressions and circuit designs.

Absorption Law

A term is absorbed when it is redundantly "OR"-ed or "AND"-ed. $$ A \vee (A \wedge B) \Leftrightarrow A $$ $$ A \wedge (A \vee B) \Leftrightarrow A $$

Annulment Law

A term "AND"-ed with 0 is always 0. A term "OR"-ed with 1 is always 1. $$ A \wedge 0 \Leftrightarrow 0 $$ $$ A \vee 1 \Leftrightarrow 1 $$

Associative Law

The grouping of variables connected by the same operator does not affect the result. $$ A \vee (B \vee C) \Leftrightarrow (A \vee B) \vee C $$ $$ A \wedge (B \wedge C) \Leftrightarrow (A \wedge B) \wedge C $$

Commutative Law

The order of variables does not matter. $$ A \vee B \Leftrightarrow B \vee A $$ $$ A \wedge B \Leftrightarrow B \wedge A $$

Complement / Inverse Law

A term "OR"-ed with its complement equals 1. A term "AND"-ed with its complement equals 0. $$ A \vee \neg A \Leftrightarrow 1 $$ $$ A \wedge \neg A \Leftrightarrow 0 $$

De Morgan's Laws

The negation of a disjunction is the conjunction of the negations
The negation of a conjunction is the disjunction of the negations

Formally written, these are:

$$ \neg(P \vee Q) \Leftrightarrow (\neg P) \wedge (\neg Q) $$

and

$$ \neg(P \wedge Q) \Leftrightarrow (\neg P) \vee (\neg Q) $$

Distributive Law

Variables can be distributed across operators, similar to standard algebra. $$ A \wedge (B \vee C) \Leftrightarrow (A \wedge B) \vee (A \wedge C) $$ $$ A \vee (B \wedge C) \Leftrightarrow (A \vee B) \wedge (A \vee C) $$

Double Negation Law

Negating a term twice results in the original term. $$ \neg(\neg A) \Leftrightarrow A $$

Idempotent Law

A term "OR"-ed or "AND"-ed with itself equals itself. $$ A \vee A \Leftrightarrow A $$ $$ A \wedge A \Leftrightarrow A $$

Identity Law

A term "OR"-ed with 0 or "AND"-ed with 1 will always equal that term. $$ A \vee 0 \Leftrightarrow A $$ $$ A \wedge 1 \Leftrightarrow A $$

Set Theory Equivalences

Boolean operations map directly to fundamental operations in set theory.

AND ($\wedge$) $\Rightarrow$ Intersection ($\cap$): The complement of an intersection of two sets is the same as the union of their complements.
OR ($\vee$) $\Rightarrow$ Union ($\cup$): The complement of a union of two sets is the same as the intersection of their complements.
NOT ($\neg$) $\Rightarrow$ Complement ($A^c$ or $A'$): Elements not in set $A$.
0 (False) $\Rightarrow$ Empty Set ($\emptyset$): A set with no elements.
1 (True) $\Rightarrow$ Universal Set ($U$): The set of all elements under consideration.

For example, De Morgan's Laws in set theory are:

The complement of a union of two sets is the same as the intersection of their complements: $$ (A \cup B)^c = A^c \cap B^c $$
The complement of an intersection of two sets is the same as the union of their complements: $$ (A \cap B)^c = A^c \cup B^c $$