TM2: Boolean Algebra + Formal Logic

When: Week 15 (after Test 4) Duration: 120 minutes Format: Closed book

Coverage

Boolean Algebra (Weeks 8-10)

Boolean functions
Boolean laws and duality
Normal forms (DNF, CNF)
Logic gates and circuits
Functional completeness
Karnaugh maps
Quine-McCluskey

Formal Logic (Weeks 11-15)

Propositional logic: syntax, semantics
Tautologies, contradictions
Logical equivalence/consequence
Natural deduction
Soundness and completeness
Predicate logic basics
Quantifiers
Categorical logic

Sample Questions

Definitions

Define tautology, contradiction, contingency.
What is functional completeness?
Define logical consequence.

Theorems

State completeness theorem. What does it mean?
Prove {NAND} is functionally complete.
Show every Boolean function has DNF.

Proofs

Prove (P → Q) ∧ (Q → R) ⊢ (P → R) using natural deduction.
Show ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
Prove tautology is valid in all interpretations.

Conceptual

Relationship between Boolean algebra and logic?
Difference between soundness and completeness?
Why can’t we use truth tables for predicate logic?

Preparation

Memorize key definitions
Practice proof construction
Understand theorem statements
Review proof techniques
Create summary sheets
Study group discussions