Logic & Proof Techniques
The foundation of rigorous reasoning and digital systems. Learn propositions and connectives, truth tables, implication and equivalence, tautologies and contradictions, quantifiers (∀, ∃) and predicate logic, and proof techniques: direct proof, contrapositive, contradiction and mathematical induction.
Software specifications, safety interlocks, database queries and circuit design are all logic. Proof techniques let engineers show algorithms are correct and formulas hold for all cases — not just the ones tested.
An analogy
Logic is like the rules of a board game: follow them precisely and every conclusion you reach is guaranteed to be valid.
Propositions and truth tables
A proposition is true or false. Truth tables list all combinations; two statements are equivalent if their columns match. A tautology is always true; a contradiction always false.
Implication pitfalls
'If the alarm is on, pressure is high' does not mean 'if pressure is high, the alarm is on' (converse) — confusing these is a common specification error. The contrapositive is equivalent; the converse is not.
Quantifiers
∀ (every sensor reads below the limit) and ∃ (some sensor reads above). Negation swaps them. Order matters: ∀x∃y ≠ ∃y∀x.
Proofs
Direct proof; contrapositive; contradiction (√2 irrational); induction for statements about all integers (sums, algorithm loops — loop invariants); counterexamples disprove universal claims.
Formulas
- Implication:
p → q ≡ ¬p ∨ q (false only when p true, q false) - Contrapositive:
p → q ≡ ¬q → ¬p - De Morgan:
¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬∀x P(x) ≡ ∃x ¬P(x) - Induction:
P(1) ∧ [P(k) → P(k + 1)] ⇒ ∀n P(n)
Worked example: Induction
Given: Claim: 1 + 2 + … + n = n(n + 1)/2
Find: Proof.
- Base n = 1: 1 = 1 ✓
- Assume true for k; then sum to k + 1 = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2 ✓
Answer: True for all n ≥ 1
Worked example: Contrapositive
Given: If n² is even then n is even
Find: Proof.
- Contrapositive: if n is odd, n² is odd
- n = 2k + 1 → n² = 2(2k² + 2k) + 1 odd ✓
Answer: Proved
Common mistakes
- Wrong: Treating the converse as equivalent. — Right: Only the contrapositive is equivalent.
- Wrong: Proof by examples. — Right: Examples illustrate; proofs cover all cases (one counterexample disproves).
Applications
- Digital design: Boolean logic and verification.
- Software correctness: Loop invariants and formal specs.
- Safety interlocks: Precise requirements using implications.
Key takeaways
- Truth tables define connectives.
- Contrapositive ≡; converse ≠.
- Quantifier negation swaps ∀/∃.
- Direct, contrapositive, contradiction, induction.
Going further
- Formal verification: Model checking and theorem provers.
- Temporal logic: Specifying sequences of events.
- SAT solvers: Automated Boolean reasoning.