Boolean Algebra

Boolean algebra is the algebra of two-valued logic used to describe and simplify digital circuits. Variables take values in $\{0,1\}$; the operations AND, OR and NOT correspond to series switches, parallel switches and inversion. Every gate network implements a Boolean function, and algebraic identities let you rewrite a network without changing its truth table.

This note states the axioms, the standard theorems (including De Morgan and absorption), duality, and the counting facts GATE tests: how many functions, how many minterms, what self-dual means. Canonical forms and universal gates continue in the next note.

Convention used in all Gate CS Mastery DL notes. Juxtaposition means AND; $+$ means OR; ${\cdot}'$ means NOT. Precedence: NOT binds tightest, then AND, then OR. So $x + yz'$ means $x + (y\cdot(z'))$.

A Boolean algebra on set $B=\{0,1\}$ with $+$, $\cdot$, ${\cdot}'$ satisfies, among other equivalent axiom sets:

From these one derives the remaining standard theorems. Hardware interprets 0 and 1 as logic levels; the algebra itself does not care which voltage is HIGH.

The dual of an expression swaps $+$ with $\cdot$ and $0$ with $1$, leaving variables and complements unchanged. If an identity holds, its dual holds. Example: the dual of $x+0=x$ is $x\cdot 1 = x$.

Duality versus complement. The two operations look alike and exams confuse them on purpose.

They are linked by $f^d(x_1, \ldots, x_n) = f'(x_1', \ldots, x_n')$: the dual is the complement evaluated at complemented inputs. Duality is a statement about identities (the dual of a true identity is true); it does not say that $f^d = f$ for a function, which holds only for self-dual $f$. Keep the parentheses that the original precedence implied: the dual of $x + yz$ is $x(y + z)$, not $xy + z$.

Self-dual function. A function $f$ is self-dual when $f(x_1,\ldots,x_n) = f'(x_1',\ldots,x_n')$ for every input (equivalently, $f = f^d$ where $f^d$ is the dual function). Self-dual functions are determined by their values on half of the input space (inputs whose first bit is 0, for example), so there are $2^{2^{n-1}}$ self-dual Boolean functions of $n$ variables.

Consensus removes the redundant $yz$ term when $xy$ and $x'z$ are present. It is the algebraic twin of eliminating a non-essential implicant.

Proof of consensus. $yz = yz(x + x') = xyz + x'yz$. The term $xyz$ is absorbed by $xy$ and $x'yz$ by $x'z$, so adding $yz$ changes nothing. The consensus of $xy$ and $x'z$ is formed by deleting the opposed variable $x$ and ANDing what is left: $y \cdot z$. Two terms have a consensus only when exactly one variable appears complemented in one and uncomplemented in the other.

For NAND, $(x \uparrow y) \uparrow z = xy + z'$ while $x \uparrow (y \uparrow z) = x' + yz$; they differ at $x = 1, y = 0, z = 0$. A multi-input NAND gate computes $(x_1 x_2 \cdots x_k)'$; it is not a cascade of two-input NANDs.

No cancellation law. $x + y = x + z$ does not imply $y = z$ (take $x = 1$), and $xy = xz$ does not imply $y = z$ (take $x = 0$). If both equations hold, then $y = z$. Do not "cancel" a common term from both sides of a Boolean equation.

Substitute 0/1 for each variable and apply the operations with the precedence above, or build a truth table with $2^n$ rows for $n$ variables.

Apply identities to reduce literal count or gate count. Typical moves: factor (distributive), absorb, cancel $x+x'=1$, apply De Morgan to push complements inward, drop consensus terms.

Example. $f = xy + xy' + x'z$. First $xy + xy' = x(y + y') = x$, so $f = x + x'z$. By the distributive law of OR over AND, $x + x'z = (x + x')(x + z) = x + z$. So $f = x + z$.

Example (product of sums). $(a + b)(a' + c) = aa' + ac + a'b + bc = ac + a'b + bc = ac + a'b$, where the last step drops $bc$, the consensus of $ac$ and $a'b$.

Example (factor and absorb). $x'y'z + x'yz + xy' = x'z(y' + y) + xy' = x'z + xy'$. No further reduction is possible: the two terms have no consensus in a variable that makes either redundant.

Why each count holds.

Truth-table evaluation of an expression tree is the reference semantics for every later minimization note.

Two expressions are equivalent exactly when their truth tables match. A truth table with $2^n$ rows is a complete proof of any identity in $n$ variables.

Shannon expansion (Boole's expansion). For any $f$,

Iterating yields the sum-of-minterms canonical form (next note). The dual expansion with AND of OR-clauses yields the product of maxterms.

XOR and XNOR. $x\oplus y = xy' + x'y$, and $x\odot y = xy + x'y'$. XOR is associative and commutative; $x\oplus x = 0$, $x\oplus 0 = x$, $x\oplus 1 = x'$. Any Boolean function has an algebraic normal form as a XOR of ANDs (Reed-Muller), which is useful but not required for GATE beyond small identities.

Further XOR facts used below:

Shannon expansion as a multiplexer. Expanding $f = xy + x'z$ about $x$ gives $f(1, y, z) = y$ and $f(0, y, z) = z$, so $f = x\cdot y + x'\cdot z$: a 2:1 multiplexer with select $x$. This is the basis of MUX-based function implementation in the Multiplexers, Decoders and Encoders note.

For $x+xy$: if $x=1$, both sides 1; if $x=0$, both sides 0. So $x+xy=x$. Dual: $x(x+y)=x$.

$(xyz)' = x'+y'+z'$ by applying the two-variable rule twice. Dual: $(x+y+z)'=x'y'z'$.

$f'(x') = (x')' = x = f(x)$, yes. Is $f=xy$ self-dual? Dual is $x+y$, and $xy \ne x+y$, so no.

$f = xy + x'z + yz$. Truth-table check shows $f$ equals $xy + x'z$ on all 8 inputs of three variables; the $yz$ term never turns a 0 into a 1 that the first two terms miss.

For $f = (x + y')z + 0$: the dual is $f^d = (xy' + z)\cdot 1 = xy' + z$, and the complement is $f' = (x'y + z')\cdot 1 = x'y + z'$. Check the link at $x = 1, y = 1, z = 0$: $f'(x', y', z') = f'(0, 0, 1) = 0 + 0 = 0$, and $f^d(1, 1, 0) = 0 + 0 = 0$.

How many functions $f(x, y, z)$ satisfy $f(0,0,0) = 0$ and $f(1,1,1) = 1$? Two of the 8 rows are fixed, so $2^6 = 64$. How many of the 70 neutral functions are also self-dual? All 16 self-dual functions are neutral, so 16.

Common misconceptions.