In modern mathematics, both the theory of proof and the derivation of theorems from axioms bear an unquestioned importance. The necessary skills behind these methods, however, are frequently underdeveloped. This book counters that neglect with a rigorous introduction that is simple enough in presentation and context to permit relatively easy comprehension. It comprises the sentential theory of inference, inference with universal quantifiers, and applications of the theory of inference developed to the elementary theory of commutative groups. Throughout the book, the authors emphasize the pervasive and important problem of translating English sentences into logical or mathematical symbolism. Their clear and coherent style of writing ensures that this work may be used by students in a wide range of ages and abilities.
Read an Excerpt
First Course in Mathematical Logic
By PATRICK SUPPES, Shirley Hill
Dover Publications, Inc.Copyright © 1964 Patrick Suppes and Shirley Hill
All rights reserved.
In the study of logic our goal is to be precise and careful. The language of logic is an exact one. Yet we are going to go about building a vocabulary for this precise language by using our sometimes confusing everyday language. We need to draw up a set of rules that will be perfectly clear and definite and free from the vagueness we may find in our natural language. We can use English sentences to do this, just as we use English to explain the precise rules of a game to someone who has not played the game. Of course, logic is more than a game. It can help us learn a way of thinking that is exact and very useful at the same time.
To begin, let us look at English sentences. Each sentence has a logical form to which we shall give a name. At first, we shall be discussing and symbolizing two kinds of sentences in logic. The names given to these two types of sentences are atomic and molecular.
In this age of science, you have seen the word atomic used many times. As a matter of fact, the meaning of the word in the language of logic is similar to its original meaning in the physical sciences. In logic, atomic refers to the simplest (or most basic) kind of sentence. If we put one or more atomic sentences together with a connecting word, then we have a molecular sentence. An atomic sentence is one complete sentence with no connecting words. We use connecting words to make molecular sentences from atomic sentences.
For example, let us consider two atomic sentences,
Today is Saturday.
There will be no school.
Both sentences are atomic sentences. By using a connecting word, we can put them together and we will have a molecular sentence. For example, we can say
Today is Saturday and there will be no school.
This molecular sentence is made up of two atomic sentences and the connecting word 'and'. When we take a molecular sentence apart, we separate it into its smallest complete atomic sentences. In the example above, we can separate the molecular sentence into the two atomic sentences. The connecting word 'and' is not a part of either atomic sentence. It is added to the atomic sentences to make a molecular sentence.
1.2 Sentential Connectives
The connecting words, small as they may be, cannot be overlooked for they are very important. In fact, we shall learn some strict rules for the use of these key words. Much of what we shall be doing in our study of logic depends upon how carefully these connecting words are used. The connecting word in the sample sentence 'Today is Saturday and there will be no school' is the word 'and'. There are others, but before we take up each word separately we should learn the correct logical name for them. That name is sentential connective. This name should be very easy to remember because it actually tells us what job the word does. It connects sentences. It makes molecular sentences from atomic sentences.
The sentential connectives we shall use in this chapter are the words 'and', 'or', 'not', and 'if ..., then.... In the study of English you may learn other names for them, but in learning logic we shall call them all sentential connectives, or just connectives. Remember that when you add a sentential connective to either one or two atomic sentences, you then have formed a molecular sentence. Three of the above connectives, 'and', 'or', and 'if ..., then ...', are used to connect two atomic sentences, but one of them is added to just one atomic sentence to make a molecular sentence. That connective is the word 'not'. We may say then that the connective 'not' controls one atomic sentence at a time and that the other connectives control two atomic sentences at a time. Remember that the connective 'not' is the only one that does not really connect two sentences. When added to just a single sentence, "not" forms a molecular sentence.
Let us look at some examples of molecular sentences that use the connectives we have named. The sentence,
The moon is not made of green cheese
is a molecular sentence that uses the connective 'not'. The connective, in this case, controls just one atomic sentence: 'The moon is made of green cheese'.
An example of a sentence using the connective 'or' is
Those clouds will be blown away or it will surely rain today.
The connective 'or' controls two atomic sentences. They are 'Those clouds will be blown away' and 'It will surely rain today'. The molecular sentence,
If this is October then Halloween is coming soon
illustrates the use of the connective 'if ..., then ...', which also controls two atomic sentences. Can you tell what those two atomic sentences are? We have already seen an example of a sentence that uses the connective 'and'. Another is
The soil is very rich and there is enough rainfall.
What are the two atomic sentences contained in this molecular sentence?
The exercises below will give you a chance to check your ability to recognize atomic sentences, molecular sentences, and sentential connectives. Remember that every sentence having a connective is molecular.
A. Write an A for each sentence that is an atomic sentence and an M for each sentence that is a molecular sentence. For each molecular sentence write the sentential connective used.
1. Lunch will be at exactly noon today.
2. The big black bear lumbered lazily down the road.
3. That music is very soft or the door is closed.
4. That big dog likes to chase cats.
5. He called for his pipe and he called for his bowl.
6. Bob is a good player or he is very lucky.
7. If Bob is a good player, then he will be on the school team.
8. California is west of Nevada and Nevada is west of Utah.
9. Many college students study logic during the first year.
10. Kittens do not usually wear mittens.
11. If kittens wear mittens, then cats may wear hats.
12. Jane can be found at Susan's house.
13. Sea lions do not grow long manes.
14. If Molly is singing, then she must be happy.
15. Sophomores do not follow freshmen in the registration schedule.
16. Jack's favorite subject is mathematics.
17. If those clouds are moving this way, then we will have rain.
18. If wishes were horses, then beggars would ride.
19. This sentence is atomic or it is molecular.
20. The sun was hot and the water looked very inviting.
21. If x = 0 then x + y = 1.
22. x + y > 2.
23. x = 1 or y + z = 2.
24. y = 2 and z = 10.
B. Make four molecular sentences by using one or two of the atomic sentences listed below together with a sentential connective. For example, you could put the connective 'and' between two of them. You may use the same atomic sentence more than once. Use each of the four connectives exactly once so that each of your molecular sentences has a different connective.
1. The wind blows very hard.
2. Paul should be able to win easily.
3. The rain may cause them to call off the race.
4. We shall know what the plans are by tomorrow.
5. There will still be time to get there by seven.
6. Jean's friend is right.
7. We were wrong about the time for the meeting.
C. Tell what the connectives are in each of the following sentences. For each molecular sentence, tell the number of atomic sentences you find in it. Remember that 'if ... then ...' is a single connective.
1. This is not my lucky day.
2. The winter is coming and the days grow shorter.
3. Many germs are not bacteria.
4. Amphibians are found in fresh water or they are found on land near moist places.
5. If there are fractures in great rock masses then earthquakes are likely to occur.
6. That number is greater than two or it is equal to two.
7. If it is a positive number then it is greater than zero.
8. This boy is my brother and I am his sister.
9. My score is high or I shall get a low grade.
10. If you hurry then you will be on time.
11. If x > 0 then y = 2.
12. If x + y = 2 then z > 0.
13. x = 0 or y = 1.
14. If x = 1 or z = 2 then y > 1.
15. If z > 10 then x + z > 10 and y + z > 10.
16. x + y = y + x.
D. First make up five atomic sentences and then make up five molecular sentences.
1.3 The Form of Molecular Sentences
The rules for the use of the sentential connectives are the same no matter what atomic sentences they connect or with what atomic sentences they are used. In one of the last exercises you found that it was possible to choose any one or two of a group of atomic sentences and combine them with a connective. The form of the molecular sentences that you made up depended upon the connective you chose, not upon what was in the atomic sentence or sentences. In other words, if you replace the atomic sentences in a molecular sentence with any other atomic sentences the form of the molecular sentence will remain the same. The way the 'if ..., then ...' connective is written shows this clearly. The three dots after 'if' and the three dots after 'then' stand in place of sentences. To form a molecular sentence using that connective you can simply put atomic sentences, any atomic sentences, in place of the dots.
It is easy to see the form of a molecular sentence if we do not write out the atomic sentences but just show where they belong. We can show the form of a molecular sentence using the 'and' connective as
( ) and ( )
Any sentences can be put in the spaces and the form is the same. Suppose we chose the two atomic sentences 'It is red' and 'It is blue'. Filling in the spaces above, we have the molecular sentence, 'It is red and it is blue'. We might have chosen two other atomic sentences and formed, for example, the sentence, 'I am tall and he is small'. The form remains the same. It is a molecular sentence using the connective 'and'. Another way of emphasizing the form is to leave the parentheses in the English sentence, as in the following sentences:
(It is red) and (it is blue).
(It is raining) and (Peter is wet).
We have said that we can fill in the spaces with any sentences. We are not limited to just atomic sentences. We can also use molecular sentences and the form is the same. For example, we can fill the first space with the molecular sentence, 'John is not here' and the second space with the molecular sentence 'Herb is not here'. The sentence will then be
John is not here and Herb is not here.
Again, the form is the same. The connective 'and' connects two sentences but this time they are molecular sentences.
We could also have used one molecular sentence and one atomic sentence, as in
John is not here and Joe is here.
The important point is that whatever sentences we use to fill the spaces shown, the form of the sentence is that of a molecular sentence using the connective 'and'.
This is true of the other connectives too. We might show the form of other types of molecular sentences as follows:
( ) or ( )
If ( ) then ( ).
We can fill the spaces with any sentences, atomic or molecular. The following are examples, some of which have parentheses included for emphasis.
Mary is here or Helen is home.
(John is in town) or (Mary is not at home).
If 2 + 3 = x then x = 5.
If (y + 1 = 4) then (y = 3).
If (Bill is not dishonest) then (John is honest).
Sometimes, in English sentences, we use one word for a particular connective, sometimes we use two or more. For instance, we can use the single word 'or' as a connective as in
It is very heavy or it is hollow.
We might also write the same sentence adding the word 'either' as a part of the connective.
Either it is very heavy or it is hollow.
The words 'either' and 'or' are both part of the connective. In English sentences we sometimes use 'either-or' and sometimes just 'or'. When we refer to the connective 'or' we know that this may also include the word 'either', if we choose to use it. The form for the connective 'or', therefore, may be
Either ( ) or ( ).
The following examples are of this form.
Either John is here or it is not raining.
Either (Mary is not here) or (Susan is not here).
Either x + y = 6 and y = 2, or x = 0.
Either (x + y = 7 and y ≠ 2) or (x > 0).
In some cases, we may wish to include the word 'both' in addition to 'and' as a way of using the 'and' connective. For example, we can say
Both it is raining and the sun is shining.
The words 'both' and 'and' are parts of the connective. We usually just use 'and' but you may find the word 'both' included occasionally. We shall refer to the connective as 'and', but the form may be seen as
Both ( ) and ( ).
Both (x > 0) and (y ≠ 0).
Both x ≠ y and y ≠ z.
In most cases in which the connective 'if ..., then ...' is used, both words are included. Sometimes, however, you may find that the word 'then' is eliminated. An example might be
If it is Dan, he is late.
Sentences of this kind are formed by the 'if ..., then ...' connective and are of the form
If ( ),( ).
Examples of this form are
If x + y = 2 and y = 0, x = 2.
If (x + y = 7 and x =6), (v = 1).
If Mary loves John, John loves Mary.
The word 'not' is found most often within the atomic sentence in English. For this reason it is easy to overlook. But a sentence such as
Logic is not difficult
is a molecular sentence because it contains 'not'. It is possible to write the connective using the phrase 'it is not the case that'. The sentence then would read
It is not the case that logic is difficult.
Thus it is possible to show the form of the molecular sentence using the connective 'not' as
It is not the case that ( )
or we may shorten it to
not ( ).
Examples of this form are
It is not the case that (x = 0).
It is not the case that (x + y > 2).
Not (x = 2 + 1).
Not (7 >x + y).
The use of 'Not ( )' is not ordinary English usage, of course, but it is often convenient, as we shall see later in mathematical contexts.
In mathematical sentences using the equality symbol = we often indicate negation by a slant line through the equality symbol: ≠. Thus, 'x ≠ 1' is read 'x is not equal to 1'.
In neither of the sentences 'x ≠ 1' and 'John is not here', can we use parentheses to show the form of the molecular sentence because the connective 'not' occurs inside the atomic sentence.
A. Use parentheses to show the form of the following molecular sentences.
1. John is here and Mary has left.
2. If x+ 1 = 10 then x =9.
3. Either Mary is not here or Jane is gone.
4. If either x = 1 or y = 2 then z = 3.
5. If x ≠ 1 and x + y = 2 then y = 2.
6. If either Smith is at home or Jones is in court then Scott is innocent.
7. y = 0 and x = 0.
8. Either y = 0 and x ≠ 0 or z = 2.
9. It is not the case that 6=7.
10. It is not the case that if x + 0 = 10 then x = 5.
B. Write English sentences in the following forms. Drop the parentheses when you write the English sentences.
1. Either ( ) or ( ).
2. ( ) or ( ).
3. Both ( ) and ( ).
4. ( ) and ( ).
5. Not ( ).
6. If ( ) then ( ).
7. If ( ), ( ).
8. If not ( ) then not ( ).
9. It is not the case that ( ).
1.4 Symbolizing Sentences
We often think of atomic sentences as short sentences. But even some of the atomic sentences in our everyday language are long and for this reason they become clumsy and awkward to handle. In logic we take care of this problem by using symbols in place of, or to stand for, entire sentences.
Excerpted from First Course in Mathematical Logic by PATRICK SUPPES, Shirley Hill. Copyright © 1964 Patrick Suppes and Shirley Hill. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
1. Symbolizing Sentences
1.2 Sentential Connectives
1.3 The Form of Molecular Sentences
1.4 Symbolizing Sentences
1.5 The Sentential Connectives and Their SymbolsOr; Not; If . . . then . . .
1.6 Grouping and Parentheses. The Negation of a Molecular Sentence
1.7 Elimination of Some Parentheses
2. Logical Inference
2.2 Rules of Inference and Proof
Modus Ponendo Ponens
Modus Tollendo Tollens
More on Negation
Adjunction and Simplification
Disjunctions as Premises
Modus Tollendo Ponens
2.3 Sentential Derivation
2.4 More About Parentheses
2.5 Further Rules of Inference
Law of Addition
Law of Hypothetica Syllogism
Law of Disjunctive Syllogism
Law of Disjunctive Simplification
De Morgan's Laws
2.6 Biconditional Sentences
2.7 Summary of Rules of Inference. Table of Rules of Inference
3. Truth and Validity
3.2 Truth Value and Truth-Functional Connectives
Equivalence: Biconditional Sentences
3.3 Diagrams of Truth Value
3.4 Invalid Conclusions
3.5 Conditional Proof
3.7 Indirect Proof
4. Truth Tables
4.1 Truth Tables
4.3 Tautological Implication and Tautological Equivalence
5. Terms, Predicates, and Universal Quantifiers
5.4 Common Nouns as Predicates
5.5 Atomic Formulas and Variables
5.6 Universal Quantifiers
5.7 Two Standard Forms
6. Universal Specification and Laws of Identity
6.1 One Quantifier
6.2 Two or More Quantifiers
6.3 Logic of Identity
6.4 Truths of Logic
7. A Simple Mathematical System: Axioms for Addition
7.1 Commutative Axiom
7.2 Associative Axiom
7.3 Axiom for Zero
7.4 Axiom for Negative Numbers
8. Universal Generalization
8.1 Theorems with Variables
8.2 Theorems with Universal Quantifiers