CHAPTER 3
LOGIC
Logic is somewhat unique among branches of mathematics. In logic we do not study the world around us so much as we examine how our own minds work; a good deal of self analysis is required. Indeed it can be argued that all of mathematics begins with logic, for without some understanding of the rules of reasoning how can we engage in logical reasoning?
3A Statements
|
Does he expect |
A statement is a communication that can be classified as either true or false. The sentence “Today is Thursday” is either true or false and hence a statement; however the sentences “How are you today” and “Please pass the butter” are neither true nor false and therefore not statements. When we want to convey information we usually speak in statements, but when we want to find out information or tell someone to do something we generally switch to different modes of speech.
When we make a statement, we ordinarily intend it to be interpreted as an accurate description of reality - that is, we mean for the listener to accept the statement as true. If someone says, “My name is John”, what he completely means is that the sentence “My name is John” is true. The unspoken intention of truthfulness is implicitly understood, as otherwise it would be of no use to say anything at all. Of course there are times when we break the norm by making statements we expect to be accepted as false - as when we joke or engage in sarcasm - but in these instances our purpose is perhaps not so much to convey information but rather to affect the listener in some other way. In fact, one might say that an integral part of spoken comedy lies in breaking the rules of discourse by making obviously unbelievable statements.
example 1
The sentences below at the left are statements, while those at the right are not:
A. Hawaii lies in the Atlantic Ocean. |
|
E. Hello, Dolly. |
B. 2 + 3 = 5 |
F. Oh, my goodness! |
|
C. Tomorrow it will rain. |
G. Where is your mother? |
|
D. Life exists on Mars. |
H. Turn left at the corner. |
Observe that a statement need not be true - indeed, statement A is undeniably false, whereas B is true. Also the truthfulness of a statement may not be immediately evident. Statement C is either true or false, but we won't know which until tomorrow. Statement D will confound us even longer.
In logic it is customary to use the letters p, q, r, etc., to refer to statements. Every statement has a so-called truth value. The truth value of a true statement is true (denoted as T), and that of a false statement is false (denoted as F). Given any statement p, there is another statement associated with p, denoted as ~p and called the negation of p; it is that statement whose truth value is necessarily opposite that of p. (The symbol “~” in this context is read as “not“; thus “~p” is read “not p”.) Here are some statements with their negations immediately below them:
p : it is raining |
|
q : Gene is male |
|
r : 4 + 3 = 7 |
~p : it is not raining |
~q : Gene is female |
~r : 4 + 3 ≠ 7 |
In each case, the truth value of the statement must be opposite to that of its negation. For example, if q is true then Gene is male, so he is not female and statement ~q is false; on the other hand, if q is false then Gene is not male, so she is female and ~q is true.
|
|
The table at the left is a truth table for negation. In the left column of the table are listed the possible truth values of a general statement p, and in the right column are listed the corresponding truth values of its negation ~p.
It is not always obvious how to compose the negation of a statement. Sometimes contradictory statements are confused as negations of one another. Two statements are contradictory if not both of them can be true. For instance, the statements “Ann is 20 years old” and “Ann is 22 years old” are contradictory, as only one of them can be true; however neither is the negation of the other. Indeed, if Ann is 21 then the statements are not opposite in truth value because both are false. Often the simplest way to negate a statement is to insert the word “not” at a strategic position. The sentence “Ann is not 20 years old” is an acceptable negation of “Ann is 20 years old”.
Words like “some”, “all”, “every”, “each”, and “no” are called quantifiers. To negate statements with quantifiers requires a little extra thought. First we have to agree on what is meant by the word “some” - does it mean more than none, more than one, more than two, at least five, or what? To eliminate any ambiguity, for purposes of our logic discussion we shall hereby decree that “some” means “at least one”. This agreement is useful because it makes statements involving quantifiers a little easier to negate.
example 2
|
|
Brown |
Let us negate the statement
p : some ogres are brown .
By our agreement on “some”, the statement means that at least one ogre is brown. For the statement to be false, no ogre can be brown. Thus a candidate for the negation is
~p : no ogre is brown .
Now, if your brain is wired properly, you should agree that if p is true then ~p is false, while if p is false then ~p is true; thus our proposed negation is the correct one. One common mistake is to wrongly take as the negation of p the statement
“some ogres are not brown” .
However, this statement and p would both be true if some ogres were brown and some green.
Next we negate the statement
q : all ogres are brown .
Another common mistake is to suggest “no ogres are brown” as the negation. However, then we have only contradictory statements. Even though only one of these two statements can be true, it is possible that both could be false - as would be the case if some ogres were brown and some green. A little deeper contemplation leads to the correct negation “at least one ogre is not brown”, or, again according to our agreement on “some”,
~q : some ogres are not brown .
You should convince yourself that if q is true then ~q is false, and if q is false then ~q is true.
Below on the left are statements containing quantifiers, and on the right their negations:
STATEMENT |
NEGATION |
|
I have no bananas. |
|
I have some bananas. |
No chicken can swim. |
Some chickens can swim. |
|
Some apples are red. |
No apples are red. |
|
Bea will take at least 4 courses. |
Bea will take fewer than 4 courses. |
|
Sometimes I feel blue. |
I never feel blue. |
|
Andy is always ready to party. |
Sometimes Andy is not ready to party. |
|
Every fish has gills. |
Some fish have no gills. |
|
Sometimes Eve does not wear a hat. |
Eve always wears a hat. |
|
All maks are buly. |
Some maks are not buly. |
|
No alligator can be petted. |
Some alligators can be petted. |
|
Some hummingbirds are loud. |
No hummingbird is loud. |
|
Each of my cats catches mice. |
Some of my cats do not catch mice. |
|
|
There are not no |
As we learn in English class, double negations cancel one another. The negation of “I have bananas” is “I have no bananas”. If you say “I don't have no bananas”, then you negate the statement “I have no bananas”, and so the conclusion must be that you do have bananas. The relevant rule of logic here is expressed in the formula
~(~p) ≡ p .
|
|
The symbol “≡” means “equivalent”, and the formula asserts that the “negation of the negation” of a statement is equivalent to the original statement. Although this formula is pretty much common sense, we can officially verify it with a truth table. The table at the right has three columns; we begin with p, negate it to get ~p, and then negate again to get ~(~p). Because the columns under p and ~(~p) are identical, the statements p and ~(~p) have always the same truth value, and therefore are considered “logically equivalent” statements.
example 3
It is an entertaining exercise to begin with a statement, negate it, and then negate again, trying to obtain a statement equivalent to the original but in an altogether different form. Here are illustrations :
p : I am a vegetarian |
q : All diplomats are polite |
|
~p : I eat meat |
~q : Some diplomats are impolite |
|
~(~p): I do not eat meat |
~(~q) : No diplomat is impolite |
|
|
|
|
r : The king is dead |
s : No one is to blame |
|
~r : The king is alive |
~s : Someone is to blame |
|
~(~r): The king is not alive |
~(~s) : Everyone is blameless . |
Notice that in each case the double negation means the same as the original.
EXERCISES 3A
|
|
|
|