Mathematical Proof and the Principles of Mathematics/Logic/Logical connectives

In the previous section we made clear what mathematical statement is. In this section we talk about how mathematical statements can be combined to make more complex statements. This is done using what are called 'logical connectives' or 'logical operators'. You can think of these as functions of one or more variables, where the variables can be either True or False and the value of the function can be either True or False. The logical connectives commonly used in mathematics are negation, conjunction, disjunction, implication, and equivalence, which are fancy words for things you encounter in everyday English.

In this section the symbols $P$ and $Q$ denote mathematical statements.

Negation

The negation of a statement $P$ is the statement that $P$ is not true. Some ways to phrase this are

Not $P$.

It is false that $P$.

Examples:

Statement	Negation
It rained on 1 September 2005.	It did not rain on 1 September 2005.
All teachers are female.	Not all teachers are female.
Mike's dog has a black tail.	Mike's dog does not have a black tail.
2 + 2 = 4	2 + 2 ≠ 4.
Triangle ABC is equilateral.	Triangle ABC is not equilateral.

Negation inverts the truth or falsehood of logical statements. In other words, not $P$ is False when $P$ is True, and Not $P$ is True when $P$ is False. In tabular form:

$P$	Not $P$
True	False
False	True

The logical symbol for negation is "$\lnot$", so you can write $\lnot P$ for Not $P$.

Even though "Not" is the simplest logical operator, the negation of statements is important when trying to prove that certain objects have or do not have certain properties. It makes the skill of being able to correctly negate statements an important one.

Conjunction

The conjunction of two statements $P$ and $Q$ is the statement that $P$ and $Q$ are both True. Some ways to phrase this are

$P$ and $Q$.

$P$ but $Q$.

$P$ however $Q$.

Note that phrasing in English can sometimes include meaning that is not captured by the word 'and'. For example the statement

We had a good time even though it rained.

captures the idea that the fact that it rained would lead you to expect that it would be difficult to have a good time. Logically though, the statement is equivalent to

We had a good time and it rained.

since both combine the statements

We had a good time.

and

It rained.

Examples:

First statement	Second statement	Conjunction
The hall was long.	The hall was dark.	The hall was long and dark.
All teachers are female.	All teachers are humans.	All teachers are female humans.
Mike's dog has a black tail.	Mike's dog has a wet nose.	Mike's dog does has a black tail and a wet nose.
4 is even.	6 is odd.	4 is even and 6 is odd.
Triangle ABC is equilateral.	Triangle ABC is equiangular.	Triangle ABC is equilateral and equiangular.

Conjunction combines the assertions of two statements into a single statement. It's difficult to be more specific without being circular, but you might say $P$ and $Q$ is True when both $P$ and $Q$ are True, and False when either $P$ or $Q$ are False. In tabular form:

$P$	$Q$	$P$ and $Q$
True	True	True
True	False	False
False	True	False
False	False	False

The logical symbol for conjunction is "$\land$", so you can write $P\land Q$ for $P$ and $Q$.

Disjunction

The disjunction of two statements $P$ and $Q$ is the statement that at least one of $P$ and $Q$ are True. Some ways to phrase this are

$P$ or $Q$.

$P$ unless $Q$.

In mathematics the exclusive or is never used, so

$P$ or $Q$.

always means

$P$ or $Q$ or both.

This contrasts with English where the exclusive or is often implied by context, as in

You can choose either the Big Box or whatever is behind Curtain #2.

In the rare cases where exclusive or is needed in mathematics, the phrase "but not both" can be added to make it clear.

Examples:

First statement	Second statement	Disjunction
The hall was long.	The hall was dark.	The hall was either long or dark.
Mike's dog has a black tail.	Dave's dog has a black tail.	Either Mike's dog or Dave's dog has a black tail.
4 is even.	6 is odd.	4 is even or 6 is odd.
Triangle ABC is isosceles.	Triangle ABC is scalene.	Triangle ABC is either isosceles or scalene.

Disjunction offers two possibilities which are given by the two statements. Again, it's difficult to be more specific without being circular, but you might say $P$ or $Q$ is True when either $P$ or $Q$ (or both) are True, and False when both $P$ and $Q$ are False. In tabular form:

$P$	$Q$	$P$ or $Q$
True	True	True
True	False	True
False	True	True
False	False	False

The logical symbol for disjunction is "$\lor$", so you can write $P\lor Q$ for $P$ and $Q$.

Implication

Implication is perhaps the most important, but also the most confusing of the logical connectives. In fact it even has a paradox named after it.

The implication of two statements $P$ and $Q$ is the statement is that $Q$ is True whenever $P$ is True. Some ways to phrase this are

$P$ implies $Q$.

If $P$ then $Q$.

$P$ only if $Q$.

$Q$ if $P$.

$Q$ is a necessary condition for $P$.

$P$ is a sufficient condition for $Q$.

When we use the phrase "If ... then ..." in English it usually means there is some sort of causality going on. For example the statement

If it rains the traffic will be terrible.

somehow contains the idea that the rain will cause the traffic to be terrible. But in terms of logic there doesn't have to be any such connection between the two statement. This is where the paradox, one of the 'paradoxes of material implication', comes in. Namely, if $P$ is a false statement, then the implication $P$ implies $Q$ is true, even if there is no connection between $P$ and $Q$. For example

