For statements \(P\) and \(Q\text{,}\) the implications or conditional is the statement
\begin{gather*}
\text{if } P \text{ then } Q
\end{gather*}
and is denoted \(P \implies Q\text{.}\) In this context \(P\) is called the hypothesis and \(Q\) is called the conclusion. The implication is false when \(P\) is true and \(Q\) is false; otherwise it is true. The truth table is
It is important to note that \(P \implies Q\) has the same truth table as \((\neg P) \lor Q\text{.}\) Additionally — the truth table is not symmetric in \(P\) and \(Q\) and hence the statements \(P \implies Q\) and \(Q \implies P\) have different truth tables. See the middle two rows of the table below.
Before we get to the peculiarities of the truth table, we should note that the statement “\(P \implies Q\)” can be read in many different ways. Some of these are (in the opinion of the authors) a little obfuscating, and we recommend to stick with “If \(P\) then \(Q\)”.
The author likes the statements above because the hypothesis comes before the conclusion. One may sometimes also see the implication \(P \implies Q\) written as
The authors recommend that you avoid these (at least until you have a bit more experience with mathematical proofs) since they write the conclusion before the hypothesis. They make it very easy to confuse the flow of logic. The statement “\(Q\) if \(P\)” is particularly confusing and, in this author’s opinion, should be avoided.
Many mathematicians like to use the terms “necessary” and “sufficient” when writing implications. These terms allow one to put more emphasis on either the hypothesis or conclusion — this can be quite useful depending on the context in which you are writing. Consider again our nonsense example
It is sufficient to check that a given person is Shakespeare to decide that they must be dead. Similarly, someone is necessarily dead in order for them to be Shakespeare You may see the implication \(P \implies Q\) written in the following ways
The first two of these emphasise that if you want to know that \(Q\) is true, then one need only check (i.e. it is sufficient to check) that \(P\) is true. While the last two emphasise that the truth of \(Q\) is required (it isnecessary) for \(P\) to be true.
Now back to the truth table. At first glance it can seem a bit strange so to get the feel of it we’ll use it on a couple of simple examples and then apply it to something a little larger. Consider the statements \(P: 13 \text{ is even}\) and \(Q: 7 \text{ is odd}\text{.}\) The statement \(P \implies Q\)
The author has definitely lied if you pass the exam but end up failing to course. The other 3 possible outcomes are consistent with them telling the truth. Let’s explore with the caveat that this should not be considered a binding discussion about your actual passing or failing of a given course. Use \(P\) to denote “The student passes the exam”, and \(Q\) to denote “The student passes the course”, so we can write my statement as \(P \implies Q\text{:}\)
Say they failed the exam, but passed the course. Well this is indeed possible — perhaps the exam was very nasty and the author was very impressed by the only-just-fail (and maybe some good homework) and so gave a passing mark overall. The statement is not false and so must be true. \(P \implies Q\) is true.
I found Shakespeare and he is up and about looking very well! The implication above is wrong and \(P \implies Q\) is false. Also we should all learn what his secret is since he is over 450 years old!
There is (was?) a theory that Marlowe faked his own death and then started writing under the name “William Shakespeare” — though this is not widely accepted. People who promulgated this theory were called Marlovians. You can search-engine your way to some interesting articles on Marlowe.
and he is not-alive. This does not actually invalidate the implication — it is still true.
Consider a very alive modern writer — despite their accomplishments they are not Shakespeare. 22
I’m sure you can find a few with the help of your favourite search-engine or online purveyor of books. You might even be lucky enough to study on a campus that that has a bookstore that still sells actual books.
. Again, this does not invalidate the implcation —so it is still true.
So perhaps the most important thing to re-emphasise at this point is that an implication statement is false only when it fails to deliver it’s claim. That is, when we find a situation in which the hypothesis is true but the conclusion is false.
When we construct the proof of such a statement we need to demonstrate that it is always true and never false. To understand how we do so, consider again the four rows of the truth table.
Notice that the implication is true in three of those cases and only false in one case — namely when the hypothesis is true and the conclusion is false. So our proof needs to show that this possibility cannot happen.
We can see from the truth table that the implication is always true. We don’t need to know anything about the conclusion since it doesn’t matter whether or not the conclusion is true or false. Because of this, a proof doesn’t actually have to consider this possibility explicitly. Anyone reading the proof knows 23
Should know.
the truth-table of the implication and so also knows that the implication is true when the hypothesis is false.
We will have to work, since the truth-value of the implication will depend on the truth value of the conclusion. Consequently most proofs start with the assumption that the hypothesis is true and then work towards showing that the conclusion must be true.
