CIS-375 Help Session Note 3 (Spring 2020)

Scire ad trascendere - Learn to transcend.

Topics covered:


Indirect proof

Proof by contrapositive

If we look at the truth table of \(a \rightarrow b\) and \((\neg b) \rightarrow \neg a\), it is not difficult to find out that they are logically equivalent. Therefore, proving \(a \rightarrow b\) is equivalent to proving \((\neg b) \rightarrow \neg a\).


Write the contrapositive of “if \(a\) and \(b\), then \(c\) or \(d\)”.

The proposition can be written as \((a \land b) \rightarrow (c \lor d)\). The contrapositive is

\[\begin{align*} &\phantom{\Rightarrow}\quad(a \land b) \rightarrow (c \lor d)\\ &\Rightarrow\quad \neg (c \lor d) \rightarrow \neg(a \land b)\\ & \Rightarrow\quad (\neg c) \land (\neg d) \rightarrow (\neg a) \lor (\neg b) \end{align*}\]

In plain English, it means “if not \(c\) and not \(d\), then not \(a\) or not \(b\)”.

Write the contrapositive of “if \(n \in \mathbb{Z}\) is a even number, then \(\exists k \in \mathbb{Z}\), \(n = 2k\)”.

The proposition can be written as \(n~\mbox{is even}\rightarrow \exists k \in \mathbb{Z}, n = 2k\). The contrapositive is

\[\begin{align*} &\phantom{\Rightarrow}\quad n~\mbox{is even}\rightarrow \exists k \in \mathbb{Z}, n = 2k\\ &\Rightarrow\quad \neg (\exists k \in \mathbb{Z}, n = 2k) \rightarrow n~\mbox{is not even}\\ &\Rightarrow\quad \forall k \in \mathbb{Z}, n \neq 2k \rightarrow n~\mbox{is not even}. \end{align*}\]

In plain English, it means “If for all integer \(k\), \(n\) is not equal to \(2k\), then \(n\) is not even.”

Proof by contradiction

We can observe that \(a \rightarrow b\) is logically equivalent to \((a \land \neg b) \rightarrow \mathrm{False}\). Therefore, to prove \(a \rightarrow b\) is True, we can assume both \(a\) and \(\neg b\) are True, and verify that this will imply something False.


Proof by contradiction: if \(x\) is a real number, then \(x^2\) is not negative.

Suppose \(x\) is a real number, but \(x^2\) is negative. If \(x \in R\), we know that either \(x < 0\), \(x = 0\) or \(x > 0\).

  1. When \(x < 0\), \(x^2 > 0\).
  2. When \(x = 0\), \(x^2 = 0\).
  3. When \(x > 0\), \(x^2 > 0\).

Therefore, such real number \(x\) does not exist. \(\Rightarrow\Leftarrow\)

Remarks. The \(\Rightarrow\Leftarrow\) notation means: thus we have reached a conclusion. Therefore the supposition must be False, which means the original proposition must be True.

Proof by contradiction: if \(a\) and \(b\) are real numbers and \(ab = 0\), then \(a = 0\) or \(b = 0\).

Suppose \(a\) and \(b\) are real numbers and \(ab = 0\), but \(a \neq 0\) and \(b \neq 0\). It is obvious that \(ab \neq 0\). \(\Rightarrow\Leftarrow\)

The technique is very useful in the proof of some very tricky statements, for example: