Proof Techniques & Logical Reasoning: Methods, Rules & Applications

Core Concepts & Definitions

1. Logical Statements & Propositions

A proposition is a declarative statement that is either true (T) or false (F), but not both. Examples:

• P: "2 + 2 = 4" (T)
• Q: "The sky is green" (F)
• R: "x > 5" (not a proposition unless x is defined).

Compound Propositions are formed using logical connectives:

Key Insight: Implication (P → Q) is false only when P is true and Q is false (e.g., "If it rains, the ground is wet" is false only if it rains but the ground isn’t wet).

---

2. Rules of Inference

Rules of inference are valid argument forms used to derive conclusions from premises. Four critical rules (from past exams):

Worked Example: Prove: If n is even, then n² is even.

1. Let n = 2k (definition of even).
2. Then n² = (2k)² = 4k² = 2*(2k²), which is even (by definition). Conclusion: n even → n² even (Modus Ponens).

---

3. Proof Techniques

A. Direct Proof

Definition: Assume P is true and show Q must follow using definitions, axioms, or algebraic manipulation.

Structure:

1. Assume P is true.
2. Manipulate P using logical steps.
3. Conclude Q is true.

Example: Prove "If n is even, then n + 4 is even."

1. Assume n is even ⇒ n = 2k for some integer k.
2. Then n + 4 = 2k + 4 = 2*(k + 2), which is even. Conclusion: n + 4 is even.

When to Use: When P → Q is straightforward and P’s structure helps derive Q.

---

B. Proof by Contradiction

Definition: Assume ¬Q (the opposite of what you want to prove) and show it leads to a contradiction (e.g., P is false or an absurdity).

Structure:

1. Assume ¬Q (or P and ¬Q).
2. Show this leads to a contradiction (e.g., 1 = 0).
3. Conclude Q must be true.

Example: Prove "√2 is irrational."

1. Assume √2 is rational ⇒ √2 = a/b (lowest terms, a, b integers).
2. Then 2 = a²/b² ⇒ a² = 2b² ⇒ a² is even ⇒ a is even ⇒ a = 2k.
3. Substitute: (2k)² = 2b² ⇒ 4k² = 2b² ⇒ b² = 2k² ⇒ b is even.
4. Contradiction: a and b are both even, but a/b was in lowest terms. Conclusion: √2 is irrational.

Past Exam Adaptation: Prove "If 3n + 2 is odd, then n is odd."

1. Assume n is even ⇒ n = 2k.
2. Then 3n + 2 = 6k + 2 = 2*(3k + 1), which is even.
3. But 3n + 2 is given as odd ⇒ Contradiction. Conclusion: n must be odd.

Advantages:

• Useful when direct proof is complex (e.g., irrationality, uniqueness proofs).
• Often shorter than direct proofs.

Disadvantages:

• Can feel "tricky" if not structured clearly.
• Not all statements lend themselves to contradiction.

---

C. Proof by Contrapositive

Definition: Prove ¬Q → ¬P instead of P → Q (logically equivalent).

Why It Works: P → Q ≡ ¬Q → ¬P (contrapositive).

Example: Prove "If n² is odd, then n is odd."

1. Contrapositive: If n is not odd (i.e., even), then n² is not odd (i.e., even).
2. Let n = 2k ⇒ n² = 4k² = 2*(2k²), which is even. Conclusion: Original statement holds.

When to Use: When negating Q is simpler than assuming P.

---

D. Proof by Induction

(Note: Primarily covered in Unit 4, but overlaps here for completeness.) Structure:

1. Base Case: Prove for n = n₀ (often 0 or 1).
2. Inductive Step: Assume true for n = k (inductive hypothesis), then prove for n = k + 1.
3. Conclusion: By induction, true for all n ≥ n₀.

Example: Prove 1 + 2 + ... + n = n(n + 1)/2 for all n ≥ 1.

1. Base Case (n = 1): LHS = 1, RHS = 1*(2)/2 = 1. ✔️
2. Inductive Step: Assume true for n = k ⇒ 1 + ... + k = k(k + 1)/2. For n = k + 1: LHS = (1 + ... + k) + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2 = RHS. Conclusion: True for all n ≥ 1.

---

4. Negations and Logical Equivalences

Negation Rules:

Example: Negate "This is a boring course."

