Logic Gates and Boolean Algebra

Boolean Algebra Basics

Three Basic Operations

AND:  Y = A · B    "1 only if both are 1"
OR:   Y = A + B    "1 if any is 1"
NOT:  Y = Ā        "Invert"

Truth Tables

AND          OR           NOT
A B | Y     A B | Y      A | Y
0 0 | 0     0 0 | 0      0 | 1
0 1 | 0     0 1 | 1      1 | 0
1 0 | 0     1 0 | 1
1 1 | 1     1 1 | 1

Basic Theorems

Associative Law:  (A·B)·C = A·(B·C)
                  (A+B)+C = A+(B+C)
Commutative Law:  A·B = B·A
                  A+B = B+A
Distributive Law: A·(B+C) = A·B + A·C

De Morgan's Theorem (Extremely Important!):
  ───
  A·B = Ā + B̄     "NAND = OR of NOTs"
  ───
  A+B = Ā · B̄     "NOR = AND of NOTs"

Reduction:
  A + Ā = 1
  A · Ā = 0
  A + 1 = 1
  A · 0 = 0
  A + A = A
  A · A = A
  =    (Double Negation)
  A = A

Basic Logic Gates

Symbols and Expressions

AND:     A ──┬──
              │  )── Y    Y = A·B
         B ──┴──

OR:      A ──┬──
              │  )── Y    Y = A+B
         B ──┴──

NOT:     A ──▷── Y        Y = Ā

NAND:    A ──┬──
              │  )─○ Y    Y = A·B̄  (AND + NOT)
         B ──┴──

NOR:     A ──┬──
              │  )─○ Y    Y = A+B̄  (OR + NOT)
         B ──┴──

XOR:     A ──┬──
              │  )── Y    Y = A⊕B = ĀB + AB̄
         B ──┴──            ("1 if different")

XNOR:    A ──┬──
              │  )─○ Y    Y = A⊕B̄  ("1 if same")
         B ──┴──

Universality of NAND / NOR

NAND can implement any logic function!
  NOT:  A NAND A = Ā
  AND:  (A NAND B) NAND (A NAND B) = A·B
  OR:   (A NAND A) NAND (B NAND B) = A+B

NOR can similarly construct everything
This is why NAND Flash and NOR Flash are named as such

Combinational Logic Simplification

Karnaugh Map (K-Map)

2 Variables:
    B
  A 0  1
  0 0  1
  1 1  0   ← Fill in output values

3 Variables: AB/C arrangement
  Group adjacent 1s (in groups of 2ⁿ) → Write minterms → Obtain simplest expression

Goal: Implement a given truth table using the minimum number of gates

Race Conditions and Hazards

Different delays in multiple signal paths → Output produces brief erroneous pulses (glitches)

Example: A and Ā should arrive at the AND gate simultaneously, but Ā has a delay due to the inverter
     → For a brief moment A=1, Ā=1 (hasn't switched to 0 yet) → AND outputs erroneous 1

Solution: Add redundant terms or add a capacitor filter at the output

Logic Levels

TTL vs CMOS

       TTL (5V)         CMOS (5V)       CMOS (3.3V)
VIH:   > 2.0V           > 3.5V          > 2.0V
VIL:   < 0.8V           < 1.5V          < 0.8V
VOH:   > 2.4V           > 4.4V          > 2.9V
VOL:   < 0.4V           < 0.1V          < 0.4V

Noise Margin = min(VOH-VIH, VIL-VOL)
CMOS noise margin is significantly better than TTL

Input Types

Floating Input — Never do this! Floating CMOS input = Indeterminate state + High power consumption
Unused input pins: Connect to Vcc or GND (via resistor)

Practical Logic Gates

CMOS Inverter

       Vdd
        │
    ┌───┤ PMOS (Top transistor)
    │   │
A ──┤   ├── Y
    │   │
    └───┤ NMOS (Bottom transistor)
        │
       GND

A=1 → NMOS ON, PMOS OFF → Y=0
A=0 → NMOS OFF, PMOS ON → Y=1

CMOS's greatest advantage: Static power consumption is nearly zero!
(Power is only consumed during switching transitions)

74 Series Quick Reference

74HC00:  Quad 2-input NAND
74HC02:  Quad 2-input NOR
74HC04:  Hex NOT (Inverter)
74HC08:  Quad 2-input AND
74HC32:  Quad 2-input OR
74HC86:  Quad 2-input XOR
74HC14:  Hex Schmitt Trigger NOT
74HC595: 8-bit Shift Register (Super common!)
74HC165: 8-bit Parallel-to-Serial

Keywords: Boolean Algebra, AND, OR, NOT, NAND, NOR, XOR, De Morgan, Karnaugh Map, CMOS, TTL