3.2 Logical connectives and the ‘not’ operator

We can construct new sentences of English by connecting two sentences in various ways. For example, consider the following two sentences.

$P$ :

‘I will go to class today.’
$Q$ :

‘I will go to class tomorrow.’

We can connect these to make a new sentence in several ways.

$P$ and $Q$ :

‘I will go to class today and I will go to class tomorrow.’
$P$ or $Q$ :

‘I will go to class today or I will go to class tomorrow.’
If $P$ then $Q$ :

‘If I [will] go to class today then I will go to class tomorrow.’

We can also express the negation of a sentence by adding the word ‘not’.

not $P$ :

‘I will not go to class today.’

Then we can connect these sentences to construct even more complex ones.

not $P$ and $Q$ :

‘I will not go to class today and I will go to class tomorrow.’
$P$ or not $Q$ :

I will go to class today or I will not go to class tomorrow.’
If not $P$ then $Q$ :

‘If I don’t go to class today then I will go to class tomorrow.’

We will now think about what it means for statements constructed like this to be true.

3.2.1 Negation (not)

Let’s introduce new labels for two statements.

$A$ :

‘I will go to class today.’
$B$ :

‘I will not go to class today.’

When we have two statements related like this, we say that $B$ is the negation of $A$ . Also, $A$ is the negation of $B$ or, in other words, ‘not(not $A$ )’ is the same as $A$ .

Observe that the statement

$C$ :

‘I will go to class tomorrow.’

is not the negation of the statement

$A$ :

‘I will go to class today.’

The truth of statements $A$ and $C$ are independent; they could both be true, both be false, or one could be true and the other false.

Given any statement $P$ , we label its negation as ‘not $P$ ’. An Euler diagram representing the statements $P$ and ‘not $P$ ’ is shown in Figure 3.3.

Figure 3.3: An Euler diagram showing

P

and ‘not

P

’

The area outside the shape labelled $P$ (but inside the rectangle) represents the statement ‘not $P$ ’. Since we put a dot inside $P$ to mean than $P$ is true, placing a dot anywhere outside $P$ means that ‘not $P$ ’ is true. Hence when $P$ is false, ‘not $P$ ’ is true and when $P$ is true, ‘not $P$ ’ is false.

Figure 3.4:

P

is false so ‘not

P

’ is true

3.2.2 Conjunction (and)

Given statements $P$ and $Q$ , the statement ‘ $P$ and $Q$ ’ is called their conjunction.

For example, given statements

$A$ :

‘I will go to class today.’
$C$ :

‘I will go to class tomorrow.’

their conjunction is

$A$ and $C$ :

‘I will go to class today and I will go to class tomorrow.’

The Euler diagram representing the statement ‘ $P$ and $Q$ ’ is shown in Figure 3.5.

Figure 3.5: Euler diagram showing

P

Q

and ‘

P

and

Q

’

The shaded intersection of $P$ and $Q$ represents the statement ‘ $P$ and $Q$ ’. A dot being inside the shape labelled ‘ $P$ and $Q$ ’ means it must be inside $P$ and inside $Q$ . In other words, the statement ‘ $P$ and $Q$ ’ is true precisely when $P$ is true and $Q$ is true. Otherwise ‘ $P$ and $Q$ ’ is false.

Exercise 3.1.

For each of the following statements, determine and explain whether the statement is true or false.

(a)

$5$ is even and $-3$ is even.
(b)

$16$ is even and $13$ is odd.
(c)

$-8$ is odd and $9$ is odd.

Solution.
1. (a)
  
  Since ‘ $5$ is even’ is false , the statement ‘ $5$ is even and $-3$ is even’ is false. Note that ‘ $-3$ is even’ is also false but this doesn’t matter: we already know that ‘ $5$ is even and $-3$ is even’ is false because ‘ $5$ is even’ is false.
2. (b)
  
  Since ‘ $16$ is even’ is true and ‘ $13$ is odd’ is true, the statement ‘ $16$ is even and $13$ is odd’ is true.
3. (c)
  
  Since ‘ $-8$ is odd‘ is false and ‘ $9$ is odd‘ is true, the statement ‘ $-8$ is odd and $9$ is odd’ is false.

3.2.3 Disjunction (or)

Given statements $P$ and $Q$ , the statement ‘ $P$ or $Q$ ’ is called their disjunction.

For example, given statements

$A$ :

‘I will go to class today.’
$C$ :

‘I will go to class tomorrow.’

their disjunction is

$A$ or $C$ :

‘I will go to class today or I will go to class tomorrow.’

