sibilities, there is a natural way of assigning a set to each statement.

First of all, we take the set of logical possibilities as our universal set.

Then to each statement we assign the subset of logical possibilities

of the universal set for which that statement is true. This idea is so

important that we embody it in a formal de¬nition.

De¬nition. Let U be a set of logical possibilities, let p be a state-

ment relative to it, and let P be that subset of the possibilities for

which p is true; then we call P the truth set of p.

If p and q are statements, then p∨q and p§q are also statements and

hence must have truth sets. To ¬nd the truth set of p ∨ q, we observe

that it is true whenever p is true or q is true (or both). Therefore we

must assign to p ∨ q the logical possibilities which are in P or in Q (or

both); that is, we must assign to p ∨ q the set P ∪ Q. On the other

hand, the statement p § q is true only when both p and q are true, so

that we must assign to p § q the set P © Q.

Thus we see that there is a close connection between the logical op-

eration of disjunction and the set operation of union, and also between

conjunction and intersection. A careful examination of the de¬nitions

of union and intersection shows that the word “or” occurs in the de¬ni-

tion of union and the word “and” occurs in the de¬nition of intersection.

Thus the connection between the two theories is not surprising.

Since the connective “not” occurs in the de¬nition of the comple-

˜

ment of a set, it is not surprising that the truth set of ¬p is P . This

2.3. THE RELATIONSHIP BETWEEN SETS AND COMPOUND STATEMENTS15

Figure 2.6: ™¦

follows since ¬p is true when p is false, so that the truth set of ¬p

contains all logical possibilities for which p is false, that is, the truth

˜

set of ¬p is P .

The truth sets of two propositions p and q are shown in Figure

2.6. Also marked on the diagram are the various logical possibilities

for these two statements. The reader should pick out in this diagram

the truth sets of the statements p ∨ q, p § q, ¬p, and ¬q.

The connection between a statement and its truth set makes it pos-

sible to “translate” a problem about compound statements into a prob-

lem about sets. It is also possible to go in the reverse direction. Given

a problem about sets, think of the universal set as being a set of logical

possibilities and think of a subset as being the truth set of a statement.

Hence we can “translate” a problem about sets into a problem about

compound statements.

So far we have discussed only the truth sets assigned to compound

statements involving ∨, §, and ¬. All the other connectives can be

de¬ned in terms of these three basic ones, so that we can deduce what

truth sets should be assigned to them. For example, we know that

p ’ q is equivalent to ¬p ∨ q (see Figure ??). Hence the truth set of

˜

p ’ q is the same as the truth set of ¬p∨q, that is, it is P ∪Q. The Venn

diagram for p ’ q is shown in Figure 2.7, where the shaded area is the

truth set for the statement. Observe that the unshaded area in Figure

˜

2.7 is the set P ’ Q = P © Q, which is the truth set of the statement

˜

p § ¬q. Thus the shaded area is the set P ’ Q = P © Q, which is the

truth set of the statement ¬(p § ¬q). We have thus discovered the fact

that p ’ q, ¬p ∨ q, and ¬(p § ¬q) are equivalent. It is always the

case that two compound statements are equivalent if and only if they

16 CHAPTER 2. SETS AND SUBSETS

Figure 2.7: ™¦

have the same truth sets. Thus we can test for equivalence by checking

whether they have the same Venn diagram.

Suppose that p is a statement that is logically true. What is its

truth set? Now p is logically true if and only if it is true in every

logically possible case, so that the truth set of p must be U . Similarly,

if p is logically false, then it is false for every logically possible case, so

that its truth set is the empty set ….

Finally, let us consider the implication relation. Recall that p im-

plies p if and only if the conditional p ’ q is logically true. But p ’ q

is logically true if and only if its truth set is U , that is, (P ’ Q) = U , or

(P ’ Q) = …. From Figure 2.4 we see that if P ’ Q is empty, then P is

contained in Q. We shall symbolize the containing relation as follows:

P ‚ Q means “P is a subset of Q”. We conclude that p ’ q is logically

true if and only if P ‚ Q.

Figure 2.8 supplies a “dictionary” for translating from statement

language to set language, and back. To each statement relative to a

set of possibilities U there corresponds a subset of U , namely the truth

set of the statement. This is shown in lines 1 and 2 of the ¬gure. To

each connective there corresponds an operation on sets, as illustrated

in the next four lines. And to each relation between statements there

corresponds a relation between sets, examples of which are shown in

the last two lines of the ¬gure.

Example 2.3 Prove by means of a Venn diagram that the statement

[p ∨ (¬p ∨ q)] is logically true. The assigned set of this statement is

˜

[P ∪ (P ∪ Q)], and its Venn diagram is shown in Figure 2.9. In

˜

that ¬gure the set P is shaded vertically, and the set P ∪ Q is shaded

2.3. THE RELATIONSHIP BETWEEN SETS AND COMPOUND STATEMENTS17

Figure 2.8: ™¦

Figure 2.9: ™¦

