1.

Logic, proof and sets I — Introducing logic and proof

Unit 1: Logic, proof and sets I

Introducing logic and proof

Overview

In this unit, we want to introduce the idea of a proof. But, before we do this, we need to
know two things. Firstly, what kind of mathematical statement can be proved and, as
we shall see, the answer to this is that we need to be looking at certain propositions, i.e.
mathematical statements that are certainly either true or false. And, secondly, we need
to discuss a little basic logic, i.e. we need to understand how the truth or falsity of very
simple propositions affect the truth or falsity of other propositions that can be formed
using certain common logical operations. In essence, then, we need to know what we are
looking at and then we need to know what it means. Once we have done this, we will be
able to prove some very simple mathematical statements and see how far we have come.

Aims

The aims of this unit are as follows.

To introduce propositions, mathematical statements that are either true or false.

To introduce the basic logical operations that allow us to form compound

propositions.

To see how truth tables allow us to determine the truth or falsity of compound
propositions.

To see how to prove some very simple propositions.

Specific learning outcomes can be found near the end of this unit.

1.1 Mathematical statements

We are interested in a certain kind of mathematical statement called a proposition and
the basic idea is that any proposition is either true or false. So, the statement

20 is an even number,

is a proposition that is true. Notice, of course, that we haven’t proved that this
statement is true, we have just relied on our past mathematical knowledge about even
numbers. The statement
20 is not an even number,

8
 1. Logic, proof and sets I — Introducing logic and proof

is also a proposition but this one is false. Notice, in particular, that the falsity of this
proposition follows logically from the truth of the first proposition because the latter is
the denial, or negation, of the second.
We form compound propositions from simpler ones by using various words. For instance,
the statement
20 and 40 are even numbers,

is the conjunction of two simpler propositions, namely ‘20 is an even number’ and ‘40 is
an even number’, and it is saying that ‘20 is an even number and 40 is an even number’.
Again, even though we haven’t tried to prove this, we would probably be happy to say
this is true because we know that the two simpler propositions are true and we know
what ‘and’ means. The statement

20 or 37 is an even number,

is the disjunction of two simpler propositions, namely ‘20 is an even number’ and ‘37 is
an even number’, and it is saying that ‘20 is an even number or 37 is an even number’.
Again, even though we haven’t tried to prove this, we would probably be happy to say
this is true because we know that the first of the two simpler propositions is true and
we know what ‘or’ means. Lastly, the statement

if 20 is an even number, then 24 is an even number,

is an example of an implication. Again, without proof, we probably know that this

proposition is true but you might be slightly disconcerted when you hear that the
implication
if 7 is an even number, then 13 is an even number,

is also true. But, to some extent, this is what this unit is all about: How do we
determine the truth or falsity of compound propositions from the truth or falsity of
their components?

1.2 Logical operations and truth tables

Given one or more propositions, it is possible to form new propositions by using certain
logical operations. Indeed, given that our original propositions can be true or false, the
fundamental task of logic is to allow us to determine whether the new proposition is
true or false. So, we have two questions to ask. Firstly, what are these logical
operations? And, secondly, given the truth or falsity of our original propositions, how
can we determine whether the new proposition is true or false?
We will answer the first question by introducing five logical operations known as
negation, conjunction, disjunction, implication and the biconditional. But, before we do
that, we need to introduce truth tables as these will enable us to define when the new
proposition is true or false by looking at the truth or falsity of the component
propositions.

9
1. Logic, proof and sets I — Introducing logic and proof

1.2.1 Truth tables

As indicated above, propositions can be true or false and so let’s denote ‘true’ by T and
‘false’ by F. Indeed, if we have one proposition, say p, there are two possibilities — it is
either true or it is false — and we can capture this in a truth table as follows.

p ?
T ?
F ?

Table 1.1: The rows for a truth table involving one proposition.

Notice that the second and third rows exhaust the possibilities when considering the
truth or falsity of p and the question marks are place-holders for whatever new
proposition we may construct from p alone using logical operations (in the first row)
and its corresponding truth or falsity (in the second and third row). It is convenient, as
we have done here, to ‘separate’ the inputs (i.e. the truth or falsity of p) from the
outputs (i.e. the truth or falsity of the new proposition by a ‘double vertical line’).
If we have two propositions, say p and q, there are four possibilities — they’re both
true, one is true and the other is false, or they’re both false — and we can capture this
in a truth table as follows.

p q ?
T T ?
T F ?
F T ?
F F ?

Table 1.2: The rows for a truth table involving two propositions.

Again, notice that the second to fifth rows exhaust the possibilities when considering
the truth or falsity of p and q and the question marks are place-holders for whatever
new proposition we may construct from p and q using logical operations (in the first
row) and its corresponding truth or falsity (in the second to fifth row). It is convenient,
as we have done here, to write the four possibilities in this order as then we can be sure
that we haven’t missed (or repeated) any of them.

Activity 1.1 Suppose that we have three propositions, say p, q and r. How many
possibilities are there when considering their truth or falsity? Following what we
have seen in the tables above, write out the table in this case.

This may all sound a bit abstract, but using the two truth tables above, we can now
easily specify the behaviour of our four fundamental logical operations by appropriately
‘filling in’ the question marks!

10
 1. Logic, proof and sets I — Introducing logic and proof

1.2.2 Logical operations

We can now introduce our five logical operations and begin to see how the truth or
falsity of compound propositions that involve them depend on the truth or falsity of
their component propositions.

Negation

The simplest way of taking a proposition and making a new proposition is to negate it.
This logical operation takes a proposition, p, and gives us the negation of p, denoted by
¬p, which we can think of as ‘not p’ in English. So, for instance, if p is the proposition
‘20 is an even number’, then ¬p would be the proposition ‘20 is not an even number’.
As the use of the word ‘not’ in English would suggest, when we take a proposition, p,
and form its negation, ¬p, we would want to find that if p is true, then ¬p is false
whereas if p is false, ¬p is true. This idea is succinctly captured by the truth table for
negation which is given in Table 1.3.

p ¬p
T F
F T

Table 1.3: The truth table for negation.

This truth table tells us, quite simply, that when p is true, ¬p is false (if we look at the
second row) and when p is false, ¬p is true (if we look at the third row). So, returning
to our example where p is the proposition ‘20 is an even number’ we would expect that
p is true and ¬p, i.e. the proposition ‘20 is not an even number’, is false.

Activity 1.2 What does the truth table for negation tell us about p when ¬p is
true and when ¬p is false?

Conjunction

This logical operation takes two propositions, p and q, and gives us their conjunction
denoted by p ∧ q, which we can think of as ‘p and q’ in English. So, for instance, if p is
the proposition ‘20 is an even number’ and q is the proposition ‘40 is an even number’,
then p ∧ q would be the proposition ‘20 is an even number and 40 is an even number’ or,
more succinctly, ‘20 and 40 are even numbers’.
As the use of the word ‘and’ in English would suggest, when we take the propositions p
and q, and form their conjunction, p ∧ q, we would want to find that if p and q are both
true, then p ∧ q is true whereas if at least one of p or q is false, p ∧ q is false. This idea is
succinctly captured by the truth table for conjunction which is given in Table 1.4.
This truth table tells us, quite simply, that when p and q are both true, p ∧ q is true (if
we look at the second row) and if at least one of p or q is false, p ∧ q is false (if we look
at the third to fifth rows). So, returning to our example where p is the proposition ‘20 is

11
1. Logic, proof and sets I — Introducing logic and proof

p q p∧q
T T T
T F F
F T F
F F F

Table 1.4: The truth table for conjunction.

an even number’ and q is the proposition ‘40 is an even number’, we would expect that
p ∧ q, i.e. the proposition ‘20 and 40 are even numbers’, is true because we expect that
both p and q are true.

Activity 1.3 What does the truth table for conjunction tell us about p and q when
p ∧ q is true and when p ∧ q is false?

Disjunction

This logical operation takes two propositions, p and q, and gives us their disjunction
denoted by p ∨ q, which we can think of as ‘p or q’ in English. So, for instance, if p is
the proposition ‘20 is an even number’ and q is the proposition ‘37 is an even number’,
then p ∨ q would be the proposition ‘20 is an even number or 37 is an even number’ or,
more succinctly, ‘20 or 37 is an even number’.
As the use of the word ‘or’ in English would suggest,∗ when we take the propositions p
and q, and form their disjunction, p ∨ q, we would want to find that if at least one of p
or q are true, then p ∨ q is true whereas if p and q are both false, p ∨ q is false. This idea
is succinctly captured by the truth table for disjunction which is given in Table 1.5.

p q p∨q
T T T
T F T
F T T
F F F

Table 1.5: The truth table for disjunction.

This truth table tells us, quite simply, that when at least one of p or q are true, p ∨ q is
true (if we look at the second to fourth rows) and if p and q are both false, p ∨ q is false
∗
In Mathematics, when we use the word ‘or’ in ‘p or q’ we will always mean ‘either p or q or both’
but, in English, it is sometimes used to specify mutually exclusive alternatives where it effectively means
‘either p or q but not both’. An example of the former, the so-called ‘inclusive or’, is ‘I will wear black
socks or a white hat’ since I can wear one, or both, of these options whereas an example of the latter,
the so-called ‘exclusive or’, is ‘I will wear a black or white hat’ since I can only wear one, but not both,
of these options. We will see the advantage of using ‘or’ in this way when we come to look at logical
equivalence in Unit 2.

12
 1. Logic, proof and sets I — Introducing logic and proof

(if we look at the fifth row). So, returning to our example where p is the proposition ‘20
is an even number’ and q is the proposition ‘37 is an even number’, we would expect
that p ∨ q, i.e. the proposition ‘20 or 37 is an even number’, is true because we expect
that p is true (even though we expect that q is false).

Activity 1.4 What does the truth table for disjunction tell us about p and q when
p ∨ q is true and when p ∨ q is false?

Implication

This logical operation takes two propositions, p and q, and can give us the implication
denoted by p ⇒ q, which we can think of as ‘if p, then q’ (or ‘p implies q’) in English.
So, for instance, if p is the proposition ‘20 is an even number’ and q is the proposition
‘24 is an even number’, then p ⇒ q would be the proposition ‘if 20 is an even number,
then 24 is an even number’.
As the use of the words ‘if . . . , then . . . ’ in English may suggest, when we take the
propositions p and q, and form the implication, p ⇒ q, we would want to find that if p
is true and q is true, then p ⇒ q is true and that if p is true and q is false, then p ⇒ q is
false. But, what if p is false? In this case, perhaps, English usage is not much use and,
for reasons that should become clear, we will take p ⇒ q to be true in these situations.†
This idea is succinctly captured by the truth table for implication which is given in
Table 1.6.

p q p⇒q
T T T
T F F
F T T
F F T

Table 1.6: The truth table for implication.

