Combinational Logic Circuits

Given $F(A,B,C,D) = \Sigma m(1,2,3,8,9,10,11,14) + d(0,4,12)$, where X marks a don't-care cell.

K-map simplification

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

Groups (don't-cares 0 and 12 are used where they make a group bigger; don't-care 4 is left out):

• Octet m(0,1,2,3,8,9,10,11) → $\overline{B}$
• Quad m(8,10,12,14) → $A\overline{D}$

$$F = \overline{B} + A\overline{D}$$

Check: the octet covers 1, 2, 3, 8, 9, 10, 11, and the quad covers 8, 10, 14 (with 12). All minterms are covered.

Realization using NAND gates

Take double complement and apply De Morgan's theorem:

$$\begin{aligned} F &= \overline{\overline{\overline{B} + A\overline{D}}} \\ &= \overline{B \cdot \overline{A\overline{D}}} \end{aligned}$$

So $F$ = NAND($B$, NAND($A$, $\overline{D}$)). $\overline{D}$ is made with a NAND gate whose inputs are tied together. The single literal $\overline{B}$ goes into the output NAND as plain $B$.

D ──[NAND]── D'   (inputs tied)

A, D' ──[NAND]── P1  ─┐
                      ├──[NAND]── F
B     ──────────     ─┘

Total: 3 two-input NAND gates (one used as an inverter).

A hazard is an unwanted short pulse (glitch) at the output of a combinational circuit. It happens when an input changes and different signal paths have different propagation delays, so the output briefly takes a wrong value even though the steady-state value is correct.

Static hazard

The output should stay at the same value, but it momentarily changes and comes back.

• Static-1 hazard: output should stay 1 but goes $1 \to 0 \to 1$. Occurs in SOP (AND-OR) circuits.
• Static-0 hazard: output should stay 0 but goes $0 \to 1 \to 0$. Occurs in POS (OR-AND) circuits.

Dynamic hazard

The output should change once ($0 \to 1$ or $1 \to 0$) but it changes three or more times, e.g. $0 \to 1 \to 0 \to 1$. It happens in multi-level circuits where one input reaches the output through three or more paths of different delay. A circuit that is free of static hazards at every level (a two-level hazard-free design) is also free of dynamic hazards.

Example of a static-1 hazard

$$F = AB + \overline{A}C$$

Let $B = C = 1$. Then $F = A + \overline{A} = 1$ for both values of A, so F should stay at 1.

A ──┬──────────[AND]── AB ──┐
    │     B ───┘            [OR]── F
    └─[NOT]──A'─[AND]─ A'C ─┘
          C ────┘

When A falls from 1 to 0, AB goes to 0 at once, but A'C rises only after the inverter delay. For that short time both AND outputs are 0, so F dips to 0: a static-1 hazard.

A    ‾‾‾‾‾|_________
AB   ‾‾‾‾‾|_________
A'C  ______|‾‾‾‾‾‾‾‾   (late by inverter delay)
F    ‾‾‾‾‾|_|‾‾‾‾‾‾‾   (glitch)

Eliminating the hazard

On the K-map, the two groups AB (cells 6, 7) and A'C (cells 1, 3) sit next to each other (cells 3 and 7) but no group covers both. A move between two adjacent 1-cells that are in different groups is a hazard.

The fix is to add a redundant group (the consensus term) that covers the adjacent cells:

$$F = AB + \overline{A}C + BC$$

When $B = C = 1$, the extra term $BC = 1$ holds F at 1 while A changes, so the glitch is removed. The logic function is unchanged because $BC$ is the consensus of $AB$ and $\overline{A}C$.

Rule: in an SOP circuit, make sure every pair of adjacent 1s on the K-map is covered by at least one common group. For POS circuits, do the same with the 0s to remove static-0 hazards.

$Y(A,B,C,D) = \Pi M(0,2,4,6,7,8,10,13,15)$ means Y = 0 at these cells. So Y = 1 at the remaining cells:

$$Y = \Sigma m(1,3,5,9,11,12,14)$$

K-map simplification

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

Grouping the 1s:

• Quad m(1,3,9,11) → $\overline{B}D$
• Pair m(1,5) → $\overline{A}\,\overline{C}D$
• Pair m(12,14) → $AB\overline{D}$

