CMPE1550: SOP/POS Forms and Gate Mapping

📚 Lesson:SOP/POS Forms and Gate Mapping

🎯 Learning Objectives

By the end of this lesson, students will be able to:

  • Convert a truth table into a Boolean expression.
  • Minimize the expression using Boolean algebra or Karnaugh maps.
  • Implement the minimized logic using only NAND or only NOR gates.
  • Understand the universality of NAND and NOR gates.

1️⃣ What Are SOP and POS

  • Sum of Products (SOP): A logic function expressed as a sum (OR) of minterms (ANDed literals). Example: $F = A \cdot B + \overline{C} \cdot D$
  • Product of Sums (POS): A logic function expressed as a product (AND) of maxterms (ORed literals). Example: $F = (A + B) \cdot (\overline{C} + D)$

These forms are derived directly from truth tables and are the starting point for gate-level implementation.

2️⃣ Mapping SOP/POS to NAND/NOR Logic

Form Gate strategy Conversion Notes
SOP AND → OR Use NAND for AND terms, then NAND-based OR via De Morgan
POS OR → AND Use NOR for OR terms, then NOR-based AND via De Morgan

3️⃣ SOP → NAND-Only

  • SOP expressions consist of ANDed literals (minterms) ORed together.
  • This structure maps naturally to NAND logic:
  • Use NAND gates to simulate AND operations.
  • Use NAND-based OR (via De Morgan) to combine terms.

Given: F = $A \cdot B + C \cdot D$

Steps:

  1. AND terms:

$A \cdot B = \text{NAND}(A, B) \rightarrow \text{NAND}(NAND(A, B), NAND(A, B))$

$C \cdot D = \text{NAND}(C, D) \rightarrow \text{NAND}(NAND(A, B), NAND(A, B))$

  1. OR of terms:

Use De Morgan:

$F = \text{NAND}(NAND(AB), NAND(CD))$

Example:

F = A·B + C·D
→ NAND(A, B) → AND
→ NAND(C, D) → AND
→ Final OR = NAND(NAND(A·B), NAND(C·D))

4️⃣ POS → NOR-Only

  • POS expressions consist of ORed literals (maxterms) ANDed together.
  • This structure maps naturally to NOR logic:
  • Use NOR gates to simulate OR operations.
  • Use NOR-based AND (via De Morgan) to combine terms.

Given Boolean Expression:

$F = A \cdot B + C$

Step 1: Express using basic gates This is an OR of an AND and a literal:

$F = (A \cdot B) + C$

Step 2: Replace each gate with NOR equivalents

  • $A \cdot B = \text{NOR}(\text{NOR}(A, A), \text{NOR}(B, B))$

  • $C → C = \text{NOR}(C, C)$

If used directly, we need to invert it.

  • Final OR → Use NOR of NORs:

$F = \text{NOR}(\text{NOR}(A \cdot B, C), \text{NOR}(A \cdot B, C))$

But since A \cdot B and C are already NOR expressions, we substitute them in.

Example:

F = (A + B)·(C + D)
→ NOR(A, B) → OR
→ NOR(C, D) → OR
→ Final AND = NOR(NOR(A + B), NOR(C + D))

5️⃣ Step-by-Step SOP Derivation

✅ Step 1: Identify the 1-output rows Scan the truth table and select all rows where the output F = 1.

✅ Step 2: Write a minterm for each 1-row For each selected row:

  • If a variable is 1, write it as the uncomplemented literal (e.g., A).
  • If a variable is 0, write it as the complemented literal (e.g., $\overline{A}$).
  • Combine the literals with AND (·). This is the opposite of POS, where 0s generate maxterms.

✅ Step 3: OR all minterms together Once all minterms are written, combine them using OR (+) to form the full SOP expression.

Example Truth Table:

A B C F
0 0 0 1 <-
0 0 1 0
0 1 0 1 <-
0 1 1 0
1 0 0 1 <-
1 0 1 0
1 1 0 1 <-
1 1 1 0

Step 1: Select 1-output rows

Rows 1, 3, 5, 7

Step 2: Write minterms

  • Row 1 (A=0, B=0, C=0): → $\overline{A} \cdot \overline{B} \cdot \overline{C}$

  • Row 3 (A=0, B=1, C=0): → $\overline{A} \cdot B \cdot \overline{C}$

  • Row 5 (A=1, B=0, C=0): → $A \cdot \overline{B} \cdot \overline{C}$

  • Row 7 (A=1, B=1, C=0): → $A \cdot B \cdot \overline{C}$

Step 3: Combine with OR \(F = (\overline{A} \cdot \overline{B} \cdot \overline{C}) + (\overline{A} \cdot B \cdot \overline{C}) + (A \cdot \overline{B} \cdot \overline{C}) + (A \cdot B \cdot \overline{C})\)

6️⃣ Step-by-Step POS Derivation

✅ Step 1: Identify the 0-output rows Scan the truth table and select all rows where the output F = 0.

✅ Step 2: Write a maxterm for each 0-row For each selected row:

  • If a variable is 0, write it as the uncomplemented literal (e.g., A).
  • If a variable is 1, write it as the complemented literal (e.g., $\overline{A}$).
  • Combine the literals with OR (+). This is the opposite of SOP, where 1s generate minterms.

✅ Step 3: AND all maxterms together Once all maxterms are written, combine them using AND (·) to form the full POS expression.

Example Truth Table:

A B C F
0 0 0 1
0 0 1 0 <-
0 1 0 1
0 1 1 0 <-
1 0 0 1
1 0 1 0 <-
1 1 0 1
1 1 1 0 <-

Step 1: Select 0-output rows Rows 2, 4, 6, 8

Step 2: Write maxterms

  • Row 2 (A=0, B=0, C=1): → $A + B + \overline{C}$

  • Row 4 (A=0, B=1, C=1): → $A + \overline{B} + \overline{C}$

  • Row 6 (A=1, B=0, C=1): → $\overline{A} + B + \overline{C}$

  • Row 8 (A=1, B=1, C=1): → $\overline{A} + \overline{B} + \overline{C}$

Step 3: Combine with AND

\[F = (A + B + \overline{C}) · (A + \overline{B} + \overline{C}) · (\overline{A} + B + \overline{C}) · (\overline{A} + \overline{B} + \overline{C})\]

7️⃣