This truth table tells us, quite simply, that when if p and q are both true, p ⇒ q is true
(if we look at the second row), if p is true and q is false, p ⇒ q is false (if we look at the
third row) and, finally, if p is false, then regardless of whether q is true or false, p ⇒ q is
true (if we look at the fourth and fifth rows). So, returning to our example where p is
†
In Mathematics, the words ‘if . . . , then . . . ’ have the meaning given here even though, in English,
they can be used in other ways. To see why our interpretation of the words makes sense, consider the
following example.
Suppose I say, ‘If it rains, then I’ll wear a raincoat’ and suppose that this is a true statement. We can
then see that, when it rains, I can certainly conclude that I will wear a raincoat (see the second row of
the truth table). But, when it doesn’t rain, we can’t conclude anything — I may or I may not wear a
raincoat — and whether I do or don’t doesn’t affect the truth of the statement I made (see the fourth
and fifth row of the truth table). Let’s be clear: an ‘if . . . , then . . . ’ statement only tells us about what
follows if something in particular happens.
Furthermore, what happens if it rains and I don’t wear a raincoat? In this case, my statement must
be false (see the third row of the truth table). And, as this is the only way it can be false, we again see
that it makes sense to say that the statement is true even when it doesn’t rain!

13
1. Logic, proof and sets I — Introducing logic and proof

the proposition ‘20 is an even number’ and q is the proposition ‘24 is an even number’,
we would expect that p ⇒ q, i.e. the proposition ‘if 20 is an even number, then 24 is an
even number’, is true because we expect that both p and q are true.

Activity 1.5 What does the truth table for implication tell us about p and q when
p ⇒ q is true and when p ⇒ q is false?

Biconditionals

This logical operation takes two propositions, p and q, and can give us the biconditional
denoted by p ⇔ q, which we can think of as ‘p if and only if q’ in English. However, this
phrase is rarely encountered outside of Mathematical contexts and so it may be worth
explaining how it arises.
Suppose that we have the implication p =⇒ q which, as we saw above, can be
interpreted as saying ‘if p, then q’. But, two other ways of capturing this implication in
English are to say ‘q if p’ (as, given the truth of the implication, we expect q to be true
if p is) or ‘p only if q’ (as, given the truth of the implication, p can only be true if q is
true as well). Now, if we think about this, we may be in a situation where the
implications p ⇒ q and q ⇒ p are both true, but

q ⇒ p can be interpreted as ‘p if q’, and

p ⇒ q can be interpreted as ‘p only if q’.
So, if both of these implications are true, we are in a situation in which ‘p if q and p only
if q’ is true, i.e. we have the truth of ‘p if and only if q’. That is, when we assert that
‘p if and only if q’ or, in symbols p ⇔ q,
we are really asserting that
(if p, then q) and (if q, then p) or, in symbols (p ⇒ q) ∧ (q ⇒ p).
We will draw out this connection in more detail in the next section, but this
interpretation of the biconditional should be more than sufficient for us to figure out its
truth table which is given in Table 1.7.

p q p⇔q
T T T
T F F
F T F
F F T

Table 1.7: The truth table for a biconditional.

To see why this works consider that, if the propositions p and q are both true or both
false, then the implications p ⇒ q and q ⇒ p are both true and so the biconditional, i.e.
the conjunction of these two implications, must be true as well (this is what we see in
the second and fifth rows). However, if

14
 1. Logic, proof and sets I — Introducing logic and proof

p is true and q is false, then p ⇒ q is false whereas q ⇒ p is true, and so the

biconditional, i.e. the conjunction of these two implications, must be false as well
(this is what we see in the third row).

p is false and q is true, then p ⇒ q is true whereas q ⇒ p is false, and so the

biconditional, i.e. the conjunction of these two implications, must be false as well
(this is what we see in the fourth row).
So we see that biconditionals like p ⇔ q are true precisely when p and q are either both
true or both false whereas they are false when one of p or q is true and the other is false.

1.3 Some simple proofs

We started this unit with six propositions that involved the idea of an even number
and, using our knowledge of mathematics, we asserted that five of them were true and
one of them was false. We now want to see how we can prove the ones that are true and
disprove the one that is false. In particular, we will need to know what an even number
is so that we can prove that simple propositions like

20 is an even number,

are true and we will need to use our understanding of the logical operations to then
prove that compound propositions like

20 and 40 are even numbers,

are true.
To see what an even number actually is, we need a definition. You may have one in
mind, maybe something like

Given a whole number, m = 0, we say that m is even if it is a multiple of 2.

where we understand a whole number to be something like 0, 1, 2, 3, etc. This is
absolutely correct, but a better definition, i.e. one that doesn’t require us to think
about ‘multiples’, is

Given a whole number, m = 0, we say that m is even if there is a whole

number k such that m = 2k.
Of course, these two definitions mean the same thing and you should spend a little time
convincing yourself that this is the case. Let’s now use this to prove or disprove each of
our six statements.

20 is an even number

We suspect that this proposition is true and so to prove it we simply note that:

As 20 = 2 × 10, there is a whole number k (obviously, in this case, k is 10) such

that 20 = 2k and so, using our definition, we see that 20 is an even number.

15
1. Logic, proof and sets I — Introducing logic and proof

20 is not an even number

We suspect that this proposition is false and so to disprove it we could note that:

Having shown that 20 is an even number, we can be sure that the proposition
‘20 is not an even number’ is not the case.
Of course, here we have appealed to the truth table for negation: as p is true, ¬p is false.

20 and 40 are even numbers

We suspect that this proposition is true and so to prove it we simply note that:

Firstly, we know that 20 is an even number from above and, secondly, as

40 = 2 × 20, there is a whole number k (obviously, in this case, k is 20) such
that 40 = 2k and so, using our definition, we see that 40 is an even number as
well. Consequently, 20 and 40 are even numbers.
Of course, here we have appealed to the truth table for conjunction: as p and q are true,
so is p ∧ q.

20 or 37 is an even number

We suspect that this proposition is true and to prove it we simply note that:

Having shown that 20 is an even number, we see that 20 or 37 is an even

