Skip to main content
Logo image

Discrete Mathematics An Open Introduction, 4th Edition

Oscar Levin

Section 1.2 Implications

Subsection Section Preview

Investigate!
Little Timmy’s Mom tells him, β€œIf you don’t eat all your broccoli, then you will not get any ice cream.” Of course, Timmy loves his ice cream, so he quickly eats all his broccoli (which actually tastes pretty good).
πŸ”—
After dinner, when Timmy asks for his ice cream, he is told no! Does Timmy have a right to be upset? Why or why not?
πŸ”—
πŸ”—
By far, the most important type of statement in mathematics is the implication. It is also the least intuitive of our basic molecular statement types. Our goal in this section is to become more familiar with this key concept.
πŸ”—
To see why this sort of statement is so prevalent, consider the Pythagorean Theorem. Despite what social media might claim, the Pythagorean Theorem is not
πŸ”—
a2+b2=c2.
Okay, sure, that has a variable in it, so we must be using the convention to take the universal generalization,
πŸ”—
βˆ€a,b,c∈R(a2+b2=c2).
So 12+52=22??? Okay, fine. The equation is true as long as a and b are the lengths of the legs of a right triangle and c is the length of the hypotenuse. In other words:
πŸ”—
πŸ”—
If a and b are the lengths of the legs of a right triangle with hypotenuse of length c, then a2+b2=c2.
πŸ”—
Math is about making general claims, but a claim is rarely going to be true of absolutely every mathematical object. The way we restrict our claims to a particular type of object is with an implication: β€œTake any object you like, if it is of the right type, then this thing is true about it.”
πŸ”—
Similarly, as we saw in the Quantifiers and Predicates subsection, when we make claims like β€œEvery square is a rectangle,” we really have an implication: β€œIf something is a square, then it is a rectangle.”
πŸ”—
Here is a reminder of what we mean by an implication.
πŸ”—

Definition 1.2.1. Implication.

An implication (or conditional) is a molecular statement of the form
πŸ”—
P→Q
where P and Q are statements. We say that
πŸ”—
  • P is the hypothesis (or antecedent).
  • Q is the conclusion (or consequent).
πŸ”—
An implication is true provided P is false or Q is true (or both), and false otherwise. In particular, the only way for P→Q to be false is for P to be true and Q to be false.
πŸ”—
πŸ”—
The definition of truth of an implication can also be represented as a truth table:
πŸ”—
P Q P→Q
T T T
T F F
F T T
F F T
Figure 1.2.2. The truth table for P→Q.
πŸ”—
Does this truth table make sense? Should we believe it? Look in particular at the third row: F, T, T, and consider the implication, β€œIf 5<3 then 5+3=8.” Does that statement feel true? The truth table says it should be (since 5<3 is false, and 5+3=8 is true).
πŸ”—
Much of what we will do in the remainder of this section is convince ourselves that this truth table makes sense.
πŸ”—

Worksheet Preview Activity
A4US

1.
Consider the statement, β€œIf Tommy doesn’t eat his broccoli, then he will not get any ice cream.” Which of the following statements mean the same thing (i.e., will be true in the same situations)? Select all that apply.
πŸ”—
  • If Tommy does eat his broccoli, then he will get ice cream.
  • Are you sure? Did we say what happens when he does eat the broccoli, or only what happens when he doesn’t?
  • If Tommy gets ice cream, then he ate his broccoli.
  • If he got ice cream, he must have eaten the broccoli, because if he didn’t, then he wouldn’t have had ice cream.
  • If Tommy doesn’t get ice cream, then he didn’t eat his broccoli.
  • Could there have been a reason that Tommy doesn’t get ice cream even if he did eat his broccoli?
  • Tommy ate his broccoli and still didn’t get any ice cream.
  • This is the opposite of the original statement (it is false precisely when the original statement is true).
πŸ”—
2.
Suppose that your shady uncle offers you the following deal: If you loan him your car, then he will bring you tacos. In which of the following situations would it be fair to say that your uncle is a liar (i.e., that his statement was false)? Select all that apply.
πŸ”—
  • You loan him your car. He brings you tacos.
  • You loan him your car. He never buys you tacos.
  • You don’t loan him your car. He still brings you tacos.
  • Maybe he just really likes giving you tacos. That’s not enough to say he was a liar, is it?
  • You don’t loan him your car. He never brings you tacos.
