Boolean Function

A Boolean function is a function whose inputs and output are binary — each variable is $0$ or $1$. It can be defined by a Boolean equation, a truth table, or one of the standard SOP / POS canonical forms.

A Boolean equation is built from literals (an appearance of a variable, possibly complemented) and terms (sub-expressions). Standard usage in digital design reserves the word term for products in SOP form and sums in POS form — minterms and maxterms in particular. The expression $B(A+D)+AC$, in this strict sense, has two top-level sum terms: $B(A+D)$ and $AC$. Some textbooks count every distinct sub-expression and literal occurrence as a “term,” which gives a much larger count (eight or so for this expression), but that usage isn’t standard. Stick to the SOP/POS sense: a term is a product or sum, and a literal is a single variable instance.

Boolean functions can be simplified using Boolean Algebra identities or visualized via Karnaugh Maps, but the same underlying function has many algebraic representations. The standard forms exist to give a canonical representation — one that any two equal functions share.

Standard forms

Two pairs of dual canonical forms:

• Minterm canonical form (canonical SOP) — disjunction of every minterm for which $f=1$.
• Maxterm canonical form (canonical POS) — conjunction of every maxterm for which $f=0$.

Standard forms are written with $\Sigma$ or $\Pi$ followed by the row indices:

$f(X,Y,Z)=\sum m(0,2,5,7)\text{or equivalently}f(X,Y,Z)=\prod M(1,3,4,6)$

The numbers index rows of the truth table. The two forms describe the same function — one lists where $f=1$, the other where $f=0$.

The maxterm canonical form can also be derived by applying De Morgan’s Laws to the minterm canonical form of $\overline{f}$.

SOP and POS (after simplification)

The bare canonical forms are usually huge. After simplification (via K-map or algebra), you end up in Sum-of-products or Product-of-sums form — same structure (disjunction of conjunctions, or conjunction of disjunctions), but with shorter terms that don’t necessarily list every variable.

Both simplified forms can be implemented as a two-level circuit: one layer of ANDs feeding an OR (SOP) or one layer of ORs feeding an AND (POS). Two-level circuits have predictable, low propagation delay.

Complement of a function

Two ways to find $\overline{f}$:

1. De Morgan’s Laws: push the negation through every operation. Each AND becomes an OR, each OR becomes an AND, and each literal flips its complement.
2. Dual + complement literals: take the dual of the expression (swap AND ↔ OR, $0\leftrightarrow 1$), then complement every literal. This works because the dual is what you’d get if “true” and “false” swapped roles, and the literal complementation switches each input back.

Both routes give the same answer. Pick whichever is easier for the expression in front of you.