number.
Of course, here we have appealed to the truth table for disjunction: as p is true, so is
p ∨ q regardless of whether q is true or false.
However, even though it is irrelevant to the proof of the proposition we are considering,
we suspect that the proposition 37 is an even number is false and it is instructive to see
how we could go about disproving it. To do this, we could argue as follows.

Suppose that k is any whole number and consider that if k ≤ 18, then 2k ≤ 36
whereas if k ≥ 19, then 2k ≥ 38. So, if we consider any whole number k, we see
that because we either have 2k ≤ 36 (when k ≤ 18) or we have 2k ≥ 38 (when
k ≥ 19), we never find that 2k = 37. That is, there is no whole number k such
that 37 = 2k and so, using our definition, we see that 37 is not an even number.
Notice, in particular, that disproving the proposition ‘37 is an even number’ is far
harder than proving the proposition ‘20 is an even number’. Indeed, we may not be in a
position to fully appreciate how this particular argument works until we get to the end
of Unit 3.

If 20 is an even number, then 24 is an even number

We suspect that this proposition is true and so to prove it we simply note that:

Firstly, we know that 20 is an even number from above and, secondly, as

24 = 2 × 12, there is a whole number k (obviously, in this case, k is 12) such

16
 1. Logic, proof and sets I — Introducing logic and proof

that 24 = 2k and so, using our definition, we see that 24 is an even number as
well. Consequently, if 20 is an even number, then 24 is an even number.
Of course, here we have appealed to the truth table for implication: as p and q are true,
so is p ⇒ q. However, as we will see in Unit 3, proving implications is not usually this
straightforward.

If 7 is an even number, then 13 is an even number

We should now suspect that this proposition is true because we suspect that ‘7 is an
even number’ is false and, using the truth table for implication, we know that p ⇒ q is
true when p is false (regardless of whether q is true or false). And so, to prove this
implication, we need to disprove the proposition ‘7 is an even number’, and we can do
this by noting that:

Suppose that k is any whole number and consider that if k ≤ 3, then 2k ≤ 6

whereas if k ≥ 4, then 2k ≥ 8. So, if we consider any whole number k, we see
that because we either have 2k ≤ 6 (when k ≤ 3) or we have 2k ≥ 8 (when
k ≥ 4), we never find that 2k = 7. That is, there is no whole number k such
that 7 = 2k and so, using our definition, 7 is not an even number.
Of course, in this case, we suspect that the proposition ‘13 is an even number’ is false as
well but it doesn’t matter. But, if you want to have a go at showing this, you can try
the next activity.

Activity 1.6 Disprove the proposition ‘13 is an even number’.

When p is false, we sometimes say that the implication p ⇒ q is trivially true because it
doesn’t tell us anything useful. In other words, since p is never the case, the truth of the
implication tells us nothing about q and, as we saw in Activity 1.5, we know from the
truth table for p ⇒ q that q can be either true or false in such cases.

A quick summary of what we have seen so far

There is a very real sense in which all of the propositions above, with the possible
exception of the first two, are not that interesting. In particular, you are probably
thinking that a ‘proof’ involves establishing the truth of mathematical statements like

If n is even, then n2 is even.

and, in a sense, you’re right! But, before we can prove things which look like this, we
need to do a little more work and, in Unit 3, we’ll see how to tackle this kind of thing.
However, having said that, we have made significant progress! We have seen that we can
only prove (or disprove) a proposition if we understand what the words in it mean.
Some of these words get their meaning from a definition (What is a ‘whole number’ ?
When do we say that a whole number is ‘even’ ?) and other words get their meaning
from logic (What does it mean to say ‘not’ ? ‘and’ ? ‘or’ ? ‘if . . . , then . . . ’ ?) as captured
by our truth tables. We have also seen that a proof (or a disproof) is written in English
(i.e. it is not just a long list of mathematical symbols) and doesn’t usually make explicit

17
1. Logic, proof and sets I — Introducing logic and proof

reference to truth or falsity. To prove a proposition is to show that it is true and to

disprove a proposition is to show that it is false. Technically, all references to what is
true or false and any reference to truth tables should be in the background informing us
about what we can or can’t say based on whatever we have said before.
This may sound a little strange, but it will become clearer. We have to draw a line
between mathematics, which involves mathematical statements and their proofs, and
logic, which ensures that we understand what is being said well enough to ensure that
what we say is true.

Learning outcomes
At the end of this unit, you should be able to:

identify that certain simple mathematical statements are propositions;

interpret compound propositions in terms of logical operations;

understand what these logical operations mean using truth tables;

understand the importance of definitions;

understand what it means to prove (or disprove) a proposition;

prove or disprove very simple propositions.

Exercises
Exercise 1.1
Suppose that p is the proposition ‘10 is an even number’, q is the proposition ‘12 is an
even number’ and r is the proposition ‘15 is an even number’. Write the following
propositions in symbols.

(i) 10 and 12 are even numbers.

(ii) 12 or 15 are even numbers.

(iii) If 12 is an even number, then 15 isn’t.

(iv) If 15 is an even number, then 12 isn’t.

(That is, rewrite them using our logical operations and the letters p, q and r.)

Exercise 1.2
Following on from Exercise 1.1, say whether you think each of the propositions (i) to
(iv) is true or false.
Prove or disprove those propositions as appropriate.

18
 1. Logic, proof and sets I — Introducing logic and proof

Exercise 1.3
Assuming that a whole number is something like 1, 2, 3, etc. as usual, we can capture
the idea that one number is divisible by another using the following definition.

Given two non-zero whole numbers, m and n, we say that m is divisible by n if

there is a whole number k such that m = nk.
Decide whether each of the following propositions is true or false.

