Necessary and Sufficient Conditions

Converses and contrapositives

The converse of a statement

The relationship between the truth of a statement and its converse.

Some of the statements we have met above have what is known as a converse. We shall start this section by giving you the converses of a number of statements. Have a look at each example and try to work out how you think we form the converse of a statement. Here are the examples:

Statement	Converse
if a and b are odd, then ab is odd	if ab is odd, then a and b are odd
if a and b are even, then ab is even	if ab is even, then a and b are even
if a is even, then a^{2} is even	if a^{2} is even, then a is even
if a is odd, then a^{2} is odd	if a^{2} is odd, then a is odd
if a and b are even, then a + b is even	if a + b is even, then a and b are even
if a and b are odd, then a + b is odd	if a + b is odd, then a and b are odd

Now we shall set out a table of the converses that are relevant to this specification:

Statement	Converse
if A then B	if B then A
A only if B	B only if A
A if B	B if A
A iff B	B iff A

From this table you can see that the converse of a statement is constructed by "swapping" A with B. We have already examined the truth tables of each of the above statements and their converses in earlier sections and we concluded:

• if A then B and its converse if B then A do NOT say the same thing: they are NOT equivalent statements
• A only if B and its converse B only if A do NOT say the same thing: they are NOT equivalent statements
• A if B and its converse, B if A do NOT say the same thing: they are NOT equivalent statements
• A iff B and its converse B iff A do say the same thing: they are equivalent statements

We can rewrite the table to include logically equivalent statements:

Statement	Converse
if A then B A only if B B if A	if B then A B only if A A if B
A iff B B iff A	B iff A A iff B

Exercise J

1. Look back at all the statements we have used as examples so far and write out their converses. How many of the converses are true?
2. What is the converse of the converse of a statement?
3. What is the converse of each of the following:
   • (a) if two triangles are congruent then they have the same area
   • (b) if two triangles are similar then they have the same internal angles
   • (c) if I am human then I am mortal [a classic example from philosophy]
   • (d) if I am a bachelor then I am an unmarried man [another example from philosophy: if you are interested in exploring further, look up analytic and synthetic statements, a priori and a posteriori knowledge, and the notion of necessity from a philosophical perspective]
4. Which of the converses you have written out for question 3 are true?

Contrapositive

The relationship between the truth of a statement and its contrapositive.

We have learnt that a statement and its converse are not the same logically. A natural follow-up question to ask is what statements are there that are logically the same as those we have met – the answer is found in the contrapositive of a statement. We shall start by listing the contrapositives that are relevant to this specification, and then we shall examine them in a little more detail:

Statement	Contrapositive
if A then B	if not B then not A
A only if B	not B only if not A
A iff B	not B iff not A

In each of these, A and B are both swapped and negated, whereas in the converse, they were simply swapped. (There is also a third possibility, called the inverse of a statement, where A and B are both negated, but not swapped. We will not consider inverses further here, and we do not test them in the TMUA.)

We examine the truth tables for each of these in turn:

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

From this we can see that if A then B and its contrapositive, if not B then not A, are logically equivalent statements.

And also:

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

From this we can see that A only if B and its contrapositive, not B only if not A, are logically equivalent statements.

Here are a few practical examples of statements and their contrapositives – for each one check you can see why they are equivalent statements and look carefully at how not is used in some of the examples:

$\text{if } x = 2 \text{ then } x^2 = 4, \text{ if } x^2 \neq 4 \text{ then } x \neq 2$

$\text{if } x^2 < 4 \text{ then } x < 2, \text{ if } x \geq 2 \text{ then } x^2 \geq 4$

if two triangles have the same angles as each other then they are similar

if two triangles are not similar, then they do not have the same angles as each other

Exercise K

1. Look at all the conditional statements that we have set out so far [i.e. all those involving 'if' in one way or another; that is: if... then..., ...iff..., ...only if...] and work out what their contrapositives say. Can you see, in each case, why the contrapositive is logically equivalent to the original statement?
2. What is the contrapositive of the converse of the statement if A then B? Are if A then B and the contrapositive of its converse logically equivalent?
3. What is the converse of the contrapositive of the statement if A then B? Are if A then B and the converse of the contrapositive logically equivalent?
4. What is the contrapositive of if a and b are odd, then ab is odd?
5. Why is it a mistake to write the contrapositive of if a and b are odd, then ab is odd as if ab is not odd then a and b are not odd?

