5.1 Contrapositive Proof

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

Contrapositive Proof

Introduction

• Like direct proof, the technique of contrapositive proof is used to prove conditional statements of the form “If $P$, then $Q$.”
• Although it is possible to use direct proof exclusively, there are occasions where contrapositive proof is much easier.

Example

• Proposition Suppose $x\in Z$. If $7x+9$ is even, then $x$ is odd.
  • Proof. (Contrapositive) Suppose $x$ is not odd.
  • Thus $x$ is even, so $x=2a$ for some integer $a$.
  • Then $7x+9=7(2a)+9=14a+8+1=2(7a+4)+1$.
  • Therefore $7x+9=2b+1$, where $b$ is the integer $7a+4$.
  • Consequently $7x+9$ is odd.
  • Therefore $7x+9$ is not even.

Example

• Proposition Suppose $x\in Z$. If $x^2-6x+5$ is even, then $x$ is odd.
  • Proof. (Contrapositive) Suppose $x$ is not odd.
  • Thus $x$ is even, so $x=2a$ for some integer $a$.
  • So $x^2-6x+5=(2a{)}^2-6(2a)+5=4a^2-12a+5=4a^2-12a+4+1=2(2a^2-6a+2)+1$.
  • Therefore $x^2-6x+5=2b+1$, where b is the integer $2a^2-6a+2$.
  • Consequently $x^2-6x+5$ is odd.
  • Therefore $x^2-6x+5$ is not even.