18 CHAPTER 2. SETS AND SUBSETS

Figure 2.10: ™¦

horizontally. Their union is the entire shaded area, which is U , so that

™¦

the compound statement is logically true.

Example 2.4 Prove by means of Venn diagrams that p ∨ (q § r) is

equivalent to (p ∨ q) § (p ∨ r). The truth set of p ∨ (q § r) is the

entire shaded area in diagram (a) of Figure 2.10, and the truth set of

(p ∨ q) § (p ∨ r) is the doubly shaded area in diagram (b). Since these

two sets are equal, we see that the two statements are equivalent. ™¦

Example 2.5 Show by means of a Venn diagram that q implies p ’ q.

The truth set of p ’ q is the shaded area in Figure 2.7. Since this

shaded area includes the set Q. we see that q implies p ’ q. ™¦

Exercises

Note. In Exercises 1, 2, and 3, ¬nd ¬rst the truth set of each

statement.

1. Use Venn diagrams to test which of the following statements are

logically true or logically false.

(a) p ∨ ¬p.

[Ans. logically true.]

2.3. THE RELATIONSHIP BETWEEN SETS AND COMPOUND STATEMENTS19

(b) p § ¬p.

[Ans. logically false.]

(c) p ∨ (¬p § q).

(d) p ’ (q ’ p).

[Ans. logically true.]

(e) p § ¬(q ’ p).

[Ans. logically false.]

2. Use Venn diagrams to test the following statements for equiva-

lences.

(a) p ∨ ¬q.

(b) ¬(p § q).

(c) ¬(q § ¬q).

(d) p ’ ¬q.

(e) ¬p ∨ ¬q.

[Ans. 2a and 2c equivalent; 2b and 2d and 2e equivalent.]

3. Use Venn diagrams for the following pairs of statements to test

whether one implies the other.

(a) p; p § q.

(b) p § ¬q; ¬p ’ ¬q.

(c) p ’ q; q ’ p.

(d) p § q; p § ¬q.

4. Devise a test for inconsistency of p and q, using Venn diagrams.

5. Three or more statements are said to be inconsistent if they can-

not all be true. What does this state about their truth sets?

6. Consider these three statements.

If this is a good course, then I will work hard in it.

If this is not a good course, then I shall get a bad grade in it.

20 CHAPTER 2. SETS AND SUBSETS

I will not work hard, but I will get a good grade in this course.

(a) Assign variables to the components of each of these state-

ments.

(b) Bring the statements into symbolic form.

(c) Find the truth sets of the statements.

(d) Rest for consistency.

[Ans. Inconsistent.]

Note. In Exercises 7, 8, and 9, assign to each set a statement

having it as a truth set.

7. Use truth tables to ¬nd which of the following sets are empty.

˜˜

(a) (P ∪ Q) © (P ∪ Q).

˜

(b) (P © Q) © (Q © R).

(c) (P © Q) ’ P .

˜˜

(d) (P ∪ R) © (P ∪ Q)

[Ans. 7b and 7c.]

8. Use truth tables to ¬nd out whether the following sets are all

di¬erent.

(a) P © (Q ∪ R).

(b) (R ’ Q) ∪ (Q ’ R).

(c) (R ∪ Q) © (R © Q).

(d) (P © Q) ∪ (P © R).

˜ ˜ ˜ ˜ ˜˜

(e) (P © Q © R) ∪ (P © Q © R) ∪ (P © Q © R) ∪ (P © Q © R).

9. Use truth tables for the following pairs of sets to test whether one

is a subset of the other.

(a) P ; P © Q.

˜ ˜

(b) P © Q; Q © P .

(c) P ’ Q; Q ’ P .

21

2.4. THE ABSTRACT LAWS OF SET OPERATIONS

˜

(d) P © Q; P ∪ Q.

10. Show, both by the use of truth tables and by the use of Venn

diagrams, that p § (q ∨ r) is equivalent to (p § q) ∨ (p § r).

11. The symmetric di¬erence of P and Q is de¬ned to be (P ’ Q) ∪

(Q ’ P ). What connective corresponds to this set operation?

12. Let p, q, r be a complete set of alternatives (see Section ??). What

can we say about the truth sets P, Q, R?

2.4 The abstract laws of set operations

The set operations which we have introduced obey some very simple ab-

stract laws, which we shall list in this section. These laws can be proved

by means of Venn diagrams or they can be translated into statements

and checked by means of truth tables.

The abstract laws given below bear a close resemblance to the ele-

mentary algebraic laws with which the student is already familiar. The

resemblance can be made even more striking by replacing ∪ by + and

© by —. For this reason, a set, its subsets, and the laws of combi-

nation of subsets are considered an algebraic system, called a Boolean

algebra”after the British mathematician George Boole who was the

¬rst person to study them from the algebraic point of view. Any other

system obeying these laws, for example, the system of compound state-

ments studied in Chapter ??, is also known as a Boolean algebra. We

can study any of these systems from either the algebraic or the logical

point of view.