$$Y = B'D + A'C'D + ABD'$$

(Grouping the 0s gives the minimal POS $Y = (A+D)(B+D)(\overline{A}+\overline{B}+\overline{D})(\overline{B}+\overline{C}+\overline{D})$, which has more terms, so the SOP form is used.)

Realization with an 8:1 multiplexer

Use A, B, C as the select lines $S_2 S_1 S_0$ and connect each data input $I_0$–$I_7$ to 0, 1, D or $\overline{D}$. For each value of ABC, compare Y for D = 0 and D = 1:

          +-----------+
 D  ───── | I0        |
 D  ───── | I1        |
 D  ───── | I2        |
 0  ───── | I3  8:1   |── Y
 D  ───── | I4  MUX   |
 D  ───── | I5        |
 D' ───── | I6        |
 D' ───── | I7        |
          +-----------+
           S2  S1  S0
           A   B   C

 D ──[NOT]── D'

Only one NOT gate is needed besides the multiplexer. Check: for $ABC = 110$, Y = $\overline{D}$, so minterm 12 (D=0) gives 1 and minterm 13 gives 0, as required.

Given $F(A,B,C,D) = \Sigma m(0,2,4,5,11) + d(3,7,12,15)$.

K-map simplification

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

Groups (don't-cares 3, 7, 15 are used for the quad; 12 is not needed):

• Pair m(0,2) → $\overline{A}\,\overline{B}\,\overline{D}$
• Pair m(4,5) → $\overline{A}B\overline{C}$
• Quad m(3,7,11,15) → $CD$

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

Check: 0, 2 by $\overline{A}\,\overline{B}\,\overline{D}$; 4, 5 by $\overline{A}B\overline{C}$; 11 by $CD$. (The minimal POS needs four sum terms, so SOP is simpler here.)

Realization using NOR gates only

For NOR-only realization of an SOP expression, write each product term as a NOR of complemented literals (De Morgan: $\overline{X}\,\overline{Y} = \overline{X+Y}$), feed these to a NOR gate (which gives $\overline{F}$), and invert with one more NOR whose inputs are tied.

$$\begin{aligned} \overline{A}\,\overline{B}\,\overline{D} &= \overline{A+B+D} \\ \overline{A}B\overline{C} &= \overline{A+\overline{B}+C} \\ CD &= \overline{\overline{C}+\overline{D}} \\ F &= \overline{\overline{P_1+P_2+P_3}} \end{aligned}$$

where $P_1, P_2, P_3$ are the three first-level NOR outputs.

B ──[NOR]── B'   (inputs tied)
C ──[NOR]── C'   (inputs tied)
D ──[NOR]── D'   (inputs tied)

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

F' ──[NOR]── F   (inputs tied)

Gates used: 3 NOR inverters (for $\overline{B}, \overline{C}, \overline{D}$), three first-level NORs, one 3-input NOR and one NOR inverter: 8 NOR gates in all.

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

K-map simplification (grouping 1s)

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

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

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

Variable A drops out completely.

POS form for NOR realization

NOR gates give a POS expression directly (NOR-NOR = OR-AND). The 0s are at cells 3, 6 and 14; grouping them (with don't-care 11):

• Pair of 0s M(3,11) → $(B+\overline{C}+\overline{D})$
• Pair of 0s M(6,14) → $(\overline{B}+\overline{C}+D)$

$$F = (B+\overline{C}+\overline{D})(\overline{B}+\overline{C}+D)$$

Check: the SOP and POS forms agree on every cell; e.g. cell 6 (B=1, C=1, D=0) makes the second sum term 0, so F = 0.

NOR-only circuit

$$F = \overline{\overline{(B+\overline{C}+\overline{D})} + \overline{(\overline{B}+\overline{C}+D)}}$$

B ──[NOR]── B'   (inputs tied)
C ──[NOR]── C'   (inputs tied)
D ──[NOR]── D'   (inputs tied)

B, C', D' ──[NOR]── P1  ─┐
                         ├──[NOR]── F
B', C', D ──[NOR]── P2  ─┘

Gates: 3 NOR inverters, 2 three-input NORs and 1 two-input NOR: 6 NOR gates. (Implementing the SOP form instead would need more gates.)

Given $F(A,B,C,D) = \Sigma m(7,9,12,13,14,15) + d(0,2,3,5)$.

K-map simplification

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

Groups (don't-care 5 is used in the BD quad; 0, 2, 3 are not needed):

• Quad m(12,13,14,15) → $AB$
• Pair m(9,13) → $A\overline{C}D$
• Quad m(5,7,13,15) → $BD$

$$F = AB + BD + A\overline{C}D$$

Check: 12, 13, 14, 15 by AB; 7 (and 5, 13, 15) by BD; 9 by $A\overline{C}D$.

Circuit using NOR gates only

For NOR-only realization of an SOP expression, write each product term as a NOR of complemented literals (De Morgan: $\overline{X}\,\overline{Y} = \overline{X+Y}$), feed these to a NOR gate (which gives $\overline{F}$), and invert with one more NOR whose inputs are tied.

$$\begin{aligned} AB &= \overline{\overline{A}+\overline{B}} \\ BD &= \overline{\overline{B}+\overline{D}} \\ A\overline{C}D &= \overline{\overline{A}+C+\overline{D}} \\ F &= \overline{\overline{P_1+P_2+P_3}} \end{aligned}$$

A ──[NOR]── A'   (inputs tied)
B ──[NOR]── B'   (inputs tied)
D ──[NOR]── D'   (inputs tied)

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

F' ──[NOR]── F   (inputs tied)

Gates: 3 NOR inverters ($\overline{A}, \overline{B}, \overline{D}$), 3 first-level NORs, a 3-input NOR giving $\overline{F}$ and a final NOR inverter.

Given $F(A,B,C,D) = \Sigma m(3,4,6,8,10,15) + d(0,2,7,14)$.

K-map and minimal SOP

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

Every group below is a quad, made possible by the don't-cares 0, 2, 7, 14:

• Quad m(2,3,6,7) → $\overline{A}C$
• Quad m(0,2,4,6) → $\overline{A}\,\overline{D}$
• Quad m(0,2,8,10) → $\overline{B}\,\overline{D}$
• Quad m(6,7,14,15) → $BC$

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

Check: 3 (and 2, 7) by $\overline{A}C$; 4, 6 by $\overline{A}\,\overline{D}$; 8, 10 by $\overline{B}\,\overline{D}$; 15 (with 7, 14) by $BC$. This is the only minimal SOP (4 terms, 8 literals).

Implementation using NOR gates only

For NOR-only realization of an SOP expression, write each product term as a NOR of complemented literals (De Morgan: $\overline{X}\,\overline{Y} = \overline{X+Y}$), feed these to a NOR gate (which gives $\overline{F}$), and invert with one more NOR whose inputs are tied.

$$\begin{aligned} \overline{A}C &= \overline{A+\overline{C}} & \overline{A}\,\overline{D} &= \overline{A+D} \\ \overline{B}\,\overline{D} &= \overline{B+D} & BC &= \overline{\overline{B}+\overline{C}} \end{aligned}$$ $$F = \overline{\overline{P_1+P_2+P_3+P_4}}$$

B ──[NOR]── B'   (inputs tied)
C ──[NOR]── C'   (inputs tied)

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

F' ──[NOR]── F   (inputs tied)

Gates: 2 NOR inverters ($\overline{B}, \overline{C}$), 4 two-input NORs, one 4-input NOR and one NOR inverter: 8 NOR gates.

Given $y(A,B,C,D) = \Pi M(0,2,3,8,10,11,12,15)$ with don't-cares $d = 7, 13, 14$. The listed maxterms are the 0-cells; the remaining cells 1, 4, 5, 6, 9 are 1s.

K-map

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

Simplified POS (grouping the 0s)

• Quad of 0s M(12,13,14,15) → $(\overline{A}+\overline{B})$
• Quad of 0s M(0,2,8,10) → $(B+D)$
• Quad of 0s M(3,7,11,15) → $(\overline{C}+\overline{D})$

$$y = (\overline{A}+\overline{B})(B+D)(\overline{C}+\overline{D})$$

Simplified SOP (grouping the 1s)

• Quad m(4,5,6,7) → $\overline{A}B$
• Quad m(1,5,9,13) → $\overline{C}D$

$$y = \overline{A}B + \overline{C}D$$

Both forms are correct. The SOP form has only 2 terms and 4 literals, so it gives the smaller NOR circuit.

Reduced circuit using NOR gates

Each product term becomes a NOR of complemented literals:

$$\begin{aligned} \overline{A}B &= \overline{A+\overline{B}} \\ \overline{C}D &= \overline{C+\overline{D}} \\ y &= \overline{\overline{\overline{A}B+\overline{C}D}} \end{aligned}$$

B ──[NOR]── B'   (inputs tied)
D ──[NOR]── D'   (inputs tied)

A, B' ──[NOR]── P1  ─┐
                     ├──[NOR]── y'
C, D' ──[NOR]── P2  ─┘

y' ──[NOR]── y   (inputs tied)

Gates: 2 NOR inverters, 2 first-level NORs, 1 NOR giving $\overline{y}$ and 1 NOR inverter: 6 two-input NOR gates.

(The POS form could be built as a NOR-NOR circuit, $y = \overline{\overline{\overline{A}+\overline{B}} + \overline{B+D} + \overline{\overline{C}+\overline{D}}}$, but it needs 8 NOR gates including inverters.)

A combinational logic circuit is a digital circuit whose outputs at any instant depend only on the present combination of its inputs. It has no memory and no feedback, so past inputs do not affect the output.

           +--------------------+
 x1 ──────>|                    |──────> z1
 x2 ──────>|   Combinational    |──────> z2
  :        |   logic (gates)    |   :
 xn ──────>|                    |──────> zm
           +--------------------+
     n inputs                 m outputs

Key features

• Built only from logic gates (AND, OR, NOT, NAND, NOR, XOR).
• Output = f(present inputs); it can be fully described by a truth table or Boolean expressions, one per output.
• No clock and no storage elements (no flip-flops).
• An n-input circuit has $2^n$ input combinations.

Examples: half adder, full adder, subtractor, multiplexer, demultiplexer, encoder, decoder, magnitude comparator, code converters.

By contrast, a sequential circuit contains memory (flip-flops), so its output depends on both present inputs and past history (the present state).

Given $F(A,B,C,D) = \Sigma m(0,1,4,8,10,11,12) + d(2,3,6,9,15)$.

K-map simplification

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

Groups (don't-cares 2, 3, 9 complete the octet; 6 and 15 are not used):

• Octet m(0,1,2,3,8,9,10,11) → $\overline{B}$
• Quad m(0,4,8,12) → $\overline{C}\,\overline{D}$

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

Check: the octet covers 0, 1, 8, 10, 11 and the quad covers 0, 4, 8, 12.

Conversion to NAND gates only

$$\begin{aligned} F &= \overline{\overline{\overline{B}+\overline{C}\,\overline{D}}} \\ &= \overline{B\cdot\overline{\overline{C}\,\overline{D}}} \end{aligned}$$

So $F$ = NAND($B$, NAND($\overline{C}$, $\overline{D}$)). The complements $\overline{C}$ and $\overline{D}$ come from NAND gates with tied inputs. The single literal $\overline{B}$ enters the output NAND as plain $B$.

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

C', D' ──[NAND]── P1  ─┐
                       ├──[NAND]── F
B      ──────────     ─┘

Total: 4 two-input NAND gates (two as inverters).

Given $F(A,B,C,D) = \Sigma m(0,1,4,8,10,11,12) + d(2,3,6,9,15)$.

K-map simplification

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

Groups (don't-cares 2, 3, 9 complete the octet; 6 and 15 are not used):

• Octet m(0,1,2,3,8,9,10,11) → $\overline{B}$
• Quad m(0,4,8,12) → $\overline{C}\,\overline{D}$

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

Check: the octet covers 0, 1, 8, 10, 11 and the quad covers 0, 4, 8, 12.

Realization using NOR gates

Write the product term as a NOR: $\overline{C}\,\overline{D} = \overline{C+D}$. Then

$$\begin{aligned} F &= \overline{B} + \overline{C+D} \\ &= \overline{\overline{\overline{B} + \overline{C+D}}} \end{aligned}$$

So: $P =$ NOR($C$, $D$); $\overline{F}$ = NOR($\overline{B}$, $P$); $F$ = NOR($\overline{F}$, $\overline{F}$).

B ──[NOR]── B'            (inputs tied)

C ──┐
    [NOR]── P ──┐
D ──┘           [NOR]── F' ──[NOR]── F
B' ─────────────┘          (inputs tied)

Total: 4 two-input NOR gates.

(Alternatively, the POS form $F = (\overline{B}+\overline{C})(\overline{B}+\overline{D})$ gives a NOR-NOR circuit, but it needs 6 NOR gates including inverters.)

Minterm numbers

Write each term as a binary number ABCD:

$$F = \Sigma m(4,5,6,7,8,9,10,12,14)$$

K-map minimization

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

• Quad m(4,5,6,7) → $\overline{A}B$
• Quad m(8,10,12,14) → $A\overline{D}$
• Pair m(8,9) → $A\overline{B}\,\overline{C}$

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

Check: row 01 is covered by $\overline{A}B$; 8, 10, 12, 14 by $A\overline{D}$; 9 (with 8) by $A\overline{B}\,\overline{C}$. The 9-term, 36-literal expression reduces to 3 terms and 7 literals.

NAND implementation

An SOP expression maps directly to a two-level NAND-NAND circuit:

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

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

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

Gates: 4 NAND inverters (for $\overline{A}, \overline{B}, \overline{C}, \overline{D}$), three first-level NANDs (two 2-input, one 3-input) and one 3-input output NAND.

A maxterm is a sum (OR) term that contains all the variables of the function exactly once, each either in true or complemented form. A maxterm is 0 for exactly one input combination and 1 for all others.

How to write a maxterm: for the input combination that should give 0, write a variable as it is if its value is 0, and complemented if its value is 1. Maxterm $M_i$ is the one that is 0 at decimal input $i$.

For three variables A, B, C:

Each maxterm is the complement of the minterm with the same number: $M_i = \overline{m_i}$.

Example: let F be 0 only for inputs 000, 010 and 101. The function is the AND (product) of the maxterms for these rows (the canonical POS form):

$$\begin{aligned} F &= M_0 \cdot M_2 \cdot M_5 = \Pi M(0,2,5) \\ &= (A+B+C)(A+\overline{B}+C)(\overline{A}+B+\overline{C}) \end{aligned}$$

Check: for input 010, the second factor $A+\overline{B}+C = 0+0+0 = 0$, so F = 0. For any other input not in the list, all three factors are 1, so F = 1.

Given $F(A,B,C,D) = \Sigma m(0,1,4,8,10,11,12) + d(2,3,6,9,15)$.

K-map simplification

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

Groups (don't-cares 2, 3, 9 complete the octet; 6 and 15 are not used):

• Octet m(0,1,2,3,8,9,10,11) → $\overline{B}$
• Quad m(0,4,8,12) → $\overline{C}\,\overline{D}$

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

Check: the octet covers 0, 1, 8, 10, 11 and the quad covers 0, 4, 8, 12.

Logic circuit

$F$ needs one OR gate, one AND gate and inverters for B, C, D:

B ──[NOT]── B' ─────────────┐
                            [OR]── F
C ──[NOT]── C' ──┐          │
                 [AND]─ C'D'┘
D ──[NOT]── D' ──┘

Since $\overline{C}\,\overline{D} = \overline{C+D}$, the AND gate with two inverters can be replaced by a single NOR gate:

B ──[NOT]── B' ─────────┐
                        [OR]── F
C ──┐                   │
    [NOR]── C'D' ───────┘
D ──┘

The simplified circuit uses only 3 gates (NOT, NOR, OR), compared with 7 four-input AND terms for the unsimplified expression.

Given $F(A,B,C,D) = \Sigma m(1,2,3,8,10,13) + d(0,4,5,6,7,9,12)$.

K-map simplification

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

The many don't-cares allow three large groups (two octets and one quad):

• Octet m(0,1,2,3,4,5,6,7) → $\overline{A}$
• Octet m(0,1,4,5,8,9,12,13) → $\overline{C}$
• Quad m(0,2,8,10) → $\overline{B}\,\overline{D}$

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

Check: 1, 2, 3 by $\overline{A}$; 8, 13 (and 1) by $\overline{C}$; 10 (and 2, 8) by $\overline{B}\,\overline{D}$. All six minterms are covered; don't-cares 0, 4, 5, 6, 7, 9, 12 are taken as 1, so the 0s are only 11, 14, 15.

Standard SOP expression

The standard (canonical) SOP lists every minterm where the simplified F is 1. Expanding:

• $\overline{A}$ → $m_0$ to $m_7$
• $\overline{C}$ → $m_0, m_1, m_4, m_5, m_8, m_9, m_{12}, m_{13}$
• $\overline{B}\,\overline{D}$ → $m_0, m_2, m_8, m_{10}$

$$F = \Sigma m(0,1,2,3,4,5,6,7,8,9,10,12,13)$$ $$\begin{aligned} F = {} & \overline{A}\,\overline{B}\,\overline{C}\,\overline{D} + \overline{A}\,\overline{B}\,\overline{C}D + \overline{A}\,\overline{B}C\overline{D} + \overline{A}\,\overline{B}CD + \overline{A}B\overline{C}\,\overline{D} + \overline{A}B\overline{C}D + \overline{A}BC\overline{D} \\ & + \overline{A}BCD + A\overline{B}\,\overline{C}\,\overline{D} + A\overline{B}\,\overline{C}D + A\overline{B}C\overline{D} + AB\overline{C}\,\overline{D} + AB\overline{C}D \end{aligned}$$

Without the don't-cares, the required minterms alone are $\Sigma m(1,2,3,8,10,13)$.

Given $F(A,B,C,D) = \Sigma m(1,2,3,8,9,10,11,13,14) + d(0,4,7,12)$. The 0-cells are 5, 6, 15.

K-map

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

Simplified SOP (grouping 1s)

• Octet m(0,1,2,3,8,9,10,11) → $\overline{B}$
• Quad m(8,9,12,13) → $A\overline{C}$
• Quad m(8,10,12,14) → $A\overline{D}$

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

Simplified POS (grouping 0s)

Treat don't-cares 4 and 7 as 0 so the 0s form large groups:

• Quad of 0s M(4,5,6,7) → $(A+\overline{B})$
• Pair of 0s M(7,15) → $(\overline{B}+\overline{C}+\overline{D})$

$$F = (A+\overline{B})(\overline{B}+\overline{C}+\overline{D})$$

Check: cell 5 (A=0, B=1) makes $A+\overline{B} = 0$; cell 15 (B=C=D=1) makes the second factor 0. All 1-cells give both factors = 1.

Standard POS expression

The standard (canonical) POS is the product of the maxterms where F = 0. For the simplified POS, the 0s are cells 4, 5, 6, 7 (from $A+\overline{B}$) and 7, 15 (from $\overline{B}+\overline{C}+\overline{D}$):

$$F = \Pi M(4,5,6,7,15)$$ $$\begin{aligned} F = {} & (A+\overline{B}+C+D)(A+\overline{B}+C+\overline{D})(A+\overline{B}+\overline{C}+D) \\ & (A+\overline{B}+\overline{C}+\overline{D})(\overline{A}+\overline{B}+\overline{C}+\overline{D}) \end{aligned}$$

In terms of the given data only, $F = \Pi M(5,6,15)\cdot d(0,4,7,12)$; the simplification chose don't-cares 4 and 7 as 0.

A standard (canonical) minterm form has all variables in every term. Here the variables are A, B, C.

Step 1: expand each term with the missing variables using $X + \overline{X} = 1$.

Term $A$ (B and C missing):

$$\begin{aligned} A &= A(B+\overline{B})(C+\overline{C}) \\ &= ABC + AB\overline{C} + A\overline{B}C + A\overline{B}\,\overline{C} \end{aligned}$$

Term $\overline{B}C$ (A missing):

$$\overline{B}C = \overline{B}C(A+\overline{A}) = A\overline{B}C + \overline{A}\,\overline{B}C$$

Step 2: add and remove the repeated term ($A\overline{B}C$ appears twice; $X + X = X$):

$$F = ABC + AB\overline{C} + A\overline{B}C + A\overline{B}\,\overline{C} + \overline{A}\,\overline{B}C$$

Step 3: write the minterm numbers

$$F = A + \overline{B}C = \Sigma m(1,4,5,6,7)$$

Check: F = 1 whenever A = 1 (rows 4 to 7) or when B = 0, C = 1 (rows 1 and 5), which gives the same set.

Given $F(A,B,C,D) = \Sigma m(0,2,4,6,8,10,15) + d(3,11,14)$.

K-map simplification

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

• Quad m(0,2,4,6) → $\overline{A}\,\overline{D}$
• Quad m(0,2,8,10) → $\overline{B}\,\overline{D}$
• Quad m(10,11,14,15) → $AC$

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

Check: 0, 2, 4, 6 by $\overline{A}\,\overline{D}$; 8, 10 by $\overline{B}\,\overline{D}$; 15 by $AC$ (using don't-cares 11 and 14). Don't-care 3 is not needed.

Reduced circuit using NOR gates

For NOR-only realization of an SOP expression, write each product term as a NOR of complemented literals (De Morgan: $\overline{X}\,\overline{Y} = \overline{X+Y}$), feed these to a NOR gate (which gives $\overline{F}$), and invert with one more NOR whose inputs are tied.

$$\begin{aligned} \overline{A}\,\overline{D} &= \overline{A+D} \\ \overline{B}\,\overline{D} &= \overline{B+D} \\ AC &= \overline{\overline{A}+\overline{C}} \\ F &= \overline{\overline{P_1+P_2+P_3}} \end{aligned}$$

A ──[NOR]── A'   (inputs tied)
C ──[NOR]── C'   (inputs tied)

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

F' ──[NOR]── F   (inputs tied)

Gates: 2 NOR inverters, 3 two-input NORs, one 3-input NOR and one NOR inverter: 7 NOR gates.

Given $F(A,B,C,D) = \Pi M(0,2,5,8,10) + d(7,15)$. The listed maxterms are the 0s; the other cells (except don't-cares 7, 15) are 1s.

Standard SOP

The standard (canonical) SOP is the sum of the minterms not in the maxterm list:

$$F = \Sigma m(1,3,4,6,9,11,12,13,14) + d(7,15)$$ $$\begin{aligned} F = {} & \overline{A}\,\overline{B}\,\overline{C}D + \overline{A}\,\overline{B}CD + \overline{A}B\overline{C}\,\overline{D} + \overline{A}BC\overline{D} + A\overline{B}\,\overline{C}D \\ & + A\overline{B}CD + AB\overline{C}\,\overline{D} + AB\overline{C}D + ABC\overline{D} \end{aligned}$$

K-map

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

Grouping 1s (minimal SOP):

• Quad m(1,3,9,11) → $\overline{B}D$
• Quad m(4,6,12,14) → $B\overline{D}$
• Quad m(9,11,13,15) → $AD$

$$F = \overline{B}D + B\overline{D} + AD$$

(The last term may also be taken as $AB$, quad 12, 13, 14, 15; both are minimal.)

Grouping 0s (minimal POS):

• Quad of 0s M(0,2,8,10) → $(B+D)$
• Pair of 0s M(5,7) → $(A+\overline{B}+\overline{D})$

$$F = (B+D)(A+\overline{B}+\overline{D})$$

Implementation using NOR gates only

The POS form has fewer terms, and POS maps directly to a two-level NOR-NOR circuit:

$$F = \overline{\overline{(B+D)} + \overline{(A+\overline{B}+\overline{D})}}$$

B ──[NOR]── B'   (inputs tied)
D ──[NOR]── D'   (inputs tied)

B, D      ──[NOR]── P1  ─┐
                         ├──[NOR]── F
A, B', D' ──[NOR]── P2  ─┘

Gates: 2 NOR inverters, one 2-input NOR, one 3-input NOR and one 2-input output NOR: 5 NOR gates.

Check with $ABCD = 0101$ (m5): $B+D = 1$, $A+\overline{B}+\overline{D} = 0$, so F = 0, correct.

Given $F(A,B,C,D) = \Sigma m(0,1,4,8,10,11,12) + d(2,3,6,9,15)$.

K-map simplification

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

Groups (don't-cares 2, 3, 9 complete the octet; 6 and 15 are not used):

• Octet m(0,1,2,3,8,9,10,11) → $\overline{B}$
• Quad m(0,4,8,12) → $\overline{C}\,\overline{D}$

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

Check: the octet covers 0, 1, 8, 10, 11 and the quad covers 0, 4, 8, 12.

Conversion of the result into standard minterm form

A standard (canonical) minterm form has every variable in every term. Multiply each term by $(X+\overline{X})$ for each missing variable X.

Term $\overline{B}$ (A, C, D missing):

$$\begin{aligned} \overline{B} &= \overline{B}(A+\overline{A})(C+\overline{C})(D+\overline{D}) \\ &= \overline{A}\,\overline{B}\,\overline{C}\,\overline{D} + \overline{A}\,\overline{B}\,\overline{C}D + \overline{A}\,\overline{B}C\overline{D} + \overline{A}\,\overline{B}CD \\ &\quad + A\overline{B}\,\overline{C}\,\overline{D} + A\overline{B}\,\overline{C}D + A\overline{B}C\overline{D} + A\overline{B}CD \\ &= m_0+m_1+m_2+m_3+m_8+m_9+m_{10}+m_{11} \end{aligned}$$

Term $\overline{C}\,\overline{D}$ (A, B missing):

$$\begin{aligned} \overline{C}\,\overline{D} &= (A+\overline{A})(B+\overline{B})\overline{C}\,\overline{D} \\ &= \overline{A}\,\overline{B}\,\overline{C}\,\overline{D} + \overline{A}B\overline{C}\,\overline{D} + A\overline{B}\,\overline{C}\,\overline{D} + AB\overline{C}\,\overline{D} \\ &= m_0+m_4+m_8+m_{12} \end{aligned}$$

Combine and drop repeated terms ($m_0$ and $m_8$ appear twice; $X+X=X$):

$$F = \Sigma m(0,1,2,3,4,8,9,10,11,12)$$ $$\begin{aligned} F = {} & \overline{A}\,\overline{B}\,\overline{C}\,\overline{D} + \overline{A}\,\overline{B}\,\overline{C}D + \overline{A}\,\overline{B}C\overline{D} + \overline{A}\,\overline{B}CD + \overline{A}B\overline{C}\,\overline{D} \\ & + A\overline{B}\,\overline{C}\,\overline{D} + A\overline{B}\,\overline{C}D + A\overline{B}C\overline{D} + A\overline{B}CD + AB\overline{C}\,\overline{D} \end{aligned}$$

This contains all 7 original minterms plus the don't-cares 2, 3, 9 that the simplification set to 1 (don't-cares 6 and 15 were taken as 0).

Given $F(A,B,C,D) = \Pi M(0,4,5,8,9,11,15)$. These cells are 0; the remaining cells are 1:

$$F = \Sigma m(1,2,3,6,7,10,12,13,14)$$

K-map

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

Grouping the 1s:

• Quad m(2,3,6,7) → $\overline{A}C$
• Quad m(2,6,10,14) → $C\overline{D}$
• Pair m(12,13) → $AB\overline{C}$
• Pair m(1,3) → $\overline{A}\,\overline{B}D$

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

Check: 2, 3, 6, 7 by $\overline{A}C$; 10, 14 (with 2, 6) by $C\overline{D}$; 12, 13 by $AB\overline{C}$; 1 (with 3) by $\overline{A}\,\overline{B}D$.

(Grouping the 0s gives the POS form $F = (A+\overline{B}+C)(A+C+D)(\overline{A}+B+C)(\overline{A}+\overline{C}+\overline{D})$, which has more literals, so the SOP form is the simplified answer.)

Standard SOP expression

The standard (canonical) SOP has one 4-literal minterm for each 1-cell:

$$\begin{aligned} F = {} & \overline{A}\,\overline{B}\,\overline{C}D + \overline{A}\,\overline{B}C\overline{D} + \overline{A}\,\overline{B}CD + \overline{A}BC\overline{D} + \overline{A}BCD \\ & + A\overline{B}C\overline{D} + AB\overline{C}\,\overline{D} + AB\overline{C}D + ABC\overline{D} \end{aligned}$$ $$= \Sigma m(1,2,3,6,7,10,12,13,14)$$

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.

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