Statements and Connectives

Statements

The terms true and false

At the heart of mathematics, and mathematical logic, is the notion of a statement and the relationship between statements. But what can we say about the statements we shall meet in mathematics? We can say that they must be either true or false, but not both. And it does not matter if we cannot work out whether a statement is actually true or false so long as it must be one or the other. We shall use this answer to give us a way of understanding roughly what we shall mean by a "statement" in these notes. For present purposes, we shall make do with the following:

• A statement is a sentence which is definitely true or definitely false.
• A statement can never be both true and false.

The principle that a statement can only be either true or false but not both is known as the law of the excluded middle. It is fundamental to all the logic and formal mathematics that you will meet in these notes. (There are systems that do not use the law of the excluded middle: we will not meet these systems in these notes, and they have a different notion of what a statement is from the ideas we are using here.)

It does not matter if we cannot work out whether a statement is actually true or false so long as it must be one or the other. For instance, here is a statement:

The equation $x^3 + y^2 = 88$ has no integer solutions.

This is clearly either true or false but establishing which is not so easy. Here is a second [rather famous] example of a sentence that is NOT a statement:

The only barber in a town shaves each and every man who does not shave himself.

This last sentence is not a statement as it is neither true nor false. (If you are interested in why, look up "Russell's Paradox" or "Barber Paradox". You do not need to worry at this stage why the sentence is neither true nor false; we will only use fairly simple statements in the TMUA, and we will never ask you to work out whether a given sentence is a statement or not.)

Here are some more examples of statements and non-statements:

1. "It rained yesterday in Auckland, New Zealand." This is a statement, as it is either true or false.
2. "Go home!" and "What is your name?" These are not statements, as it does not make sense to say that they are true or false.
3. "If x = 3, then x² = 9." This is certainly true, so it is a statement. We will have more to say about "If ... then ..." statements later.
4. "If x = 3, then x² = 4." This is certainly false, so it is a statement. There is no requirement for statements to be true!
5. "The sum of two odd numbers is an even number." This is certainly true, so it is a statement.

From now on, we will only be working with statements and relationships between statements. We shall try to keep to the convention that we write all our logical statements using italics when they are in words and as bold letters when a statement is indicated by a letter [e.g. A, B, etc.]. Later we shall use bold for some terms to help us see how they fit into sentences.

A little more on statements

Now we know what we mean by a statement, we shall pause to dig a little deeper into the sorts of statements you might meet and how we discern their truth or falsity. Here is a statement:

24 is divisible by 2

This statement says something that is true and cannot be false, so it is an example of a statement we know to be true just by looking at it. Here is another example:

453653987389875629 is divisible by 987283

This is clearly a statement as it is obviously either true or false. However, whilst it is obvious that it is a statement, it is not so obvious whether it is a true statement or a false statement. To decide that we would need to do some more [somewhat tedious] work.

Here is another statement:

The square root of 2 is irrational

This statement is very much like the first statement [24 is divisible by 2] in that it is true. However, it is not as obvious as the first statement and some work needs to be done to show why it must be true. Later we shall see how we can set out a proof to show that this statement is true.

And here is an expression that has the potential to be a statement:

The positive integer x is divisible by 2

Here we don't know what x is so we cannot say whether the expression is true or false as it stands; in other words, whether the expression is true or false is conditional on what we are told about x so until we clarify this, we cannot say the expression is a statement according to our definition. We could say it is true or false if we had some more information about x. General expressions like this tend to occur in combination with other statements [and, as you will read later, they need to be "quantified" in some way – that is, the set of possible x values to which the statement applies must be clearly stated] and then what is often important is what the combination is saying. For instance, the statement:

if the integer x is divisible by 4 then the integer x is divisible by 2,

is definitely true even though each of the expressions that we have combined to make the bigger statement cannot be said to be true or false by themselves.

So, we shall meet three sorts of basic statement in what follows:

• those that are obviously true [or obviously false];
• those that are true or false, but which need some work to decide which;
• those that are combinations of expressions which are quantified [roughly, that means the range of what the $x$ can be is clearly stated] and are then either true or false [and these will often require some work to decide which they are].

Later in these notes, we shall spend a lot of time building new statements out of basic statements.