If 0=1 then the moon is made of cheese.

is logically true even though whether the moon is made of cheese has nothing to do with whether 0 is equal to 1.

This state of affairs may seem rather strange, which is why it's called a paradox. So perhaps it would help to ask when you can say that the statement $P$ implies $Q$ is False rather than when you can say it's True. Imagine your dentist says to you

If you eat a lot of sugar then you'll get more cavities.

This is an implication between the two statements

You eat a lot of sugar.

and

You'll get more cavities.

Now suppose you want to prove your dentist wrong and say "Ha! You don't know what you're talking about. I shall seek dental care elsewhere." If you stay away from sugar and don't get cavities then your dentist will be right. If you stay away from sugar but get cavities anyway then your dentist can ask "Did you brush after eating?" and you'll say "No," and your dentist will say "There you go!" and will still be right. The only way you can prove your dentist wrong is to eat a lot of sugar but not get cavities.

This fact is actually useful in some situations and since it's logically valid there's nothing wrong with using it in a proof.

Examples:

First statement	Second statement	Implication
The hall was long.	The hall had many doors.	If the hall was long then it had many doors.
Mike's dog has a wet nose.	Mike's dog is healthy.	If Mike's dog has a wet nose then he/she is healthy.
4 is even.	6 is odd.	If 4 is even then 6 is odd.
Triangle ABC is equilateral.	Triangle ABC is isosceles.	If Triangle ABC is equilateral then it is isosceles.

As we've seen, the implication $P$ implies $Q$ is True when $P$ is false. It's also True when $Q$ is True and only false when $P$ is True and $Q$ is False. In tabular form:

$P$	$Q$	$P$ or $Q$
True	True	True
True	False	False
False	True	True
False	False	True

The logical symbol for implication is "$\implies$", though "$\supset$" is sometimes seen instead. so you can write $P\implies Q$ for $P$ implies $Q$.

Unlike $P$ and $Q$ and $P$ or $Q$, the value of $P$ implies $Q$ may change if you switch $P$ with $Q$. In other words

$P$ implies $Q$

is not always the same as

$Q$ implies $P$.

The two statements are related though and we call the statement

$Q$ implies $P$

the 'converse' of

$P$ implies $Q$

Implication plays an important role since most theorems take on the form of an implication.

Equivalence

The last connective we'll be talking about is equivalence. This one does not occur in English very often, so some of the ways of stating an equivalence may be unfamiliar. But it is important enough in mathematics that it gets its own terminology.

The equivalence of two statements $P$ and $Q$ is the statement is that $P$ and $Q$ have the same truth value. Another way of say this is that $P$ implies $Q$ and $Q$ implies $P$.

Some ways to phrase this are

$P$ is equivalent to $Q$.

$P$ if and only if $Q$.

$P$ exactly when $Q$.

$P$ iff $Q$. (iff is an abbreviation for if and only if).

$P$ is a necessary and sufficient condition for $Q$.

Examples:

First statement	Second statement	Equivalence
4 is even.	6 is odd.	4 is even iff 6 is odd.
Triangle ABC is equilateral.	Triangle ABC is equiangular.	Triangle ABC is equilateral exactly when it is equiangular.

The equivalence $P$ iff $Q$ is True when $P$ and $Q$ have the same truth values, and False when they have different truth values. In other words $P$ iff $Q$ is True when $P$ and $Q$ are both True or both False, and $P$ iff $Q$ is False is one of $P$ and $Q$ is True while the other is false. In tabular form:

$P$	$Q$	$P$ or $Q$
True	True	True
True	False	False
False	True	False
False	False	True

The logical symbol for implication is "$\iff$", so you can write $P\iff Q$ for $P$ iff $Q$.

The statement

$P$ iff $Q$

states that the implication

$P$ implies $Q$

and its converse are both true.

Complex expression

With the connectives given above we can build up more complex expressions. For example

(not $P$) or $Q$

($P$ or $Q$) and $R$

To avoid writing excessive parentheses, there are precedence rules to decide the order of operations in otherwise ambiguous expressions. The top priority is 'not', so you never need to put parentheses around 'not $P$'. Next comes 'and' and 'or' which have the same priority. Then 'implies' and finally 'iff'.

So, for example, the first example above can be written more simply as

not $P$ or $Q$

but the second example can't be simplified.

It can be shown that any logical connective in any number of variables can be expressed as some combination of the connectives given above. In fact you really only need 'not', 'and', and 'or'. We won't prove this here since it's really a theorem in logic rather than mathematics, but we can give you the basic idea by constructing an expression for exclusive or. First, list the conditions where the connective is True; in this case $P$ xor $Q$ is True when $P$ is True and $Q$ is False, or $P$ is False and $Q$ is True, and False otherwise. Now list state each condition as a conjunction, so in this case we get

$P$ and not $Q$

and

not $P$ and $Q$

Finally form the disjunction of all the statements formed in the previous step, so the final result, which we can take as the definition of $P$ xor $Q$, is

($P$ and not $Q$) or (not $P$ and $Q$)