Logic Gates and Boolean Algebra

Logic Gates – Definitions & Core Concepts

  • A logic gate (electronic gate) is a circuit that operates on binary signals to perform a specific logical operation.
  • Operates on voltage pulses that represent logic levels: HIGH (1) and LOW (0).
  • Essential gate types:
    • NOT (Inverter)
    • AND
    • OR
    • NOR (NOT-OR)
    • NAND (NOT-AND)
    • XOR (Exclusive-OR)
    • XNOR (Exclusive-NOR)
  • Gates are the basic building blocks of all digital systems.

Fundamental Gates & Individual Behaviour

NOT (Inverter)

  • Performs inversion/complementation.
  • Changes 1 \rightarrow 0 and 0 \rightarrow 1.
  • Truth-table:
    • 0 ⇒ 1
    • 1 ⇒ 0
  • Number of input combinations for an n-input device: N = 2^{n}.

AND Gate

  • Multi-input / single-output; performs logical multiplication.
  • Output HIGH only if all inputs are HIGH.
  • 2-Input truth-table: 00→0, 01→0, 10→0, 11→1.

OR Gate

  • Performs logical addition.
  • Output HIGH if any input is HIGH.
  • 2-Input truth-table: 00→0, 01→1, 10→1, 11→1.

NOR (NOT-OR)

  • Universal gate; OR followed by inversion.
  • Output HIGH only when all inputs are LOW.
  • 2-Input truth-table: 00→1, 01→0, 10→0, 11→0.

NAND (NOT-AND)

  • Also universal.
  • AND followed by inversion.
  • Output LOW only when all inputs are HIGH.
  • 2-Input truth-table: 00→1, 01→1, 10→1, 11→0.

XOR (Exclusive-OR)

  • Inequality detector; HIGH when inputs differ.
  • Truth-table: 00→0, 01→1, 10→1, 11→0.

XNOR (Exclusive-NOR)

  • Equality detector; HIGH when inputs are equal.
  • Truth-table: 00→1, 01→0, 10→0, 11→1.

Consolidated Truth-Tables

2-Input Summary

ABANDNANDORNORXORXNOR
00010101
01011010
10011010
11101001

3-Input Highlights

  • AND HIGH only for ABC=111.
  • NAND LOW only for ABC=111.
  • OR LOW only for ABC=000.
  • NOR HIGH only for ABC=000.

Combining Logic Gates

  • Gates can be interconnected to build complex Boolean functions or to substitute gate types.

Example 1 – Conditional Output

  • Requirement: Q=1 only when A=1 and B=0.
  • Implementation: Q = A \cdot \overline{B} (NOT + AND).

Example 2 – Composite Network

  • D = \overline{(A + B)}
  • E = B \cdot C
  • Q = D + E ⇒ Q = \overline{(A + B)} + (B \cdot C)
  • Truth table given in transcript confirms operation.

Practice Assignment

  • Compute the truth table for a four-variable network (diagram on Page 22) to derive output F.

Practical IC & Design Considerations

  • ICs often contain several identical gates (e.g., four 2-input NANDs).
  • Resource optimisation:
    • Tie inputs together to reduce gate-input count (3-input AND used as 2-input).
    • Single-input NAND/NOR functions as a NOT gate.
    • Entire circuits can be built from one universal family (all NANDs or all NORs).

Gate-Type Conversion Rule (OR ↔ AND)

  1. Invert each input.
  2. Change gate type (AND ↔ OR).
  3. Invert the output.

NAND Equivalents

  • NOT ⇒ single-input NAND.
  • AND ⇒ NAND then NOT.
  • OR ⇒ invert inputs, feed to NAND.
  • NOR ⇒ invert inputs, NAND, then NOT.

Boolean Functions

  • A Boolean function is an expression of binary variables using logical operators.
  • Truth table uniquely defines the function.
  • Example (Page 30): Only A=0,B=0,C=1 gives X=1 ⇒ X = \overline{A}\,\overline{B}\,C (single minterm).
  • Two main canonical forms:
    • Sum-of-Products (SOP) – OR of minterms.
    • Product-of-Sums (POS) – AND of maxterms.

Boolean Algebra Essentials

  • Mathematical language for describing & simplifying digital circuits.

Basic Operation Rules

  • Addition (OR): 0+0=0, 0+1=1, 1+0=1, 1+1=1.
  • Multiplication (AND): 0\cdot0=0, 0\cdot1=0, 1\cdot0=0, 1\cdot1=1.

Fundamental Laws

  • Commutative: A+B=B+A, AB=BA.
  • Associative: A+(B+C)=(A+B)+C, A(BC)=(AB)C.
  • Distributive: A(B+C)=AB+AC.

Simplification Rules (1–14)

  1. A+0=A
  2. A+1=1
  3. A\cdot0=0
  4. A\cdot1=A
  5. A+A=A
  6. A+\overline{A}=1
  7. A\cdot A=A
  8. A\cdot \overline{A}=0
  9. \overline{\overline{A}} = A
  10. A + A B = A
  11. A + \overline{A} B = A + B
  12. (A + B)(A + C) = A + B C
    13–14. (Further rules implied but not specified in transcript.)

De Morgan’s Theorems

  • (A + B)' = A' \cdot B'
  • (A \cdot B)' = A' + B'
  • Verified via truth tables; critical for gate substitution & simplification.

Duality Principle

  • To obtain the dual of an expression: interchange + \leftrightarrow \cdot and swap constants 0 \leftrightarrow 1.
  • Provides alternate representations aiding simplification.

Circuit Analysis Techniques

  • Truth-Table Method: Enumerate all input combinations, compute outputs step-by-step.
  • Boolean-Algebra Method: Translate schematic to Boolean expression, apply algebraic laws to simplify and predict outputs.

Recap – Key Takeaways

  • Logic gates manipulate binary information; NAND and NOR are universal, enabling implementation of any Boolean function.
  • Boolean algebra offers a concise framework for circuit analysis, optimisation, and design validation.
  • Mastery of truth tables, De Morgan’s theorems, and gate-conversion strategies is essential for efficient digital logic engineering and exam success.