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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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 and denote mathematical statements.

Negation[edit | edit source]

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

Not .
It is false that .

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 is False when is True, and Not is True when is False. In tabular form:

Not
True False
False True

The logical symbol for negation is "", so you can write for Not .

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[edit | edit source]

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

and .
but .
however .

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 and is True when both and are True, and False when either or are False. In tabular form:

and
True True True
True False False
False True False
False False False

The logical symbol for conjunction is "", so you can write for and .

Disjunction[edit | edit source]

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

or .
unless .

In mathematics the exclusive or is never used, so

or .

always means

or 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 or is True when either or (or both) are True, and False when both and are False. In tabular form:

or
True True True
True False True
False True True
False False False

The logical symbol for disjunction is "", so you can write for and .

Implication[edit | edit source]

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 and is the statement is that is True whenever is True. Some ways to phrase this are

implies .
If then .
only if .
if .
is a necessary condition for .
is a sufficient condition for .

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 is a false statement, then the implication implies is true, even if there is no connection between and . 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 implies 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 implies is True when is false. It's also True when is True and only false when is True and is False. In tabular form:

or
True True True
True False False
False True True
False False True

The logical symbol for implication is "", though "" is sometimes seen instead. so you can write for implies .

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

implies

is not always the same as

implies .

The two statements are related though and we call the statement

implies

the 'converse' of

implies

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

Equivalence[edit | edit source]

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 and is the statement is that and have the same truth value. Another way of say this is that implies and implies .

Some ways to phrase this are

is equivalent to .
if and only if .
exactly when .
iff . (iff is an abbreviation for if and only if).
is a necessary and sufficient condition for .

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 iff is True when and have the same truth values, and False when they have different truth values. In other words iff is True when and are both True or both False, and iff is False is one of and is True while the other is false. In tabular form:

or
True True True
True False False
False True False
False False True

The logical symbol for implication is "", so you can write for iff .

The statement

iff

states that the implication

implies

and its converse are both true.

Complex expression[edit | edit source]

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

(not ) or
( or ) and

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 '. 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 or

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 xor is True when is True and is False, or is False and is True, and False otherwise. Now list state each condition as a conjunction, so in this case we get

and not

and

not and

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 xor , is

( and not ) or (not and )