Minterms/maxterms; K-map Σm(0,1,2,4,5,9,12,15)+d, NAND

Minterms and maxterms

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).

K-map simplification

$Y(A,B,C,D) = \Sigma m(0,1,2,4,5,9,12,15) + d(7,10,13)$

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

• Pair m(0,2) → $\overline{A}\,\overline{B}\,\overline{D}$
• Quad m(4,5,12,13) → $B\overline{C}$
• Quad m(1,5,9,13) → $\overline{C}D$
• Quad m(5,7,13,15) → $BD$

$$Y = \overline{A}\,\overline{B}\,\overline{D} + B\overline{C} + \overline{C}D + BD$$

Check: 0, 2 by $\overline{A}\,\overline{B}\,\overline{D}$; 4, 5, 12 by $B\overline{C}$; 1, 9 by $\overline{C}D$; 15 by $BD$ (with don't-cares 7, 13). Don't-care 10 is not used.

NAND-only implementation

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.

$$Y = \overline{\overline{\overline{A}\,\overline{B}\,\overline{D}}\cdot\overline{B\overline{C}}\cdot\overline{\overline{C}D}\cdot\overline{BD}}$$

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

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

Gates: 4 NAND inverters, 4 first-level NANDs and one 4-input output NAND.