Tan S.T. Finite Mathematics for the Managerial, Life, and Social Sciences
Подождите немного. Документ загружается.
This page intentionally left blank
In how many ways can the Futurists
(a rock group) plan their concert
tour to San Francisco, Los Angeles,
San Diego, Denver, and Las Vegas if
the three performances in California
must be given consecutively? In
Example 13, page 343, we will show
how to determine the number of
possible different itineraries.
W
E OFTEN DEAL with well-defined collections of objects
called sets. In this chapter, we see how sets can be
combined algebraically to yield other sets. We also look at some
techniques for determining the number of elements in a set and
for determining the number of ways the elements of a set can be
arranged or combined. These techniques enable us to solve
many practical problems, as you will see throughout the chapter.
SETS AND COUNTING
6
© Photodisc/Getty Images
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 313
314 6 SETS AND COUNTING
Set Terminology and Notation
We often deal with collections of different kinds of objects. For example, in conduct-
ing a study of the distribution of the weights of newborn infants, we might consider
the collection of all infants born in Massachusetts General Hospital during 2006. In a
study of the fuel consumption of compact cars, we might be interested in the collec-
tion of compact cars manufactured by General Motors in the 2006 model year. Such
collections are examples of sets. More specifically, a set is a well-defined collection
of objects. Thus, a set is not just any collection of objects; a set must be well defined
in the sense that if we are given an object, then we should be able to determine
whether or not it belongs to the collection.
The objects of a set are called the elements, or members, of a set and are usually
denoted by lowercase letters a, b, c, . . . ; the sets themselves are usually denoted by
uppercase letters A, B, C, . . . . The elements of a set can be displayed by listing all the
elements between braces. For example, using roster notation, the set A consisting of
the first three letters of the English alphabet is written
A {a, b, c}
The set B of all letters of the alphabet can be written
B {a, b, c, . . . , z}
Another notation commonly used is set-builder notation. Here, a rule is given
that describes the definite property or properties an object x must satisfy to qualify for
membership in the set. Using this notation, the set B is written as
B { is a letter of the English alphabet}
and is read “B is the set of all elements x such that x is a letter of the English alphabet.”
If a is an element of a set A, we write a 僆 A and read “a belongs to A” or “a is
an element of A.” If, however, the element a does not belong to the set A, then we
write a 僆 A and read “a does not belong to A.” For example, if A {1, 2, 3, 4, 5}, then
3 僆 A but 6 僆 A.
EXAMPLE 1
Let A, B, and C be the sets
A {a, e, i, o, u}
B {a, i, o, e, u}
C {a, e, i, o}
Set Equality
Two sets A and B are equal, written A B, if and only if they have exactly the
same elements.
x 0x
6.1 Sets and Set Operations
Explore & Discuss
1. Let A denote the collection of all the days in August 2006 in which the average daily
temperature at the San Francisco International Airport was approximately 75°F. Is A a
set? Explain your answer.
2. Let B denote the collection of all the days in August 2006 in which the average daily
temperature at the San Francisco International Airport was between 73.5°F and 81.2°F,
inclusive. Is B a set? Explain your answer.
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 314
6.1 SETS AND SET OPERATIONS 315
Then, A B since they both contain exactly the same elements. Note that the order
in which the elements are displayed is immaterial. Also, A C since u 僆 A but
u 僆 C. Similarly, we conclude that B C.
By this definition, two sets A and B are equal if and only if (1) A 債 B and (2) B 債 A.
You can verify this (see Exercise 66).
EXAMPLE 2
Referring to Example 1, we find that C 債 B since every element of
C is also an element of B. Also, if D is the set
D {a, e, i, o, x}
then D is not a subset of A, written D 債 A, since x 僆 D but x 僆 A. Observe that
A 債 D as well, since u 僆 A but u 僆 D.
If A and B are sets such that A 債 B but A B, then we say that A is a proper sub-
set of B. In other words, a set A is a proper subset of a set B, written A 傺 B, if
(1) A 債 B and (2) there exists at least one element in B that is not in A. The second
condition states that the set A is properly “smaller” than the set B.
EXAMPLE 3
Let A {1, 2, 3, 4, 5, 6} and B {2, 4, 6}. Then B is a proper subset
of A because (1) B 債 A, which is easily verified, and (2) there exists at least one
element in A that is not in B—for example, the element 1.
When we refer to sets and subsets we use the symbols 傺, 債, 傻, and 傶 to express
the idea of “containment.” However, when we wish to show that an element is
contained in a set, we use the symbol 僆 to express the idea of “membership.”
Thus, in Example 3, we would write 1 僆 A and not {1} 僆 A.
The empty set, , is a subset of every set. To see this, observe that has no ele-
ments. Thus it contains no element that is not also in any set A.
EXAMPLE 4
List all subsets of the set A {a, b, c}.
Solution
There is one subset consisting of no elements—namely, the empty set .
Next, observe that there are three subsets consisting of one element,
{a}, {b}, {c}
three subsets consisting of two elements,
{a, b}, {a, c}, {b, c}
and one subset consisting of three elements, the set A itself. Therefore, the subsets
of A are
, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}
Empty Set
The set that contains no elements is called the empty set and is denoted by .
Subset
If every element of a set A is also an element of a set B, then we say that A is a
subset of B and write A 債 B.
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 315
In contrast with the empty set, we have, at the other extreme, the notion of a
largest, or universal, set. A universal set is the set of all elements of interest in a par-
ticular discussion. It is the largest in the sense that all sets considered in the discussion
of the problem are subsets of the universal set. Of course, different universal sets are
associated with different problems, as shown in Example 5.
EXAMPLE 5
a. If the problem at hand is to determine the ratio of female to male students in a
college, then a logical choice of a universal set is the set consisting of the whole
student body of the college.
b. If the problem is to determine the ratio of female to male students in the business
department of the college in part (a), then the set of all students in the business
department can be chosen as the universal set.
A visual representation of sets is realized through the use of Venn diagrams,
which are of considerable help in understanding the concepts introduced earlier as
well as in solving problems involving sets. The universal set U is represented by a rect-
angle, and subsets of U are represented by regions lying inside the rectangle.
EXAMPLE 6
Use Venn diagrams to illustrate the following statements:
a. The sets A and B are equal.
b. The set A is a proper subset of the set B.
c. The sets A and B are not subsets of each other.
Solution
The respective Venn diagrams are shown in Figure 1a–c.
(c) A 債 B and B 債 A
Set Operations
Having introduced the concept of a set, our next task is to consider operations on
sets—that is, to consider ways in which sets can be combined to yield other sets.
These operations enable us to combine sets in much the same way the operations of
addition and multiplication enable us to combine numbers to obtain other numbers. In
what follows, all sets are assumed to be subsets of a given universal set U.
U
U
A, B
U U
or
AB
A
AB
B
316 6 SETS AND COUNTING
FIGURE 1
(a) A B (b) A 傺 B
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 316
The shaded portion of the Venn diagram (Figure 2) depicts the set A 傼 B.
EXAMPLE 7
If A {a, b, c} and B {a, c, d}, then A 傼 B {a, b, c, d}.
The shaded portion of the Venn diagram (Figure 3) depicts the set A 傽 B.
EXAMPLE 8
Let A {a, b, c} and B {a, c, d}. Then A 傽 B {a, c}. (Compare
this result with Example 7.)
EXAMPLE 9
Let A {1, 3, 5, 7, 9} and B {2, 4, 6, 8, 10}. Then A 傽 B .
The two sets of Example 9 have empty, or null, intersection. In general, the sets A and
B are said to be disjoint if they have no elements in common—that is, if A 傽 B .
EXAMPLE 10
Let U be the set of all students in the classroom. If M
{x 僆 U 0x is male} and F {x 僆 U 0x is female}, then F 傽 M and so F and M
are disjoint.
The shaded portion of the Venn diagram (Figure 4) shows the set A
c
.
EXAMPLE 11
Let U {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and A {2, 4, 6, 8, 10}. Then
A
c
{1, 3, 5, 7, 9}.
6.1 SETS AND SET OPERATIONS 317
U
U
AB
FIGURE 2
Set union A 傼 B
A B
U
FIGURE 3
Set intersection A 傽 B
A
A
c
U
FIGURE 4
Set complementation
Set Union
Let A and B be sets. The union of A and B, written A 傼 B, is the set of all ele-
ments that belong to either A or B or both.
A 傼 B 5x 0x 僆 A or x 僆 B or both6
Set Intersection
Let A and B be sets. The set of elements common to the sets A and B, written
A 傽 B, is called the
intersection of A and B.
A 艚 B 5x 0x 僆 A and x 僆 B6
Complement of a Set
If U is a universal set and A is a subset of U, then the set of all elements in U
that are not in A is called the
complement of A and is denoted A
c
.
A
c
5x 0x 僆 U and x 僆 A6
Explore & Discuss
Let A, B, and C be nonempty subsets of a set U.
1. Suppose A 傽 B , A 傽 C , and B 傽 C . Can you conclude that
A 傽 B 傽 C ? Explain your answer with an example.
2. Suppose A 傽 B 傽 C . Can you conclude that A 傽 B , A 傽 C , and
B 傽 C ? Explain your answer.
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 317
The following rules hold for the operation of complementation. See whether you
can verify them.
The operations on sets satisfy the following properties.
Two additional properties, referred to as De Morgan’s laws, hold for the operations on
sets.
Equation (1) states that the complement of the union of two sets is equal to the inter-
section of their complements. Equation (2) states that the complement of the intersec-
tion of two sets is equal to the union of their complements.
We will not prove De Morgan’s laws here, but we will demonstrate the validity
of (2) in the following example.
EXAMPLE 12
Using Venn diagrams, show that
(A 傽 B)
c
A
c
傼 B
c
Solution
(A 傽 B)
c
is the set of elements in U but not in A 傽 B and is thus the shaded
region shown in Figure 5. Next, A
c
and B
c
are shown in Figure 6a–b. Their union,
A
c
傼 B
c
, is easily seen to be equal to (A 傽 B)
c
by referring once again to Figure 5.
De Morgan’s Laws
Let A and B be sets. Then
(A 傼 B)
c
A
c
傽 B
c
(1)
(A 傽 B)
c
A
c
傼 B
c
(2)
Properties of Set Operations
Let U be a universal set. If A, B, and C are arbitrary subsets of U, then
A 傼 B B 傼 A
Commutative law for union
A 傽 B B 傽 A Commutative law for intersection
A 傼 (B 傼 C) (A 傼 B) 傼 C Associative law for union
A 傽 (B 傽 C) (A 傽 B) 傽 C Associative law for intersection
A 傼 (B 傽 C)
(A 傼 B) 傽 (A 傼 C)
Distributive law for union
A 傽 (B 傼 C)
(A 傽 B) 傼 (A 傽 C)
Distributive law for intersection
Set Complementation
If U is a universal set and A is a subset of U, then
a. U
c
b.
c
U c. (A
c
)
c
A
d. A 傼 A
c
U e. A 傽 A
c
318 6 SETS AND COUNTING
B
A
U
FIGURE 5
(A 傽 B)
c
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 318
(a) (b)
EXAMPLE 13
Let U {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A {1, 2, 4, 8, 9}, and
B {3, 4, 5, 6, 8}. Verify by direct computation that (A 傼 B)
c
A
c
傽 B
c
.
Solution
A 傼 B {1, 2, 3, 4, 5, 6, 8, 9}, so (A 傼 B)
c
{7, 10}. Moreover,
A
c
{3, 5, 6, 7, 10} and B
c
{1, 2, 7, 9, 10}, so A
c
傽 B
c
{7, 10}. The required
result follows.
APPLIED EXAMPLE 14
Automobile Options Let U denote the set
of all cars in a dealer’s lot, and let
A {x 僆 U 0x is equipped with automatic transmission}
B {x 僆 U 0x is equipped with air conditioning}
C {x 僆 U 0x is equipped with side air bags}
Find an expression in terms of A, B, and C for each of the following sets:
a. The set of cars with at least one of the given options
b. The set of cars with exactly one of the given options
c. The set of cars with automatic transmission and side air bags but no air
conditioning
Solution
a. The set of cars with at least one of the given options is A 傼 B 傼 C (Fig-
ure 7a).
b. The set of cars with automatic transmission only is given by A 傽 B
c
傽 C
c
.
Similarly, we find that the set of cars with air conditioning only is given by
B 傽 C
c
傽 A
c
, while the set of cars with side air bags only is given by
C 傽 A
c
傽 B
c
. Thus, the set of cars with exactly one of the given options is
(A 傽 B
c
傽 C
c
) 傼 (B 傽 C
c
傽 A
c
) 傼 (C 傽 A
c
傽 B
c
) (Figure 7b).
c. The set of cars with automatic transmission and side air bags but no air condi-
tioning is given by A 傽 C 傽 B
c
(Figure 7c).
A
U
B
B
c
U
A
c
6.1 SETS AND SET OPERATIONS 319
FIGURE 6
A
c
傼 B
c
is the set obtained by joining (a)
and (b).
U U
C
B A
U
C
B
A
A
C
B
(a) The set of cars with at least one (b) The set of cars with exactly one (c) The set of cars with automatic
option option transmission and side air bags but
no air conditioning
FIGURE 7
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 319
320 6 SETS AND COUNTING
1. Let U {1, 2, 3, 4, 5, 6, 7}, A {1, 2, 3}, B {3, 4, 5, 6},
and C {2, 3, 4}. Find the following sets:
a. A
c
b. A 傼 B c. B 傽 C
d. (A 傼 B) 傽 C e. (A 傽 B) 傼 C f. A
c
傽 (B 傼 C)
c
2. Let U denote the set of all members of the House of Rep-
resentatives. Let
D {x 僆 U 0x is a Democrat}
R {x 僆 U 0x is a Republican}
F {x 僆 U 0x is a female}
L {x 僆 U 0x is a lawyer by training}
Describe each of the following sets in words.
a. D 傽 F b. F
c
傽 R c. D 傽 F 傽 L
c
Solutions to Self-Check Exercises 6.1 can be found on
page 323.
1. a. What is a set? Give an example.
b. When are two sets equal? Give an example of two equal
sets.
c. What is the empty set?
2. What can you say about two sets A and B such that
a. A 傼 B 債 A b. A 傼 B
c. A 傽 B B d. A 傽 B
3. a. If A 傺 B, what can you say about the relationship
between A
c
and B
c
?
b. If A
c
, what can you say about A?
In Exercises 1–4, write the set in set-builder notation.
1. The set of gold medalists in the 2006 Winter Olympic
Games
2. The set of football teams in the NFL
3. {3, 4, 5, 6, 7}
4. {1, 3, 5, 7, 9, 11, . . . , 39}
In Exercises 5–8, list the elements of the set in roster
notation.
5. {x 0x is a digit in the number 352,646}
6. {x 0x is a letter in the word HIPPOPOTAMUS}
7. {x 02 x 4 and x is an integer}
8. {x 02 x 4 and x is a fraction}
In Exercises 9–14, state whether the statements are true
or false.
9. a. {a, b, c} {c, a, b} b. A 僆 A
10. a. 僆 A b. A 傺 A
11. a. 0 僆 b. 0
12. a. {} b. {a, b} 僆 {a, b, c}
13. {Chevrolet, Pontiac, Buick} 傺 {x 0x is a division of General
Motors}
14. {x 0x is a silver medalist in the 2006 Winter Olympic
Games}
In Exercises 15 and 16, let A ⴝ
{
1, 2, 3, 4, 5
}
. Determine
whether the statements are true or false.
15. a. 2 僆 A b. A 債 {2, 4, 6}
16. a. 0 僆 A b. {1, 3, 5} 僆 A
17. Let A {1, 2, 3}. Which of the following sets are equal
to A?
a. {2, 1, 3} b. {3, 2, 1}
c. {0, 1, 2, 3}
18. Let A {a, e, l, t, r}. Which of the following sets are equal
to A?
a. {x 0x is a letter of the word later}
b. {x 0x is a letter of the word latter}
c. {x 0x is a letter of the word relate}
19. List all subsets of the following sets:
a. {1, 2} b. {1, 2, 3} c. {1, 2, 3, 4}
20.
List all subsets of the set A {IBM, U.S. Steel, Union
Carbide, Boeing}. Which of these are proper subsets of A?
In Exercises 21–24, find the smallest possible set (i.e.,
the set with the least number of elements) that contains
the given sets as subsets.
21. {1, 2}, {1, 3, 4}, {4, 6, 8, 10}
22. {1, 2, 4}, {a, b}
23. {Jill, John, Jack}, {Susan, Sharon}
24. {GM, Ford, Chrysler}, {Daimler-Benz, Volkswagen}, {Toy-
ota, Nissan}
6.1 Exercises
6.1 Self-Check Exercises
6.1 Concept Questions
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 320
25. Use Venn diagrams to represent the following relationships:
a. A 傺 B and B 傺 C
b. A 傺 U and B 傺 U, where A and B have no elements in
common
c. The sets A, B, and C are equal.
26. Let U denote the set of all students who applied for admis-
sion to the freshman class at Faber College for the upcom-
ing academic year, and let
A {x 僆 U 0x is a successful applicant}
B {x 僆 U 0x is a female student who enrolled in
the freshman class}
C {x 僆 U 0x is a male student who enrolled in
the freshman class}
a. Use Venn diagrams to represent the sets U, A, B, and C.
b. Determine whether the following statements are true or
false.
i. A 債 B ii. B 傺 A iii. C 傺 B
In Exercises 27 and 28, shade the portion of the accom-
panying figure that represents each set.
27. a. A 傽 B
c
b. A
c
傽 B
28. a. A
c
傽 B
c
b. (A 傼 B)
c
In Exercises 29–32, shade the portion of the accompany-
ing figure that represents each set.
29. a. A 傼 B 傼 C b. A 傽 B 傽 C
30. a. A 傽 B 傽 C
c
b. A
c
傽 B 傽 C
31. a. A
c
傽 B
c
傽 C
c
b. (A 傼 B)
c
傽 C
32. a. A 傼 (B 傽 C)
c
b. (A 傼 B 傼 C)
c
In Exercises 33–36, let U ⴝ
{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
}
,
A ⴝ
{
1, 3, 5, 7, 9
}
, B ⴝ
{
2, 4, 6, 8, 10
}
, and C ⴝ
{
1, 2, 4,
5, 8, 9
}
. List the elements of each set.
33. a. A
c
b. B 傼 C c. C 傼 C
c
34. a. C 傽 C
c
b. (A 傽 C)
c
c. A 傼 (B 傽 C)
35. a. (A 傽 B) 傼 C b. (A 傼 B 傼 C )
c
c. (A 傽 B 傽 C)
c
36. a. A
c
傽 (B 傽 C
c
) b. (A 傼 B
c
) 傼 (B 傽 C
c
)
c. (A 傼 B)
c
傽 C
c
U
C
A B
A
U
B
In Exercises 37 and 38, determine whether the pairs of
sets are disjoint.
37. a. {1, 2, 3, 4}, {4, 5, 6, 7}
b. {a, c, e, t}, {b, d, f }
38. a. , {1, 3, 5}
b. {0, 1, 3, 4}, {0, 2, 5, 7}
In Exercises 39–42, let U denote the set of all employees
at Universal Life Insurance Company and let
T ⴝ
{
x 苸 U 兩 x drinks tea
}
C ⴝ
{
x 苸 U 兩 x drinks coffee
}
Describe each set in words.
39. a. T
c
b. C
c
40. a. T 傼 C b. T 傽 C
41. a. T 傽 C
c
b. T
c
傽 C
42. a. T
c
傽 C
c
b. (T 傼 C)
c
In Exercises 43–46, let U denote the set of all employees
in a hospital. Let
N ⴝ
{
x 苸 U 兩 x is a nurse
}
D ⴝ
{
x 苸 U 兩 x is a doctor
}
A ⴝ
{
x 苸 U 兩 x is an administrator
}
M ⴝ
{
x 苸 U 兩 x is a male
}
F ⴝ
{
x 苸 U 兩 x is a female
}
Describe each set in words.
43. a. D
c
b. N
c
44. a. N 傼 D b. N 傽 M
45. a. D 傽 M
c
b. D 傽 A
46. a. N 傽 F b. (D 傼 N)
c
In Exercises 47 and 48, let U denote the set of all sena-
tors in Congress and let
D ⴝ
{
x 苸 U 兩 x is a Democrat
}
R ⴝ
{
x 苸 U 兩 x is a Republican
}
F ⴝ
{
x 苸 U 兩 x is a female
}
L ⴝ
{
x 苸 U 兩 x is a lawyer
}
Write the set that represents each statement.
47. a. The set of all Democrats who are female
b. The set of all Republicans who are male and are not
lawyers
48. a. The set of all Democrats who are female or are lawyers
b. The set of all senators who are not Democrats or are
lawyers
6.1 SETS AND SET OPERATIONS 321
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 321