(i) 20 is divisible by 4.

(ii) 20 is not divisible by 4.

(iii) 20 and 40 are divisible by 4.

(iv) 20 or 37 is divisible by 4.

(v) If 37 is divisible by 5, then 74 is divisible by 5.

Using the definition above, prove or disprove each of these propositions as appropriate.

Exercise 1.4
[Slightly harder!] Given that p and q are propositions, let’s introduce a new logical
operation, denoted by ‘↑’, which is defined by saying that the proposition p ↑ q is false
when p and q are both true but that it is true otherwise.
Write down the truth table for p ↑ q.
Can you write down, using our usual logical operations and the symbols p and q, a
proposition that would have the same truth table as p ↑ q?

Exercise 1.5
[Just for fun!] Suppose that we had three propositions p, q and r. If we wanted to
create the truth table for the proposition (p ∧ q) ⇒ r, we would start with three
columns to allow for the fact that each of p, q and r could be either true or false. How
many rows would we need to capture all of these possibilities?
Draw these three columns and fill in each of the possibilities (preferably in a sensible
order) so that you have enough rows.
Add another column for the proposition (p ∧ q) ⇒ r and fill this in using what you
know about the truth tables for ∧ and ⇒.

19
2. Logic, proof and sets II — Logical equivalence

Unit 2: Logic, proof and sets II

Logical equivalence

Overview

In this unit, we introduce the idea of logical equivalence. This is, essentially, the idea
that certain propositions can be written in different ways but still mean the same thing.
Indeed, although we just explore the idea and see some examples of how it works in this
unit, in Units 3 and 4, we will see that an awareness of certain logical equivalences can
lead us to simpler proofs.

Aims

The aims of this unit are as follows.

To introduce logical equivalence.

To see how to show that two propositions are logically equivalent.

To introduce some of the most useful logical equivalences.

Specific learning outcomes can be found near the end of this unit.

2.1 Logical equivalence

There is a very important sense in which, at least logically, propositions that ‘look
different’ to one another can actually ‘say the same thing’. More precisely, they ‘say the
same thing’ in the sense that if either one of these ‘different looking propositions’ is
true, then so is the other, whereas if either one of them is false, then so is the other.
When this happens, we say that the two propositions are logically equivalent. To see a
very simple example of this, consider the following.

Example 2.1 Suppose that p is a proposition. Show that ¬¬p is logically

equivalent to p.∗

Here, we start by noting that ¬¬p is the ‘negation of the negation of p’ or ‘not not p’
in English. It is, perhaps, not surprising that p and ¬¬p are logically equivalent (or
‘say the same thing’) because, in English, this is an example of a ‘double negative’.
But, in the context of logic, we need to be a bit more precise when establishing
logical equivalence and we can do this as follows.
To show that ¬¬p is logically equivalent to p, we need to show that whenever p is
true so is ¬¬p and whenever p is false so is ¬¬p. This can be done by using a truth

20
 2. Logic, proof and sets II — Logical equivalence

table and, to see how to do this, let’s construct the truth table step by step and then
we can draw our conclusions.
Firstly, we note that p can be true or false which means that the first column of our
truth table should capture these two possibilities as follows.

p ?
T ?
F ?

Secondly, to find out about the truth or falsity of ¬¬p when either of these two
possibilities occurs, it is convenient to think about the truth or falsity of the
‘intermediate’ proposition ¬p. So, using what we saw in Table 1.3, the second
column of our truth table can capture what this does as follows.

p ¬p ?
T F ?
F T ?

Thirdly, we can now look at the truth or falsity of ¬¬p by seeing what happens
when we negate ¬p. So, using what we saw in Table 1.3 again, but applying this to
what is in the the second column of our truth table, we can fill in the third column
of our truth table (i.e. the one for ¬¬p) as follows.

p ¬p ¬¬p
T F T
F T F

We can now see how the truth or falsity of p affects the truth or falsity of ¬¬p and,
if we write the relevant entries in the truth table in bold, to get

p ¬p ¬¬p
T F T
F T F

Thus we see that whenever p is true so is ¬¬p (if we look at the second row) and
whenever p is false so is ¬¬p (if we look at the third row). That is, p and ¬¬p are
logically equivalent.

Before we go on and make this more precise, let’s consider a slightly more complicated
example.

∗
This establishes that, logically, two negations can be ‘cancelled’ !

21
2. Logic, proof and sets II — Logical equivalence

Example 2.2 Suppose that p and q are propositions. Show that p ∧ q is logically
equivalent to q ∧ p.†

Here, we start by noting that p ∧ q is ‘p and q’ in English whereas q ∧ p is ‘q and p’.

It is, perhaps, not surprising that p ∧ q and q ∧ p are logically equivalent (or ‘say the
same thing’) because, in English, the ‘order’ in which we conjoin two clauses with an
‘and’ doesn’t matter. But, once again, in the context of logic, we need to be a bit
more precise when establishing logical equivalence and we can do this as follows.
To show that p ∧ q is logically equivalent to q ∧ p, we need to show that whenever
p ∧ q is true so is q ∧ p and whenever p ∧ q is false so is q ∧ p. This can be done by
using a truth table and, to see how to do this, let’s construct the truth table step by
step and then we can draw our conclusions.
Firstly, we note that both p and q can, individually, be either true or false which
means that we need two columns in our truth table to capture the four possibilities
as follows.

p q ?
T T ?
T F ?
F T ?
F F ?

Secondly, to find out about the truth or falsity of p ∧ q when any of these four
possibilities occurs, we can use what we saw in Table 1.4 so that the third column of
our truth table can capture what this does as follows.

p q p∧q ?
T T T ?
T F F ?
F T F ?
F F F ?