In what follows we shall tend to learn how various logical rules work by dealing with statements denoted just by letters – such as A or B or P or Q - but then we shall apply these rules to statements that have definite truth values. This is a little like learning about quadratic equations by studying various things about $ax^2 + bx + c = 0$ and then applying what you discover to specific examples.

Truth values

In what follows we shall talk a lot about the "truth value" of a statement. By "truth value" we simply mean whether the statement is true or false. For instance, the truth value of the statement 2 is an even number is "true", and the truth value of the statement 2 is an odd number is "false".

Logically equivalent

We shall often say that two statements are logically equivalent. This will mean that the two statements have the same truth values in the same circumstances. [This is a slightly casual definition, but it will suffice for these notes.]

For instance, the following two statements are logically equivalent:

Today is Tuesday

Today is the day after Monday

Making new statements

Introduction

As we discussed briefly above, mathematics is in part about seeing how the truth or falsity of one statement relates to the truth or falsity of other statements. To help us begin to understand these relationships we shall learn how to build new (compound) statements by formally combining other statements, and we shall learn how the truth or falsity of the combinations depends on the truth or falsity of the statements that we use to build them.

Before we begin to unpack compound statements in detail, here are some examples of formal combinations of statements with the statements written in italics and the formal 'combining terms' written in bold:

• 21 is divisible by 3 and 21 is divisible by 6 [A and B]
• 21 is divisible by 3 or 21 is divisible by 6 [A or B]
• 21 is not divisible by 6 [not B]
• if 21 is divisible by 3 then 21 is divisible by 6 [if A then B]
• 21 is divisible by 3 if 21 is divisible by 6 [A if B]
• 21 is divisible by 3 only if 21 is divisible by 6 [A only if B]
• 21 is divisible by 3 if and only if 21 is divisible by 6 [A if and only if B]

Exercise A

1. Decide which of the above combinations you think must be true and which must be false. Can you explain your answers?
2. What, if anything, happens to your answers if you replace 21 by $x$ in each of the statements [assume $x$ can be drawn from the set of real numbers]?
3. When you replace 21 by $x$, are all the resulting expressions still statements?
4. What happens to your answer to 2 if you change the set of $x$ values to which the statements apply?

The negation of a statement: the term not

In this section we shall look at using not with statements. The formal use of not in logic is very similar to the everyday use of the term 'not' so you will already have a good intuitive grasp of how not works.

Formally, if we have a statement A then we can construct another statement from it, which we shall write as not A, the negation of A. For instance:

• A: 21 is divisible by 3
• not A: not [21 is divisible by 3]

and we tend to write not [21 is divisible by 3] as 21 is not divisible by 3.

You should note that in formal logic, not applies only to what occurs immediately after it unless there are brackets: so not A or B means (not A) or B and, as you will find out later, this is different from not (A or B).

Here we shall learn how to understand the negation of a statement and the relationship between the truth value of a statement and its negation.

Let us start with a simple example of negation.

Example. Let A be the statement:

29 is a prime number

then not A is the statement:

it is not the case that 29 is a prime number

which we can write more succinctly as: 29 is not a prime number.

So we have:

• A: 29 is a prime number
• not A: 29 is not a prime number

Here it is obvious that A is true and not A is false, and this is a general property of not: it changes true statements into false ones, and it changes false statements to true ones. This rule will always work because, recall, we take statements to be always either true or false [the law of the excluded middle] by definition.

We can display the way not works for general statements in one of two ways [in fact, there are other ways but we shall stick to just two ways here]. We can either draw out a 'truth table' or we can draw a picture. Let's start with the truth table:

A	not A
T	F
F	T

Here T is shorthand for 'true' and F is shorthand for 'false'. The first row in the table tells us that whenever A is true then not A is false, while the second row in the table tells us that whenever A is false then not A is true.

We can also think about A and not A using diagrams. The diagrams we will use derive from set theory – they are like Venn diagrams – and you might have met them when studying probability. The diagrams we use are less formal than truth tables and have a slightly different emphasis – they tend to be useful mostly when talking about general statements, although they can also be useful when thinking through examples with statements that have definite truth values. Here the diagrams are primarily intended to help you think about things.

In the diagrams that follow you should think of the area inside the A circle as representing all the cases where A is true. And that means you should think of the area outside the circle as representing all the cases when A is false; that is, all the cases where not A is true. We shall use the convention that each shaded area in a diagram shows where one particular statement is true: A is true inside the A circle and not A is true outside the A circle. We shall write what area is shaded [and so what area is true] under each diagram. Here are a couple of examples:

not A

Notice that the "A" written near the circle labels the circle and its inside.

If you know some set theory, then you can think of the circle A as representing the set where A is true, so then not A is like the complement of that set. Similarly, if you know about events in probability, then you can think of A as an event and not A as the complementary event A' – the event that A does not occur.

Exercise B

1. If A is true, what can you say about not not A? What about not not not A?
2. Can you work out a general rule for the truth value of not not not...not A [m lots of not] when A is true, and when A is false?

Combining statements: using and

In this section we shall look at the logical term and. The word "and" appears all over the place in everyday English. However, the use of "and" in logic is very precise - perhaps more so than in colloquial English - so you will need to be a little careful when you use the logical version of "and".

We begin by setting out a simple example of a compound statement A and B.

Example.

• A: 21 is divisible by 3
• B: all humans are mammals

The compound statement is therefore:

A and B: 21 is divisible by 3 and all humans are mammals

In general, the statement A and B is true when both of A and B are true, and it is false when at least one of the statements is false. We could write this up as a table:

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

Recall, here we have written T as shorthand for "true" and F for "false". The table shows that for A and B to be true both A and B must be true. [These very useful tables are called "truth tables". They were introduced by the philosopher Ludwig Wittgenstein in his book Tractatus Logico-Philosophicus. We do not use truth tables officially in the TMUA — they are not part of the test's official specification — so there will not be questions that depend on using them or knowing about them. Nevertheless, truth tables are very useful whilst you learn logic, and we recommend that you make sure you are familiar with them.]

Let's look at another example:

Consider the statement: the monarch is a man and the Prince of Wales is called William. Each of the parts the monarch is a man, and the Prince of Wales is called William is true, so the whole statement is true. (At least this is the case in the UK at the time of writing these notes.)

We can also think of the statement A and B using our diagrams. Remember that everything inside the A circle is where A is true and everything inside the B circle is where B is true. A and B is true when both A and B are true. So, A and B is represented by the overlap of the A circle and the B circle:

A and B

If you know set theory, you can think of A and B as being like A ∩ B [A intersect B] in diagrams. Similarly, in the language of probability, you can think of A and B as the event that both A and B occur (also written as A ∩ B).

Combining statements: using or

The next way we might want to combine two statements is with the word "or". There are two possible meanings of this word. In general usage, "A or B" is often understood to mean "either A is true, or B is true, but not both". For instance, in general usage we might hear things like "you can have jam roly-poly or a mille feuille for pudding" and we would usually take that to mean we could have one or the other pudding but not both. This type of "or" is sometimes called an "exclusive or" [this is often written as XOR, but we will not be using XOR at all in these notes or in the TMUA]. However, mathematicians take the word "or" to mean "inclusive or", so that A or B means "either A is true, or B is true, or both are true". Over the years, it has been found to be much more convenient to use this version of "or" rather than the "exclusive or". When mathematicians want to mean exclusive or, they are explicit about it, and write something like "either A is true, or B is true, but not both". When they just write "or" in a mathematical statement, they always mean "inclusive or". This is the meaning of "or" - which we shall write in bold as or - that will be used in the admission test.

We can again write a truth table to show this:

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

For example, the statement the monarch is a man or the Prince of Wales is called William is a [mathematically] true statement, even though it sounds a little strange colloquially.

We can look at or using our diagrams. A or B is true when we are either inside A or inside B or inside both. So, A or B is represented by the shaded region in the following diagram:

A or B

In set theory terms, A or B is like A ∪ B [A union B] and in probability terms, it is like the event that either A or B or both occur, also written as A ∪ B.

Exercise C

1. Complete the truth table for A and (B and C):

A	B	C	B and C	A and (B and C)
T	T	T	T	T
T	T	F	F	F
T	F	T	F
T	F	F	F
F	T	T
F	T	F
F	F	T
F	F	F

1. Now draw up the truth table for (A and B) and C. What do you notice? What do you think you can conclude about A and B and C?

2. Revisit question 2 above but this time use diagrams to justify your conclusion.

3. Draw up a truth table for each of the following:

   • A or (B or C)
   • (A or B) or C

   What do you notice? What do you think you can conclude about A or B or C?

4. Revisit question 4 but this time use diagrams to justify your conclusions.

5. Draw up truth tables for each of the following:

   • A or (B and C)
   • (A or B) and (A or C)

   What do you notice? Can you justify your conclusions using diagrams? [We say that or distributes over and.]

6. Can you find an equivalent statement for A and (B or C)?

7. How do your results for questions 6 and 7 compare with the arithmetic operations of multiplication and addition?

8. Consider A and B or C. Is this statement ambiguous or not? Justify your answer.

9. Draw up truth tables for:

   • not (A or B)
   • (not A) and (not B)

   What do you notice? Can you justify your conclusions using diagrams?

10. Can you come up with an alternative [logically equivalent] way of writing not (A and B)? Justify your alternative statement using both truth tables and diagrams.

Revisiting logical equivalence

Recall, earlier we stated:

"We shall often say that two statements are logically equivalent. This will mean that the two statements have the same truth values in the same circumstances."

From the above Exercise C you should have noticed that A or (B and C) and (A or B) and (A or C) have the very same truth tables – each expression is true or is false in the same way once you are given the truth values of A, B and C. When two expressions match up in their truth tables in this way, we say that they are "logically equivalent". And so, identity of truth tables is another way to think about logical equivalence.

We can also use logical equivalence to understand A or B or C and A and B and C. We take it that the statement A or B or C is logically equivalent to either (A or B) or C or to A or (B or C). We can do the same thing for A and B and C. We can justify this as there is no ambiguity when we break A or B or C into statements that are of the form "...or..."; that is we can take the statement A or B or C and interpret it as either saying (A or B) or C or as saying A or (B or C); in both cases we get the same answers for the same truth values of A, B and C. And, we have to work this way – i.e. breaking the statements down using brackets - because we have only defined "or" in situations of the form ... or ...

The same applies for A and B and C.

You should also note that A or B and B or A are logically equivalent [can you explain why?] and also A and B and B and A are logically equivalent [again, can you explain why?].

You should start to build up a good grasp of when combinations of statement are logically equivalent: when can you swap the order of statements [for instance, A or B vs B or A], when can you remove brackets, when can't you remove brackets, how do you deal with brackets using or and and.

Negating compound statements

Be able to negate statements that use any of the above terms.

Negating more complicated statements can be tricky, and truth tables can often help. For example, what is the negation of A and B? It is not (A and B), but that use of brackets looks a little odd, and it would be tricky to write this as a sentence in English! We can write a truth table for this situation:

A	B	A and B	not (A and B)
T	T	T	F
T	F	F	T
F	T	F	T
F	F	F	T

Which table have we seen earlier which has three trues and one false in the final column? It was the or table, so it seems that not (A and B) is actually an or statement. To get false in an or statement, we need both parts to be false. If we consider (not A) or (not B), both of the parts are false in just the first row, giving the same resulting table:

A	B	A and B	not (A and B)	not A	not B	(not A) or (not B)
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

So not (A and B) is the same as (not A) or (not B). And by "the same" we mean they have the same truth values for any given truth values of A and B; recall that sometimes we say that two statements that have the same truth tables are logically equivalent, or just equivalent.

Example. As an example, the negation of

x is even and x is prime

is

x is not even or x is not prime,

or alternatively, replacing not even by odd [assuming x is an integer, which we look at more formally under quantification later]:

x is odd or x is not prime.

What about negating A or B? Let's look at the truth table:

A	B	A or B	not (A or B)
T	T	T	F
T	F	T	F
F	T	T	F
F	F	F	T

Which table have we seen earlier which has one true (T) and three falses (F) in the final column? It was the and table, so it looks like not (A or B) is actually an and statement. If we consider (not A) and (not B), we get exactly the same table:

A	B	A or B	not (A or B)	not A	not B	(not A) and (not B)
T	T	T	F	F	F	F
T	F	T	F	F	T	F
F	T	T	F	T	F	F
F	F	F	T	T	T	T

So not (A or B) is the same as (not A) and (not B). And, again, by 'same' we mean they have the same truth values for any given truth values of A and B; they are logically equivalent.

Exercise D

1. Look through a mathematics textbook to find some mathematical statements. What are their negations?
2. Look through some text in English (for example, on a website, in a newspaper or in a book) to find some statements. What are the negations of the statements you have found?