Below are the basic laws of Boolean algebras. The proofs of these

laws will be left as exercises.

The laws governing union and intersection:

22 CHAPTER 2. SETS AND SUBSETS

A1. A ∪ A = A.

A2. A © A = A.

A3. A ∪ B = B ∪ A.

A4. A © B = B © A.

A5. A ∪ (B ∪ C) = (A ∪ B) ∪ C.

A6. A © (B © C) = (A © B) © C.

A7. A © (B ∪ C) = (A © B) ∪ (A © C).

A8. A ∪ (B © C) = (A ∪ B) © (A ∪ C).

A9. A ∪ U = U .

A10. A © … = ….

A11. A ∪ … = A.

A12. A © U = A.

The laws governing complements:

˜˜

B1. A = A.

˜

B2. A ∪ A = U .

˜

B3. A © A = ….

˜˜

B4. A ∪ B = A © B.

˜˜

B5. A © B = A ∪ B.

˜

B6. U = ….

The laws governing set-di¬erences:

˜

C1. A ’ B = A © B.

˜

C2. U ’ A = A.

C3. A ’ U = ….

C4. A ’ … = A.

C5. … ’ A = ….

C6. A ’ A = ….

C7. (A ’ B) ’ C = A ’ (B ∪ C).

C8. A ’ (B ’ C) = (A ’ B) ∪ (A © C).

C9. A ∪ (B ’ C) = (A ∪ B) ’ (C ’ A).

C10. A © (B ’ C) = (A © B) ’ (A © C).

Exercises

1. Test laws in the group A1“A12 by means of Venn diagrams.

2. “Translate” the A-laws into laws about compound statements.

Test these by truth tables.

3. Test the laws in groups B and C by Venn diagrams.

23

2.4. THE ABSTRACT LAWS OF SET OPERATIONS

4. “Translate” the B- and C-laws into laws about compound state-

ments. Test these by means of truth tables.

5. Derive the following results from the 28 basic laws.

˜

(a) A = (A © B) ∪ (A © B).

˜ ˜

(b) A ∪ B = (A © B) ∪ (A © B) ∪ (A © B).

(c) A © (A ∪ B) = A.

˜

(d) A ∪ (A © B) = A ∪ B.

6. From the A- and B-laws and from C1, derive C2“C6.

7. Use A1“A12 and C2“C10 to derive B1, B2, B3, and B6.

Supplementary exercises.

Note. Use the following de¬nitions in these exercises: Let + be

symmetric di¬erence (see Exercise 11), — be intersection, let 0 be

… and 1 be U .

8. From A2, A4, and A6 derive the properties of multiplication.

9. Find corresponding properties for addition.

10. Set up addition and multiplication tables for 0 and 1.

11. What do A — 0, A — 1, A + 0, and A + 1 equal?

˜

[Ans. 0; A; A; A.]

12. Show that

A — (B + C) = (A — B) + (A — C).

13. Show that the following equation is not always true.

A + (B — C) = (A + B) — (A + C).

24 CHAPTER 2. SETS AND SUBSETS

Figure 2.11: ™¦

2.5 Two-digit number systems

In the decimal number system one can write any number by using only

the ten digits, 0, 1, 2, . . . , 9. Other number systems can be constructed

which use either fewer or more digits. Probably the simplest number

system is the binary number system which uses only the digits 0 and

1. We shall consider all the possible ways of forming number systems

using only these two digits.

The two basic arithmetical operations are addition and multiplica-

tion. To understand any arithmetic system, it is necessary to know

how to add or multiply any two digits together. Thus to understand

the decimal system, we had to learn a multiplication table and an ad-

dition table, each of which had 100 entries. To understand the binary

system, we have to learn a multiplication and an addition table, each

of which has only four entries. These are shown in Figure 2.11. The

multiplication table given there is completely determined by the two

familiar rules that multiplying a number by zero gives zero, and mul-

tiplying a number by one leaves it unchanged. For addition, we have

only the rule that the addition of zero to a number does not change

that number. The latter rule is su¬cient to determine all but one of

the entries in the addition table in Figure 2.11. We must still decide

what shall be the sum 1 + 1.

What are the possible ways in which we can complete the addition

table? The only one-digit numbers that we can use are 0 and l, and

these lead to interesting systems. Of the possible two-digit numbers, we

see that 00 and 01 are the same as 0 and l and so do not give anything

new. The number 11 or any greater number would introduce a “jump”

in the table, hence the only other possibility is 10. The addition tables

of these three di¬erent number systems are shown in Figure 2.12, and

they all have the multiplication table shown in Figure 2.11. Each of

these systems is interesting in itself as the interpretations below show.

Let us say that the parity of a positive integer is the fact of its being

25

2.5. TWO-DIGIT NUMBER SYSTEMS

Figure 2.12: ™¦

odd or even. Consider now the number system having the addition

table (a) in Figure 2.12 and let 0 represent “even” and 1 represent

“odd”. The tables above now tell how the parity of a combination of