Logic Gates

XOR

Example: F2 = x + y’ $\cdot$ z

AND, OR, NOT gates are sufficient for building any boolean function
- {AND, OR, NOT} is called a complete set of logic
However, other gates are also used because:
- They replace many AND, OR & NOT gates (e.g. XOR)
- Economical
- Self-sufficient or universal (e.g. NAND/NOR)
Universal gates: a gate that itself is a complete set of logic
- e.g. {NAND} is a complete set of logic (NAND: (A $\cdot$ B)’)
  - NOT x = (x $\cdot$ x)’
  - x AND y = ((x $\cdot$ y)’ $\cdot$ (x $\cdot$ y)’)’ (i.e. NOT (X NAND Y) )
  - x OR y = ((x $\cdot$ x)’ $\cdot$ (y $\cdot$ y)’)’ (i.e. (NOT X) NAND (NOT Y) )
- e.g. {NOR} is a complete set of logic (NOR: (A + B)’)
  - NOT x = (x + x)’
  - x AND y = ((x + x)’ + (x + x)’)’
  - x OR y = ((x + y)’ + (x + y)’)’
A Sum of Products expression can be easily implemented using 2-level AND-OR circuit, or 2-level NAND circuit
- e.g. F = A $\cdot$ B + C’ $\cdot$ D + E (the 3 diagrams below all represent F)
A Product of Sums expression can be easily implemented using 2-level OR-AND circuit, or 2-level NOR circuit
- e.g. G = (A + B) $\cdot$ (C’ + D) $\cdot$ E (the 3 diagrams below all represent G)

A chip that contains a circuit
Programming Logic Array (PLA): A programmable IC that implements sum-of-products circuits (might allow multiple outputs)
- 2 stages: AND gates (to get all product terms) & OR gates (to get outputs)
- Connection between the stages (or planes) can be “burned” (or programmed)

inputs: X, Y; outputs: C, S
In canonical form (sum of minterms)
- C = X $\cdot$ Y
- S = X’ $\cdot$ Y + X $\cdot$ Y’
S can be simplified to X $\oplus$ Y