Negation and Implication

Statements with 'if'

We now turn to look at the part of the specification that involves the word "if".

Language and implication

Before we start to look at how we might understand the formal ideas behind statements that involve "if" in various ways, we shall step sideways to examine how we deal with "if" in everyday English as this will help us when we come to look at the way "if" statements are unpacked in logic.

Here is a collection of statements:

- **(i)** If it is Sunday, then the church bells ring

ii. The church bells ring if it is Sunday iii. The church bells ring only if it is Sunday iv. It is Sunday if the church bells ring - (v) It is Sunday only if the church bells ring vi. The church bells ring if and only if it is Sunday

Before we start to look at each statement in turn, take a moment to think through what you would understand by each one. Ask yourself what you would know if the statement is true and it is Sunday; ask yourself what you would know if the statement is true and the bells ring; ask yourself what you can claim about the bells if the statement is true and it is not Sunday; and ask yourself what you can claim about the day if the statement is true and the bells don't ring.

Let's start to look at each statement in turn to see if we can work out what it is telling us and what it is not telling us. In each case we shall assume the statement is true. We start with:

i. If it is Sunday, then the church bells ring

First, we ask what does it tell us if we know it is Sunday? It tells us that the church bells will ring. What, then does it tell us about the church bells if it is not Sunday? It tells us nothing; and it tells us nothing because it doesn't tell us about whether the church bells will ring on Wednesday or on Tuesday and so on.

What can we say if we know statement i is true and we hear the church bells? Can we say it must be Sunday? The answer is we cannot say it is Sunday. We cannot say it is Sunday as the bells might ring on Tuesday or Wednesday so hearing the bells ring is, according to statement i, not enough to tell us what the day is. Finally, what can we determine about the day if the bells do NOT ring? The answer is that we can tell it is NOT Sunday. We can tell it is not Sunday because, if it were Sunday then the bells definitely would ring.

We can summarise these findings as follows:

Statement: i. If it is Sunday, then the church bells ring

What we know	What we can conclude if i is true
It is Sunday	The bells ring
It is not Sunday	Nothing
The bells ring	Nothing
The bells do not ring	It is not Sunday

We can repeat this process for each of the other sentences. We shall summarise the results in a series of tables but take some time to study each one to check it matches any conclusions you have drawn. Some of the examples take some time to think through, particularly statement iii:

Statement: ii. The church bells ring if it is Sunday

What we know	What we can conclude if ii is true
It is Sunday	The bells ring
It is not Sunday	Nothing
The bells ring	Nothing
The bells do not ring	It is not Sunday

Here we note that the tables for each of statements i and ii are identical. The two statements are logically equivalent. That is to say, we take it that If it is Sunday, then the church bells ring says the very same thing as The church bells ring if it is Sunday. We shall say some more about this below when we start to look at "if" statements formally.

Statement: iii. The church bells ring only if it is Sunday

What we know	What we can conclude if iii is true
It is Sunday	Nothing
It is not Sunday	The church bells do not ring
The bells ring	It is Sunday
The bells do not ring	Nothing

Statement: iv. It is Sunday if the church bells ring

What we know	What we can conclude if iv is true
It is Sunday	Nothing
It is not Sunday	The church bells do not ring
The bells ring	It is Sunday
The bells do not ring	Nothing

Statement: v. It is Sunday only if the church bells ring

What we know	What we can conclude if v is true
It is Sunday	The church bells ring
It is not Sunday	Nothing
The bells ring	Nothing
The bells do not ring	It is not Sunday

Statement: vi. The church bells ring if and only if it is Sunday

What we know	What we can conclude if vi is true
It is Sunday	The church bells ring
It is not Sunday	The church bells do not ring
The bells ring	It is Sunday
The bells do not ring	It is not Sunday

We will return to these more formally in the following sections.

Combining statements: if A then B

Statements of the form: if A then B.