You might interpret statement ‘ $A$ or $C$ ’ as meaning I will go to class either today or tomorrow, but not both. It is often the case in English that the word ‘or’ is meant to be interpreted in this exclusive way. In mathematics, a disjunction like ‘ $A$ or $C$ ’ is always inclusive unless stated otherwise. So, in this case, ’ $A$ or $C$ ’ includes the scenario where I will go to class both today and tomorrow.

The Euler diagram representing the statement ‘ $P$ or $Q$ ’ is shown in Figure 3.6.

Figure 3.6: Euler diagram showing

P

Q

and ‘

P

Q

’

The shaded union of $P$ and $Q$ represents the statement ‘ $P$ or $Q$ ’. A dot being inside the shape labelled ‘ $P$ or $Q$ ’ means it must be inside $P$ or $Q$ or both. In other words, the statement ‘ $P$ or $Q$ ’ is true when $P$ is true or $Q$ is true (or both). Otherwise ‘ $P$ or $Q$ ’ is false.

Exercise 3.2.

For each of the following statements, determine and explain whether the statement is true or false.

(a)

$5$ is even or $-3$ is even.
(b)

$16$ is even or $13$ is odd.
(c)

$-8$ is odd or $9$ is odd.

Solution.
1. (a)
  
  Since ‘ $5$ is even’ is false and ‘ $-3$ is even’ is false, the statement ‘ $5$ is even or $-3$ is even’ is false.
2. (b)
  
  Since ‘ $16$ is even’ is true and ‘ $13$ is odd’ is true, the statement ‘ $16$ is even or $13$ is odd’ is true. (Remember that ‘or’ is always inclusive.)
3. (c)
  
  Since ‘ $-8$ is odd‘ is false and ‘ $9$ is odd‘ is true, the statement ‘ $-8$ is odd or $9$ is odd’ is true.

3.2.4 Conditional (If … then …)

Consider the following two statements.

‘If today is Saturday, then I will not go to class today.’
‘For any two real numbers $x$ and $y$ , if $x=y$ then $x^{2}=y^{2}$ .’

These are called conditional statements. In general, given statements $P$ and $Q$ , the statement ‘If $P$ then $Q$ ’ is called a conditional statement.

Note that, in English, there are different ways of expressing the same conditional statement. For example, the following statements mean the same thing.

‘If today is Saturday, then I will not go to class today.’
‘I will not go to class today if today is Saturday.’
‘I will not go to class on Saturdays.’

When making conditional statements, it is conventional to stick to the form ‘If $P$ then $Q$ ’ rather than ‘ $Q$ if $P$ ’²² 2 However, see Section 3.2.5 for an example of when the phrasing ‘ $Q$ if $P$ ’ is commonly used. or any other phrasing. This helps to make such statements clear. Mathematicians often write $P\Rightarrow Q$ to mean ‘If $P$ then $Q$ ’. This can also be read as ‘ $P$ implies $Q$ ’.

Warning: do not misuse the ‘ $\Rightarrow$ ’ symbol. It only ever belongs between two statements. Phrases such as ‘ $3x+2x\Rightarrow 5x$ ’, literally ‘if $3x+2x$ then $5x$ ’, are meaningless.

The conditional statement ‘If $P$ then $Q$ ’ asserts that if $P$ is true then $Q$ is also true. The Euler diagram representing a conditional statement looks as shown in Figure 3.7.

Figure 3.7: Euler diagram showing ‘If

P

then

Q

’

We can use the diagram to draw the following conclusions.

•

If $P$ is true then $Q$ must also be true; if we put a dot inside $P$ then it is guaranteed to be inside $Q$ . [Thus the diagram does indeed capture the intended meaning of ‘If $P$ then $Q$ ’.]
•

If $Q$ is false then $P$ must also be false; we cannot put a dot outside $Q$ but inside $P$ . [This observation is crucial to the ideas of proving the contrapositive of a statement (Section 4.4) and proof by contradiction (Section 4.5).]
•

Statement $P$ being false tells us nothing about the truth of $Q$ ; a dot placed outside $P$ could be either inside or outside $Q$ .

Given the statement ‘If $P$ then $Q$ ’, we can say that $P$ is a sufficient condition for $Q$ because knowing that $P$ is true is sufficient to ensure that $Q$ is true. Similarly, $Q$ can be said to be a necessary condition for $P$ because, for $P$ to be true, it is necessary that $Q$ is true. We will not use these terms again in this companion, but you should be aware of them in case you see them used elsewhere.

