Minterms/maxterms; K-map Σm(2,4,5,13,14)+d, universal gates

Minterm and maxterm

A minterm is a product (AND) term that contains every variable of the function exactly once, in true or complemented form. It equals 1 for exactly one input combination. A variable is written true if its value is 1 and complemented if it is 0; e.g. for ABC = 101 the minterm is $m_5 = A\overline{B}C$. A function in canonical SOP is a sum of minterms: $F = \Sigma m(\dots)$.

A maxterm is a sum (OR) term that contains every variable exactly once, in true or complemented form. It equals 0 for exactly one input combination. A variable is written true if its value is 0 and complemented if it is 1; e.g. for ABC = 101 the maxterm is $M_5 = \overline{A}+B+\overline{C}$. A function in canonical POS is a product of maxterms: $F = \Pi M(\dots)$.

$M_i = \overline{m_i}$, and a function's minterm list and maxterm list are complementary (together they hold all $2^n$ numbers).

Simplification by K-map

$F(A,B,C,D) = \Sigma m(2,4,5,13,14) + d(0,1,8,10)$

        CD
AB      00  01  11  10
      +---+---+---+---+
 00   | X | X | 0 | 1 |
      +---+---+---+---+
 01   | 1 | 1 | 0 | 0 |
      +---+---+---+---+
 11   | 0 | 1 | 0 | 1 |
      +---+---+---+---+
 10   | X | 0 | 0 | X |
      +---+---+---+---+

• Quad m(0,1,4,5) → $\overline{A}\,\overline{C}$
• Quad m(0,2,8,10) → $\overline{B}\,\overline{D}$
• Pair m(5,13) → $B\overline{C}D$
• Pair m(10,14) → $AC\overline{D}$

$$F = \overline{A}\,\overline{C} + \overline{B}\,\overline{D} + B\overline{C}D + AC\overline{D}$$

Check: 4, 5 by $\overline{A}\,\overline{C}$ (with 0, 1); 2 by $\overline{B}\,\overline{D}$ (with 0, 8, 10); 13 by $B\overline{C}D$; 14 by $AC\overline{D}$ (with 10). This is a minimal cover (4 terms, 10 literals); the minimal POS also needs 4 terms and 10 literals, so the SOP form is used.

Logic diagram using universal gates (NAND only)

An SOP expression maps directly to a two-level NAND-NAND circuit (De Morgan: $X + Y = \overline{\overline{X}\cdot\overline{Y}}$). Each product term becomes a first-level NAND and the output NAND replaces the OR gate. Complemented inputs are made with NAND gates whose inputs are tied.

$$F = \overline{\overline{\overline{A}\,\overline{C}}\cdot\overline{\overline{B}\,\overline{D}}\cdot\overline{B\overline{C}D}\cdot\overline{AC\overline{D}}}$$

A ──[NAND]── A'   (inputs tied)
B ──[NAND]── B'   (inputs tied)
C ──[NAND]── C'   (inputs tied)
D ──[NAND]── D'   (inputs tied)

A', C'   ──[NAND]── P1  ─┐
B', D'   ──[NAND]── P2  ─┤
                         ├──[NAND]── F
B, C', D ──[NAND]── P3  ─┤
A, C, D' ──[NAND]── P4  ─┘

Gates: 4 NAND inverters, two 2-input NANDs, two 3-input NANDs and one 4-input output NAND (9 NAND gates).