6.2 Proving Conditional Statements by Contradiction

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-11-06 Teacher: Prof. Musacchio

Proof by Contradiction

Outline for Proving a Conditional Statement with Contradiction

• Proposition If $P$, then $Q$.
  • Proof. Suppose $P$ and $\sim Q$.
  • .
  • .
  • .
  • Therefore $C\wedge \sim C$.

Example

• Proposition Suppose a ∈ Z. If a^2 is even, then a is even.
  • Proof. For the sake of contradiction, suppose a2 is even and a is not even.
  • Then a^2 is even, and a is odd.
  • Since a is odd, there is an integer c for which a = 2c + 1.
  • Then a^2 = (2c + 1)^2 = 4c^2 + 4c + 1 = 2(2c^2 + 2c) + 1, so a^2 is odd.
  • Thus a^2 is even and a^2 is not even, a contradiction.