Implications in Discrete Mathematics

---

---

Implications are useful in Discrete Mathematics to express relationships between statements. We must know these concepts for proving theorems, constructing logical arguments, and understanding conditional reasoning.

In this chapter, we will see what implications are, how they function, and provide examples that illustrate their role in logic and mathematics. We will also cover the truth conditions for implications, discuss how to prove them, and understand the related concepts like contrapositive and converse statements.

What is an Implication?

An implication (or conditional statement) is a compound statement that takes the form of "If P, then Q" (written as P → Q). Here,

• P is the hypothesis (also called the antecedent).
• Q is the conclusion (also called the consequent).

Truth Conditions of an Implication

The truth of an implication depends on the truth values of its hypothesis and conclusion. The rule is simple:

• P→Q is false if P is true and Q is false.
• In all other cases, the implication is true.

This might seem complex and unintuitive at first. For example, consider the statement, "If 1 = 1, then most horses have four legs." The statement is looking quite awkward. But the statement is true because both parts of the statement are true.

Truth Table for Implications

Let us see the truth table for implications −

Examples of Implications

Example 1 − If Bob gets a 90 on the final, then Bob will pass the class

We have seen this example before but here we will analyze it in more detail.

• P − Bob gets a 90 on the final.
• Q − Bob will pass the class.

If Bob does indeed score 90 and passes the class, then the implication is true. However, if Bob gets a 90 but fails the class, the implication is false, and the statement is misleading.

On the other hand, if Bob does not get a 90, we do not care about whether he passes or fails – the implication holds true regardless because P is false.

This is an example of how implications work even when the hypothesis is False:

• True case − Bob gets 90 and passes (P and Q are both True).
• False case − Bob gets 90 but does not pass (P is True, but Q is False).

Indifferent Cases − Bob does not get 90 (no matter what happens next, P→Q is still true because P is False).

Example 2 − If 1 = 1, then most horses have four legs

This is a strange but valid implication. Since both 1 = 1 and the fact that most horses have four legs are true, the implication is also true. There is no need for the two parts to be related. All we care about is whether the hypothesis and conclusion fit the truth conditions.

Example 3 − If 8 is a prime number, then the 7624th digit of π is 8

Since 8 is not a prime number, the hypothesis is false. It does not matter what the conclusion says (even though we have no idea what the 7624th digit of π is), the implication is automatically True because P is False.

Direct Proof of Implications

Let us now understand the concept of direct proof. It is the simplest and most straightforward way to prove an implication P → Q. The strategy is to assume that P is True and then show that Q must be True as well.

Example: Proving that the Sum of Two Even Numbers is Even

Let us understand this with an example: "If a and b are even, then their sum a + b is even."

To do this, we assume that a and b are both even. By definition, even numbers can be expressed as multiples of 2 −

• a = 2k for some integer k.
• b = 2j for some integer j.

Then their sum is −

$$\mathrm{a \:+\: b \:=\: 2k \:+\: 2j \:=\: 2(k \:+ \:j)}$$

Since k + j is an integer, it follows that a + b is also a multiple of 2, which means a + b is even. Thus, we have proved that if a and b are even, their sum must also be even.  

If and Only If (Biconditional Statements)

After the implications, more strict form is a biconditional statement. This is an implication that works in both directions. It combines the original implication and its converse −

• P ↔ Q means "P if and only if Q."

For this statement to be true, both P → Q and Q → P must be true. In other words, both directions of the implication need to hold.

Example: Even and Square Numbers

Consider the following statement −

"An integer n is even if and only if n2 is even." 

This is True because −

• If n is even, then n² is even.
• If n² is even, then n must also be even.

Thus, the biconditional statement holds.

Necessary and Sufficient Conditions

Another important idea is necessary and sufficient conditions. These helps clarify when certain conditions are required or enough to guarantee a conclusion.

• P is necessary for Q − Q cannot be true unless P is true. This is expressed as Q → P.
• P is sufficient for Q − If P is true, then Q is guaranteed to be true. This is expressed as P → Q.

Example: Differentiability and Continuity

From calculus, we know −

"If a function is differentiable at a point, then it is continuous at that point." 

Here, the differentiability is a sufficient condition for continuity, but it is not necessary. A function can be continuous without being differentiable, as is the case with the absolute value function at x=0x = 0x=0.

Common Misunderstandings about Implications

Sometimes we misunderstand the complex nature of implications and all. It is important to remember that an implication does not assert a causal relationship between its components.

The statement "If P, then Q" is purely about logical structure, not causality. This is why seemingly unrelated statements, like "If 1 = 1, then most horses have four legs," can be True.

Also, remember that an implication is still true if the hypothesis is false, even if the conclusion seems unrelated.

Conclusion

In this chapter, we covered the concept of implications in discrete mathematics. We explained how implications are formed, including the truth conditions that are used. We also discussed related ideas of biconditional statements, and explored the difference between necessary and sufficient conditions.