πŸ”—
3.
Consider the sentence, β€œIf xβ‰₯10, then x2β‰₯25.” This sentence becomes a statement when we replace x by a value, or β€œcapture” the x in the scope of a quantifier. Which of the following claims are true (select all that apply)?
πŸ”—
  • If we replace x by 15, then the resulting statement is true. (Note, 152=225.)
  • If we replace x by 3, then the resulting statement is true.
  • If we replace x by 6, then the resulting statement is true.
  • The universal generalization (β€œfor all x, if xβ‰₯10 the x2β‰₯25”) is true.
  • There is a number we could replace x with that makes the statement false.
πŸ”—
4.
Consider the statement, β€œIf I see a movie, then I eat popcorn” (which happens to be true). Based solely on your intuition of English, which of the following statements mean the same thing? Select all that apply.
πŸ”—
  • If I eat popcorn, then I see a movie.
  • This is not equivalent to the original statement. Maybe I also eat popcorn when I watch TV? In that case, the original statement would be true, but this one would be false.
  • If I don’t eat popcorn, then I don’t see a movie.
  • Correct.
  • It is necessary that I eat popcorn when I see a movie.
  • This is equivalent to the original statement (although here β€œnecessary” is used in a logical sense).
  • To see a movie, it is sufficient for me to eat popcorn.
  • Just because I eat popcorn, doesn’t mean I see a movie. I might eat popcorn in other situations. So this is not equivalent to the original statement.
  • I only watch a movie if I eat popcorn.
  • Another way of saying this is, β€œI watch a movie only if I eat popcorn.” This is equivalent to the original statement.
πŸ”—
πŸ”—
πŸ”—

Subsection Understanding the Truth Table

The truth value of the implication is determined by the truth values of its two parts. Our definition of the truth conditions for an implication says that there is only one way for an implication to be false: when the hypothesis is true and the conclusion is false.
πŸ”—

Example 1.2.3.

Consider the statement:
πŸ”—
If Bob gets a 90 on the final, then Bob will pass the class.
πŸ”—
This is definitely an implication: P is the statement β€œBob gets a 90 on the final,” and Q is the statement β€œBob will pass the class.”
πŸ”—
Suppose I made that statement to Bob. In what circumstances would it be fair to call me a liar? What if Bob really did get a 90 on the final, and he did pass the class? Then I have not lied; my statement is true. However, if Bob did get a 90 on the final and did not pass the class, then I lied, making the statement false. The tricky case is this: What if Bob did not get a 90 on the final? Maybe he passes the class, maybe he doesn’t. Did I lie in either case? I think not. In these last two cases, P was false, and the statement Pβ†’Q was true. In the first case, Q was true, and so was Pβ†’Q. So Pβ†’Q is true when either P is false or Q is true.
πŸ”—
πŸ”—
Just to be clear, although we sometimes read Pβ†’Q as β€œP implies Q”, we are not insisting that there is some causal relationship between the statements P and Q (although there might be). β€œIf x<y, then x+1<y+1,” is a true statement (or at least, its universal generalization is). We know it is true because we understand how the two parts interact. If you add 1 to two numbers x and y, then their order does not change. But the statement, β€œif 1<2, then Euclid studied geometry” is also a true implication.
πŸ”—

Example 1.2.4.

Decide which of the following statements are true and which are false. Briefly explain.
πŸ”—
  1. If 1=1, then most horses have 4 legs.
  2. If 0=1, then 1=1.
  3. If 8 is a prime number, then the 7624th digit of Ο€ is an 8.
  4. If the 7624th digit of Ο€ is an 8, then 2+2=4.
πŸ”—
Solution.
All four of the statements are true. Remember, the only way for an implication to be false is for the if part to be true and the then part to be false.
  1. Here both the hypothesis and the conclusion are true, so the implication is true. It does not matter that there is no meaningful connection between the true mathematical fact and the fact about horses.
  2. Here the hypothesis is false and the conclusion is true, so the implication is true.
  3. I have no idea what the 7624th digit of Ο€ is, but this does not matter. Since the hypothesis is false, the implication is automatically true.
  4. Regardless of the truth value of the hypothesis, the conclusion is true, making the implication true.