So far we have learnt how to use the formal terms not, and and or. In this section we shall look at statements of the form "if...then...". In the previous section we looked informally at this sort of statement when we examined if it is Sunday, then the church bells ring and other similar statements. However, we need to be very careful as there aren't definitive rules as to how to interpret these sorts of statements in everyday English, whereas in logic the meaning is precise.

For example, suppose that someone says the statement if it is raining then I will use my umbrella. In everyday English, this sentence would be understood with one of the following two meanings:

• If it is raining, I will use my umbrella, while if it is not raining, then I will not use my umbrella.
• If it is raining, I will use my umbrella, while it says nothing at all about what will happen if it is not raining.

When writing mathematical statements, though, we cannot allow such a significant ambiguity. That is why it is important to understand exactly what mathematicians mean when they say if A then B.

In logic, the statement if A then B means that if A is true, then B must also be true. But what if A is false? What can we say then? In everyday English, different meanings might be understood depending upon the exact sentence and context. But in mathematical logic, this statement has a precise meaning, namely:

• If A is true, then B is true.
• If A is false, then B may be either true or false.

Thus, the only way that if A then B can be false is if A is true and B is false.

Since if A then B is a statement, we can write a truth table for it:

A	B	if A then B
T	T	T
T	F	F
F	T	T
F	F	T

We can look at if A then B in a diagram by shading all the areas that make if A then B true:

if A then B

Now let us look again at statements i and ii above:

• i. If it is Sunday, then the church bells ring
• ii. The church bells ring if it is Sunday

We can see from the tables we drew up that both statements seem to mean the same thing in everyday English. Using this allows us to introduce another way of writing if...then..., statements just using if. We do this by defining if A then B to be logically equivalent to B if A.

Finally, here are some examples of mathematical statements of the form if A then B:

• if $x = 4$, then $x^2 = 8$. This is a false statement, because when $x = 4$ is true, $x^2 = 8$ is false.
• if $0 = 1$, then $2 + 2 = 5$. This is a true statement, since $0 = 1$ is false. It is true even though $2 + 2 = 5$ is false. This may seem a little strange at first sight!
• if $a$ and $b$ are odd integers, then $a + b$ is an even integer. This is a true statement, as whenever "$a$ and $b$ are odd integers" is true, so is "$a + b$ is an even integer".
• The standard proofs that $\sqrt{2}$ is irrational begin as follows: "if $\sqrt{2}$ is rational, then we can write $\sqrt{2} = a/b$, where $a$ and $b$ are integers with $b \neq 0$." This is a true statement, for the only way it could be false is if "$\sqrt{2}$ is rational" is true, but "we can write $\sqrt{2} = a/b$, where $a$ and $b$ are integers with $b \neq 0$" is false.

Exercise E

1. Notice that the truth table for if A then B has three Trues and one False in the final column. Can you guess how if A then B might be written in terms of some or all of and, or, and not?
2. Once you have written out your guesses for if A then B using and, or and not, can you justify that they have the same truth table as if A then B?
3. Can you justify your answer using diagrams?
4. What can you say about the truth of:
   • if A then (A or B)
   • if A then (A and B)

Equivalent statement for if A then B using not, or, and and

Understand and be able to use mathematical logic in simple situations.

In the exercise above [Exercise E] we asked you to work out if you could express if A then B in an equivalent form using the logical terms not, or and and. In this section we shall explore this a little further as it will be useful for us later. We will take two approaches: first, using truth tables; and, second, using "Venn diagrams".

Let us start by recalling the truth table for if A then B:

A	B	if A then B
T	T	T
T	F	F
F	T	T
F	F	T

The final column in this table is similar to the final column of an or table. This suggests that if A then B is equivalent to some statement involving or, but the difficulty is to find the correct or statement using statement A and statement B. We can get a clue from looking at the row in the table where if A then B is false: the only situation where an or statement can be false is when both the statements that make the or statement are false. Looking at the row in the table where if A then B is false, we can see that A is true and B is false so if we could replace the T under A with an F in this row, we would have the correct line in an or table. The way to achieve this is to replace A by not A. This all suggests that if A then B is equivalent to (not A) or B. Let us construct the truth table for not A or B [recall that not only ever applies to what immediately follows it, so instead of writing (not A) or B we can write not A or B as there is no ambiguity] and see if it gives us the same table as for if A then B:

A	B	not A	not A or B
T	T	F	T
T	F	F	F
F	T	T	T
F	F	T	T

We can see that the two tables do give the same results, so we have shown that if A then B is equivalent to not A or B.

You can also see this by looking at the "Venn diagram" for if A then B:

if A then B

In set theory notation, the shaded area can be written as $\overline{\mathbf{A}} \cup \mathbf{B}$ [that is "A-complement union with B"] which translates to logic as (not A) or B as expected.

Exercise F

1. Show, using truth tables, that not (A and not B) is equivalent to not A or B.
2. Show, using truth tables, that if A then B is equivalent to not (A and not B).
3. Find [logically] equivalent statements for each of the following:
   • (a) if $x > 1$ then $x^2 > 1$
   • (b) if two triangles are similar then they have the same interior angles
   • (c) if a triangle obeys Pythagoras' theorem then it has a right angle

Combining statements: A only if B

Statements of the form: A only if B.

Above we met statements of the form if A then B (or equivalently B if A); now we are going to look at statements of the form A only if B.

It is hard to untangle the everyday use of the term "only if" from the formal logical use of only if. Earlier we asked you to work out what you thought the statement it is Sunday only if the church bells ring told you. There you might have noticed that this statement had the same table of conclusions as the statement if it is Sunday, then the church bells ring. This motivates what is the case in formal logic: statements of the form A only if B are logically equivalent to statements of the form if A then B.

Now we shall look at a second example, the true statement

$\text{if } x = 3, \text{ then } x^2 = 9$

This can be written as

$x = 3 \text{ only if } x^2 = 9$

This makes some intuitive sense, for if $x^2 \neq 9$, then we cannot have $x = 3$.

We can write out the formal truth table for A only if B:

A	B	A only if B
T	T	T
T	F	F
F	T	T
F	F	T

Let's draw a diagram for A only if B to show where it is true:

A [very] useful tip is to replace the statement A only if B by if A then B whenever the former statement occurs.

Combining statements: A if and only if B

Statements of the form: A if and only if B.