• Original: ∀x (Course(x) → Boring(x)).
• Negation: ∃x (Course(x) ∧ ¬Boring(x)) ⇒ "There exists a course that is not boring."

Past Exam Tip: Always negate quantifiers first, then the inner statement.

---

5. Common Pitfalls & Misconceptions

1. Implication ≠ Causation:
   • P → Q does not mean P causes Q. Example: "If it’s a square, it’s a rectangle" (true, but not causal).
2. Contrapositive Confusion:
   • P → Q’s contrapositive is ¬Q → ¬P, not Q → P (converse).
3. Existence vs. Universality:
   • ∃x P(x) (exists) ≠ ∀x P(x) (for all). Example: "Some primes are odd" (true) vs. "All primes are odd" (false).
4. Induction Base Case:
   • Forgetting to verify the base case leads to invalid proofs.

---

Applications in Computer Science

1. Algorithm Correctness:
   • Proofs ensure programs terminate and produce correct outputs (e.g., sorting algorithms).
2. Cryptography:
   • Proofs of primality or hardness (e.g., RSA relies on number-theoretic proofs).
3. Database Theory:
   • Logical reasoning for query optimization and normalization.
4. Compiler Design:
   • Proving equivalence of intermediate code representations.

Example: Proving a loop invariant. Claim: The loop for (i = 0; i < n; i++) sum += i; computes sum = n(n - 1)/2. Proof by Induction:

1. Base Case (n = 1): sum = 0 = 1*0/2. ✔️
2. Inductive Step: Assume true for n = k, then for n = k + 1, the loop adds k to the sum, maintaining the invariant.

---

Exam Tip: How to Score Full Marks

1. Structure Your Proofs Clearly

Use this template for direct/contradiction proofs:

**Statement**: [Clearly state what you’re proving, e.g., "Prove if *n* is even, then *n²* is even."]

**Proof**:
1. [Assume P is true or assume ¬Q for contradiction.]
2. [Manipulate using definitions/algebra.]
3. [Conclude Q is true or reach a contradiction.]
**Conclusion**: [Restate the proven statement.]

2. For Rules of Inference

• List the rule name (e.g., "By Modus Tollens...").
• Show the premises and conclusion explicitly.
• Example:

  Given: P → Q, ¬Q. By Modus Tollens, we conclude ¬P.

3. Handle Negations Carefully

• Step-by-step: Break complex statements into simpler parts.
• Example: Negate "All students passed or no student attended."
  • Original: ∀x (Student(x) → Passed(x)) ∨ ∀x ¬Attended(x).
  • Negation: ∃x (Student(x) ∧ ¬Passed(x)) ∧ ∃x Attended(x).

4. Common Exam Patterns

5. Avoid These Mistakes

• Assuming what you need to prove: Never start with Q and work backward.
• Incorrect quantifier negation: ∀x P(x) negates to ∃x ¬P(x), not ∀x ¬P(x).
• Algebraic errors: Double-check each step (e.g., expanding (2k)²).
• Vague conclusions: Always restate the proven statement explicitly.

6. Time Management

• Direct proofs: ~3–4 minutes per mark.
• Contradiction proofs: ~4–5 minutes (more steps).
• Inference rules: ~1–2 minutes each.

---

Practice Problems (With Hints)

1. Direct Proof: Prove: If n is odd, then n³ is odd. Hint: Let n = 2k + 1, expand n³.

2. Contradiction: Prove: √3 is irrational. Hint: Assume √3 = a/b, show both a and b must be even.

3. Contrapositive: Prove: If n² is not divisible by 4, then n is not even. Hint: Contrapositive is "If n is even, then n² is divisible by 4."

4. Inference Rules: Given: P → Q, Q → R, ¬R, conclude ¬P. Hint: Chain implications, then use Modus Tollens.

---

Summary Table: Proof Techniques

---

Final Checklist for Exams

Before submitting:

1. Did I state the theorem clearly?
2. Did I assume the correct premise (or its negation)?
3. Did I use definitions/axioms correctly?
4. Did I conclude properly (restate the proven statement)?
5. Did I avoid circular reasoning?

---

Note: For TU/PU exams, always justify each step with definitions or logical rules. Partial credit is often given for correct intermediate steps, even if the final conclusion is missing. Practice writing proofs formally (as shown above) to maximize marks.