Note that, in this companion, we will not discuss precisely what it means for the entire statement ‘If $P$ then $Q$ ’ to be true or false. Rather, we are thinking of ‘If $P$ then $Q$ ’ as expressing a relationship between statements $P$ and $Q$ , and discussing what this means about the truth of $P$ and $Q$ .³³ 3 For completeness, you should be aware that logicians consider the statement ‘If $P$ then $Q$ ’ to be equivalent to ‘not $P$ or $Q$ ’. This means, in particular, that ‘If $P$ then $Q$ ’ is considered to be true when $P$ is false and $Q$ is true, and also when $P$ and $Q$ are both false! These facts are not particularly useful when doing mathematics since we are usually more concerned with the truth of statements $P$ and $Q$ themselves.

Many of the statements we considered in Chapter 2 can be thought of as conditional statements. For example, Claim 2.8 (‘For all positive real numbers $x$ , $x^{2}+x$ is positive’) could instead be written as ‘If $x$ is a positive real number then $x^{2}+x$ is positive’.

The point here is that you already know how you can prove a conditional statement ‘If $P$ then $Q$ ’: you can start by assuming $P$ is true then show that $Q$ follows as a logical certainty using a chain of deductive reasoning.

Example 3.3.

Suppose $x$ and $y$ are any two real numbers. We shall prove the statement: ‘if $x=y$ then $x^{2}=y^{2}$ .’

Suppose that $x$ and $y$ are two real numbers and that $x=y$ .

•

Multiplying both sides of the equation $x=y$ by $x$ gives $x^{2}=xy$ .
•

Multiplying both sides of the equation $x=y$ by $y$ gives $xy=y^{2}$ .

Since $x^{2}$ and $y^{2}$ both equal $xy$ , they must be the same, that is $x^{2}=y^{2}$ .

The converse of a conditional statement

When we form the conjunction or disjunction of two statements $P$ and $Q$ , the order in which we do so does not matter. For example, the following statements mean exactly the same thing.

$A$ and $C$ :

‘I will go to class today and I will go to class tomorrow.’
$C$ and $A$ :

‘I will go to class tomorrow and I will go to class today.’

However, the order of statements in a conditional statement does matter. Given statements $P$ and $Q$ , the converse of the statement ‘If $P$ then $Q$ ’ is the statement ‘If $Q$ then $P$ .’

Given a conditional statement ‘If $P$ then $Q$ ’ (or ‘ $P\Rightarrow Q$ ’), we cannot assume that the converse ‘If $Q$ then $P$ ’ (or ‘ $Q\Rightarrow P$ ’) also holds. This can be illustrated by considering our familiar example.

$D$ :

‘If today is Saturday, then I will not go to class today.’
$E$ :

‘If I will not go to class today, then today is Saturday.’

Statement $E$ is the converse of $D$ . Statement $E$ means that the only day I do not go to class is a Saturday. This is false, even though $D$ is true.

On the other hand, the converse of a conditional statement may also be true.

$F$ :

‘If I am in Edinburgh then I am in the capital of Scotland.’
$G$ :

‘If I am in the capital of Scotland then I am in Edinburgh.’

This time statements $F$ and its converse $G$ are both true.

The truth of a conditional statement guarantees nothing about the truth of its converse. Assuming that the converse of a true statement is true is a very common error, so be careful not to do it!

Example 3.4.

Consider the statement from Claim 2.8 phrased as a conditional statement: ‘Let $x$ be a real number. If $x$ is positive then $x^{2}+x$ is positive.’ We proved this statement in Example 2.20.

The converse of the statement is ‘If $x^{2}+x$ is positive then $x$ is positive.’ This is false. For example, let $x=-2$ . Then $x^{2}+x=(-2)^{2}+(-2)=4-2=2$ which is positive but $x=-2$ is not positive.

Example 3.5 (The Pythagorean theorem).

Suppose we have a triangle with sides of length $a$ , $b$ , and $c$ . If the angle between sides $a$ and $b$ is a right angle then $a^{2}+b^{2}=c^{2}$ . (You probably know this result already, perhaps phrased differently.) A proof is presented in Theorem 4.14.

In fact, the converse of this statement is also true. Suppose we have a triangle with sides of length $a$ , $b$ , and $c$ . If $a^{2}+b^{2}=c^{2}$ then the angle between sides $a$ and $b$ is a right angle. A proof is presented in Theorem 4.15.

3.2.5 Equivalence (If and only if)

Recall from Section 3.2.4 the statements $F$ and its converse $G$ .

$F$ :

‘If I am in Edinburgh then I am in the capital of Scotland.’
$G$ :

‘If I am in the capital of Scotland then I am in Edinburgh.’