Before you read on, make sure you have completed Exercise K questions 4 and 5 above.

It is important to take care when working out the contrapositive of complicated statements. Consider the statement (about integers) if a and b are odd, then ab is odd. This statement is true. Its contrapositive is therefore also true. But what is it? It is very tempting to insert a careless 'not' to produce if ab is not odd then a and b are not odd, and from this it is a short step to if ab is even then a and b are even. However, this is false [why?], and it is not the contrapositive. The correct form (in English that makes sense and is not strangled) is:

if ab is even then a and b are not both odd

or

if ab is even then at least one of a and b is even

The reason for this mistake is, of course, that negation is not as simple as it seems – here we need to use not (A and B) is logically equivalent to not A or not B.

Summary: converses and contrapositives

Often TMUA questions will give you a statement and ask about the truth values of the various related statement, such as the converse and contrapositive. You should remember that a statement and its contrapositive are logically equivalent, whereas this is not necessarily the case for a statement and its converse. To determine the truth or falsity of the converse of statement usually takes some extra effort.

We recommend you have a look through past TMUA papers and examine every question where the terms converse or contrapositive arise. You can look at the model answers too if you are not sure how to answer any question you identify.

An off-specification aside: symbols

Not in the specification and not required for the test.

We have now finished looking at the main areas of logic listed in the specification; we have still to look at the notions of necessity, sufficiency and the meaning of some statements such as for all, for some and there exists and we shall return to these below. In this section we shall briefly look at how what we have learnt above is expressed using symbols. We are adding this because it is useful to know how we can write everything we have met using symbols. You should note, however, that the TMUA will NOT test your ability to use these symbols and these symbols will NOT appear in any of the questions that we set – so, if you want, it is fine to skip this section.

Here is a table of common symbols used in formal logic:

What we have met	Alternative/equivalent expression	Formal symbol
A and B	B and A	A ∧ B A&B
A or B	B or A	A ∨ B
not A		¬A [sometimes ¬A or even Ã]
if A then B	A only if B B if A	A ⇒ B B ⇐ A
if B then A	B only if A A if B	B ⇒ A A ⇐ B
A if and only if B	A iff B B iff A	A ⇐ B

Exercise L

1. Revisit some [or all] of the statements we have met so far in these notes and rewrite them using the symbols above.
2. If you have met electronic circuits, you will probably have met variants on some of these such as A xor B, A nand B and so on. We will not look at these here but, if you have met them, it would be a useful exercise to examine how they fit with everything we have looked at.

Necessary and sufficient

Understand and use the terms necessary and sufficient.

The terms necessary and sufficient turn up a lot in mathematics. You might, for instance, have seen things like:

For two triangles to be congruent it is sufficient that they have two equal sides and the enclosed angle in common.

Or:

For two triangles to be similar it is necessary, but not sufficient, that they have an angle in common.

Or you might have seen parts of questions that say something like:

...by considering $(x^2 + gx + h)(x - k)$, or otherwise, show that $g^2 > 4h$ is a sufficient condition but not a necessary condition for the inequality

$(g - k)^2 > 3(h - gk)$

to hold [STEP I 2001 question 3]

In this section, we shall explain how mathematicians use the term necessary and the term sufficient. We need to explain them as they have subtly different features from their everyday uses; the good thing is we have met the notions already, we just didn't refer to them as necessity and sufficiency.

A is sufficient for B means exactly the same as if A then B. Usually we think of this as follows: A is sufficient for B if we can say that when A is true then we are guaranteed that B is true as well. And further, we need to note that if A is sufficient for B and we find that A is actually false, we cannot say whether B is true or false - as there might be cases where B is true and A is false.

The best way to think about A is sufficient for B is to think of it as saying that when we know A is true then we are guaranteed that B is true [and also remember that we cannot say anything about B when we are told A is false].

Here is an example:

x is an odd natural number greater than 1 and not divisible by any natural number other than 1 and itself is sufficient for x to be prime.

This is true because

if x is an odd natural number greater than 1 and not divisible by any natural number other than 1 and itself then x is prime.