Thirdly, we can now look at the truth or falsity of q ∧ p by seeing what happens
when we have the four original possibilities. So, using what we saw in Table 1.4
again, and using what we have in the first two columns again, we can fill in the
fourth column of our truth table (i.e. the one for q ∧ p) as follows.

p q p∧q q∧p
T T T T
T F F F
F T F F
F F F F

We can now see how the the truth or falsity of both p ∧ q and q ∧ p are affected by the
four possibilities we get when we consider the truth or falsity of p and q individually.
Indeed, again writing the relevant entries in the truth table in bold, we get

22
 2. Logic, proof and sets II — Logical equivalence

p q p∧q q∧p
T T T T
T F F F
F T F F
F F F F

Thus we see that whenever p ∧ q is true so is q ∧ p (if we look at the second row) and
whenever p ∧ q is false so is q ∧ p (if we look at the third to fifth rows). That is, p ∧ q
and q ∧ p are logically equivalent.

Activity 2.1 Suppose that p and q are propositions. Show that p ∨ q is logically
equivalent to q ∨ p.‡

But, as you should expect, not all propositions are logically equivalent as, generally
speaking, propositions that ‘look different’ are indeed ‘different’ as they do not ‘say the
same thing’. However, one example of two propositions that are not logically equivalent
which you may, perhaps, find surprising is considered in the next example.

Example 2.3 Suppose that p and q are propositions. Show that p ⇒ q and q ⇒ p
are not logically equivalent.§

Here, we start by noting that p ⇒ q is ‘if p, then q’ in English whereas q ⇒ p is ‘if q,

then p’. It is, perhaps, not surprising that p ⇒ q and q ⇒ p are not logically
equivalent (or ‘say the same thing’) because, in English, the ‘order’ in which we
conjoin two clauses with an ‘if . . . , then . . . ’ does matter.¶
To do this, we note that p and q can, individually, be either true or false and,
following the method in Examples 2.1 and 2.2, we construct the truth table for
p ⇒ q and q ⇒ p using Table 1.6 to fill in the appropriate columns. This gives us

p q p⇒q q⇒p
T T T T
T F F T
F T T F
F F T T

where, as before, we have written the relevant entries in bold. We can then see that
p ⇒ q and q ⇒ p are not logically equivalent because, if we look at the third and
fourth rows of the truth table, there are cases where one is true but the other is false.
†
This establishes that, logically, the order in which we take the conjunction of two propositions
doesn’t matter!
‡
This establishes that, logically, the order in which we take the disjunction of two propositions doesn’t
matter!

23
2. Logic, proof and sets II — Logical equivalence

Indeed, in order to distinguish these two implications, we will often refer to q ⇒ p as

the converse of p ⇒ q.

2.2 Some important results involving logical

equivalence
Now that we have established what it means to say that two propositions are logically
equivalent, we can establish some important results that involve it. We start by seeing
how we can also define logical equivalence in terms of biconditionals. We then introduce
some important logical equivalences which establish the logical relationships that hold
between a biconditional and its component implications, between an implication and its
contrapositive, and between a conjunction and a disjunction.

2.2.1 Biconditionals and logical equivalence

Let’s suppose that we have two propositions, let’s call them r and s, that are made up
from the propositions p and q as well as various logical operations. For example, r and s
could be p and ¬¬p, or p ∧ q and q ∧ p, or p ⇒ q and q ⇒ p if we were to look at the
last three examples above.
Now, as we have seen, the logical equivalence of two propositions like r and s asserts
that, when we look at all the possibilities we can get from the truth or falsity of p and
q, the propositions r and s are either both true or both false and, as we saw above, this
is exactly what we need to make the biconditional r ⇔ s true. That is, we can assert
that r and s are logically equivalent if the biconditional r ⇔ s is always true where,
here, ‘always true’ means that it is true for every possibility we can get from the truth
or falsity of p and q.
This is a useful insight for two reasons. Firstly, it gives us a way of expressing logical
equivalence in symbols, i.e. to say that the propositions r and s are logically equivalent
is to say that r ⇔ s is true and vice versa. Secondly, it gives us another way of
establishing logical equivalence, i.e. we just need to construct a truth table for r ⇔ s
(using all the possibilities we can get from the truth or falsity of p and q) and see that it
is, as we want, always true.
So, as we established that p and ¬¬p are logically equivalent in Example 2.1, we should
expect that the biconditional
p ⇔ (¬¬p),
is always true. Indeed, we can see that this is the case if we look at its truth table
§
This establishes that, logically, the order in which we take the implication of two propositions does
matter!
¶
For instance, suppose that p is the proposition ‘it is raining’ and q is the proposition ‘I wear a
raincoat’, we then see that the proposition
p ⇒ q is ‘If it is raining, then I wear a raincoat’ and we would expect this to be true. Generally
speaking, the presence of rain encourages us to wear a raincoat.
q ⇒ p is ‘If I wear a raincoat, then it is raining’ and we would expect this to be false. Sometimes, we
wear a raincoat because it is cold or we anticipate rain later on — it need not actually be raining!
That is, we see that these two implications are, in fact, saying two completely different things.

24
 2. Logic, proof and sets II — Logical equivalence

p ¬p ¬¬p p ⇔ (¬¬p)
T F T T
F T F T

In particular, observe that when p is true, so is ¬¬p, and so p ⇔ (¬¬p) is true (if we
look at the second row) and when p is false, so is ¬¬p, and so p ⇔ (¬¬p) is true (if we
look at the third row). That is, regardless of the truth or falsity of p itself, p ⇔ (¬¬p) is
always true. It is the truth of this biconditional in all possible cases that captures the
fact that p and ¬¬p are logically equivalent.
Indeed, in a slightly more complicated setting, as we established that p ∧ q and q ∧ p are
logically equivalent in Example 2.2, we should expect that the biconditional

