1.4 Implications

Consider the following truth-table where the truth value of the third column depends on the truth values of $P,Q$. \[ \begin{array}{c|c|c} P&Q&*\\\hline T&T&T\\ T&F&F\\ F&T&T\\ F&F&T \end{array} \] Suppose we know that $*$ is true. What does this tell us about the relationship between $P$ and $Q$?

The $*$ statement is true if

the statement $Q$ must be true whenever $P$ is true

Thus this truth table encodes the notion of implication: $P\implies Q$.

We define the implication $P$ implies $Q$ or in symbols $P\implies Q$ to be the statement with truth table \[ \begin{array}{c|c|c} P&Q&P\implies Q\\\hline T&T&T\\ T&F&F\\ F&T&T\\ F&F&T \end{array} \]

This can be expressed in terms of the fundamental logical connectives previously introduced by defining $P\implies Q$ as the statement $(\lnot P)\lor Q$. Note that $(\lnot P)\lor Q$ has exactly the truth table given above. Hence any statement involving $P\implies Q$ can be expressed as a disjunction using the logical equivalence \[P\implies\! Q \; \equiv\; (\lnot P)\lor Q.\] By convention if we write something like $P\lor Q \implies R\land S$ we will interpret this as meaning $(P\lor Q) \implies (R\land S)$. In words we might say “if P is true or Q is true then R and S are both true”: we can think of the if…then… as providing the implied brackets around then $P$ or $Q$.

Example 1.6

Consider the statement

if $n-1$ is a multiple of $4$ then $n^2-1$ is a multiple of $4$

We write this symbolically as $P(n)\implies Q(n)$ where: \[\begin{align*} P(n):\;& n-1 \text{ is a multiple of }4\\ Q(n):\;& n^2-1 \text{ is a multiple of }4\\ \end{align*}\]

The truth values of $P$ and $Q$ depend on the value of $n$ \[ \begin{array}{c|c|c|c} n&P(n)&Q(n)&P(n)\implies Q(n)\\\hline ...-3, 1, 5, ... &T&T&T\\ &T&F&F\\ ...-1, 3, 7, ... &F&T&T\\ ...-2, 0, 2, 4,... &F&F&T \end{array} \]

For some values of $n$ both $P$ and $Q$ are true. For some values $P$ is false, but $Q$ is true. For some values (even $n$) both $P$ and $Q$ are false. But notice that for all values of $n$ the implication $P(n)\implies Q(n)$ is true, as there are no values of $n$ for which $n-1$ is a multiple of $4$ but where $n^2-1$ is not a multiple of $4$.

To reiterate, the meaning of $\implies$ is that whenever the first statement is true, the second statement must also be true.

Example 1.7

Consider the statement

if $p$ is prime then $2^p - 1$ is prime

How do we show that this is false?

Let us again consider a truth table: \[ \begin{array}{c|c|c|c} p&p\text{ is prime}&2^p\text{ is prime}&(p\text{ is prime})\implies (2^p - 1\text{ is prime}) \\\hline 2,3,5,7,13,... &T&T&T\\ 11,23, ... &T&F&F\\ &F&T&T\\ 1,4,6,8,9,... &F&F&T \end{array} \] We disprove the statement by giving a counterexample, here $p=11$ is a possible counterexample.

Counterexamples are cases where the first statement is true and the second statement is false which makes the implication false.

