is irrational.II: |
THE STATEMENT |
If the notion is held that validity is a matter of form rather than a matter of meaning, then in investigating questions of validity it is reasonable to use a symbolism that indicates form alone. With a suitable symbolic language we can hope to lay bare the formal structure of argument without being distracted by particular meanings.
For example, let “P” be a translation of the statement
P: All men are mortals.
“P” can be considered a statement of relationship between two classes; that is, the class of men and the class of mortals. The words “all” and “are” indicate the relation, while the words “men” and “mortals” are names for the classes so related.
Consider now the expression
P*: All x are y.
Unless “x” and “y” are names of known classes, the expression “P*” is in a sense meaningless. For instance, it makes no sense to assert that “P*” is true, or that it is false. However, if “a” and “y” in “P*” are taken to be placeholders for class names, then “P*” can serve to indicate a type of statement form. The statement “P” has this form. The first statement of the second argument on page 5 also has the form of “P*”. In fact, you can obtain it from “P*” by replacing “x” by the name “people who like classical music” and “y” by the name “baseball players”.
An expression such as “P*” that employs symbols “x” and “y” as placeholders for class names is called a propositional function with variables x and y. Such propositional functions will be considered in Chap. V. For the present, we shall restrict ourselves to the simpler question of relationships between statements considered as units. Capitals “P”, “Q”, “R”,… will be used as translations of complete statements. No attempt will be made in the notation to indicate the internal structure of a statement unless it is a compound of simpler statements.
With this restriction we shall be unable to handle even such a simple argument as is represented by the Socrates Argument, page 5, since the validity of such an argument depends on subject and predicate relations that require the logic of propositional functions for analysis. Even so, we shall be able to express formally many arguments.
For the present, we take a statement in its simplest form to be a simple declarative sentence that is either true or false, but not both. For our purposes, the statement
Smith is intelligent
can be recast in the form
Smith is an intelligent man.
That is, the individual “Smith” is asserted to be a member of the class “intelligent men”. In a similar fashion, the statement
All bats fly
can be recast in the form
All bats are animals that fly.
That is, it is asserted that the class “bats” is included in the class “animals that fly”.
It is not easy to give criteria for determining when two statements assert the same proposition. The foregoing restatements may not express the exact shades of meaning of the original statements, but the difference is not serious, and the restated forms are easier to deal with formally. Such restatements work out well enough in formal analysis of mathematical statements. In what follows, we shall always consider the simple statements used to mean assertions of class inclusion even though they may not appear in that form.
Each of the following statements illustrates a different relationship between subject and predicate.
1. Washington was the first president of the United States.
2. Washington was wise.
3. Washington was crossing the Delaware.
4. Washington was a soldier.
In (1), the relationship expressed is that of identity; in (2), that of subject and attribute; in (3), that of agent and action; in (4), that of inclusion of an individual in a class. The statements in (2), (3), (4) are readily recast as statements of class inclusion. In (1), it is asserted that “Washington” and “the first president of the United States” are names of the same thing or object. We do not attempt to restate this in terms of class inclusion, and shall avoid statements of this type for the moment.
We have described the simplest statements as simple declarative sentences. We shall also wish to regard as statements, compounds of simple statements formed by using connective words such as “and”, “or”, “if ______ then______”. In what follows we shall try to develop a precise symbolic language for expressing such composition as a purely formal operation.
EXERCISES
List the individual and the class, for each of Examples 1 to 6. Put these under column headings of Individual and Class.
1. Eagles are animals that fly.
2. President Lincoln was an intelligent man.
3. Saturday is a day of the week.
4. 8/9 is a rational number.
5. Doctors are good reasoners.
6. The sum of 6 and —7 is an integer.
Recast each of Examples 7 to 14 as a statement of class inclusion. For example, “All bats fly” could be recast as “The class of bats is included in the class of animals that fly”.
7. John is a high school student.
8. Triangle ABC is isosceles.
9. The number is irrational.
10. A quadrilateral with two pairs of parallel sides is a parallelogram.
11. All real numbers are complex.
12. Any teacher is an educator.
13. Each state is in the Union.
14. Circles are conics.
The negation of a statement is formed by means of the word “not”. If “P” is a translation of a statement, then the negation of the statement is translated “
P”. “P” is read “not-P”; the symbol “” is called “curl” or “twiddle” or “tilde”. (The notion of “P” is that of asserting the falsity of “P”. If, indeed, “P” is considered to be false, then “P” will be considered to be true. If “P” is a translation of
New York is a city,
then “P” is translated
Not, New York is a city.
In everyday language, the negative particle “not” is generally associated with the verb. Consequently, a restatement of “P” in everyday language would read
New York is not a city.
In making such restatements, we want to be sure that the statement and its restatement assert the same proposition. For simple statements, the correct and natural restatement is easily discovered, but care must be taken with statements containing the quantifying words “all” and “some”.
Consider the problem of restating in natural language the negation of
Q: All integers are real numbers.
Then, for the negation of “Q” we have
Q: Not, all integers are real numbers.
To recast “Q” in the form “All integers are not real numbers” is at the least ambiguous. The ambiguity becomes apparent upon reading the sentence, first stressing the word all, then stressing the word not The meaning in the first reading is expressed by the statement
V: Some integers are not real numbers.
For the second reading, the meaning is expressed by the statement
W: No integers are real numbers.
Since it is quite clear that “V” and “W” do not assert the same proposition, they cannot both be correct restatements of “Q”. According to our definition of negation, “Q” must be opposite in its truth value to “Q”. Any correct restatement of “Q” must also have this property. The statement “W” fails this test, for while “Q” and “W” cannot possibly both be true, they can conceivably both be false. Indeed, both statements would be false if it were the case that there is exactly one integer which is not a real number. However, if “V” is tested in the same way, it is found to have the required properties, and may be taken as a correct restatement of “Q”.
The form “All ______ are not ______” is seen to be ambiguous. Its meaning depends upon vocal stress, or on context. Such a form should be avoided in mathematics and in logic.
As another example of the problem of restatement, consider
S: All angles can be trisected using straightedge and compass alone.
This statement is known to be false. Some students, knowing that “S” is false, jump to the conclusion that you can’t trisect an angle. By this they mean
U: No angle can be trisected by using straightedge and compass alone.
But “U” is known to be false, and thus cannot be a correct restatement of “S“. Since both “S” and “U” are false, according to our notion of negation, “S” and “U” are true statements. As was seen in the previous example concerning integers and real numbers, a correct restatement of “S” is
Some angles cannot be trisected using straightedge and compass alone.
Another common restatement of “S” is
There exists at least one angle that cannot be trisected by using straightedge and compass alone.
It is a standard demonstration of higher algebra that an angle of 120° is such an angle.
“U” is correctly translated
Not, no angle can be trisected by using straightedge and compass alone,
which is grammatically very awkward. It is better to use the restatement
Some angles can be trisected by using straightedge and compass alone;
or the form
There exists an angle that can be trisected by using straightedge and compass alone.
Angles of 90° and 180° are such angles.
Write a grammatical restatement of the negation of each of the following sentences.
1. Chicago is the Windy City.
2. John is not at his home.
3. Solid geometry does not exist as a separate course.
4. This textbook has many exercises.
5. a || b
6. All rational numbers are real.
7. Some cats are black.
8. Some pairs of lines in a plane are parallel.
9. No imaginary numbers are real.
10. All people are intelligent.
11. No slow learners attend this school.
12. All courses overlap.
13. None of us may go.
14. Some of these references are not relevant to my subject.
15. Some triangles are not isosceles.
16. All brilliant persons are teachers.
17. No employees are honest.
18. Some unpleasant statements are not true.
19. All fractions with a common denominator are added by writing the sum of the numerators over the common denominator.
20. Some students write skillfully.
21. Some complex numbers are imaginary numbers.
22. None of us is perfect.
23. Only members are admitted to the club.
The conjunction and is commonly used to combine sentences and phrases to form larger sentences. Similarly, the ampersand symbol “&” is used in logic to form the statement “A&B” from the statements “A” and “B”; “A&B” is read “A and B” or “the conjunction of A and B”.
In translating into symbolic form, care must be taken that the symbols “A” and “B” are indeed translations of statements. For the statement
The number twelve is rational and positive,
a translation directly into symbols is not possible since the word “positive” is not a statement. If the statement is changed to the form
The number twelve is rational and the number twelve is positive,
then a direct translation is clearly “A&B” where “A” and “B” are the translations:
A: The number twelve is rational.
B: The number twelve is positive.
If “P” and “Q” are statements, then we say that the conjunction “P&Q” is a statement that is true in case both “P” and “Q” are true, and that in all other cases the conjunction is false.
From this definition it follows that the truth of “P&Q” is dependent solely on the truth values of “P” and “Q”, and not on any other relationships that might exist between “P” and “Q”.
Normally, good English usage requires that the parts of a conjunction have some relation to each other. There appears to be no good reason for making a conjunction of the statements “Euclid is dead” and “Twelve is an integer” because they have no discernible relation beyond being both true. But to give precise criteria for distinguishing between acceptable and unacceptable conjunctions seems quite difficult. The problem is avoided in logic by permitting conjunction of any two statements. This latitude in the use of “&” permits some odd looking translations to occur, but does no harm. In practice, the use of “&” is quite parallel to the use of “and” in ordinary discourse. The situation with respect to the disjunction “or” is not so satisfactory.
The disjunction “or” is used to connect two clauses or sentences to form a larger sentence. The meaning of this connection seems generally to be dependent on the meanings of the parts connected. For example,
He will succeed or die in the attempt.
A simple closed curve in the plane divides it into two regions such that any point not on the curve is either inside or outside the curve.
He’ll have to fish or cut bait.
In these sentences the use of “or” is clearly meant to be exclusive; that is, the two assertions connected by “or” are to be considered mutually exclusive. This exclusive use of the word “or” as an indication of a clear alternative is the only one sanctioned by Webster’s New International Dictionary,1 but one can find many common examples of the nonexclusive use of “or”.
Consider the following example taken from a sign on a private pond:
Residents or women may fish here without permits.
Does this sign mean what it seems to say? Would a person who is both a woman and a resident need a permit to fish? That would be the implication of the sign if its designer intended the “or” to be taken in the exclusive sense. This is clearly not the intent. In this sentence the word “or” is used in the inclusive sense. We might dismiss this as an example of poor English, since the meaning can be conveyed by the correct construction:
Residents and women may fish here without permits.
However, if the sign had read
Any person who is a resident or a woman may fish here without a permit;
then, while the “or” is again used inclusively, it cannot be changed to “and” without radically altering the intended meaning of the sentence.
In the sentence
You will damage the motor if you run it when too low on oil or water,
the intended meaning is conveyed by the inclusive “or”. Again, to replace “or” by “and” would alter the intended meaning. Perhaps the meaning might best be conveyed in this case by using the awkward hybrid “and/or”.
In the foregoing examples, the meaning of the “or” is clear enough, but its meaning is dependent on context. The ambiguity of “or” in the English language is not unique among Western languages. The French “ou”, the German “oder”, the Russian “ili” have much the same ambiguity—that is, they take their meaning partly from context. In Latin, “aut ______ aut ______” was used to indicate the exclusive “or”, while “vel” was used to indicate the inclusive “or”. In English, perhaps the closest we can come to the Latin “vel” is the awkward “and/or” sometimes used in commercial and legal documents. The unhappy construction “A or B, or both” is also used to convey the sense of the inclusive disjunction.
In a symbolic logic, a symbol for disjunction is needed that is independent of context. Because “or” is commonly used in the inclusive sense in mathematics, we choose this usage for the symbolic logic. The symbol “v”, from the Latin “vel”, is used to represent the inclusive “or”.
If “P” and “Q” are statements, then “P∨Q” is a statement that is true either when “P” is true or “Q” is true or both are true. “P∨Q” is false only when both “P” and “Q” are false.
Suppose that “P” is a translation for “Euclid is dead” and “Q” is a translation for “The sum of 2 and 3 is 8”. Then “P∨Q” is a statement, and a true one if we agree that “P” is true. In ordinary conversation two such unrelated statements as “P” and “Q” are seldom combined in a disjunction. However, no harm is done in permitting such examples to appear in the logic, and thereby we avoid the problem of defining the closer relationship between the two parts of a disjunction that seems desirable in ordinary discourse.
It is not necessary to have a special symbol to translate the exclusive “or”, since there are a number of ways to express this disjunction by means of symbols already introduced. Taking “A” and “B” as statements, form the expression
(2.1) (A ∨ B) & ((A & B)).
First, “A∨B” is a statement [definition of “∨”]. “A&B” is also a statement [definition of “&”]; therefore, “(A&B)” is a statement [definition of “”]. Hence, finally, the expression (2.1) is a statement [definition of “&”]. Second, if we check the statement (2.1) with the definitions of the truth values of the compounds appearing in it, there are the following cases to consider:
a. If “A” and “B” are true, then “A∨B” is true and “(A&B)” is false, so that the conjunction (2.1) is false.
b. If “A” and “B” are both false, then “A∨B” is false and “(A&B)” is true, so that the conjunction (2.1) is again false.
c. If “A“ and ”B” are opposite in truth value, then “A∨B” and “(A&B)” are both true, so that their conjunction (2.1) is true.
In summary, the expression (2.1) is a statement that is true if, and only if, one of the statements “A”, “B” is true and the other is false. This is just the notion of an exclusive disjunction.
In the same way, it can be verified that the statement
[A & ( B)] ∨ [( A) & B].
also expresses an exclusive disjunction.
EXERCISES
1. Take the following symbolic translations:
P: x is an irrational number.
Q: x is a complex number.
Write a translation for each of the following statements:
a. x is not an irrational number.
b. x is not a complex number.
c. x is an irrational and complex number.
d. x is an irrational or a complex number.
2. Take the following symbolic translations:
R: ABC is a triangle.
S: ABC is equilateral.
Write a translation for each of the following statements:
a. ABC is not a triangle.
b. Not, ABC is equilateral.
c. ABC is a triangle or ABC is equilateral.
d. ABC is an equilateral triangle.
e. ABC is a triangle or ABC is equilateral, but not both.
For each of the following sentences, express as many symbolic translations as are necessary, as in Examples 1 and 2, and write a translation of the sentence. Translate “or” in the inclusive sense.
3. x is a real and complex number but is not irrational.
4. x is an irrational number or a rational number.
5. James is a married man.
6. y is not isosceles or y has two equal angles. (Here it is to be understood that “y” is the name of a triangle.)
7. y is not a triangle or y is not isosceles or y has two equal angles.
8. a/sin A = b/sin B = c/sin C. (This is a common type of abbreviation in mathematics, and always represents a conjunction of statements of equality.)
9. It is not the case that, all roses are red and all violets are blue.
10. Some roses are not red or some violets are not blue.
11. It is not the case that x is a real number and x is an imaginary number.
12. x is not a real number or x is not an imaginary number.
13. y is a parallelogram or y is a rectangle.
14. It is not the case that y is a parallelogram or y is a rectangle.
15. y is not a parallelogram and y is not a rectangle.
1 Webster’s New International Dictionary of the English Language, second edition, unabridged. Springfield, Mass.: G. & C. Merriam Company, 1952.
We cannot easily deal with the logical structure of mathematical arguments without some convenient symbolism for translating statements of the “if ______ then ______” type. Suppose that “x” and “y” represent certain angles and that “A” and “B” are translations as follows:
A: x and y have their sides parallel.
B: x = y.
Our symbolism must easily translate such statements as
(2.2) If x and y have their sides parallel, then x = y,
and
x and y having their sides parallel implies that x = y.
We translate these conditional statements by “A → B”. We refer to “→” as the implication or the conditional symbol, and read it “implies” or sometimes “only if”. In the conditional “A → B”, “A” is called the antecedent and “B” is called the consequent.
We define formally: if “P” and “Q” are statements, then “P → Q” is a statement; “P → Q” is a true statement unless “P” is true and “Q” is false, in which case it is a false statement.
Consider this definition of the conditional in relation to the statement (2.2), which was translated “A → B”. Note that (2.2) is not intended as a general statement about all pairs of angles x and y, but is a statement about two particular angles whose names are “x” and “y”. If the angles are as pictured in Fig. 1, then by the foregoing definition, “A → B” is a true statement since both “A” and “B” are true statements. For the angles pictured in Fig. 2, the statement “A → B” is also true by the definition, even though “A” is false and “B” is true. For angles as pictured in Fig. 3, “A → B” is a false statement since “A” is true and “B” is false. Finally, for the angles pictured in Fig. 4, “A → B” is a true statement by the definition, even though both “A” and “B” are false.
FIG. 1. Two angles of 45° with their sides parallel, left side to left side and right side to right side.
FIG. 2. Two angles x and y of 30°, but with their sides not respectively parallel.
FIG. 3. Two angles x = 30° and y = 150° with their sides parallel left side to right side and right side to left side.
FIG. 4. Angles x = 30° and y = 60° such that no sides are parallel.
The definition of the conditional and the illustrations of its four cases are not in conflict with ordinary usage, but some of the true cases may appear strange because one does not ordinarily assert conditionals in which the antecedent is known to be false. However, as with the connectives previously considered, we want the truth value of the conditional to be defined for all the ways in which truth values can be assigned to its component statements. The unfamiliar cases may be regarded as merely supplementing ordinary usage of the conditional.
An example that makes the four cases of the conditional seem more comfortable comes from consideration of the following assertion. Your friend agrees,
If it is raining, then I shall drive you home.
We use the following translations.
P: It is raining.
Q: He drives you home.
P → Q: If it is raining, then he drives you home.
The question is, under what conditions would you be angry with your friend?
If the situation is such that it is raining and he drives you home, then you are satisfied. In short, if “P” is true and “Q” is true, you are quite at ease with the notion that “P → Q” is true. On the other hand, suppose it is not raining but your friend does drive you home. Would you have cause to be angry with him? No, because that was not the agreement in the first place. So you are still willing to accept “P → Q” as true, even though “P” is false and “Q” is true. Now, suppose it is raining and he does not drive you home. Then you will be angry; you are quite willing to accept “P → Q” as false in this case, “P” being true and “Q” being false. The fourth case, when it is not raining and your friend does not drive you home, leaves you with no cause for anger since that was the agreement all along. That is, you accept “P → Q” as true (no anger) when “P” is false and “Q” is false.
It is particularly in the case of the conditional that one normally expects some relationship to exist between the antecedent and the consequent. In ordinary discourse the true conditional “(Euclid is dead) → (2 + 3 = 5)” is ridiculous because of the lack of any sensible relationship between the death of Euclid and the sum of 2 and 3. Such conditionals are permitted in the logic for the same reason they are permitted in comparable combinations involving “&” and “∨”.
The latitude permitted in statements connected by “&“, “∨”, and “→” certainly makes these connectives weaker than the connectives “and”, “or”, and “implies” of ordinary discourse. Yet the logical connectives are strong enough for the purposes of mathematics, and have the advantage of precise definition, which the connectives of ordinary discourse do not.
The symbols so far introduced are adequate to deal with relations between mathematical statements as long as we do not attempt to investigate subject and predicate relations. Indeed, not all of “”, “&”, “∨”, “→” are needed. Frege1 developed a statement calculus using just the symbols “→” and “”, while Russell1 did so using the symbols “” and “∨”. Sheffer2 gives an example of a statement calculus using a single symbol, not, however, equivalent to any symbol we have discussed. We shall continue to use all the symbols so far introduced, and perhaps even others, as a matter of convenience. To do so involves us in less complicated expressions and circumlocutions than would be the case if we limited ourselves to the symbols of Frege or Russell.
The dependence of the truth of compound statements upon the truth values of the statements occurring in them may be summarized in a truth table as follows:
In the first two columns are listed the truth values assumed for the statements “A” and “B”, while the succeeding columns list the corresponding truth values of the statements heading them. Of the four illustrations of the conditional (2.2), each corresponds to one of the rows of the truth table (2.3), where in this case the third, fourth, and fifth columns are ignored.
The connectives “&”, “∨”, and “→” are binary connectives; that is, they are used to combine statements two at a time. The connective “” is always applied to a single statement, and is thus singulary. It is important to understand the dual nature of the definition of each of these symbols. In the first place, combining two statements by a binary connective produces a statement, and applying “” to a statement produces a statement. In the second place, the truth of a binary compound is uniquely determined by the truth of its component statements, and the truth value of a negation is uniquely determined by the truth value of the statement negated. The truth table (2.3) summarizes this second aspect of the definitions.
1 Gottlob Frege, Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens, Halle: Nebert, 1879; or Philosophical Writings of Gottlob Frege, collected and translated by P. Geuch and M. Black, New York: Philosophical Library, Inc., 1952.
1 Bertrand Russell, Introduction to Mathematical Philosophy, pp. 144–150, New York: The Macmillan Company, 1919.
2 H. M. Sheffer, “A Set of Five Independent Postulates for Boolean Algebras, with Application to Logical Constants,” Transactions of the American Mathematical Society, vol. 14, pp. 481–488, 1913.
At this point, one cannot conclude that the expression “P&Q∨R” is a statement, even if it is known that “P”, “Q”, and “R” are statements. That “(P&Q)∨R” is a statement follows easily from the definitions. If “P” and “Q” are statements, then so is “P&Q”. The parentheses are used to indicate that “(P&Q)∨R” is a disjunction of the statements “P&Q” and “R”; thus “(P&Q)∨R” is a statement. “P&Q∨R” can be regarded as unpunctuated. When it is punctuated by parentheses as indicated, it becomes a statement. Other punctuations are possible. “P&(Q∨R)” is a statement, but “(P&(Q∨)R)” and “[P&(Q]∨R)” are not.
An expression is considered well formed if it can be built up by a finite number of applications of the binary and singulary operations as indicated by the parentheses appearing in it.
Recall that the negation symbol is always applied to a single statement, so that while “P&[(Q∨R)]” is properly formed, “P&[Q(∨R)]” is not.
If it is desired to express the form of the statement “(P&Q)∨R” without any reference to the meanings of its component statements, one might try the expression “(______&______)∨______”, where the blanks are looked upon as placeholders for statements. The expression is clearly not itself a statement, but may be regarded as the skeleton of a statement.
That there are drawbacks to this method of expressing the form of a statement by means of a skeleton is illustrated in the following example.
John is married and Jane is his wife, or
(2.4) John is married and Jane is his sister.
The statement (2.4) has for skeleton
(2.5) (_____ & ___)∨(___ & ___).
If the skeleton (2.5) truly expresses the form of (2.4), then the replacement of the blanks by any statements whatever should result in a statement having the same form as (2.4). What the skeleton does not indicate is the necessity of replacing the first and third blanks with the same statement in order to get a statement in the same form as (2.4). One might try to cope with this problem by using different colors, or numerical subscripts, for the blanks of the skeleton. On the whole, it seems simpler just to write
(2.6) (P&Q)∨(P&R),
to indicate the form of (2.4) and to regard the letters “P”, “Q”, “B” not as translations of any of the component statements of (2.4), but merely as placeholders for any statements whatever.
The expression (2.6) is called a statement formula. It is not itself a statement, but it does indicate how a statement could be constructed from three given statements. In general, a statement formula is an expression composed of placeholder symbols, parentheses, and connective symbols that becomes a properly formed statement when the placeholders are replaced by properly formed statements.
If a placeholder “P” appears more than once in a statement formula, then in building a statement in the corresponding form, the same statement must replace “P” wherever it occurs. However, there is no requirement to replace different placeholders by different statements.
If, from three given statements, a statement is constructed in the form of
(2.7) (P&Q)∨R,
then the truth of the resulting statement will usually depend on the truth values of the three given statements. The truth value can be computed with the help of the truth table (2.3). Suppose that the truth values of the statements replacing “P”, “Q”, “R” are, respectively, “F”, “T”, “F”; that is, false, true, false. From the second row of the truth table, it is found that “P&Q” is replaced by a false statement. Hence, the constructed statement is a disjunction of a false statement and a false statement. Therefore it is false, as indicated by the fourth row of the truth table.
The truth value of any properly formed statement can be determined in the foregoing abbreviated manner. However, it is usually convenient to carry out such computations in tabular form. In the following truth table, the eight different ways truth values may be assigned in (2.7) are shown in the first three columns, and the last column shows the corresponding truth values assumed by (2.7).
The sixth row of this truth table summarizes the analysis of (2.7) carried out in the preceding paragraph.
EXERCISES
Construct a complete truth table for each of the following statement formulas:
1. R&(R)
2. [R&(R)]
3. R&(S)
5. P&(Q∨R); compare your table with the one on page 32.
6. (P → Q) → R
7. (P → Q) → Q; compare with Exercise 6 and with the table for A∨B in (2.3).
8. (R∨S)&[(R&S)]
9. [R&(S)]∨[(R)&S]; compare with the table for Exercise 8.
10. (P&Q) →P
For the statement formula,
(2.8) (P → Q)&(Q → P),
the associated complete truth table is:
If “P” and “Q” are statements, then (2.8) is a statement. From the truth table we see that “(P → Q)&(Q → P)” is true if “P” and “Q” have the same truth values and is false if “P” and “Q” have opposite truth values.
It is convenient to introduce “P ↔ Q” as an abbreviation for the statement formula (2.8). “P ↔ Q” is read “P equivalent Q”. In table form we have:
Note that, if for two statements “P” and “Q” it is known that “P ↔ Q” is true, it does not follow that the two statements are identical, or that they assert the same proposition. All that can be said is that the two statements have the same truth value.
With the symbolism already introduced, we can interpret some of the language used in mathematics. If “P” and “Q” are statements, we know that “P → Q” is a statement. We have called “P → Q” a conditional and have read it “P implies Q”. There are other ways of reading the conditional that are often used in mathematical writing. Some of these synonymous ways follow; remember each one would be translated as “P → Q”:
“Q” is a necessary condition for “P”.
A necessary condition for “P” is “Q”.
“P” is a sufficient condition for “Q”.
A sufficient condition for “Q” is “P”.
Clearly, if we have the assertion
“Q” is a necessary and sufficient condition for “P”
the translation is
P ↔ Q.
For, the first part,
“Q” is a necessary condition for “P”,
assures us of the translation
P → Q;
and the second part,
“Q” is a sufficient condition for “P”,
yields the translation
Q → P.
Together, we have
(P → Q)&(Q → P),
which is another way to write
P ↔ Q.
EXERCISES
Write translations in terms of “P”, “Q”, “R” and the connectives for each of the following statements, taking as translations:
P: a is perpendicular to c.
Q: b is perpendicular to c.
R: a is parallel to b.
1. If a is perpendicular to c and b is perpendicular to c, then a is parallel to b.
2. If a is perpendicular to c and b is not perpendicular to c, then a is not parallel to b.
3. If a is perpendicular to c or b is perpendicular to c, then a is parallel to b or a is not parallel to b.
4. If a is not parallel to b, then a is not perpendicular to c or b is not perpendicular to c.
Using suitable translations “P”, “Q”, “R”, …, write symbolic translations for each of the statements in Exercises 5 to 12.
5. If p and q are integers and q ≠ 0, then p/q is a rational number.
6. If ABC is a triangle and ABC is isosceles, then ABC has two equal sides.
7. That ABC is a triangle and ABC has two equal sides is a necessary condition for it to be isosceles.
8. Whenever ABC is a triangle, then a sufficient condition for it to be isosceles is that it have two equal sides.
9. If a, b, c, and x are real numbers, a ≠ 0, ax2 + bx + c = 0, and b2 – 4ac = 0, then the roots of ax2 + bx + c = 0 are real and equal.
10. Whenever ABCD is a quadrilateral, then a necessary condition for it to be a square is that it be a rectangle.
11. Whenever ABCD is a quadrilateral, then a sufficient condition for it to be a square is that it be a rectangle whose sides are each 5 ft long.
12. Whenever ABCD is a quadrilateral, then a necessary and sufficient condition for it to be a square is that it have four right angles and four equal sides.
13. Express in symbols: The negation of a conditional is equivalent to the conjunction of its antecedent and the negation of its consequent.
14. Write out truth tables for “(A ↔ B)” and “(A∨B)&((A&B))”. Compare the truth tables. Refer back to (2.1) and read again the paragraph concerning it.
The class of statement formulas has an important subclass called the class of valid statement formulas. A valid statement formula has the property that whatever the truth values of the statements placed in it, the resulting statement is true; only formulas having this property are called valid.
The following formulas are examples of valid statement formulas:
To test the validity of a statement formula such as
it is convenient to write out the complete truth table belonging to it.
From the last column of the truth table it follows that the statement formula (2.9) yields a true statement whatever the truth values of the statements placed in it at “P” and “Q”. Hence, (2.9) is a valid statement formula.
As an illustration of the utility of formula (2.9) consider the problem of expressing a negation of the statement
(2.10) l1 and l2 are perpendicular to l3,
where “l1”, “l2”, and “l3” are names of three given lines. We can, of course, form the negatively prefixing “not” to (2.10), but the resulting statement is awkward. Instead let us change (2.10) into the conjunction
(2.11) (l1 is perpendicular to l3)&(l2 is perpendicular to l3).
Now, the valid formula (2.9) shows us how to find a statement equivalent to the negation of any conjunction. Accordingly,
(2.12) (l1 is not perpendicular to l3)∨(l2 is not perpendicular to l3)
is a statement equivalent to the negation of (2.11). The statement (2.12) is often more convenient to use than the negation of (2.10) or the negation of (2.11).
The statements in Exercises 9 to 12, Sec. 2.4, afford another illustration of the valid formula (2.9). The equivalence of these pairs of statements is just an instance of formula (2.9).
Because of their generality, the valid statement formulas occupy an important position in the statement logic. In effect, they describe laws of the logic in much the same way that trigonometric identities describe laws of trigonometry. The distinction between equation and identical equation in trigonometry is parallel to the distinction between statement formula and valid statement formula in the statement logic. For example, the equation sin 
+ cos = 1 is a true statement of equality for some angles (for example, = 0°, 90°, 360°,…) and is a false statement of equality for other angles . However, the equation sin2 + cos2 = 1 is a true statement of equality for all angles , and so describes a general property of the sine and cosine functions.
Certain of the valid statement formulas are formally analogous to algebraic identities expressing properties of real numbers. They are
The first five statement formulas of (2.13) correspond to the following algebraic statements which are true for any real numbers “x”, “y”, “z”:
With the analogy as drawn above, there fails to be any analogue for (f), for while it is the case, as in (e), that 2 · (3 + 4) = 2 · 3 + 2 · 4, it is of course not the case, as in (f), that 2 + (3 · 4) = (2 + 3) · (2 + 4).
The valid statement formula (2.13c) can be made the basis for a useful abbreviation. The expression “P&Q&R” is not a well-formed formula (Sec. 2.6) but may be taken as an abbreviation both for “(P&Q)&R” and for “P&(Q&R)”. Of course, with this agreement, “P&Q&R” is ambiguous, but in view of the validity of (2.13c), the ambiguity can do no harm. Clearly (2.13d) can be made the basis for a similar abbreviation.
The expression “P → Q → R” should not be used as an abbreviation because the binary connective “→” is not associative. That is,
(2.14) [(P → Q) → R] ↔ [P → (Q → R)]
is not a valid statement formula. Let us interpret (2.14) by taking for “P”, “Q”, “R” the statements
P: ABC is a triangle.
(2.15) Q: ∠A > ∠B.
R: BC > AC.
where A, B, and C are points in the plane, as in Fig. 5. Here AC is an arc of the circle whose diameter is AB; hence, the angle at A is considered to be equal to 90°. With this interpretation, “P → (Q → R)” becomes the statement
(2.16) If ABC is a triangle, then ∠A > ∠B implies BC > AC.
Taken as a general statement, (2.16) is a theorem of plane geometry, but here we take it as a statement about the particular geometrical figure pictured in Fig. 5. Thus, the statements taken for “P”, “Q”, and “R” have the truth values “F”, “T”, “F”, respectively. It follows that (2.16) is a true statement.
With the interpretation (2.15), “(P → Q) → R” becomes
(2.17) Whenever ABC is a triangle implies ∠A > ∠B, then BC > AC.
Now, ABC is not a triangle; so the statement “ABC is a triangle implies ∠A > ∠B” is true. It is not true that “BC > AC”, and so (2.17) is a conditional with a true antecedent and a false consequent, and thus is false (see Sec. 2.5). Since under the interpretation (2.15) we have found (2.16) true and (2.17) false, it follows that (2.14) is not a valid statement formula. The complete truth table for (2.14) is:
FIG. 5. AC is an arc of the circle whose diameter is AB.
Since the two properly formed formulas that can be formed out of “P → Q → R” by proper insertion of parentheses are not equivalent, this expression will not be employed as an abbreviation for anything.
Parentheses may be omitted from formulas containing “&” alone, or “∨” alone, but formulas containing both of these symbols generally require use of parentheses to avoid serious ambiguity. The same problem exists in arithmetic; 2 · 3 + 4 · 5 might lead to the answers 50, 26, or 70, depending on whether the expression is viewed as meaning [(2 · 3) + 4] · 5, (2 · 3) + (4 · 5), or [2 · (3 + 4)] · 5. Of course, the correct interpretation is the second one, leading to the answer 26. It is the correct interpretation because of the notational agreement made in arithmetic that in numerical statements involving both multiplication and addition, multiplication binds numbers more closely than addition.
A similar agreement can help to reduce the occurrence of parentheses in statement formulas. Let us agree that “&” binds statements more closely than “∨”. With this convention, we can take “A∨B&C” to be an abbreviation for “A∨(B&C)”. We cannot expect to use “A∨B&C” also as an abbreviation for “(A∨B)&C” since, “A∨(B&C) ↔ (A∨B)&C” is not a valid statement formula.
In algebra, the product of x and y is usually written xy, without an explicit symbol to indicate the multiplication. This convention not only allows abbreviation of algebraic expressions but is also a practical aid in using the agreement on omission of parentheses. It is without doubt easier to interpret xy + yz correctly than it is to interpret x · y + y · z correctly.
To obtain similar benefits of easy interpretation for the statement logic, we use the abbreviation “AB” for “A&B”. Then the formula “A∨(B&C)”, which was abbreviated to “A∨B&C”, can now be further abbreviated to “A∨BC”. With these conventions, many statement formulas will be formally analogous to algebraic expressions, where “∨”, “&”, “↔” correspond formally to “+”, “·”, “=”.
For the negation symbol “” the convention is that it binds a statement more closely than either “&” or “∨”. Thus “P∨Q” is an abbreviation for “(P)∨Q”. To express the denial of a disjunction, parentheses will always be required, as in “(P∨Q)”. Similarly, “PQ” is an abbreviation for “(P)Q”, and the denial of a conjunction will always require parentheses, as in “(PQ)”. We shall also write “P” for “(P)”, and “P” for “[(P)]” from now on.
Finally, “”, “&”, and “∨” are taken to bind statements more closely than either “→” or “↔”. With this convention, “P∨Q ↔ Q∨P” is a legitimate abbreviation for “(P∨Q) ↔ (Q∨P)”.
There will be no further conventions, so that if “→” or “↔” are repeated, or both occur, in the same formula, parentheses will still be required to avoid ambiguity.
In summary, the notational conventions provide for eliminating the “&” symbol by using juxtaposition to indicate conjunction. The conventions provide for reducing the number of parentheses needed by ordering the connectives according to the closeness with which they bind statements, with “” binding closest, then “&”, then “∨”, and all of these binding statements more closely than “→” or “→”. Thus to restore parentheses to the formula
parentheses are placed first about the negation symbols and the statements to which they apply to obtain
Next, parentheses are placed about the conjunctions
and finally parentheses are placed about the disjunctions
If desired, this last formula may be written with distinctive collection symbols
With these conventions, formulas (2.13) can be written
A person who feels at home with the symbolism of algebra will be quite comfortable with all of these formulas except (2.18f), which will seem strange because its algebraic counterpart is not an identity.
Almost all the formulas that follow have already been encountered in unabbreviated form and are here compared with their abbreviated forms:
1. Construct truth tables for the above formulas, and determine which of them are valid statement formulas.
2. Show by means of truth tables that the following are valid statement formulas:
a. PQ → P
b. (P → A∨B) ↔ [B → (P → A)]
c. (P → A∨B) ↔ [(P → B) → (P → 4)]
d. (A → Q)(B → Q) ↔ (A∨B → Q)
e. [P → (Q → R)] ↔ [PQ → R]
f. (P → A∨B) ↔ (P → A)∨(P → B)
g. (P → Q)(P → R) ↔ (P → QR)
h. P ↔ p
i. (PB) ↔ (P → B)
3. As was mentioned in Sec. 2.5, not all of the connectives “”, “&”, “∨”, “→”, “↔” are essential to the logic. For example, we could take “” and “&” as basic symbols, and define the other connectives in terms of these. Recall that “P∨Q” is true except when both “P” and “Q” are false. This suggests expressing “P∨Q” in the form “(PQ)”. It is then easy to check by truth tables that “P∨Q ↔ (PQ)” is a valid statement formula.
a. Using only the symbols: “”, “&”, “P”, “Q”, “(”, “)”, find formulas equivalent to “P∨Q”, “P → Q”, “P ↔ Q”.
b. Using only the symbols: “”, “∨”, “P”, “Q”, “(”, “)”, find formulas equivalent to “P&Q”, “P → Q”, “P ↔ Q”.
It is often convenient to rename some or all of the placeholders in a statement formula. If in
(2.19) A∨(B → C)
“A” is replaced by “P” and “B” by “Q”, then (2.19) becomes
(2.20) P∨(Q → C).
While (2.19) and (2.20) are not equivalent in the sense of Sec. 2.7, they are, nevertheless, alike in the sense that any statement that can be derived from (2.19) by replacing its placeholders by statements can also be derived from (2.20) by a suitable replacement of placeholders. Conversely, any statement derivable from (2.20) can also be derived from (2.19). To put it in another way, the totality of statements in the form of (2.19) is identical with the totality of statements in the form of (2.20).
Renaming the placeholders of a formula does not always yield a formula which is the same in the sense of the foregoing paragraph. If, for instance, “A” is replaced by “P” and “B” by “C” in (2.19) the result is
(2.21) P∨(C → C).
The disjunction (2.21) is valid since “C → C” is true for any statement placed in “C”. Since (2.19) is clearly not a valid formula, there is at least one statement derivable from (2.19) that cannot be derived from (2.21). However, any statement derivable from (2.21) can be derived from (2.19). That is to say, the totality of statements in the form of (2.21) is a subset of the totality of statements in the form of (2.19).
We formulate the notion of replacement in somewhat more general terms in the following, where we use script letters as names of formulas.
Replacement Rule: A formula 
is said to be derived from a formula 
by replacement of “A” by 
if and only if every occurrence of the placeholder “A” in 
is replaced by the same formula 
.
Note that the symbol replaced must be a placeholder, but that it may be replaced by a statement formula. For instance, from “A∨A” we can obtain “(P → Q)∨(P → Q)” by replacing the placeholder “A” by the formula “P → Q”.
With this more general kind of replacement, it is still the case that if 
is obtained from 
by replacement, then every statement derivable from 
is also derivable from 
. It follows that if 
is a valid formula, then so is 
a valid formula. It is this property of the replacement process that makes it a useful tool. For instance, in the valid formula, Exercise 2e, Sec. 2.9,
[P → (Q → R)] ↔ [PQ → R],
“R” may be replaced by “P” to obtain the valid formula
[P → (Q → P)] ↔ [PQ → P].
It should be observed that to obtain (2.20) from (2.19) requires two applications of the replacement rule.
In Sec. 2.8 the method of truth tables was used to establish the validity of formula (2.9):
(PQ) ↔ P∨Q.
By replacing “P” by “P” and “Q” by “Q”, the valid formula
(2.22) (PQ) ↔ P∨Q
is obtained. By Exercise 2h, Sec. 2.9,
is valid. Also, by replacement in (2.23),
is valid. On considering these last three formulas, it seems reasonable to expect that
is a valid formula. Truth table analysis will show that it is indeed valid.
The replacement rule will not yield (2.25) from (2.22) since it would be necessary to replace formula “P” by “P” and formula “Q” by “Q”, which would violate the replacement rule requirement that placeholders be replaced rather than formulas. Yet in view of the equivalences (2.23) and (2.24) such substitutions seem reasonable, and it appears likely that a suitably formulated principle of substitution might well enable one to establish validity in some cases without resorting to truth tables. Again we use script letters as names of formulas and write
Substitution Principle: If 
is a formula containing a component formula 
, and if 
is a formula obtained from 
by substituting a formula 
for one or more occurrences of 
in 
, and if 
is valid, then 
is valid.
An example of the use of the substitution principle follows. Suppose
On substituting 
for 
in 
, we obtain for 
Now since “(PQ) ↔ P∨Q” is valid (formula 2.9), we have 
is valid and it follows by the substitution principle that 
or
is a valid formula. Truth-table analysis will verify the validity, but is not needed.
A valuable result is obtained by applying the substitution principle to a valid formula. Suppose 
is a valid formula, and 
is obtained from 
by use of the substitution principle. Then
is valid. Since every assignment of truth values to the placeholders of 
results in the value “T” for 
, then the same must be true for 
, and it follows that 
is a valid statement formula. In short, substitution in a valid formula yields a valid formula. It is exactly this result that is needed to obtain (2.25) from (2.22) by substitution from (2.23) and (2.24).
In considering the quite distinct notions of replacement and substitution, it is well to emphasize the following points:
“Replacement” is a means of renaming placeholders and
a. Only placeholders may be replaced.
b. If a placeholder is to be replaced, it must be replaced in every one of its occurrences.
“Substitution” is a means of obtaining essentially new formulas and
a. For any formula a validly equivalent formula may be substituted.
b. It is not necessary to substitute in all occurrences of the formula in question.
EXERCISES
In the following exercises, use the replacement rule and the substitution principle to show validity:
1. Show that “[(P → Q)] ↔ (P → Q)” is valid using “P ↔ P” (Exercise 2h, Sec. 2.9).
2. Show that “(RR) ↔ RR” is valid.
3. Show that “P → (Q → P)” is valid, using Exercises 2a and 2e, Sec. 2.9.
4. Start with the valid formula of Exercise 2d, Sec. 2.9, and obtain the valid formula “(A → Q)(B → Q) ↔ [(AB) → Q]”. You will need (2.9).
5. Obtain the valid formula “PQ ↔ (P∨Q)”. Start with “P ↔ P”, use replacement, and substitution from (2.9).
6. Obtain the valid formula “(P → Q) ↔ PQ”. Start with Exercise 2h, Sec. 2.9, and use Exercise 2i.
Formula (2.25):
which can be shown to be valid by the methods of Sec. 2.10 and 2.11, can be regarded as showing how to express “∨” in terms of “” and “&”. Formula (2.26), which follows, can be regarded as showing how to express “→” in terms of “” and “∨”.
A proof for (2.26) is given in the following truth table:
If in (2.26) “P” is replaced by “P” and then “P” substituted for “P”, a valid formula is obtained which may be regarded as an alternative form of (2.26). It is
Suppose “P” and “Q” are translations of statements as follows:
P: You are completely satisfied.
Q: You get your money back.
Then “P∨Q” is a translation of
P∨Q: You are completely satisfied or
you get your money back.
By (2.27), an equivalent statement is
P → Q: If you are not completely satisfied, then you get your money back.
Perhaps a manufacturer making such a guarantee has in mind the exclusive “or”, so that “P∨Q” is not a translation of his guarantee. However, following the doctrine that “the customer is always right”, he will not quarrel with customer claims and will have to pay off as if the guarantee is given with the inclusive “or”.
For a trigonometric interpretation of (2.26), let “P” and “Q” be the translations
Then the interpretation of (2.26) is
Note that it is quite possible for both “
+ 
≠ 90°” and “sin = cos ” to be true statements. (This will be the case, for instance, if = = 225°.) For this interpretation, “P → Q” is known to be true for all angles and ; thus by (2.26) “P∨Q” is also true for all angles and .
A companion to the valid formula (2.9)
is the valid formula
Formulas (2.28) and (2.29) are known as De Morgan’s laws after the English logician A. De Morgan (1806–1878), though these forms were known and used long before his time.
The validity of (2.29) can be established by truth tables, but it is instructive to do so by means of replacement and substitution. Replace “P” by “P”, and “Q” by “Q” in (2.28) to obtain
Substitution for “P” and “Q” yields
Now, following the pattern of the Substitution Principle, take for 
and substitute from (2.30) to obtain for 
By the Substitution Principle, 
; so
and a final substitution to remove the double negation yields
which is the required formula (2.29).
A theorem of mathematics is commonly stated in the form of a conditional. If “P → Q” is the translation of a theorem, it is sometimes easiest to prove it indirectly by showing that “(P → Q)” is a false statement. If “(P → Q)” is false, then by definition of negation, “P → Q” is true. Unfortunately, “(P → Q)” is grammatically awkward in translation. It is useful to have an equivalent form for “(P → Q)” which is more comfortable in translation. Such a formula can be derived by the methods of Secs. 2.10 and 2.11.
Start with
and substitute from (2.26) to get
If “Q” is replaced by “Q” in the De Morgan formula (2.28), and if then “Q” is substituted for “Q”, the result is
This is then substituted in (2.31) to get
A final substitution to remove the double negation yields the desired valid formula
Suppose we wish to prove the statement
where “a”, “b”, “c” are unknown, but fixed, lines in a plane. With translations,
a translation of (2.33) is “P → Q”. To prove “P → Q” indirectly, we should have to start with
which is in an awkward form. By (2.32) a form equivalent to (2.34) is
The form of (2.35) is quite comfortable to work with. If it is proved false, then so is (2.34) false, and (2.33) is proved true.
EXERCISES
First, write the negation of each of the following statements in a form suitable for direct translation into symbols. That is, for “The eye is black and blue”, write, “Not; the eye is black and the eye is blue”. Second, if the resulting negation seems grammatically awkward, use valid formulas, replacement, or substitution to find an equivalent statement that is more graceful. That is, the above statement would be changed to, “The eye is not black or the eye is not blue”. (Where “or” appears, take it in the inclusive sense.)
1. I shall not be home Tuesday or Wednesday.
2. The bus stops at Bay Street or Water Street.
3. My office hours are on Tuesday, Wednesday, and Saturday.
4. m or n is a zero of f(x).
5. No refund or exchange is permitted.
6. It is not true that John will go to college or to work upon graduation from high school.
7. ΔABC is isosceles or equilateral.
8. The pay telephone takes nickels, dimes, or quarters.
9. If the weather is mild this fall, people will not buy heavy coats.
10. If a ≠ b and c ≠ d, then a + c ≠ b + d.
11. If a > b and b > c, then a > c.
12. If two triangles are congruent, their corresponding sides are equal.
13. a > b.
14. a ⊥ c and b ⊥ c, and a is not parallel to b.
15. a || b, and c is a transversal forming alternate interior angles 
and with a and b, and ≠ .
16. If n is an even number, then n is exactly divisible by 2.
17. If 
is irrational, it cannot be expressed in the form p/q, q ≠ 0, where p and q are integers.
18. 
is irrational.
19. If n is rational, it can be expressed as the quotient of two integers, p/q, q ≠ 0.
20. If P(x) is a polynomial with real coefficients, then whenever a + bi is a root of P(x) so is a — bi a root of P(x). (Translate in the form: “A → (B → C)”.)
Below is listed a group of valid statement formulas that are important in their own right or are referred to one or more times in the sequel.
From the nature of their definition, valid statement formulas are laws of the statement logic. As such, they are useful in formal mathematical proofs. Fully to exploit these logical laws, some rules are needed for obtaining true statements from given statements, assumed or proved to be true. The most fundamental of these rules occurs tacitly in many geometric proofs of elementary mathematics. It is almost always required when a previously proved theorem is to be used as a step of a proof.
Consider the usual method of employing the congruence theorem commonly denoted by “S.S.S.”. An instance of this theorem may be written
(ABC is a triangle) (A′B′C′ is a triangle) (AB = A′B′)
(2.61)
(BC = B′C′) (CA = C′A′) → (ABC 
A′B′C′).
The statement (2.61) is accepted as true because it is an instance of a general statement that has been proved true for all pairs of triangles. In the course of a proof requiring this theorem, it is customary first to prove in some way the statement
(ABC is a triangle) (A′B′C′ is a triangle) (AB = A′B′)
(2.62)
(BC = B′C′)(CA = C′A′),
and then to infer the statement
(2.63) ABC A′B′C′.
In the traditional two-column form of demonstration, the statements (2.62) and (2.63) appear in the left-hand column headed Statements (perhaps with “∴” preceding (2.63)), and statement (2.61), or commonly just “S.S.S.” appears in the right-hand column headed Reasons. Whatever the particular format, the result is the inference that (2.63) is considered proved because (2.61) and (2.62) are proved statements.
In the translation
P: Statement (2.62)
Q: Statement (2.63),
the inference takes the form
If “P” and “P → Q” are proved statements, then
(2.64)
“Q” is inferred to be a proved statement.
Considering (2.64) as a general assertion about statements, we shall assume it as a rule of inference. It is often called the “Rule of Modus Ponens” or the “Law of Detachment”, and we shall refer to it simply as “modus ponens” or sometimes just “mod pon”. In (2.64), “P → Q” is called the major premise, “P” the minor premise, and “Q” the conclusion.
As a convenient abbreviation for inference rules, we shall adopt a notation that for (2.64) takes the form
We must distinguish carefully between the notion of a conditional and the notion of an inference by modus ponens. By itself, “P → Q” is a formula whose truth values depend in a certain way upon the truth values of “P” and “Q”. Even if it is known that “P → Q” is true, nothing can be said about the truth of “Q”. One cannot, so to speak, detach “Q” as true from a true “P → Q”. However, from a true “P” and a true “P → Q”, one can detach a true “Q” by modus ponens.
Note that from a consideration of the definition of “↔”, it follows that if “P” and “P ↔ Q” are proved, then so is “Q” proved. We can regard this as a special case of modus ponens.
In the application of modus ponens to (2.61) it is necessary to know that (2.62) is true or proved. Customary procedure is to establish the truth of each of the five statements of the continued conjunction (2.62) separately, and then to infer from this the truth of (2.62) itself. This procedure depends upon a generalization of the following rule of inference:
If “P” is proved and “Q” is proved, then “PQ” is inferred
(2.65)
to be proved.
If (2.62) is translated without using the convention about omission of parentheses, it has the form “((((PQ)R)S)T)”. Four applications of (2.65) are necessary to infer the truth of (2.62) from the truths of each of “P”, “Q”, “R”, “S”, “T”.
The rule (2.65) will be called the Rule of Conjunctive Inference, and may be abbreviated
A rule that is related to conjunctive inference is often needed in proofs. It is called conjunctive simplification:
If “PQ” is proved, then either “P” or “Q” is inferred
(2.66)
to be proved.
Through use of (2.66) it is possible to “detach” conjunction any one of the statements in the conjunction. The rule (2.66) may be abbreviated
To derive the rule of conjunctive simplification, we use modus ponens with (2.50), or (2.51), as major premise and “PQ” as minor premise; then “P”, or “Q”, is inferred to be true.
The three rules of inference in conjunction with valid statement formulas provide additional means for inferring new statements from given statements. The valid statement formula
is listed as (2.59). It embodies an important logical law, and its validity is established by the following truth table:
Suppose it is desired to prove a statement in the form “P → R”. If it is first possible to prove the two statements “P → Q” and “Q → R”, then by the rule of conjunctive inference (2.65), “(P → Q) (Q → R)” may be inferred. After this, using “(P → Q)(Q → R)” as minor premise, and (2.59) as major premise, “P → R” may be inferred by modus ponens. In summary, “P → R” has been inferred from “P → Q” and “Q → R”.
We can express this method of proving “P → R” as a new inference rule derived from the two previous inference rules. It is called the hypothetical syllogism:
The derived inference rule (2.67) occurs frequently in mathematical proofs, and it is easily extended to a chain of several conditionals:
In the same way, a derived rule of inference stems from the valid formula (2.42):
The validity of (2.68) can be established by starting with the valid formula:
1. (P → Q) ↔ |
[Formula (2.26)] |
2. (P → Q) ↔ |
[Substitution from “Q ↔ |
3. A → Q) ↔ |
[Replace “P” by “A” in Step 1] |
4. (A → |
[Replace “Q” by “ |
5. ( |
[Replace “A” by “ |
6. ( |
[Substitution in Step 5 from (2.45) with replacement] |
7. (P → Q) ↔ ( |
[Substitution, Step 6 in Step 2] |
Now then, if “P → Q” is the translation of a proved statement, with it as minor premise, and (2.68) as major premise, “Q → P” can be inferred to be true by modus ponens. The corresponding derived rule of inference is written
The formula “Q → P” is called the contrapositive of “P → Q”, but the name contrapositive inference will be reserved for an extension of (2.69). Suppose both “P → Q” and “Q” are proved. By (2.69), “Q → P” can be inferred; then, with “Q → P” as major premise and “Q” as minor premise, “P” can be inferred by modus ponens. It is this scheme of inference that we shall call the Rule of Contrapositive Inference. In the notation adopted, it is written
Contrapositive inference occurs frequently in everyday discourse as well as in mathematics. An instance of (2.70) is the argument
If Mr. Doe is a communist, he associates with communists.
But Mr. Doe doesn’t associate with communists.
Therefore, Mr. Doe isn’t a communist.
The argument is valid whatever the truth or falsity of the statements in it may be.
Another instance is the cliché
If John’s a Democrat, I’ll eat my hat.
By his tone of voice, the speaker makes it clear that he is not going to eat his hat, and the inference is that “John is not a Democrat”.
At a certain stage in the standard proof of the irrationality of the square root of 2, it is known that for a certain integer x, x2 is even. To proceed with the proof, it is necessary to show that x is even. It is easy to show that
for if x is odd, it can be expressed in the form 2n + 1 for some integer n. Then
which is clearly odd. With this proved, the desired result follows by contrapositive inference:
So it is proved that x is not odd, that is, x is even.
In Sec. 2.7, several alternative ways to read “P → Q” were discussed. There are two additional ways in which the conditional occurs in mathematical writing. One of these is
P only if Q.
The sense of the above statement seems to be: if we do not have Q, then we cannot have P. But “Q → P” is just a translation of this statement. Since “(Q → P) ↔ (P → Q)”, we have by substitution the desired interpretation.
Another way in which the conditional “P → Q” occurs is in the form
Q if P.
There is no question that the interpretation of this form is “P → Q”.
Now, let us put the two forms together:
P if and only if Q.
In this form we have, in translation,
(P → Q)(Q → P),
the familiar form of “P ↔ Q”. Notice that the form is exactly like the one we obtained, Sec. 2.7, in the discussion of necessary and sufficient conditions. Current writing in mathematics tends to use “if and only if” much more than “necessary and sufficient”.
EXERCISES
For each of Exercises 1 to 10, cite all the inference schemes used, the tacit theorems if any, and show by rewriting the statements explicitly how the inference schemes are used.
1. x = y
y = z
∴ x = y and y = z
2. If x > y and y > z, then x > z.
x > y
y > z
∴ x > z
3. If a || c and b || c, a || b.
a || c; b || c
∴ a || b
4. If a || b, ∠x = ∠y
a || b
∴ ∠x = ∠y
5. If x = y and y = 3, x = 3.
z = y
y = 3
∴ x = 3
6. MN = AB/2 and MN || AB
∴ MN = AB/2
∴ MN || AB
7. A point P is called the pole of a line p if and only if P is not joined to any point on p by a line.
P is joined to a point on p by a line.
∴ P is not the pole of p.
8. Angle ACB is an inscribed angle in circle O.
If angle ACB is inscribed in circle O, it is measured by one-half of its intercepted arc AB.
∴ Angle ACB is measured by one-half of arc AB.
9. Triangles ABC and A′B′C′ are right triangles with hypotenuses c and c′, respectively, c = c′, ∠ABC = ∠A′B′C′.
∴ ΔABC ≅ ΔA′B′C′
10. Point X is on the perpendicular bisector of line segment AB if and only if AX = BX.
AX ≠ BX.
∴ X is not on the perpendicular bisector of line segment AB.
11. Consider the following conventional proof of the statement: The opposite sides of a parallelogram are equal.
Rewrite the proof so that the uses of inference schemes are explicit. Pay particular attention to the tacit uses of modus ponens and conjunctive inference.
You might have to supply some statements and steps that are omitted in this conventional proof. In addition, you might wish to recast the statements of some of the theorems and axioms used.
Important inference rules or schemes are collected below.
