Module 3: Boolean Algebra

Duration: Weeks 8-10

Core Topics

Boolean Functions (Week 8)

• Truth tables
• Basic operations: AND, OR, NOT, XOR, NAND, NOR
• Boolean laws and duality
• Normal forms: DNF and CNF
• Perfect normal forms

Digital Circuits (Week 9)

• Logic gates
• Circuit design and analysis
• Multi-level circuits
• Functional completeness
• Universal gates (NAND, NOR)

Minimization (Week 10)

• Karnaugh maps (K-maps)
• Don’t care conditions
• Quine-McCluskey algorithm
• Prime implicants

Key Concepts

Boolean Function: f: {0,1}ⁿ → {0,1}

Normal Forms:

• DNF: Sum of products (OR of ANDs)
• CNF: Product of sums (AND of ORs)

Functionally Complete: A set of operations that can express any Boolean function

• Examples: {AND, OR, NOT}, {NAND}, {NOR}

K-Map: Visual method for minimizing Boolean expressions (works well for ≤4 variables)

Applications

• Digital circuit design
• Computer hardware architecture
• Compiler optimization
• SAT solvers

What You’ll Be Able To Do

• Construct truth tables for Boolean expressions
• Convert between DNF, CNF, and arbitrary forms
• Simplify expressions using Boolean laws
• Design circuits using logic gates
• Minimize functions with K-maps
• Prove functional completeness