⚡🧠 TM2 – Boolean Algebra + Formal Logic

📅 Exam Details

📚 Coverage

The second theoretical minimum covers key concepts from the latter modules of the course:

⚡ Boolean Algebra (Weeks 8–10)

• Boolean functions and truth tables
• Boolean laws and duality principle
• Normal forms (DNF, CNF)
• Logic gates (AND, OR, NOT, NAND, NOR, XOR)
• Functional completeness
• Karnaugh maps
• Quine-McCluskey algorithm

🧠 Formal Logic (Weeks 11–15)

• Propositional logic (syntax and semantics)
• Tautologies, contradictions, contingencies
• Logical equivalence and consequence
• Natural deduction proof systems
• Soundness and completeness
• Predicate logic with quantifiers
• Categorical logic and syllogisms

📝 Sample Questions

Definitions

• Define tautology, contradiction, contingency
• What is functional completeness?
• Define logical consequence
• What is DNF? What is CNF?
• Define soundness vs completeness

Theorems

• State the completeness theorem
• Show {NAND} is functionally complete
• Every Boolean function has DNF representation
• De Morgan’s laws

Proofs

• Prove transitivity of implication using natural deduction
• Show De Morgan’s law using truth table or Boolean algebra
• Prove a tautology is valid in all interpretations
• Show {NAND} can express AND, OR, NOT

Conceptual

• Relationship between Boolean algebra and logic?
• Difference between soundness and completeness?
• Why can’t we use truth tables for predicate logic?
• What makes a gate set universal?

✅ What You Must Know

• Boolean operations (AND, OR, NOT) and laws
• DNF and CNF normal forms
• Functional completeness concept
• Tautologies, contradictions, contingencies
• Logical equivalence and consequence
• Soundness vs completeness distinction
• Natural deduction inference rules (modus ponens, modus tollens, etc.)
• Quantifier negation rules
• Key theorems: Completeness theorem, De Morgan’s laws, functional completeness proofs
• Proof techniques: truth tables, Boolean algebra, natural deduction, gate construction

📖 Preparation Checklist

✅ Week 14 (2 weeks before)

• Review all lecture notes from Weeks 8–15
• Memorize all Boolean laws
• List all natural deduction rules
• Practice proofs in natural deduction

✅ Week 15 (1 week before)

• Can recite all definitions precisely?
• Practice functional completeness proofs
• Join study group, quiz on theorems
• Attend review session

✅ Day Before

• Review materials once
• Get 8 hours sleep!
• Stay calm and confident

💡 Pro Tips

🎯 Success Strategy

• Laws are your tools: Memorize Boolean laws cold
• Name your inference rules: In proofs, cite “Modus Ponens”, “∧-Intro”, etc.
• Truth tables work: When stuck, build truth table
• K-maps are visual: Practice grouping patterns
• Quantifiers are tricky: Double-check negations

Common Pitfalls to Avoid

• ❌ Confusing semantic consequence and syntactic provability
• ❌ Wrong quantifier negation (negating “for all” gives “there exists…not”, not “for all…not”)
• ❌ Forgetting to justify proof steps
• ❌ K-map groups not power-of-2 sizes
• ❌ Mixing up soundness and completeness

What Graders Look For

• ✓ Exact definitions (word-for-word accuracy)
• ✓ Named inference rules in proofs
• ✓ Clear step-by-step Boolean simplifications
• ✓ Correct gate constructions for completeness
• ✓ Proper quantifier manipulation
• ✓ Understanding of soundness/completeness distinction