
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Proof by Contrapositive in Discrete Mathematics
In Discrete mathematics, we use logics to deduct and prove in several ways. Another way of proving logics is using the techniques with the proof by contrapositive. This method demonstrates the truth of an implication by proving the equivalent contrapositive statement instead. It is a useful and often simpler way to verify a claim when direct proof methods might be cumbersome or unclear.
What is Proof by Contrapositive?
To understand the concept of proof by contrapositive, we must cover the basics of implications. Let us first recall what an implication is. In logical terms, an implication is a statement of the form "if P, then Q", which we write as −
$$\mathrm{P \:\rightarrow\: Q}$$
Here, P is called the hypothesis (or premise), and Q is the conclusion.
The contrapositive of an implication reverses and negates both the hypothesis and the conclusion. So, the contrapositive of the statement P → Q is −
$$\mathrm{\neg\: Q \:\rightarrow\: \neg \:P}$$
This means that instead of proving "if P, then Q", we prove "if not Q, then not P". An important fact is that the contrapositive is logically equivalent to the original statement. In other words, if the contrapositive is true, the original implication must also be true.
Why Use Contrapositive Proofs?
Sometimes, it is difficult to prove a statement directly. The relationship between P and Q might be too complex or unclear when handling this. However, the contrapositive may offer a simpler or more intuitive way out. Giving the contrapositive can sometimes break down the problem into smaller, more manageable parts.
To get the idea clear on how a proof by contrapositive works, let us look at an example from the idea of even and odd numbers.
Example 1: Proving the Statement with Contrapositive
Consider the statement: "For all integers n, if n2 is even, then n is even".
We want to prove this implication. Proving it directly would mean starting with the assumption that n2 is even and trying to show that n itself is even. While possible, this approach might not feel straightforward. Instead, let us prove its contrapositive:
The contrapositive of the given statement is −
"If n is odd, then n2 is odd"
Proving this contrapositive will be enough to confirm the truth of the original implication. So, we start by assuming that n is odd and show that n2 must also be odd.
Step 1: Assume the negation of the conclusion
We start with assuming that n is odd. If n is odd, we can write n in the form −
$$\mathrm{n \:=\: 2k \:+\: 1}$$
where k is an integer. This is the standard way to represent odd numbers because they differ from the nearest even number by 1.
Step 2: Square the assumption
Next, we need to find n2, the square of an odd number. Using the expression for n, we calculate −
$$\mathrm{n^2\: = \:(2k \:+\: 1)^2}$$
Expanding the square −
$$\mathrm{n^2 \:=\: 4k^2 \:+\:4k \:+\: 1}$$
Step 3: Analyze the result
We can factor this expression −
$$\mathrm{n^2 \:=\: 2(2k^2 \:+\: 2k) \:+\: 1}$$
Notice that the expression 2(2k2 + 2k) is clearly an even number since it is divisible by 2. Therefore, n2 is of the form "even number + 1", which means that n2 is odd.
Step 4: Conclusion
Thus, we have shown that if n is odd, then n2 must also be odd. Since we have successfully proven the contrapositive, we can now conclude that the original statement is true −
"For all integers n, if n2, then n is even."
Let us now see another effective example of Proof by Contrapositive.
Example 2: Divisibility and Contrapositive
Let us prove the following statement −
"For all integers a and b, if a × b is odd, then both a and b are odd."
Again, a direct proof could be tricky, but the contrapositive offers a simpler approach. The contrapositive of this statement is −
"If either a or b is even, then a × b is even."
This is much easier to prove. We assume that one of the numbers, say a, is even. If a is even, then we can write a = 2k for some integer k. Now, a × b = (2k) × b = 2(k × b), which is clearly an even number because it is divisible by 2. Hence, we can conclude this is contrapositive, and by extension, the original statement is True.
Importance of Proving by Contrapositive
The following points highlight why it is sometimes becoming important to use Proof by Contraceptive −
- Logical Equivalence − Proof by contrapositive helps in that the original statement and its contrapositive are logically equivalent. Proving one is the same as proving the other.
- Simplicity − Sometimes, it is easier to prove the contrapositive because it allows us to work with negations, which can simplify the relationships between the variables.
- Versatility − Proof by contrapositive is very much useful when we are working with statements with properties like even and odd numbers, divisibility, and inequalities. It is widely applicable in number theory, logic, and discrete mathematics.
Conclusion
In this chapter, we explained the concept of proof by contrapositive, the fundamental technique in discrete mathematics.
We have started by explaining the basic idea of how the contrapositive of a statement is logically equivalent to the original statement. Then, we gave a detailed example proving that if n2 is even, then n is even, using the contrapositive approach. We also looked at another example involving divisibility to further illustrate the utility of this proof method.