πŸ”—
This is a strange example and isn’t really how we use implications anyway. This strangeness is not just mathematicians being stubborn though. The truth conditions for implications must be like they are for mathematics to make sense. Let’s see why.
πŸ”—

Example 1.2.5.

Consider the statement, β€œAll squares are rectangles,” which can also be phrased as, β€œFor all shapes, if the shape is a square, then it is a rectangle.” Is this statement true or false? Are we sure? What about the following three shapes?
πŸ”—
three shapes, a square, a non-square rectangle, and a triangle.
Solution.
Of course the statement is true. A square is a 4-sided plane figure with 4 right angles and 4 equal-length sides, while a rectangle is a 4-sided plane figure with 4 right angles.
However, what we mean when we consider a universal statement like this is that, no matter what we β€œplug in” for the variable (β€œthe shape” in this case), the resulting statement is true. When the statement is about a particular shape, we have an implication Pβ†’Q. This means it must be true that, if the actual shape on the left is a square, then it is a rectangle. Great. The shape is a square (P is true) and is a rectangle (Q is true), so yes, the implication is true.
Is the implication true of the rectangle in the middle? Well, that shape is not a square (P is false), and it is a rectangle (Q is true). But look, we believe that all squares are rectangles, so the statement must be true. Even of a rectangle. The only way this works is if β€œtrue implies false” is true!
Similarly, all squares are rectangles is a true statement, even when we look at a triangle. P is false (the triangle is not a square), and Q is false (the triangle is not a rectangle). Thankfully, we defined implications to be true in this case as well.
We have given shapes that illustrate lines 1, 3, and 4 of the truth table for implications (Figure 1.2.2). What shape illustrates line 2? That would need to be a shape that was a square and was not a rectangle.... Of course we can’t find one, precisely because the statement is true!
πŸ”—
πŸ”—

Reading Questions Reading Questions

1.

It happens to be true that all mammals have hair. Which of the following are also true?
πŸ”—
  • Having hair is a necessary condition for being a mammal.
  • Having hair is a sufficient condition for being a mammal.
  • This would be saying that as soon as a thing has hair, it is a mammal. But...tarantulas!
  • If an animal doesn’t have hair, then it is not a mammal.
  • This is the contrapositive of the original statement.
  • An animal is a mammal only if it has hair.
  • And this is the same as saying if an animal is a mammal, then it has hair.
πŸ”—

2.

Give an example of a true implication (written out in words) that has a false converse. Explain why your implication is true and why the converse is false.
πŸ”—
πŸ”—

3.

What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.
πŸ”—
πŸ”—
πŸ”—

Exercises Practice Problems

1.

In my safe is a sheet of paper with two shapes drawn on it in colored crayon. One is a diamond, and the other is a circle. Each shape is drawn in a single color. Suppose you believe me when I tell you that, "If the diamond is purple, then the circle is blue.
πŸ”—
What do you therefore know about the truth value of the following statements?
πŸ”—
  1. If the circle is blue, then the diamond is purple.
  2. The diamond and the circle are both blue.
  3. The diamond and the circle are both purple.
  4. If the circle is not blue, then the diamond is not purple.
  5. The diamond is not purple, or the circle is blue.
πŸ”—
πŸ”—

2.

Suppose the statement, "If the circle is orange, then the square is purple," is true. Assume also that the converse is false. Classify each statement below as true or false (if possible).
πŸ”—
  1. The circle is orange.
  2. The square is purple.
  3. The circle is orange if and only if the square is not purple.
  4. The circle is orange if and only if the square is purple.
πŸ”—
πŸ”—

3.

Consider the statement, "If you will give me magic beans, then I will give you a cow." Decide whether each statement below is the converse, the contrapositive, or neither.
πŸ”—
  1. If you will not give me magic beans, then I will not give you a cow.
  2. If you will give me magic beans, then I will not give you a cow.
  3. You will give me magic beans, and I will not give you a cow.
  4. If I will give you a cow, then you will give me magic beans.
  5. If I will not give you a cow, then you will not give me magic beans.
  6. If I will give you a cow, then you will not give me magic beans.
πŸ”—
πŸ”—

4.