(p ∧ q) ⇔ (q ∧ p),

is always true. Indeed, we can see that this is the case if we look at its truth table

p q p∧q q∧p (p ∧ q) ⇔ (q ∧ p)
T T T T T
T F F F T
F T F F T
F F F F T

In particular, observe that regardless of whether p or q are individually true or false,

(p ∧ q) ⇔ (q ∧ p) is always true because p ∧ q and q ∧ p are both true (if we look at the
second row) or p ∧ q and q ∧ p are both false (if we look at the third to fifth rows). That
is, regardless of the truth or falsity of p and q individually, (p ∧ q) ⇔ (q ∧ p) is always
true. It is the truth of this biconditional in all possible cases that captures the fact that
p ∧ q and q ∧ p are logically equivalent.

Activity 2.2 Following on from Activity 2.1 where we established that p ∨ q is

logically equivalent to q ∨ p, use a truth table to show that the biconditional
(p ∨ q) ⇔ (q ∨ p) is always true.

However, as we established in Example 2.3, the proposition p ⇒ q and its converse

q ⇒ p are not logically equivalent, and so we should expect that the biconditional

(p ⇒ q) ⇔ (q ⇒ p),

is not always true. Indeed, we can see that this is the case if we look at its truth table

p q p⇒q q⇒p (p ⇒ q) ⇔ (q ⇒ p)
T T T T T
T F F T F
F T T F F
F F T T T

25
2. Logic, proof and sets II — Logical equivalence

In particular, when one of p or q is true and the other is false, (p ⇒ q) ⇔ (q ⇒ p) is

false (if we look at the third and fourth rows) and so this biconditional is not always
true. That is, we can not guarantee the truth of (p ⇒ q) ⇔ (q ⇒ p) regardless of the
truth or falsity of p and q individually. It is our failure to assert the truth of this
biconditional in all possible cases that captures the fact that p ⇒ q and q ⇒ p are not
logically equivalent.
So, to summarise, we can see that if two propositions p and q are logically equivalent,
then the proposition p ⇔ q is always true and vice versa.

2.2.2 Biconditionals and implications

When we introduced the biconditional in the previous section, we observed that the
assertion
‘p if and only if q’ or, in symbols p ⇔ q,
is really just the assertion that
(if p, then q) and (if q, then p) or, in symbols (p ⇒ q) ∧ (q ⇒ p).
But, we now know that this observation, i.e. that these two assertions ‘say the same
thing’, is just a very loose way of saying that they are logically equivalent. So, just to
show that this is indeed the case, we can use the following truth table to show that they
are logically equivalent.

p q p⇒q q⇒p (p ⇒ q) ∧ (q ⇒ p) p⇔q

T T T T T T
T F F T F F
F T T F F F
F F T T T T

In particular, looking at the entries in bold, observe that when we look at all the
possible ways of taking p and q to be true or false, we find that the propositions
(p ⇒ q) ∧ (q ⇒ p) and p ⇔ q,
are either both true or both false which is exactly what we need to establish their
logical equivalence.

Activity 2.3 Make sure you understand how this truth table was constructed. You
can, perhaps, do this by filling in the details like we did in Examples 2.1 and 2.2.

Activity 2.4 Alternatively, we can show that the propositions

(p ⇒ q) ∧ (q ⇒ p) and p ⇔ q,

are logically equivalent if the biconditional

[(p ⇒ q) ∧ (q ⇒ p)] ⇔ (p ⇔ q),

is always true. Use a truth table to show that this is the case.

26
 2. Logic, proof and sets II — Logical equivalence

2.2.3 Implications and contrapositives

Recall that, given two propositions p and q, we will often find that the implication
p ⇒ q is true whereas its converse, q ⇒ p is not. For example, the implication

if n = 3, then n2 = 9,

is clearly true but its converse

if n2 = 9, then n = 3,

is false because n need not be 3, it could be −3!

However, there is another way of writing the implication p ⇒ q, called its contrapositive,
which is true whenever the implication is. That is, the implication p ⇒ q is logically
equivalent to its contrapositive which is the proposition

(¬q) ⇒ (¬p).

So, in our example, we saw that the implication

if n = 3, then n2 = 9,

is true, and its contrapositive, i.e. the proposition

if n2 = 9, then n = 3,

is also true since, if n2 = 9, we can be sure that n = 3.

If we have two propositions p and q, then (¬q) ⇒ (¬p) is called the contrapositive of the
implication p ⇒ q. Unlike the converse, q ⇒ p, a contrapositive is logically equivalent to
its implication as the truth table below shows.
Of course, we should establish that an implication, p ⇒ q, is logically equivalent to its
contrapositive, (¬q) ⇒ (¬p), and we can do this with the following truth table.

p q p⇒q ¬q ¬p (¬q) ⇒ (¬p)

T T T F F T
T F F T F F
F T T F T T
F F T T T T

In particular, looking at the entries in bold, observe that when we look at all the
possible ways of taking p and q to be true or false, we find that the propositions

p⇒q and (¬q) ⇒ (¬p),

are either both true or both false which is exactly what we need to establish their
logical equivalence.

27
2. Logic, proof and sets II — Logical equivalence

Activity 2.5 Make sure you understand how this truth table was constructed. You
can, perhaps, do this by filling in the details like we did in Examples 2.1 and 2.2.

Activity 2.6 Alternatively, we can show that the propositions

p⇒q and (¬q) ⇒ (¬p),

are logically equivalent if the biconditional

