In considering any problem, either logical or mathematical, it is important to have a thorough understanding of the logical possibilities connected with the problem. The consideration in this section is undertaken to determine the truth or falsity of statements related to a problem. As an illustration of what we mean by logical possibilities, the truth-table method for analyzing a compound proposition is nothing more than a tabulation of the various logical possibilities for the simple propositions involved. However, the truth table is not always a sufficiently refined analysis to serve the purposes of the problem.                                                                        For example, consider the following proposition concerning integers a and b. "Either a is not less than b or b is not less than a. " Intuitively, it is evident that this proposition is a tautology. Yet if we designate by p the proposition "a is less than b, " and by q the proposition "b is less than a," and construct the truth table for the compound proposition  (Table 1-1), we fail to establish this fact because 0 appears in row 1 of the table.

TABLE 1-1

TRIITH TABLE FOR p' + q'

The trouble is that although truth tables are adequate for considering the logical possibilities for functions of propositional variables alone, they are usually not adequate for the treatment of specific propositions, that is, for functions involving constants. In the above example, consideration of the propositions p and q reveals that it is impossible for p and q to be true simultaneously. Hence row 1 of the table simply does not apply,  and the proposition is a tautology.

The propositions considered above furnish an example of related propositions. Many other relations are possible between two or more propositions, each identified by the fact that one or more rows of a corresponding truth table do not represent possible truth values for the propositions. It is not our purpose to investigate systematically all such relationships, but the example serves to illustrate a need for discussing the matter of logical possibilities, at least in a general way.

Another instance where a discussion of logical possibilities is important arises in the following example.

EXAMPLE. A bowl contains fifteen marbles of which five are white, five are red, and five are blue. Two marbles are drawn, one at a time, from the bowl.

Discuss the truth value of the proposition "one white and one blue marble are drawn." (Such propositions are important in studying probability theory.)

 Solution. To analyze the truth properties of the proposition, it is helpful to consider the logical possibilities associated with the situation to which the proposition refers. These are tabulated in Table 1-2. It appears that in cases 6 and 8 the proposition is true and in all others it is false.

Table 1-2

In this example, nine cases were considered as logical possibilities. If,  however, the white balls were numbered and the proposition had been "white ball number 2 was drawn after a red ball," it would have been necessary to consider more than nine cases as logical possibilities. The number and nature of logical possibilities associated with a proposition or set of propositions depend on the propositions under consideration,  and no general formula or method can be given. If the propositions involve only variables, a truth table will suffice; in most other cases it will not.

The primary reason for discussing logical possibilities for propositions is to help in bridging the gap that exists intuitively between the algebra of sets and the algebra of logic. We may assign to any set of propositions under discussion a universal set whose elements are the logical possibilities for the set of propositions. This can usually be done in many ways. When it is required to specify these elements precisely, we will choose the most convenient set of possibilities that have the following two properties.

(1) The possibilities listed are such that in any conceivable circumstance, one and only one of the possibilities is the case.

(2) The possibilities are such that the truth value of each proposition can be determined by any one of the possibilities.

                  FIG. 1-1. Truth sets for compound propositions.

Next, a subset of this universal set is assigned to each proposition so that the subset consists of exactly those possibilities for which the proposition is true. This set is called the truth set for the proposition.

It should be clear that the truth set for a propositional function is uniquely determined by the truth sets for the simple propositions which make it up. We may even represent truth sets abstractly by Venn diagrams, exactly as we represented sets in (THE ALGEBRA OF SETS). This use of truth sets can be a very helpful aid to understanding logic. It also illustrates the strong relationship between the algebra of sets and the algebra of logic.

Figure 1-1 uses Venn diagrams to show the truth sets for pq, p + q, and p → q in terms of the truth sets for p and q. P and Q represent the truth sets for the propositions p and q, and the shaded areas represent the truth sets for the compound propositions.