Making new statements

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]

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:

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:

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:

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.

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:

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$^{6}$:

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.

Let’s look at another example:

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:

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).

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:

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:

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.

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 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:

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:

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.

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

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:

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.