(p ⇒ q) ⇔ [(¬q) ⇒ (¬p)],

is always true. Use a truth table to show that this is the case.

2.2.4 Conjunctions and disjunctions

The last logical equivalence that we want to investigate involves the relationship
between conjunctions and disjunctions. In particular, we can show that the propositions

p∨q and ¬[(¬p) ∧ (¬q)],

are logically equivalent by using the following truth table.

p q p∨q ¬p ¬q (¬p) ∧ (¬q) ¬[(¬p) ∧ (¬q)]

T T T F F F T
T F T F T F T
F T T T F F T
F F F T T T F

In particular, looking at the entries in bold, observe that when we look at all the
possible ways of taking p and q to be true or false, we find that the two propositions are
either both true or both false which is exactly what we need to establish their logical
equivalence.

Activity 2.7 Make sure you understand how this truth table was constructed. You
can, perhaps, do this by filling in the details like we did in Examples 2.1 and 2.2.

Activity 2.8 Alternatively, we can show that the propositions

p∨q and ¬[(¬p) ∧ (¬q)],

are logically equivalent if the biconditional

(p ∨ q) ⇔ ¬[(¬p) ∧ (¬q)],

is always true. Use a truth table to show that this is the case.

28
 2. Logic, proof and sets II — Logical equivalence

Indeed, because of the logical equivalence of p and ¬(¬p) that we established earlier, this
particular logical equivalence can also be expressed in terms of the logical equivalence of

¬(p ∨ q) and (¬p) ∧ (¬q),

or the logical equivalence of

(¬p) ∨ (¬q) and ¬(p ∧ q),

or, indeed, the logical equivalence of

¬[(¬p) ∨ (¬q)] and p ∧ q,

all of which you’ll have an opportunity to establish in the exercises. But, notice that
these four versions of this logical equivalence allow us to do certain useful things. The
first (and fourth) versions allow us to see that any disjunction (or conjunction) is
logically equivalent to a proposition which involves negation and conjunction (or
disjunction). That is, logically, we don’t actually need both of them even though,
mathematically, it is simpler if we can use both. Also, the second (and third) versions
allow us to see how the negation of a disjunction (or conjunction) is logically equivalent
to the conjunction (or disjunction) of the negation of the component propositions. That
is, we can see how negation affects disjunctions and conjunctions in an almost ‘algebraic’
way, especially if we think about how arithmetic operations work with brackets!
We won’t look at this ‘algebraic’ interpretation of our logical operations any further in
this course, but you can have a bit of fun looking at the logical ‘redundancy’ of some of
our logical operations in the exercises. However, bear these logical equivalences in mind
as they will be useful in Units 3 and 4.

Learning outcomes
At the end of this unit, you should be able to:

define logical equivalence;

show that two propositions are logically equivalent;

understand the difference between an implication, its converse and its

contrapositive;

recall certain important logical equivalences.

29
2. Logic, proof and sets II — Logical equivalence

Exercises
Exercise 2.1
Suppose that p and q are propositions. Fill in the gaps in the following truth table.

p q ¬q p ∨ (¬q) ¬p (¬p) ∧ q ¬[(¬p) ∧ q]

T T F
T T F
F F
F T T

What does this truth table tell you about the propositions p ∨ (¬q) and ¬[(¬p) ∧ q]?

Exercise 2.2
Suppose that p and q are propositions. Determine whether the following pairs of
propositions are logically equivalent or not.

(i) ¬[¬(¬p)] and ¬p.

(ii) ¬(p ⇒ q) and p ∧ (¬q).

(iii) ¬(p ∨ q) and (¬p) ∧ q.

Exercise 2.3
Suppose that p and q are propositions. Show that the following pairs of propositions are
logically equivalent.

(i) ¬(p ∨ q) and (¬p) ∧ (¬q).

(ii) ¬(p ∧ q) and (negp) ∨ (¬q).

(iii) p ∧ q and ¬[(¬p) ∨ (¬q)].

Exercise 2.4
[Just for fun!] Suppose that we have two propositions p and q. If we were to form all of
the possible propositions that involve p and q using our logical connectives, explain why
only 16 of them are logically distinct. (By this we mean that every one of these possible
propositions is logically equivalent to one of these 16 logically distinct propositions.)

Find 16 logically distinct propositions.

Exercise 2.5
[Just for fun!] We have introduced five logical operations (i.e. ¬, ∧, ∨, ⇒ and ⇔) but,
despite the convenience of having these, it is not necessary to have them all. For
instance, we have seen that we do not need both of the logical operations ‘∧’ and ‘∨’
because any proposition involving ‘∨’ (say) can be rewritten as a logically equivalent

30
 2. Logic, proof and sets II — Logical equivalence

proposition that involved ‘∧’ and ‘¬’. In fact, as it happens, we could have got by with
just ‘∧’ and ‘¬’ and, following on from Exercise 2.4, we can start to see why.
Suppose that we have two propositions p and q. Show that every one of the 16 logically
distinct propositions that we found in Exercise 2.4 is logically equivalent to a
proposition that only uses the logical operations ‘¬’ and ‘∧’.

Exercise 2.6
[Just for fun!] In fact, following on from Exercise 2.5, we can actually get away with
just one logical operation. But, as it happens, none of the five logical operations that we
have introduced in this course can play this role. However, we can introduce (just for
this exercise) a new logical operation that can do this and start to see why it works.
Suppose that we have two propositions p and q. As in Exercise 1.4, we can define a
logical operation, denoted by ↑, using the following truth table.

p q p↑q
T T F
T F T
F T T
F F T

Show that every one of the 16 logically distinct propositions that we found in
Exercise 2.4 is logically equivalent to a proposition that only uses this logical operation.

31