Statements of the form A if and only if B are very common in mathematics so we shall spend some time unpicking them. First, it is worth noting that A if and only if B is often abbreviated to A iff B where 'iff' is usually read as 'if and only if' [we don't use the abbreviation iff in the TMUA but you should know it as it is very common]. Second, the reason iff statements are important is because when they are true they assert that A and B are really saying the same thing - albeit often in different ways – in that they are both true in all the same circumstances and false in all the same circumstances. In mathematics it is a very useful thing to know when two statements say the same thing in different ways – some might even claim that mathematics is, in essence, about demonstrating that different statements say the same thing in different ways. Before we take iff statements to pieces and get a feel for how they show two statements are equivalent, let's write out an obvious example:

an integer is even if and only if it is not odd

When unpicking what A if and only if B means it is useful to grasp that it is shorthand for the following:

(A if B) and (A only if B)

And we know from earlier that

A if B is the same as [logically equivalent to] if B then A

and

A only if B is the same as [logically equivalent to] if A then B

Now we know this, we can use all the rules we have learnt above to construct a truth table to work out when this statement is true and when it is false:

A	B	A if B if B then A	A only if B if A then B	(if B then A) and (if A then B) A if and only if B A iff B
T	T	T	T	T
T	F	T	F	F
F	T	F	T	F
F	F	T	T	T

From this we can see that A iff B is true when A and B are both true or when A and B are both false. That is to say that A iff B is true only when A and B always say the same thing – they are true together and false together. This is why proving A iff B is so important for mathematics as it is a way of telling us that two statements that might appear different are really saying the same thing from a mathematical point of view. For instance:

$[x] = [x] \text{ if and only if } x \text{ is an integer}$

where $[x]$ is the greatest integer less than or equal to $x$ and $[x]$ is the smallest integer greater than or equal to $x$. And here is another example:

an integer is divisible by 9 if and only if the sum of its digits is divisible by 9

How might we illustrate A iff B on a diagram? We can approach achieving an answer in two ways: either we can just work it out using diagrams for if A then B and for if B then A together with the rules for and; or we can just shade the areas on a diagram where A and B are true simultaneously and also where A and B are false simultaneously. Here is the result:

A if and only if B

Exercise G

Draw the diagrams for if A then B [A only if B] and for if B then A [A if B] and then use these two diagrams and the rules for and with diagrams to work out the diagram for A iff B.

Swapping A and B

Understand and be able to use mathematical logic in simple situations.

One thing we have mentioned but not examined much so far is what happens to each of the logical statements when we swap A with B. In this section we shall briefly examine this.

First, we look at A and B. The question we want to ask is whether A and B is the same as B and A; and by 'the same' we mean logically equivalent, that A and B has the same truth value as B and A for any given truth values of A and of B. The simple answer is 'yes' and this should be obvious from the way we defined A and B: our definition was independent of the order of A and B.

Exercise H

Examine the truth tables for A and B and convince yourself that A and B and B and A are the same. Look at the diagram we drew for A and B and work out what the diagram for B and A would look like.

Next, we look at A or B. The question we want to ask is whether A or B is the same as B or A; and, again, by 'the same' we mean that A or B has the same truth value as B or A for any given truth values of A and of B. The simple answer is 'yes', and again this should be obvious from the way we defined A or B: our definition was independent of the order of A or B.

What about if A then B? Does if A then B have the same truth table as if B then A? The simple answer is 'no' and we demonstrate this either by looking at the respective truth tables or drawing the respective diagrams. Let's look at the truth table:

A	B	if A then B	if B then A
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T

From this we can see that the last two columns are different, so the two statements are not the same.

Let's look at if A then B and if B then A in a little more detail. It's a common error when students are first learning logic to think that one statement is the same [has the same truth profile] as the other. For instance, we might start with the statement:

$\text{if } 0 < a < b \text{ then } a^2 < b^2$

and it is then tempting to say that this is the same as:

$\text{if } a^2 < b^2 \text{ then } 0 < a < b$

but a little thought shows that they are not equivalent statements. The first is always true no matter what real values of $a$ and $b$ we substitute, whilst the second is false as there are some values of $a$ and $b$ which make it false. For instance, if we set $a = 1$ and $b = -2$ then $a^2 < b^2$ but it's not the case that $0 < a < b$.

Here it is worth pausing for a moment to examine how we have dealt with our example. What do we do when we look at a statement such as if $0 < a < b$ then $a^2 < b^2$? First, we realise that what we have written, namely if $0 < a < b$ then $a^2 < b^2$ is shorthand for something a little more precise – we ignored the extra bits above to avoid overloading you with information. What extra information have we ignored here? Well, really the statement if $0 < a < b$ then $a^2 < b^2$ should tell us what values of $a$ and $b$ it applies to; we ought to write:

$\text{for all real values of } a \text{ and } b, \text{ if } 0 < a < b \text{ then } a^2 < b^2$

Later we shall say a little more about phrases such as 'for all'.

With the statement now written out in full, we can return to dealing with the statement: we ask ourselves what happens to the statement when the left-hand side is true and when it is false – do we always find the whole statement is true no matter what allowed values of $a$ and $b$ we substitute into the statement? In the case of if $0 < a < b$ then $a^2 < b^2$ we see that whenever we have values of $a$ and $b$ that obey [make true] $0 < a < b$ then those same values of $a$ and $b$ must also make the right-hand side – the expression $a^2 < b^2$ – true. So, to say it again, the statement for all real values of $a$ and $b$, if $0 < a < b$ then $a^2 < b^2$ is always true.

What about the second statement, if $a^2 < b^2$ then $0 < a < b$? Again, we shall take the same approach [we shall assume we have the phrase for all real values of $a$ and $b$ lurking about]. We ask if there are any values of $a$ and $b$ that make the left-hand side, the $a^2 < b^2$, true and the right-hand side, $0 < a < b$, false. The answer is that there are, and we gave such an example above [$a = 1$ and $b = -2$]. So, for the statement if $a^2 < b^2$ then $0 < a < b$ we can find values of $a$ and $b$ that make the left-hand side true and the right-hand side false. This means that the statement is false.

Now we can return to our main theme: we now consider what happens when we swap A with B in the statement A only if B. Again, we can look at the truth table or diagrams to decide whether A only if B is the same as B only if A:

A	B	A only if B	B only if A
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T

It is clear from the truth table that the two statements are not the same – they are not logically equivalent.

Exercise I

1. Draw diagrams for A only if B and for B only if A to convince yourself they have different truth profiles.

2. Look at diagrams for all of the following together:

   • A or B
   • A and B
   • if A then B
   • A only if B

   Examine the symmetry of the diagrams. What do you notice about the cases that remain unchanged when you swap A and B and what do you notice about the symmetry of those cases that have different truth tables when you swap A and B?

3. Using your answer to 2, what can you say about A iff B and B iff A, are they the same - do they have the same truth tables for a given A and B? [Do this before reading the next section.]

Finally, we shall look at the statement A iff B and compare it with the statement B iff A. Recall that when we first met A iff B we said it was a statement that appears a lot in mathematics because it tells us that A and B are saying the same thing – when A is true then B is true and vice versa. We can examine whether A iff B and B iff A say the same thing by looking at truth tables:

A	B	A iff B	B iff A
T	T	T	T
T	F	F	F
F	T	F	F
F	F	T	T

As an aside, we can also look at how we construct the diagram of A iff B from (if A then B) and (if B then A).

First, recall the diagrams of if A then B [A only if B] and of if B then A [A if B]:

if A then B

if B then A

Then recall that and means we shade only those areas that are shaded on both diagrams. When we do this, we get:

A if and only if B

And we note that the diagram is symmetric in that it does not matter which circle we label A and which we label B. Symmetry of diagrams is one way of spotting when the A and the B can be swapped in a statement without changing the [logical] meaning of the statement.

Summary

Statements

• Can be either true or false but not both.
• Can be combined to make "bigger statements".

Same / logically equivalent

• Two statements are the same – logically equivalent – when they have identical truth tables. Or more informally: they are true and false in the same way.

not A

• Turns false statements into true statements and vice versa.
• Applies only to what immediately follows it unless brackets are used.
• not not A is logically equivalent to A
• Truth table:

A	not A
T	F
F	T

A and B

• True only when both A and B are true, otherwise false.
• Symmetry: A and B is logically equivalent to B and A
• (A and B) and C is logically equivalent to A and (B and C) and is also logically equivalent to A and B and C
• Truth table:

A	B	A and B
T	T	T
T	F	F
F	T	F
F	F	F

A or B

• True when either A or B or both are true – i.e., true when at least one of the two statements A, B, is true.
• Symmetry: A or B is logically equivalent to B or A
• (A or B) or C is logically equivalent to A or (B or C) and is also logically equivalent to A or B or C
• Truth table:

A	B	A or B
T	T	T
T	F	T
F	T	T
F	F	F

Negating compound statements

• not (A and B) is logically equivalent to not A or not B.
• not (A or B) is logically equivalent to not A and not B.

if A then B

• Also written as B if A or as A only if B
• Not symmetric: if A then B is not the same as if B then A
• Truth table:

A	B	If A then B
T	T	T
T	F	F
F	T	T
F	F	T

A if and only if B

• Also written as A iff B
• Symmetric: A iff B is logically equivalent to B iff A
• Equivalent to (if B then A) and (if A then B)
• Equivalent to (A if B) and (A only if B)
• Full truth table:

A	B	A if B if B then A	A only if B if A then B	(if B then A) and (if A then B) A if and only if B A iff B
T	T	T	T	T
T	F	T	F	F
F	T	F	T	F
F	F	T	T	T