Chapter 1 Introduction to Proofs and Mathematical Logic
In this chapter we shall give an introduction to what proofs are and how we establish that results are correct before moving onto consider proofs involved in Number Theory in chapter 2 onwards.
A proof is a valid argument that establishes the truth of a logical (mathematical) statement. We shall consider proofs from a slightly more informal way by introducing you to the language, notation and methods of proofs, commonly used in most first year mathematics courses.
A logical statement or proposition is a collection of words or mathematical symbols that can meaningfully be assigned the values of true or false. A statement must be either true or false but not both. It cannot be half-true or sort-of-true.
For example,
- “\(1>0\)” is a true statement
- “57 is a prime number” is a false statement
- “Every dog has four legs” is a false statement
- “What is the meaning of life?” is not a logical statement
Sometimes the truth or falsity of statement might depend on the context. For example the statement \[ x > y \] will be true if \(x=1\) and \(y=0\) but false if \(x=0\) and \(y=1\).
‘Statements’ like this are not really propositions at all, but are usually referred to as predicates. For simplicities sake we shall not worry too much about the distinction between propositions and predicates.
A statement that is always true is called a tautology, whilst a statement that is always false is called a contradiction.
Logical Connectives
Many of the statements we meet in practice, are rather long and complicated statements. It is often useful to break them down into smaller parts and consider how these smaller parts contribute to the truth value of the original statement. We shall consider five logical connectives:
Conjunction. The conjunction of two logical statements is true exactly when both statements are true. If \(P\) and \(Q\) are logical statements then the conjunction is denoted by \(P\land Q\) (pronounced “\(P\) and \(Q\)”) and the truth value can be described using a logic table (or truth table). \[ \begin{array}{c|c|c} P&Q&P\land Q\\\hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&F \end{array} \]
Disjunction. The disjunction of two logical statements is true exactly when at least one of the statements are true. If \(P\) and \(Q\) are logical statements then the disjunction is denoted by \(P\lor Q\) (pronounced “\(P\) or \(Q\)”) and the truth table is \[ \begin{array}{c|c|c} P&Q&P\lor Q\\\hline T&T&T\\ T&F&T\\ F&T&T\\ F&F&F \end{array} \] This is the inclusive or meaning that one or both of the statements are true.
Negation. The negation of a logical statement is true exactly when the statement is false. If \(P\) is a logical statement then the negation is denoted by \(\lnot P\) (pronounced “not \(P\)”) and the truth table is \[ \begin{array}{c|c} P&\lnot P\\\hline T&F\\ F&T \end{array} \]
Implication. The implication of two logical statements \(P\) and \(Q\) is denoted by \(P\implies Q\) (pronounced “\(P\) implies \(Q\)” or “If \(P\) then \(Q\)”) and the truth table is \[ \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} \]
Equivalence. The equivalence of two logical statements \(P\) and \(Q\) is denoted by \(P\Leftrightarrow Q\) (pronounced “\(P\) is equivalent to \(Q\)” or “\(P\) if and only if \(Q\)”) and the truth table is \[ \begin{array}{c|c|c} P&Q&P\Leftrightarrow Q\\\hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&T \end{array} \]
\[ (x > 1) \land (x < 3) \]
This statement is true exactly when \(x>1\) is true and \(x < 3\) is true.
In other words, the statement is true for all those real numbers in the interval \((1,3)\).
\[ (x > 1) \lor (x < 3) \]
This statement is true exactly when \(x>1\) is true or \(x < 3\) is true (or both).
Notice that every real number is either bigger than 1 or less than 3, so this statement is always true. In other words it is a tautology.
\[ \lnot(x > 1) \]
This statement is true when \(x > 1\) is false.
In other words it is true when \(x\le 1\).
\[ (x > 1) \implies (x > 0) \]
The statement \(P\implies Q\) being true means that
So the truth of \(Q\) is “dependant” on the truth of \(P\). Notice that it doesn’t say that \(P\) is actually true - just that IF it is true then so is \(Q\).
So \((x>1)\implies(x>0)\) means, IF \(x>1\) then \(x>0\). Intuitively, this is clearly a true statement (since \(1>0\)) and is another example of a tautology.
\[ (x > 1) \implies (x > 0) \]
Notice that if \(x=-1\) then the statement becomes \[ (-1>1)\implies (-1>0) \] which is an example of a “false \(\implies\) false” implication,
while if \(x=0.5\) then it becomes \[ (0.5>1)\implies (0.5>0) \] which is an example of a “false \(\implies\) true” implication.
Both of these implications are however true!
\[ (x < -1) \lor (x > 1)\Leftrightarrow x^2>1. \]
If the left hand side is true, then either \(x<-1\) or \(x>1\). In both cases \(x^2>1\).
On the other hand, if \(x^2>1\) then \(x^2-1>0\) and so \((x-1)(x+1)>0\). Therefore either \(x-1>0\) and \(x+1>0\) or \(x-1<0\) and \(x+1<0\). The first case happens when \(x>1\) and the second case happens when \(x < -1\).
Notice in the above example, in considering \(P\Leftrightarrow Q\) we argued that \[ True\implies True\text{ and }True\Longleftarrow True. \]
However it immediately follows that \[ False\implies False\text{ and }False\Longleftarrow False. \] Can you think why?
Notice that the equivalence connective is the conjunction of two implications: \[ \begin{array}{c|c|c|c|c|c} P&Q&P\implies Q&Q\implies P&P\implies Q\land Q\implies P&P\Leftrightarrow Q\\\hline T&T&T&T&T&T\\ T&F&F&T&F&F\\ F&T&T&F&F&F\\ F&F&T&T&T&T \end{array} \]
Rules of Logic
Showing that the truth tables of two statements are identical allows us to form a number of useful rules for mathematical logic.
We say that statements \(P\) and \(Q\) are logically equivalent, and denote this by \(P\equiv Q\), if they have identical truth tables. In other words \(P\) is true exactly when \(Q\) is true. So from our last example, \[ (P\implies Q)\land (Q\implies P)\text{ is logically equivalent to }P\Leftrightarrow Q \]
Let \(P\) and \(Q\) be propositions.
- Double negation rule. \(P\) is logically equivalent to \(\lnot\lnot P\).
- De Morgan’s rule. \(\lnot(P\lor Q)\) is logically equivalent to \((\lnot P)\land(\lnot Q)\) and \(\lnot(P\land Q)\) is logically equivalent to \((\lnot P)\lor(\lnot Q)\).
- Implication rule. \(P\implies Q\) is logically equivalent to \((\lnot P)\lor Q\).
- Contrapositive rule. \(P\implies Q\) is logically equivalent to \((\lnot Q)\implies (\lnot P)\).
As an exercise, construct the truth tables to justify each of these rules.
Show that \(P\equiv Q\) if and only if \(P\Leftrightarrow Q\) is a tautology.
Why then do we have two symbols \(\equiv\) and \(\Leftrightarrow\)?
Formally the difference is that \(\equiv\) tells us about the propositions while \(\Leftrightarrow\) is part of a proposition.
Find the negations of each of the following statements.
- \((x > 1)\land(x\le0)\)
- \((x > 1)\lor(x\le0)\)
- \(((x>1)\land(x<3))\lor(x\le0)\)
- James, Jo, Andy are boys names
- \(a,b,c\in\mathbb R\)
Solution.
- The negation is \((x\le1)\lor(x>0)\).
- The negation is \((x\le1)\land(x>0)\).
- The negation is \(((x\le1)\lor(x\ge3))\land(x>0)\).
- The negation is James is not a boys name or Jo is not a boys name or Andy is not a boys name.
- The negation is \(a\notin\mathbb R\lor b\notin\mathbb R\lor c\notin\mathbb R\).
Compare the logical statements \(\lnot(P\implies Q)\) and \(P\implies(\lnot Q)\).
The truth tables are \[ \begin{array}{c|c|c|c|c|c} P&Q&\lnot Q&P\implies Q&\lnot(P\implies Q)&P\implies(\lnot Q)\\\hline T&T&F&T&F&F\\ T&F&T&F&T&T\\ F&T&F&T&F&T\\ F&F&T&T&F&T \end{array} \] These are different statements.
So the negation of “If I am elected I will reduce taxes” is not the same as “If I am elected I will not reduce taxes”!
So what is the negation of \(P\implies Q\)?
If \(P\implies Q\) is logically equivalent to \(\lnot P\lor Q\), then \(\lnot(P\implies Q)\) must be logically equivalent to \(\lnot(\lnot P\lor Q)\). This in turn is logically equivalent to \((\lnot\lnot P)\land (\lnot Q)\) or in other words \(P\land(\lnot Q)\).
\[ \begin{array}{c|c|c|c|c|c} P&Q&\lnot Q&P\implies Q&\lnot(P\implies Q)&P\land(\lnot Q)\\\hline T&T&F&T&F&F\\ T&F&T&F&T&T\\ F&T&F&T&F&F\\ F&F&T&T&F&F \end{array} \] So the negation of If I am elected I will reduce taxes is actually
I am elected and I will not reduce taxes.
Converse and Contrapositive
The converse of the implication \[P\implies Q\] is the implication \[Q\implies P.\]
Notice these are not the same thing! \[ \begin{array}{c|c|c|c|c|c} P&Q&P\implies Q&Q\implies P\\\hline T&T&T&T\\ T&F&F&T\\ F&T&T&F\\ F&F&T&T \end{array} \]
So
is different from
The contrapositive of the implication \[P\implies Q\] is the implication \[(\lnot Q)\implies (\lnot P).\] Interestingly, these are the same thing! \[ \begin{array}{c|c|c|c|c|c} P&Q&P\implies Q&(\lnot Q)\implies (\lnot P)\\\hline T&T&T&T\\ T&F&F&F\\ F&T&T&T\\ F&F&T&T \end{array} \]
So
is logically the same as
State the converse and contrapositive of the following statements
- If \(f(x) = \sin(x)\) then \(f'(x) = \cos(x)\).
- If \(y=\cos(A+B)\) then \(y=\cos(A)\cos(B)-\sin(A)\sin(B)\).
Solution.
- If \(f(x) = \sin(x)\) then \(f'(x) = \cos(x)\).
The converse is
If \(f'(x) = \cos(x)\) then \(f(x)=\sin(x)\).
The contrapositive is
If \(f'(x) \ne \cos(x)\) then \(f(x)\ne\sin(x)\).
- If \(y=\cos(A+B)\) then \(y=\cos(A)\cos(B)-\sin(A)\sin(B)\).
The converse is
If \(y=\cos(A)\cos(B)-\sin(A)\sin(B)\) then \(y=\cos(A+B)\).
The contrapositive is
If \(y\ne\cos(A)\cos(B)-\sin(A)\sin(B)\) then \(y\ne\cos(A+B)\).
Write the following statement symbolically and construct its negation, converse and contrapositive (assume that \(m,n\) and \(p\) are all integers).
Solution.
\[mp=np\implies (p=0)\lor(m=n).\]
The converse is \[(p=0)\lor(m=n)\implies mp=np\] and the contrapositive is \[(p\ne0)\land(m\ne n)\implies mp\ne np.\]
This is of the form \(P\implies Q\) and as seen earlier the negation is \[ \lnot(P\implies Q)\equiv P\land\lnot Q. \]
So the negation is \[ mp=np\land p\ne0\land m\ne n. \]
Quantifiers
Frequently we wish to consider statements that are true for all values of some given variable. For example \[ \text{for every real number }x, x^2\ge0. \] In symbolic terms we often write this as \[ \forall x\in\mathbb R, x^2\ge0. \] The symbol “\(\forall\)” is pronounced “for all” or “for every” or “for each”, and is called the universal quantifier.
On the other hand, we may wish to consider statements that are only true for some values of some given variable. For example \[ \text{there exists (at least one) real number }x, |x|=1. \] In symbolic terms we write this as \[ \exists x\in\mathbb R, |x|=1. \] The symbol “\(\exists\)” is pronounced “there exists” or “for some”, and is called the existential quantifier.
What would be the negation of the statement \[ \forall x\in\mathbb R, x^2\ge0? \]
The statement says that “the square of every real number is non-negative” or “every real number has a non-negative square”.
So the negation says that “not every real number has a non-negative square”. In other words “there are some real numbers that do not have a non-negative square”. In symbolic form this is \[ \exists x\in\mathbb R, \lnot(x^2\ge 0). \]
In general, the negation of the universal quantifier \[ \forall x, P(x) \] is the existential quantifier \[ \exists x, \lnot P(x). \]
In the same way the negation of the existential quantifiers \[ \exists x, P(x) \] is the universal quantifier \[ \forall x, \lnot P(x). \]
The negation of \[ \exists x\in\mathbb R, |x|=1 \] is \[ \forall x\in\mathbb R, |x|\ne 1. \]