Key Formulas & Truth Tables
De Morgan's Laws:
(A + B)' = A' · B'
(A · B)' = A' + B'
The complement of a sum equals the product of complements; the complement of a product equals the sum of complements
(A + B)' = A' · B'
(A · B)' = A' + B'
The complement of a sum equals the product of complements; the complement of a product equals the sum of complements
Boolean Algebra Axioms:
A + 0 = A, A · 1 = A (Identity)
A + 1 = 1, A · 0 = 0 (Domination)
A + A = A, A · A = A (Idempotent)
A + A' = 1, A · A' = 0 (Complement)
A + 0 = A, A · 1 = A (Identity)
A + 1 = 1, A · 0 = 0 (Domination)
A + A = A, A · A = A (Idempotent)
A + A' = 1, A · A' = 0 (Complement)
Consensus Theorem: AB + A'C + BC = AB + A'C
Distributive: A(B+C) = AB + AC, A + BC = (A+B)(A+C)
Distributive: A(B+C) = AB + AC, A + BC = (A+B)(A+C)
AND Gate: Y = A · B — output 1 only when ALL inputs are 1
OR Gate: Y = A + B — output 1 when ANY input is 1
XOR Gate: Y = A ⊕ B = A'B + AB' — output 1 when inputs differ
OR Gate: Y = A + B — output 1 when ANY input is 1
XOR Gate: Y = A ⊕ B = A'B + AB' — output 1 when inputs differ
Core Concepts
1. Logic Gates
Basic building blocks of digital circuits: AND, OR, NOT (inverter), NAND, NOR, XOR, XNOR. Any Boolean function can be implemented using only NAND gates (or only NOR gates) — functional completeness.
Basic building blocks of digital circuits: AND, OR, NOT (inverter), NAND, NOR, XOR, XNOR. Any Boolean function can be implemented using only NAND gates (or only NOR gates) — functional completeness.
2. Combinational Logic
Circuits whose outputs depend ONLY on current inputs — no memory. Examples: multiplexers, demultiplexers, encoders, decoders, adders (half adder, full adder), comparators.
Circuits whose outputs depend ONLY on current inputs — no memory. Examples: multiplexers, demultiplexers, encoders, decoders, adders (half adder, full adder), comparators.
3. Sequential Logic
Circuits with memory — outputs depend on current inputs AND previous state. Built using flip-flops: SR, D, JK, T. Examples: registers, counters, shift registers, finite state machines.
Circuits with memory — outputs depend on current inputs AND previous state. Built using flip-flops: SR, D, JK, T. Examples: registers, counters, shift registers, finite state machines.
4. Karnaugh Maps (K-maps)
Graphical method for simplifying Boolean expressions. Group adjacent 1s in powers of 2 (1, 2, 4, 8...). Larger groups → simpler terms. Limited to 4-6 variables practically.
Graphical method for simplifying Boolean expressions. Group adjacent 1s in powers of 2 (1, 2, 4, 8...). Larger groups → simpler terms. Limited to 4-6 variables practically.
5. Number Systems in Digital Logic
Binary (base-2): 0,1. Octal (base-8): 0-7. Hexadecimal (base-16): 0-F. Conversion: group binary digits in 3s (octal) or 4s (hex). Two's complement for signed arithmetic.
Binary (base-2): 0,1. Octal (base-8): 0-7. Hexadecimal (base-16): 0-F. Conversion: group binary digits in 3s (octal) or 4s (hex). Two's complement for signed arithmetic.
Core Definitions
Minterm: A product (AND) term containing all variables exactly once, in true or complemented form. For F(A,B,C) = Σ(1,3,5,7), minterms are A'B'C, A'BC, AB'C, ABC.
Maxterm: A sum (OR) term containing all variables exactly once. Dual of minterm. POS (Product of Sums) form uses maxterms.
Propation Delay: The time between input change and output response. Critical path delay determines maximum clock speed. Measured in nanoseconds.
Flip-Flop: A 1-bit memory element. D flip-flop: Q(next) = D. JK flip-flop: toggles when J=K=1. T flip-flop: toggles when T=1. Edge-triggered (responds to clock edge).
Hazards: Unwanted switching transients due to unequal path delays. Static hazard: output should stay constant but glitches. Dynamic hazard: multiple transitions when one expected. Fixed by adding redundant terms.
Worked Examples
Example 1: K-Map Simplification
F(A,B,C) = Σ(0,2,4,6) — group all four 1s in one group of 4.
All four share C' (C=0) → F = C'
F(A,B,C) = Σ(0,2,4,6) — group all four 1s in one group of 4.
All four share C' (C=0) → F = C'
Example 2: Half Adder Design
Inputs: A, B. Outputs: Sum, Carry.
Sum = A ⊕ B (XOR gate)
Carry = A · B (AND gate)
Inputs: A, B. Outputs: Sum, Carry.
Sum = A ⊕ B (XOR gate)
Carry = A · B (AND gate)
Example 3: De Morgan's Application
F = (A + B)' → NAND implementation: Connect A and B to a NAND gate.
F = (A · B)' → NOR implementation: Connect A and B to a NOR gate.
F = (A + B)' → NAND implementation: Connect A and B to a NAND gate.
F = (A · B)' → NOR implementation: Connect A and B to a NOR gate.
Practice Problems
Problem 1: Simplify using De Morgan's: (A + B + C)'
Answer: A' · B' · C'
Answer: A' · B' · C'
Problem 2: Convert binary 10110110 to hexadecimal and octal.
Answer: Hex: B6; Octal: 266
Answer: Hex: B6; Octal: 266
Problem 3: Minimize F(A,B) = Σ(0,1,2) using K-map.
Answer: All four cells except AB → F = A' + B'
Answer: All four cells except AB → F = A' + B'
Problem 4: What is the output of an XOR gate when both inputs are 1?
Answer: 0 (XOR outputs 1 only when inputs differ)
Answer: 0 (XOR outputs 1 only when inputs differ)
Problem 5: Why are NAND gates called "universal gates"?
Answer: Any Boolean function can be implemented using only NAND gates. NOT = NAND with tied inputs. AND = NAND followed by NOT (two NANDs). OR = NAND with inverted inputs (using De Morgan's).
Answer: Any Boolean function can be implemented using only NAND gates. NOT = NAND with tied inputs. AND = NAND followed by NOT (two NANDs). OR = NAND with inverted inputs (using De Morgan's).