Symbolically we negate $P\implies Q$ as follows: \[\begin{align*} \lnot(P\implies Q) &\equiv\lnot(\lnot P \lor Q)&\text{by definition of $\implies$}\\ &\equiv(\lnot\lnot P)\land \lnot Q\text{by de Morgan's rule}\\ &\equiv P\land \lnot Q&\text{by the double $\lnot$ rule} \end{align*}\]

The implication $P\implies Q$ is false when $P$ is true but $Q$ fails to be true.

Converse and Contrapositive

The converse of an implication $P\implies Q$ is the reversed implication $Q\implies P$.

This has a different meaning to $P\implies Q$ and may be false even if $P\implies Q$ is true.

Example 1.8

$n-1$ is a multiple of $4$ $\implies$ $n^2-1$ is a multiple of $4$

is a true statement. Its converse is

$n^2-1$ is a multiple of $4$ $\implies$ $n-1$ is a multiple of $4$

which is false, for example $3^2-1$ is a multiple of $4$ but $3-1$ is not a multiple of $4$.

We define the equivalence $P\iff Q$ (or in words $P$ if and only if $Q$) to be the statement $(P\implies Q) \land (Q\implies P)$. This has truth table \[ \begin{array}{c|c|c} P&Q&P\iff Q\\\hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&T \end{array} \]

Example 1.9

$n^2-1$ is a multiple of $4$ $\iff$ $n$ is odd

is a true statement.

The contrapositive of an implication $P\implies Q$ is the implication $\lnot Q\implies \lnot P$.

The implication $P\implies Q$ and its contrapositive $\lnot Q\implies \lnot P$ are equivalent: the first says

when $P$ is true then $Q$ must also be true

but a consequence of this is

$Q$ is false could happen only if $P$ is false

which is the contrapositive.

We can show that $P\implies Q\; \equiv\; \lnot Q\implies \lnot P$ as follows: \[\begin{align*} P\implies Q\; &\equiv\; \lnot P\lor Q & \text{definition of $\implies$}\\ &\equiv\; Q\lor \lnot P & \text{commutativity}\\ &\equiv\; \lnot\lnot Q\lor \lnot P & \text{double $\lnot$ rule}\\ &\equiv\; \lnot Q\implies \lnot P & \text{definition of $\implies$} \end{align*}\]

Example 1.10

The statement

$n^2-1$ is a multiple of $4$ $\implies$ $n$ is odd

has contrapositive

$n$ is even $\implies$ $n^2-1$ is not a multiple of $4$

It is easy to see that the latter must be true since if $n$ is even then $n^2$ will be a multiple of $4$ and hence $n^2-1$ is not a multiple of $4$. Since the original statement is equivalent to its contrapositive, it follows that that statement is also true.

Example 1.11

Here’s another word problem example.

Andy, Billie, Charlie and Dannie are friends, some of whom are mathematicians. Consider the statements:

If Billie is not a mathematician then Andy and Charlie are not mathematicians
If Andy not a mathematician or Billie is a mathematician then Charlie is a mathematician.
If Billie and Charlie are mathematicians then neither Andy nor Dannie are mathematicians.

Assuming the statements are true, which of the friends are mathematicians?

We begin by writing the statements symbolically:

$\lnot B \implies (\lnot A \land \lnot C)$
$(\lnot A\lor B)\implies C$
$B\land C \implies \lnot(A\lor D)$

By definition of $\implies$ and the double $\lnot$ rule, the first statement can be rewritten \[\lnot B \implies (\lnot A \land \lnot C) \equiv \lnot \lnot B \lor (\lnot A \land \lnot C)\equiv B \lor (\lnot A \land \lnot C).\] Then by de Morgan’s rule this is equivalent to \[(B \lor \lnot A)\land( B\lor \lnot C).\] As the statement is assumed to be true, both parts of the conjunction must be true, in particular $B \lor \lnot A$ is a true statement. This is the same as $\lnot A\lor B$ and by the second statement above we know $(\lnot A\lor B)\implies C$. Hence we deduce that $C$ must be true.

But we also know that $B\lor \lnot C$ is true so the conjunction of this with $C$ (that is $(B\lor \lnot C)\land C$) is also true. So we have \[(B\lor \lnot C)\land C\equiv (B\land C) \lor (\lnot C\land C)\equiv (B\land C) \lor F \equiv B\land C\] applying the de Morgan, complement and identity rules.

We have therefore shown that $B$ and $C$ are true, but now from statement 3 it follows that the statement $\lnot (A\lor D) \equiv \lnot A \land \lnot D$ holds.

Therefore Billie and Charlie are mathematicians while Andy and Dannie are not.

In the above example, a couple of times we used the observation that when we know that an implication $P\implies Q$ is true and also that $P$ itself is true, then we can conclude that $Q$ must also be true. (In the above example we did this using the statements $(\lnot A\lor B)\implies C$) and $\lnot A\lor B$ to deduce $C$.). This principle goes by the name r defining(“modus ponens”) which can be justified by the following logical equivalences: \[\begin{align*} P\land(P\implies Q)\; &\equiv\; P\land (\lnot P \lor Q) & \text{definition of $\implies$}\\ &\equiv\; (P\land \lnot P)\lor (P\land Q) & \text{de Morgan's rule}\\ &\equiv\; F\lor (P\land Q) & \text{complement rule}\\ &\equiv\; P\land Q & \text{identity rule} \end{align*}\]

These equivalences tell us that knowing $P$ holds and $P\implies Q$ is the same as knowing that $P$ and $Q$ are both true.

The following theorem gathers together some logical equivalences involving $\implies$.

Theorem 1.12

$P\implies Q \;\equiv\; \lnot P \lor Q$ (definition)
$P\implies Q \;\equiv\; \lnot Q\implies\lnot P$ (contrapositive)
$P\land(P\implies Q) \;\equiv\; P\land Q$ (modus ponens)
$P\implies (Q\land R) \;\equiv\; (P\implies Q)\land (P\implies R)$
$(P\lor R )\implies R \;\equiv\; (P\implies R) \land (Q\implies R)$
$(P\land Q)\implies R \;\equiv\;P\implies (Q\implies R)$