Discrete Math: A Proof By Contraposition

Proof by contraposition is a type of proof used in mathematics and is a rule of inference. In logic the contrapositive of a statement can be formed by reversing the direction of inference and negating both terms for example :

p → q
= -p ← -q
= -q → -p

This simply means “if p, then q” is drawn from the single premise “if not q, then not p.” A statement and its contrapositive are logically equivalent: if the statement is true, then its contrapositive is true, and vice versa.

Let’s prove or show that n to the power of 2 is a even number using contraposition.

Prove if n² is even then n is even.

Determine our p and q value:
p → q = “if n² is even then n is even”

p: “n² is even”
q: “n is even”

p: “n² is NOT even” = “n² is odd”
-q: “n is NOT even” = “n is odd”

NOTE: If a number is not even then it is odd

This means our contrapositive is :
-q → -p = “if n is odd then n² is odd”

We must prove or show the contraposition, that if n is odd then n² is odd, if we can prove this to be true then we have also proven that if n² is even then n is even.

NOTE: An even number is an integer in the form 2q, where q is an integer
An odd number is an integer in the form 2q + 1 or 2q-1, where q is an integer.

  1. Assume ’n’ is an odd integer
    n = 2q + 1, where q is an integer
  2. Do some algebra
    n² = (2q + 1)² , where q is an integer
    n² = 4q² + 4q + 1 , where q is an integer
    n² = 2(2q² + 2q) + 1, where q is an integer
    n² = 2a + 1 , where a is an integer and a = (2q² + 2q)
    n² = an odd integer

Conclusion:
Having used a direct proof to show the contraposition of the proposition, we conclude that if n² is even then n is even.

If you want to read up on more types of proofs or Discrete Math topics in general a great book to easily learn and practice these topics is Practice Problems in Discrete Mathematics by Bojana Obrenic’, and Discrete Math Workbook: Interactive Exercises by James R. bush.

Practice Problems in Discrete Mathematics by Bojana Obrenic’
Image for post
Image for post
Discrete Math Workbook: Interactive Exercises by James R. bush

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, discrete math, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358:https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Algortithm Analysis:

Image for post
Image for post

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store