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

NegationEdit

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.

ConjunctionEdit

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  .

DisjunctionEdit

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  .

ImplicationEdit

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.

EquivalenceEdit

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 expressionEdit

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