SOP, POS, minterms and maxterms

Why it exists

A truth table says what a function is; a circuit needs an expression. There are many expressions for one function, so engineers fix two standard shapes: sum of products (an OR of AND terms, a two-level AND-OR circuit) and product of sums (an AND of OR terms, a two-level OR-AND circuit). Every function has a unique canonical form in each shape, built directly from its truth table, and every minimisation method (K-map, tabular) starts from it. GATE questions in this area ask you to list the minterms, convert between the two canonical forms, count minterms, or identify the complement.

Prerequisites

You need the laws from Boolean algebra, especially $x + x' = 1$ and De Morgan.

Precise definitions

Literal. A variable or its complement ($A$ or $A'$).

Product term (AND term). A literal or an AND of literals. Sum term (OR term). A literal or an OR of literals.

Sum of products (SOP). An OR of product terms, for example $AB' + C$. Product of sums (POS). An AND of sum terms, for example $(A + B')(C + D)$. A form with at most two levels of gates (not counting inverters) is a standard form.

Minterm. For $n$ variables, a product term that contains every variable exactly once, so that it is 1 on exactly one row of the truth table. The row with binary index $i$ (the first variable is the most significant bit) has the minterm $m_i$: a variable appears uncomplemented where the bit of $i$ is 1 and complemented where it is 0. For three variables $A, B, C$:

Maxterm. A sum term that contains every variable exactly once, so that it is 0 on exactly one row. The maxterm $M_i$ has a variable uncomplemented where the bit of $i$ is 0 and complemented where it is 1 (the opposite of the minterm). The two are complements: $M_i = (m_i)'$ and $m_i = (M_i)'$.

Useful facts about minterms. Two different minterms multiply to 0 ($m_i m_j = 0$ for $i \ne j$). All $2^n$ minterms add up to 1. A minterm with $n$ variables has $n$ literals.

Canonical sum of products (sum of minterms). The function equals the OR of the minterms of the rows where it is 1:

$F = \sum m(i_1, i_2, \dots) .$

Canonical product of sums (product of maxterms). The function equals the AND of the maxterms of the rows where it is 0:

$F = \prod M(j_1, j_2, \dots) .$

Conversion. If $F = \sum m(S)$ over $n$ variables, then $F = \prod M(T)$ where $T$ is the set of all indices not in $S$. Also $F' = \sum m(T)$ and $F' = \prod M(S)$. The two canonical forms of one function list complementary sets of indices. A function with $k$ ones has $k$ minterms in its canonical SOP and $2^n - k$ maxterms in its canonical POS.

Obtaining a canonical SOP from any SOP. Multiply each product term that lacks a variable $x$ by $(x + x')$ and expand; remove duplicates. For a canonical POS from a POS, add $x x'$ to each sum term lacking $x$ and use the distributive law $x + yz = (x+y)(x+z)$.

Don't cares. An input combination that cannot occur, or whose output is not needed, is a don't care, written $d(\dots)$ or X. A function is then given as $F = \sum m(\dots) + \sum d(\dots)$. The designer may treat each don't care as 0 or 1, whichever gives a simpler circuit (see Karnaugh maps).

Minimal forms. A minimal SOP has the fewest product terms and, among those, the fewest literals. The canonical SOP is rarely minimal. The $n$-input parity (XOR) function is the extreme case: no two minterms are adjacent, so its minimal SOP is its canonical SOP, with $2^{n-1}$ terms of $n$ literals.

Counting. There are $2^n$ minterms for $n$ variables, so $2^{2^n}$ functions (each subset of minterms is a different function). A product term that omits $k$ of the $n$ variables is a sum of $2^k$ minterms.

How it works

Step through the table for $F = AB' + C$. The columns show the function, its sum of minterms $m_1 + m_3 + m_4 + m_5 + m_7$, and its product of maxterms $M_0 M_2 M_6$. Rows where $F = 1$ are exactly the minterms; rows where $F = 0$ are exactly the maxterms. The two canonical forms agree on every row.

Method: write the truth table, then read it off. For SOP, take each row with output 1, write the product of all variables (true form for a 1, complemented for a 0) and OR them. For POS, take each row with output 0, write the sum of all variables (true form for a 0, complemented for a 1) and AND them. The reversal of the rule between minterm and maxterm is the usual place to slip; check one row (substitute the row's values: a minterm must give 1, a maxterm must give 0).

Worked examples

#include <stdio.h>
 
static int f1(int a, int b, int c) { return (a && !b) || c; }
static int f2(int a, int b, int c) { return (!a && b) || (a && c); }
 
static void lists(const char *name, int (*f)(int, int, int)) {
    printf("%s: minterms", name);
    for (int i = 0; i < 8; i++)
        if (f((i >> 2) & 1, (i >> 1) & 1, i & 1)) printf(" %d", i);
    printf(" | maxterms");
    for (int i = 0; i < 8; i++)
        if (!f((i >> 2) & 1, (i >> 1) & 1, i & 1)) printf(" %d", i);
    printf("\n");
}
 
int main(void) {
    lists("AB'+C", f1);
    lists("A'B+AC", f2);
    int count = 0;
    for (int i = 0; i < 16; i++) {
        int a = (i >> 3) & 1, b = (i >> 2) & 1;
        if (a || !b) count++;
    }
    printf("A+B' over four variables has %d minterms\n", count);
    return 0;
}

AB'+C: minterms 1 3 4 5 7 | maxterms 0 2 6
A'B+AC: minterms 2 3 5 7 | maxterms 0 1 4 6
A+B' over four variables has 12 minterms

Cheat box

Traps and GATE patterns

Connections

Both canonical forms are what a Karnaugh map and the tabular method start from. A decoder generates all minterms of its inputs, so any function is an OR of decoder outputs. A multiplexer with $n - 1$ select lines implements a sum of minterms by Shannon expansion, and the design of combinational circuits begins with exactly this truth-table-to-expression step.

PYQs

The number of min-terms after minimizing the
following Boolean expression is ________.

[D' + AB' + A'C + AC'D + A'C'D]'.

The truth table represents the Boolean function

Given f1,f2 and f in the canonical sum of products
form(in decimal) for the circuit

f1 = Σm(4, 5, 6, 7, 8)

f3 = Σm(1, 6, 15)

f = Σm(1, 6, 8, 15)

then f2 is

Self-check

Revision card

References