You have discovered an old paper on graph theory that discusses the viscosity of a graph (which for all you know, is something completely made up by the author). A theorem in the paper claims that β€œif a graph satisfies condition (V), then the graph is viscous.” Which of the following are equivalent ways of stating this claim? Which are equivalent to the converse of the claim?
πŸ”—
  1. Satisfying condition (V) is a necessary condition for a graph to be viscous.
  2. For a graph to be viscous, it is sufficient for it to satisfy condition (V).
  3. A graph is viscous only if it satisfies condition (V).
  4. Every viscous graph satisfies condition (V).
  5. For a graph to be viscous, it is necessary that it satisfies condition (V).
πŸ”—
πŸ”—

5.

Which of the following statements are equivalent to the implication, "if you win the lottery, then you will be rich," and which are equivalent to the converse of the implication?
πŸ”—
  1. You will win the lottery if you are rich.
  2. You will be rich if you win the lottery.
  3. You will be rich only if you win the lottery.
  4. It is sufficient to win the lottery to be rich.
  5. Either you don’t win the lottery, or else you are rich.
πŸ”—
πŸ”—
πŸ”—

Exercises Additional Exercises

1.

Translate into English:
πŸ”—
  1. βˆ€x(E(x)β†’E(x+2)).
  2. βˆ€xβˆƒy(sin⁑(x)=y).
  3. βˆ€yβˆƒx(sin⁑(x)=y).
  4. βˆ€xβˆ€y(x3=y3β†’x=y).
πŸ”—
πŸ”—

2.

Consider the statement, β€œIf Oscar eats Chinese food, then he drinks milk.”
πŸ”—
  1. Write the converse of the statement.
  2. Write the contrapositive of the statement.
  3. Is it possible for the contrapositive to be false? If it was, what would that tell you?
  4. Suppose the original statement is true, and that Oscar drinks milk. Can you conclude anything (about his eating Chinese food)? Explain.
  5. Suppose the original statement is true, and that Oscar does not drink milk. Can you conclude anything (about his eating Chinese food)? Explain.
πŸ”—
πŸ”—

3.

Write each of the following statements in the form, β€œIf …, then ….” Careful, some statements may be false (which is fine for the purposes of this question).
πŸ”—
  1. To lose weight, you must exercise.
  2. To lose weight, all you need to do is exercise.
  3. Every American is patriotic.
  4. You are patriotic only if you are American.
  5. The set of rational numbers is a subset of the real numbers.
  6. A number is prime if it is not even.
  7. Either the Broncos will win the Super Bowl, or they won’t play in the Super Bowl.
πŸ”—
πŸ”—

4.

Consider the implication, β€œIf you clean your room, then you can watch TV.” Rephrase the implication in as many ways as possible. Then do the same for the converse.
πŸ”—
Hint.
Of course there are many answers. It helps to assume that the statement is true and the converse is not true. Think about what that means in the real world, and then start saying it in different ways. Some ideas: Use β€œnecessary and sufficient” language, use β€œonly if,” consider negations, use β€œor else” language.
πŸ”—

5.

Recall from calculus, if a function is differentiable at a point c, then it is continuous at c, but that the converse of this statement is not true (for example, f(x)=|x| at the point 0). Restate this fact using β€œnecessary and sufficient” language.
πŸ”—
πŸ”—

6.

Consider the statement, β€œFor all natural numbers n, if n is prime, then n is solitary.” You do not need to know what solitary means for this problem, just that it is a property that some numbers have and others do not.
πŸ”—
  1. Write the converse and the contrapositive of the statement, saying which is which. Note: the original statement claims that an implication is true for all n, and it is that implication that we are taking the converse and contrapositive of.
  2. Write the negation of the original statement. What would you need to show to prove that the statement is false?
  3. Even though you don’t know whether 10 is solitary (in fact, nobody knows this), is the statement, β€œIf 10 is prime, then 10 is solitary” true or false? Explain.
  4. It turns out that 8 is solitary. Does this tell you anything about the truth or falsity of the original statement, its converse or its contrapositive? Explain.
  5. Assuming that the original statement is true, what can you say about the relationship between the set P of prime numbers and the set S of solitary numbers. Explain.
πŸ”—
πŸ”—
πŸ”—
You have attempted 1 of 9 activities on this page.
πŸ”—
PrevTopNext