<< . .

. 2
( : 20)



. . >>

If we have a number of statements relative to a set of logical pos-
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

<< . .

. 2
( : 20)



. . >>