Two statements $P$ and $Q$ are said to be (logically) equivalent when $P\Rightarrow Q$ and $Q\Rightarrow P$ . In this case, we may write ‘ $P\Leftrightarrow Q$ ’ or ‘ $Q$ if and only if $P$ ’⁴⁴ 4 Mathematicians sometimes write ‘iff’ as a shorthand for ‘if and only if’..

So statements $F$ and $G$ above assert that

$H$ :

‘I am in Edinburgh.’ and
$I$ :

‘I am in the capital of Scotland.’

are logically equivalent, and in place of $F$ and $G$ we can write:

‘I am in the capital of Scotland if and only if I am in Edinburgh.’

Note that $P$ and $Q$ are reversed in ‘ $P\Leftrightarrow Q$ ’ compared with ‘ $Q$ if and only if $P$ ’. This is not a typo. Recall from Section 3.2.4 that ‘ $P\Rightarrow Q$ ’ means ‘If $P$ then $Q$ ’ or, alternatively ‘ $Q$ if $P$ ’. So the ‘if’ part of ‘ $Q$ if and only if $P$ ’ corresponds to the statement ‘ $P\Rightarrow Q$ ’.

The Euler diagram representing a logical equivalence is shown in Figure 3.8.

Figure 3.8: Euler diagram showing ‘

P\Leftrightarrow Q

’ (‘

Q

if and only if

P

’)

The shapes for statements $P$ and $Q$ coincide; any dot placed on the diagram will be either inside both $P$ and $Q$ or outside both $P$ and $Q$ .

Example 3.6.

Consider the statement: ‘For any positive real numbers $x$ and $y$ , $x^{2}=y^{2}$ if and only if $x=y$ .’

Let’s introduce labels:

$J$ :

$x=y$
$K$ :

$x^{2}=y^{2}$

So the statement under consideration is saying that, assuming $x$ and $y$ are positive real numbers, $J\Leftrightarrow K$ . Proving $J\Leftrightarrow K$ means proving that $J\Rightarrow K$ and $K\Rightarrow J$ .

We already proved $J\Rightarrow K$ for any two real numbers $x$ and $y$ in Example 3.3 and so the same proof holds assuming $x$ and $y$ are both positive.

To prove that $K\Rightarrow J$ , we can proceed as follows. Suppose $x^{2}=y^{2}$ ,

	$\displaystyle\qquad x^{2}$	$\displaystyle=y^{2}$
$\displaystyle\Leftrightarrow$	$\displaystyle\sqrt{x^{2}}$	$\displaystyle=\sqrt{y^{2}}$	(taking square roots on both sides)
$\displaystyle\Leftrightarrow$	$\displaystyle x$	$\displaystyle=y$	(since $x$ and $y$ are both positive).

Since we have proved $J\Rightarrow K$ and $K\Rightarrow J$ , we have proved $J\Leftrightarrow K$ .

It is likely that in the past you will have seen and written many line-by-line deductions like the one above without the ‘ $\Leftrightarrow$ ’ symbol between statements. For example, instead of the above, you may have written:

$\displaystyle\qquad x^{2}$	$\displaystyle=y^{2}$
$\displaystyle\sqrt{x^{2}}$	$\displaystyle=\sqrt{y^{2}}$	(taking square roots on both sides)
$\displaystyle x$	$\displaystyle=y$	(since $x$ and $y$ are both positive).

You should always include the correct logical connectives in your line-by-line reasoning. Doing so makes your argument clearer and can help prevent errors in reasoning.

For instance, note that the statement ‘ $K\Rightarrow J$ ’ is not true if $x$ or $y$ were allowed to be negative. For example, let $x=-3$ and $y=3$ so that $x^{2}=y^{2}$ . This does not imply that $x=y$ .

So where does the argument above go wrong if $x$ or $y$ can be negative? It’s the following step:

		$\displaystyle\qquad\sqrt{x^{2}}$	$\displaystyle=\sqrt{y^{2}}$	(taking square roots on both sides)
	$\displaystyle\Leftrightarrow$	$\displaystyle x$	$\displaystyle=y.$

(You can see this is false by putting $x=-3$ and $y=3$ .) For completeness, observe that the following chain of reasoning is correct for any real numbers $x$ and $y$ :

	$\displaystyle\qquad x^{2}$	$\displaystyle=y^{2}$
$\displaystyle\Leftrightarrow$	$\displaystyle\sqrt{x^{2}}$	$\displaystyle=\sqrt{y^{2}}$	(taking square roots on both sides)
$\displaystyle\Leftarrow$	$\displaystyle x$	$\displaystyle=y.$

But this does not allow us to conclude that $x=y$ in the case where $x$ or $y$ could be negative.