Digital Logic Circuits: Logic Gates, Boolean Algebra Laws, and Karnaugh Map Simplification

The Foundation of Digital Hardware

All microprocessor architectures and digital computer circuits are constructed from basic electronic switches called logic gates. Understanding how these gates function and how complex Boolean expressions can be minimized into cost-effective physical circuits is a core requirement of A/L ICT Unit 4.

1. Standard and Universal Logic Gates

• AND Gate: Output is 1 only when all inputs are 1. Expression: F = A . B
• OR Gate: Output is 1 when at least one input is 1. Expression: F = A + B
• NOT Gate (Inverter): Inverts the input signal. Expression: F = A' (or ¬A)
• NAND Gate (Universal): Inverted AND. Output is 0 only when all inputs are 1. Expression: F = (A . B)'
• NOR Gate (Universal): Inverted OR. Output is 1 only when all inputs are 0. Expression: F = (A + B)'
• XOR (Exclusive OR): Output is 1 when inputs are different. Expression: F = A ⊕ B = A'.B + A.B'

Note: NAND and NOR are known as "Universal Gates" because any digital circuit or Boolean function can be implemented using only NAND gates or only NOR gates.

2. Essential Laws of Boolean Algebra

Boolean algebra simplifies logical expressions to reduce the physical number of gates required:

• Identity Laws: A + 0 = A, A . 1 = A
• Null Laws: A + 1 = 1, A . 0 = 0
• Idempotent Laws: A + A = A, A . A = A
• Complement Laws: A + A' = 1, A . A' = 0
• Distributive Law: A . (B + C) = (A . B) + (A . C) and A + (B . C) = (A + B) . (A + C)
• De Morgan's First Law: (A + B)' = A' . B' (The complement of a sum is the product of the complements)
• De Morgan's Second Law: (A . B)' = A' + B' (The complement of a product is the sum of the complements)

3. Karnaugh Map (K-Map) Simplification

Karnaugh maps provide a graphical technique for minimizing Boolean functions without tedious algebraic manipulation. Cells are arranged using Gray Code (only one variable changes state between adjacent cells).

Rules for grouping 1s in a K-Map:

1. Groups must contain 2^n cells (1, 2, 4, 8, or 16 cells).
2. Groups must be rectangular or square (never diagonal).
3. Make groups as large as possible to eliminate more variables.
4. Groups may wrap around edges and corners.
5. Every '1' cell must be included in at least one group (overlapping is allowed).