Everand Logo

Welcome to Everand!

  • Explore 1.5M+ audiobooks & ebooks free for days

    Only $12.99 CAD/month after trial. Cancel anytime.

    Introduction to Logic
    Introduction to Logic
    Introduction to Logic
    Ebook623 pages8 hoursDover Books on Mathematics

    Introduction to Logic

    By Patrick Suppes

    4/5

    ()

    Read preview

    About this ebook

    Part I of this coherent, well-organized text deals with formal principles of inference and definition. Part II explores elementary intuitive set theory, with separate chapters on sets, relations, and functions. Ideal for undergraduates.
    LanguageEnglish
    PublisherDover Publications
    Release dateJul 12, 2012
    ISBN9780486138053
    Introduction to Logic

    Other titles in Introduction to Logic Series (30)

    View More
    View More

    Read more from Patrick Suppes

    Related to Introduction to Logic

    Titles in the series (100)

    View More
    View More

    Related ebooks

    Mathematics For You

    View More
    View More

    Related categories

    Reviews for Introduction to Logic

    4/5

    7 ratings0 reviews

    What did you think?

    Tap to rate

    Review must be at least 10 words

      Book preview

      Introduction to Logic - Patrick Suppes

      INTRODUCTION

      Our everyday use of language is vague, and our everyday level of thinking is often muddled. One of the main purposes of this book is to introduce you to a way of thinking that encourages carefulness and precision. There are many ways to learn how to use language and ideas precisely. Our approach shall be through a study of logic. In modern times logic has become a deep and broad subject. We shall initially concentrate on that portion of it which is concerned with the theory of correct reasoning, which is also called the theory of logical inference, the theory of proof or the theory of deduction. The principles of logical inference are universally applied in every branch of systematic knowledge. It is often said that the most important critical test of any scientific theory is its usefulness and accuracy in predicting phenomena before the phenomena are observed. Any such prediction must involve application of the principles of logical inference. For example, if we know what forces are acting on a body and we know at a given time where the body is and what its velocity is, we may use the theory of mechanics together with the rules of logical inference and certain theorems of mathematics to predict where the body will be at some later time.

      For over two thousand years mathematicians have been making correct inferences of a systematic and intricate sort, and logicians and philosophers have been analyzing the character of valid arguments. It is, therefore, somewhat surprising that a fully adequate formal theory of inference has been developed only in the last three or four decades. In the long period extending from Aristotle in the fourth century B.C. to Leibniz in the seventeenth century, much of importance and significance was discovered about logic by ancient, medieval and post-medieval logicians, but the most important defect in this classical tradition was the failure to relate logic as the theory of inference to the kind of deductive reasonings that are continually used in mathematics.

      Leibniz had some insight into the necessity of making this connection, but not until the latter part of the nineteenth century and the beginning of this century were systematic relations between logic and mathematics established, primarily through the work of Frege, Peano, and Russell. In spite of the scope and magnitude of their researches, only in recent years has there been formulated a completely explicit theory of inference adequate to deal with all the standard examples of deductive reasoning in mathematics and the empirical sciences. The number of people who have contributed to these recent developments is large, but perhaps most prominent have been Kurt Gödel, David Hilbert, and Alfred Tarski.

      Yet it is a mistake to think that the theory of inference developed in the first part of this book has relevance exclusively to scientific contexts. The theory applies just as well to proceedings in courts of law or to philosophical analyses of the eternal verities. Indeed, it is not too much to claim that the theory of inference is pertinent to every serious human deliberation.

      A correct piece of reasoning, whether in mathematics, physics or casual conversation, is valid by virtue of its logical form. Because most arguments are expressed in ordinary language with the addition of a few technical symbols particular to the discipline at hand, the logical form of the argument is not transparent. Fortunately, this logical structure may be laid bare by isolating a small number of key words and phrases like ‘and’, ‘not’, ‘every’ and ‘some’. In order to fix upon these central expressions and to lay down explicit rules of inference depending on their occurrence, one of our first steps shall be to introduce logical symbols for them. With the aid of these symbols it is relatively easy to state and apply rules of valid inference, a task which occupies the first seven chapters.

      To bring logical precision to our analysis of ideas, it is not ordinarily enough to be able to construct valid inferences; it is also essential to have some mastery of methods for defining in an exact way one concept in terms of other concepts. In any given branch of science or mathematics one of the most powerful methods for eliminating conceptual vagueness is to isolate a small number of concepts basic to the subject at hand and then to define the other concepts of the discipline in terms of the basic set. The purpose of Chapter 8 is to lay down exact rules for giving such definitions. Correct definitions, like correct inferences, will be shown to depend primarily on matters of logical form. However, certain subtle questions of existence arise in the theory of definition which have no counterpart in the theory of inference.

      The first eight chapters constitute Part I, which is devoted to general principles of inference and definition. Part II, the last four chapters, is concerned with elementary set theory. Because the several respects in which set theory is intimately tied to logic will not be familiar to many readers, some explanation for the inclusion of this material will not be amiss.

      Set theory, or the general theory of classes as it is sometimes called, is the basic discipline of mathematics, for with a few rare exceptions the entities which are studied and analyzed in mathematics may be regarded as certain particular sets or classes of objects. As we shall see, the objects studied in a branch of pure mathematics like the theory of groups or in a branch of mathematical physics like the theory of mechanics may be characterized as certain sets. For this reason any part of mathematics may be called a special branch of set theory. However, since this usage would identify set theory with the whole of mathematics it is customary to reserve the term ‘set theory’ for the general theory of classes or sets and certain topics, such as the construction of the integers and real numbers as sets, which are closely connected historically with investigations into the foundations of mathematics.

      The first chapter of Part II is concerned with an intuitive account of the more important relationships among arbitrary sets. There are, for example, simple operations on sets which correspond to the arithmetical operations of addition, multiplication, and subtraction. The next chapter (Chapter 10) deals with the theory of relations, which is brought within set theory via the notion of an ordered couple of objects. Emphasis is given to ordering relations because of their importance in many branches of mathematics and science. Chapter 11 deals with functions, which from the standpoint of set theory are just relations having a special property.

      While the first three chapters of Part II are concerned with general set theory, the final chapter (Chapter 12) turns to the relation between set theory and certain methodological or foundational questions in mathematics and philosophy. The central point of this chapter is to indicate how any branch of mathematics or any scientific theory may be axiomatized within set theory. The viewpoint which is expounded in detail in Chapter 12 is that the best way to axiomatize a theory is to define an appropriate predicate within set theory.

      Since the beginning of this century philosophers have written a great deal about the structure of scientific theories but they have said lamentably little about the detailed structure of particular theories. The axiomatization of a theory within set theory is an important initial step in making its structure both exact and explicit. Once such an axiomatization is provided it is then possible to ask the kind of structure questions characteristic of modern mathematics. For instance, when are two models of a theory isomorphic, that is, when do they have exactly the same structure? Indeed, familiar philosophical problems like the reduction of one branch of empirical science to another may be made precise in terms of such set-theoretical notions as that of isomorphism. Application of these ideas to substantive examples from pure mathematics and the empirical sciences is given in Chapter 12.

      The aim of both Parts I and II is to present logic as a part of mathematics and science and to show by numerous detailed examples how relevant logic is even to empirical sciences like psychology. For this reason it may be said that the emphasis in this book is on the systematic use and application of logic rather than on the development of logic as an autonomous discipline.

      Finally, it should be remarked that no precise definition of logic. is attempted in these pages. In the narrow sense, logic is the theory of valid arguments or the theory of deductive inference. A slightly broader sense includes the theory of definition. A still broader sense includes the general theory of sets. Moreover, the theory of definition together with the theory of sets provides an exact foundation for the axiomatic method, the study of which is informally considered part of logic by most mathematicians.

      PART I

      PRINCIPLES OF INFERENCE AND DEFINITION

      CHAPTER 1

      THE SENTENTIAL CONNECTIVES

      To begin with, we want to develop a vocabulary which is precise and at the same time adequate for analysis of the problems and concepts of systematic knowledge. We must use vague language to create a precise language. This is not as silly as it seems. The rules of chess, for example, are a good deal more precise than those of English grammar, and yet we use English sentences governed by imprecise rules to state the precise rules of chess. In point of fact, our first step will be rather similar to drawing up the rules of a game. We want to lay down careful rules of usage for certain key words: ‘not’, ‘and’, ‘or’, ‘if ..., then...’, ‘if and only if’, which are called sentential connectives. The rules of usage will not, however, represent the rules of an arbitrary game. They are designed to make explicit the predominant systematic usage of these words; this systematic usage has itself arisen from reflection on the ways in which these words are used in ordinary, everyday contexts. Yet we shall not hesitate to deviate from ordinary usage whenever there are persuasive reasons for so doing.

      § 1.1 Negation and Conjunction. We deny the truth of a sentence by asserting its negation. For example, if we think that the sentence ‘Sugar causes tooth decay’ is false, we assert the sentence ‘Sugar does not cause tooth decay’. The usual method of asserting the negation of a simple sentence is illustrated in this example: we attach the word ‘not’ to the main verb of the sentence. However, the assertion of the negation of a compound sentence is more complicated. For example, we deny the sentence ‘Sugar causes tooth decay and whiskey causes ulcers’ by asserting ‘It is not the case that both sugar causes tooth decay and whiskey causes ulcers’. In spite of the apparent divergence between these two examples, it is convenient to adopt in logic a single sign for forming the negation of a sentence. We shall use the prefix ‘–’, which is placed before the whole sentence. Thus the negation of the first example is written:

      -(Sugar causes tooth decay).

      The second example illustrates how we may always translate ‘–’; we may always use ‘it is not the case that’.

      The main reason for adopting the single sign ‘–’ for negation, regardless of whether the sentence being negated is simple or compound, is that the meaning of the sign is the same in both cases. The negation of a true sentence is false, and the negation of a false sentence is true.

      We use the word ‘and’ to conjoin two sentences to make a single sentence which we call the conjunction of the two sentences. For example, the sentence ‘Mary loves John and John loves Mary’ is the conjunction of the sentence ‘Mary loves John’ and the sentence ‘John loves Mary’. We shall use the ampersand sign ‘&’ for conjunction. Thus the conjunction of any two sentences P and Q is written

      P & Q.

      The rule governing the use of the sigh i & is in close accord with ordinary usage. The conjunction of two sentences is true if and only if both sentences are true. We remark that in logic we may combine any two sentences to form a conjunction. There is no requirement that the two sentences be related in content or subject matter. Any combinations, however absurd, are permitted. Of course, we are usually not interested in sentences like ‘John loves Mary, and 4 is divisible buy 2’. Although it might seem desirable to have an additional rule stating that we may only conjoin two sentences which have a common subject matter, the undesirability of such a rule becomes apparent once we reflect on the vagueness of the notion of common subject matter.

      Various words are used as approximate synonyms for ‘not’ and ‘and’ in ordinary language. For example, the word ‘never’ in the sentence:

      I will never surrender to your demands

      has almost the same meaning as ‘not’ in:

      I will not surrender to your demands.

      Yet it is true that ‘never’ carries a sense of continuing refusal which ‘not’ does not.

      The word ‘but’ has about the sense of ‘and’, and we symbolize it by ‘&’, although in many cases of ordinary usage there are differences of meaning. For example, if a young woman told a young man:

      I love you and I love your brother almost as well,

      he would probably react differently than if she had said:

      I love you but I love your brother almost as well.

      In view of such differences in meaning, a natural suggestion is that different symbols be introduced for sentential connectives like ‘never’ and ‘but’. There is, however, a profound argument against such a course of action. The rules of usage agreed upon for negation and conjunction make these two sentential connectives truth-functional; that is, the truth or falsity of the negation of a sentence P, or the truth or falsity of the conjunction of two sentences P and Q is a function just of the truth or falsity of P in the case of negation, and of P and Q in the case of conjunction. Clearly a truth-functional analysis of ‘but’ different from that given for ‘and’ is out of the question, but any venture into non-truth-functional analysis leads to considerations which are vague and obscure. Any doubt about this is quickly dispelled by the attempt to state a precise rule of usage for ‘but’ which differs from that already given for ‘and’.

      Of course, the rich, variegated character of English or any other natural language guarantees that in many contexts connectives are used in delicately shaded, non-truth-functional ways. Loss in subtlety of nuance seems a necessary concomitant to developing a precise, symbolic analysis of sentences. But this process of distorting abstraction is not peculiar to logic; it is characteristic of science in general. Few poets would be interested in a truth-functional analysis of language, and no naturalist would consider the physicist’s concepts of position, velocity, acceleration, mass, and force adequate to describe the flight of an eagle. The concepts of logic developed in this book are useful in discovering and communicating systematic knowledge, but their relevance to other functions of language and thought is less direct.

      § 1.2 Disjunction. We use the word ‘or’ to obtain the disjunction of two sentences. In everyday language, the word ‘or’, is used in two distinct senses. In the so-called non-exclusive sense, the disjunction of two sentences is true if at least one of the sentences is true. In legal contracts this sense is often expressed by the barbarism ‘and/or’, illustrated in the following example:

      Before any such work is done or any such materials are furnished, the Lessee and any contractor or other person engaged to do such work and/or furnish such materials shall furnish such bond or bonds as the Lessor may reasonably require ....

      We remark that in the above example there are no disjunctions of sentences, but disjunctions of clauses or terms which are not sentences. We shall find, however, that it is more convenient to treat such examples as disjunctions of sentences; this viewpoint reflects another divergence between logic and everyday language.

      The Latin word ‘vel’ has approximately the sense of ‘or’ in the non-exclusive sense, and consequently we use the sign ‘v’ for the disjunction of two sentences in this sense. Thus the disjunction of any two sentences P and Q is written

      P V Q

      We shall restrict our use of the word ‘disjunction’ to the non-exclusive sense, and our rule of usage is: The disjunction of two sentences is true if and only if at least one of the sentences is true.

      When people use ‘or’ in the exclusive sense to combine two sentences, they are asserting that one of the sentences is true and the other is false. This usage is often made more explicit by adding the phrase ‘but not both’. Thus a father tells his child, ‘You may go to the movies or you may go to the circus this Saturday but not both’. We shall introduce no special sign for ‘or’ in the exclusive sense, for it turns out that in scientific discussions we can always get along with ‘or’ in the non-exclusive sense (which is also called the inclusive sense).

      § 1.3 Implication: Conditional Sentences. We use the words ‘if ..., then ...’ to obtain from two sentences a conditional sentence. A conditional sentence is also called an implication. As words are used in everyday language, it is difficult to characterize the circumstances under which most people will accept a conditional sentence as true. Consider an example similar to one we have already used:

      (1) If Mary loves John, then John loves Mary.

      If the sentence ‘Mary loves John’ is true and the sentence ‘John loves Mary’ is false, then everyone would agree that (1) is false. Furthermore, if the sentence ‘Mary loves John’ is true and the sentence ‘John loves Mary’ is also true, then nearly everyone would agree that (1) is true. The two possibilities of truth and falsity which we have just stated are the only ones that arise very often in the ordinary use of language. There are, however, two further possibilities, and if we ask the proverbial man in the street about them, there is no telling what his reply will be. These two further cases are the following. Suppose that the sentence ‘Mary loves John’ is false, then what do we say about the truth of (1): first, when the sentence ‘John loves Mary’ is also false; and second, when the sentence ‘John loves Mary’ is true? In mathematics and logic, this question is answered in the following way: sentence (1) is true if the sentence ‘Mary loves John’ is false, regardless of the truth or falsity of the sentence ‘John loves Mary’.

      To state our rule of usage for ‘if ..., then ...’, it is convenient to use the terminology that the sentence immediately following ‘if’ is the antecedent or hypothesis. of the conditional sentence, and the sentence immediately following ‘then’ is the consequent or conclusion. Thus ‘Mary loves John’ is the antecedent of (1), and ‘John loves Mary’ is the consequent. The rule of usage is then: A conditional sentence is false if the antecedents is true and the consequent is false; otherwise it is true.

      Intuitive objections to this rule could be made on two counts. First, it can be maintained that implication is not a truth-functional connective, but that there should be some sort of definite connection between the antecedent and the consequent of a conditional sentence. According to the rule of usage just stated, the sentence:

      (2) If poetry is for the young, then 3 + 8 = 11

      is true, since the consequent is true. Yet many people would want to dismiss such a sentence as nonsensical; they would claim that the truth of the consequent in no way depends on the truth of the antecedent, and therefore (2) is not a meaningful implication. However, the logician’s commitment to truth-functional connectives is not without its reasons. How is one to characterize such an obscure notion as that of dependence? This is the same problem we encountered in considering conjunctions. If you think an important, perhaps crucial problem is being dodged simply on the grounds that it is difficult, assurances will be forthcoming in the next chapter that truth-functional connectives are very adequate for both the theory and practice of logical inference.

      Even if truth-functional commitments are accepted, a second objection to the rule of usage for implication is that the wrong stipulation has been made in calling any implication true when its antecedent is false. But particular examples argue strongly for our rule. For the case when the consequent is also false, consider:

      (3) If there are approximately one hundred million husbands in the United States, then there are approximately one hundred million wives in the United States.

      It is hard to imagine anyone denying the truth of (3). For the case when the consequent is true, consider the following modification of (3):

      (4) If there are approximately one hundred million husbands in the United States, then the number of husbands in this country is greater than the number in France.

      If (3) and (4) are admitted as true, then the truth-functional rule for conditional sentences with false antecedents is fixed.

      It might be objected that by choosing slightly different examples a case could be made for considering any implication false when its antecedent is false. For instance, suppose that (3) were replaced by:

      (5) If there are approximately one hundred million husbands in the United States, then there is exactly one wife in the United States.

      Then within our truth-functional framework it might be maintained that an implication with false antecedent and false consequent is false, since it may be plausibly argued that in ordinary usage (5) is false. However, there are good grounds for choosing (3) rather than (5), for (3) has the property that its consequent follows from its antecedent on the basis of some familiar principles of arithmetic and marriage. With respect to (5) no such intuitive line of reasoning seems possible; in fact, it is the very absence of such a connection which makes us declare it false. Although we have already admitted that the notion of connection or dependence being appealed to here is too vague to be a formal concept of logic, in choosing examples which will force upon us, within our truth-functional framework, a truth value for implications with false antecedents it is reasonable to pick an example like (3) for which our intuitive feeling of dependence is strong rather than an example like (5) for which it is weak. The truth-functional demand that sentences. like (5) be counted as true has no undesirable effects, since conditional sentences whose antecedents and consequents are unrelated and whose antecedents are false play no serious role in systematic arguments.

      As a matter of notation, the conditional sentence formed from any two sentences P and Q is written

      P → Q.

      The sign ‘→’ is often called the sign of implication. Several other idioms in English have approximately the same systematic meaning as ‘if ..., then...’. We shall also write P → Q, for

      P only if Q

      Q if P

      Q provided that P

      P is a sufficient condition for Q

      Q is a necessary condition for P

      Of these five idioms, variant use of ‘only if’ is most pronounced. It is a common mistake to use ‘only if’ in the sense of ‘if’. For example, the sentence:

      (6) John dates Mary only if Elizabeth is mad at him

      would not ordinarily be taken to mean:

      If John dates Mary then Elizabeth is mad at him,

      and it would be more accurate (but still not exactly idiomatically correct) to translate (6) as:

      If Elizabeth is mad at him then John dates Mary.

      The prevalence of sentences like (6) makes it difficult for many people first learning logic or mathematics to accept the stipulation that

      (7) P only if Q

      means the same as

      (8) If P then Q.

      Yet it is the case that in scientific discourse (7) and (8) are idiomatically equivalent and they will be treated as such throughout the rest of this book.

      Concerning the last two idioms it is worth noting that they are widely used in mathematics. Thus the sentence ‘If a triangle is equilateral then it is isosceles’ may be rephrased:

      In order for a triangle to be isosceles it is sufficient that it be equilateral

      or:

      It is necessary that an equilateral triangle be isosceles.

      Notice that some grammatical changes in the component sentences P and Q are appropriate when we go from

      If P then Q

      to

      (9) P is a sufficient condition for Q

      so that (9) is not an exact formulation; but these changes are usually obvious and need not be pursued here.

      § 1.4 Equivalence: Biconditional Sentences. We use the words ‘if and only if’ to obtain from two sentences a biconditional sentence. A biconditional sentence is also called an equivalence, and the two sentences connected by ‘if and only if’ are called the left and right members of the equivalence. The biconditional

      (1) P if and only if Q

      has the same meaning as the sentence

      (2) P if Q, and P only if Q

      and (2) is equivalent to

      (3) If P then Q, and if Q then P.

      Our rules of usage for conjunction and implication tell us that (3) is true just when P and Q are both true or both false. Thus the rule: A bicondi-tional sentence is true if and only if its two members are either both true or both false. As a matter of notation, we write

      P ↔ Q

      for the biconditional formed from sentences P and Q.

      Corresponding to our remarks at the end of the last section it should be noted that (1) is equivalent to

      Q is a necessary and sufficient condition for P.

      § 1.5 Grouping and Parentheses. In ordinary language the proper grouping of sentences which are combined into a compound sentence is indicated by a variety of linguistic devices. When symbolizing such sentences in logic, these devices may all be accurately translated by an appropriate use of parentheses. , ,

      For instance, the sentence:

      If Showboat wins the race, then Shotless and Ursula will show

      is symbolized by

      (1) S → (H & U),

      where S is ‘Showboat wins the race’, H is ‘Shotless will show’, and U is ‘Ursula will show’. We read (1)

      If S then H and U.

      On the other hand, we read

      (2) (S → H) & U

      as

      Both if S then H, and U.

      It should thus be clear why (1) rather than (2) is the correct symbolization of the original sentence. The parentheses are used in a natural way, familiar from elementary algebra, to indicate which connective is dominant.

      By adopting one natural convention concerning the relative dominance of the various connectives, a considerable reduction in the number of parentheses used in practice will be effected. The convention is ‘↔’ and ‘→’ dominate ‘&’ and ‘v’. Thus (1) may be written

      (3) S → H & U,

      and

      P ↔ Q & R

      means

      P ↔ (Q & R):

      On the other hand, under this convention it is not clear what

      P & Q ∨ R

      is supposed to mean, and similarly for

      P ↔ Q → R.

      § 1.6 Truth Tables and Tautologies. Our truth-functional rules of usage for negation, conjunction, disjunction, implication and equivalence may be summarized in tabular form. These basic truth tables tell us at a glance under what circumstances the negation of a sentence is true if we know the truth or falsity of the sentence, similarly for the conjunction of two sentences, and the disjunction or implication of two sentences as well.

      e9780486138053_i0002.jpg

      We may think of using the basic truth tables in the following manner. If N is the true sentence ‘Newton was born in 1642’ and G is the false sentence ‘Galileo died in 1640’, then we may compute the truth or falsity of a complicated compound sentence such as

      (1) ((N ∨ G) & -N) → (G → N).

      Since N is true, we see from the disjunction table that N ∨ G is true, from the negation table that -N is false, and hence from the conjunction table that the antecedent of (1) is false. Finally, from the implication table we conclude that the whole sentence is true. A more explicit application of the truth tables in a manner analogous to the use of a multiplication table is illustrated by the following diagrammatic analysis, which is self-explanatory.

      e9780486138053_i0003.jpg

      (Note that in this diagram the analysis proceeds from the inside out. The final loop connects the two members of the major connective.)

      Let us call a sentence atomic if it contains no sentential connectives. Thus the sentence:

      Mr. Knightley loved Emma

      is atomic, while the sentences:

      Emma did not love Frank Churchill

      and

      Mrs. Elton was a snob and Miss Bates a bore

      are not atomic, for the first contains a negation and the second a conjunction.

      We now use the concept of a sentence being atomic to define what is probably the most important notion of this chapter. The intuitive idea is that a compound sentence is a tautology if it is true independently of the truth values of its component atomic sentences. For instance for any atomic sentence P

      P V –P

      is a tautology. If P is true, we have:

      e9780486138053_i0004.jpg

      If P is false, we have:

      e9780486138053_i0005.jpg

      Thus whether P is true or false, P v –P is true and hence a tautology. Derived truth tables are more convenient and compact than the diagrammatic analysis shown above when we want to know if a sentence is a tautology.

      The second column is obtained from the first by using the negation table, and the third column from the first two by using the disjunction table. Since both lines in the final column have the entry ‘T’, the whole sentence is a tautology. The idea of the derived truth table is that a sentence is a tautology if it is true for all combinations of possible truth values of its component atomic sentences. The number of such combinations depends on the number of component atomic sentences. Thus, if there are three distinct atomic sentences, there are eight distinct combinations of possible truth values, since each atomic sentence has exactly two possible truth values: truth and falsity. In general, if there are n component atomic sentences, there are 2n combinations of possible truth values, which means that the derived truth table for a compound sentence having n distinct atomic sentences has 2n lines. For instance, to show that P ∨ Q → P is not a tautology when P and Q are distinct atomic sentences, we need 2² = 4 lines, as in the following truth table.

      e9780486138053_i0007.jpg

      In this table the third column is obtained from the first two by using the disjunction table, and the final column from the third and first by using the implication table. Since the third row of the fourth column has the entry ‘F’ for false, we conclude that P v Q → P is not a tautology, for this third row shows that if P is false and Q true, then P v Q → P is false. It should be emphasized that a sentence is a tautology if and only if every entry in the final column is ‘T’ (for true). The letter ‘F’ in a single row of the final column is sufficient to guarantee that the sentence being analyzed is not a tautology.

      When we take as our formal definition

      A sentence is a tautology if and only if the result of replacing any of its component atomic sentences (in all occurrences) by other atomic sentences is always a true sentence

      the relation of this definition to the truth table test for a tautology should be clear. ¹ A given row of the table represents trying a particular combination of atomic sentences. Since only the truth or falsity of the atomic sentences effects the truth or falsity of the whole sentence in a truth-functional analysis, once all possible combinations of truth and falsity have been tested, the effects of all possible substitutions of atomic sentences have been tested. As we have seen, if a sentence contains just one atomic sentence, there are only two possibilities:

      T

      F

      If it has two distinct component atomic sentences, there are four:

      If it has three distinct component atomic sentences, there are eight:

      And in general, as we have already remarked, if there are n distinct component atomic sentences there are 2n possible combinations of truth values and thus 2" rows to the truth table.

      The phrase ‘in all occurrences’ is added parenthetically in the formal definition to make explicit that all occurrences of a given atomic sentence in a compound sentence are to be treated alike. Thus in the truth table for P v Q → P given above, one occurrence of P is given the value T when and only when the other is. This point is made clearer by using the following format (which is not as convenient for computational purposes):

      e9780486138053_i0010.jpg

      Note the identical columns for both occurrences of P.²

      It is also important to notice that if the requirement that P and Q be distinct atomic sentences is lifted, instances of P and Q can be found for which P v Q → P is a tautology: e.g., let P be ‘it is raining or it is not raining’ and Q be ‘it is hot’. Then it is easily shown by means of the appropriate derived truth table that the sentence ‘if either it is raining or it is not raining or it is hot then either it is raining or it is not raining’ is a tautology. Furthermore, if P and Q are the same sentence then P v Q → P is a tautology. As a second example, in general P → Q is not a tautology, that is, it is easy to find sentences P and Q such that P → Q is not a tautology, but if P and Q are the same sentence P → Q is a tautology.

      Finally it should also be noticed that if a sentence is a tautology, we may substitute any compound sentence for a component atomic sentence (in all its occurrences) and the result will be a tautology. For example, the appropriate truth table quickly shows that if P is an atomic sentence P → P is a tautology, but once this is shown it easily follows that P → P is a tautology when P is any sentence whatsoever.

      The last two paragraphs may be summarized in two useful rules:

      (I) A statement which is not

      Enjoying the preview?
      Page 1 of 1