is true. It is useful to note here that there is a case where x is an odd natural number greater than 1 and not divisible by any number other than 1 and itself is false but x is prime is true: i.e., the case x = 2. This is fine, though, as it does not make the statement itself false [check the truth table for if A then B] and, what is more, it illustrates the point we made above: there we said 'there might be cases where B is true and A is false' and here we have a case of this when x = 2.

Now necessity: in simple terms we say that A is necessary for B when if B then A, or equivalently A if B, is true. Usually, we think of this as follows: A is necessary for B if we can say that when B is true then we are guaranteed that A is true as well and if A is false then B must be false as well. And further, as before, we need to note that if A is necessary for B and we find that B is actually false, we cannot say whether A is true or false: there might be cases where A is true and B is false.

Here is an example of necessity:

two triangles having one side of the same length is necessary for the two triangles to be congruent.

We can see that this necessity condition is quite weak. It tells us something about congruence but not enough to guarantee that two triangles are congruent – two triangles each having one side of the same length is not sufficient to guarantee they are congruent!

We can now look at the term necessary and sufficient. From what we have written so far, it should be clear that if we write A is necessary and sufficient for B, then we mean A iff B. In other words, we mean that when A is true B is true, and vice versa, and when A is false then B is false, and vice versa.

Here is an example:

two triangles having the same three angles is a necessary and sufficient condition for the two triangles to be similar.

So, to summarise:

• if you are asked for a sufficient condition for B to be true then you need to look for a condition that guarantees to make B true.
• if you are asked for a necessary condition for B to be true then you need to look for something that must be the case for B to be true but might not be enough by itself to guarantee that B is true.

And if you are asked to find necessary and sufficient conditions for B then you need to look for something that guarantees the truth of B in all circumstances: that is, when your condition is true then B is true, and vice versa, and when your condition is false then B is false, and vice versa.

We can also think about necessity and sufficiency using a diagram. This diagram is slightly different from the diagrams we used earlier – although there are some connections between them – so it is best to look at these diagrams in isolation and treat them as a way of helping you grasp the notions of necessity and sufficiency.

Using the diagram, we can see that A is sufficient for B; that is to say, if we are inside the A circle then we must be inside the B circle too. Note that whilst A is sufficient for B, there are cases where we can be inside the B circle but outside the A circle; that is to say that even if A is false there is still the possibility that B is true – you should reconcile this with your formal understanding of A is sufficient for B, i.e. with if A then B which is also written as A ⇒ B.

Now let's look at necessity. Here is a second diagram with A and B swapped:

Another way of looking at this second diagram is to think about necessity: the diagram shows us that A is necessary for B; that is to say, we must be inside the A circle in order to have any chance of being inside the B circle. What is important to note here though is that being inside the A circle is not enough [i.e. is not sufficient] by itself to guarantee we are also inside the B circle. So, we need A in order for B to be true, but A alone is not enough to guarantee B is true – that is what necessity is all about.

Again, reconcile this with your formal understanding of A is necessary for B, A $\Leftarrow$ B.

Finally, what happens if A is necessary and sufficient for B? If we look at our diagrams, we see that the A and the B circle need to be covering each other; in other words, the A circle and the B circle are the very same circle and that means they are really logically equivalent. So, A is necessary and sufficient for B is another way of saying A iff B or even A $\Leftarrow$ B.

Here is a summary of the notions of necessity and sufficiency:

A is sufficient for B	A only if B, if A then B
A is necessary for B	A if B, if B then A
A is necessary and sufficient for B	A iff B

A is sufficient for B	A $\Rightarrow$ B
A is necessary for B	A $\Leftarrow$ B
A is necessary and sufficient for B	A $\Leftarrow$ B

Almost every TMUA paper will have some questions based on the terms necessary or sufficient. You should look through all the past papers and check you know how to deal with them and to check your understanding of the meaning of the two terms.

You should make sure you understand what each of the following terms means as they occur a lot in TMUA questions; use past paper questions and the model answers we have produced to help you:

• necessary
• sufficient
• necessary and sufficient
• necessary but not sufficient
• sufficient but not necessary
• not necessary and not sufficient [this is usually written as neither necessary nor sufficient, but we don't write that in the TMUA as we want to be very clear]