250
Sets, Combinatorics, and Probability
91. Prove that for subsets A 1 , A 2 , … , A n and B of a set S, the following generalized distributive properties hold,
where n ≥ 2. (See Exercises 87 and 89.)
a. B c (A 1 d A 2 d c d A n ) = (B c A 1 ) d (B c A 2 ) d c d (B c A n )
b. B d (A 1 c A 2 c c c A n ) = (B d A 1 ) c (B d A 2 ) c c c (B d A n )
92. Prove that for subsets A 1 , A 2 , … , A n of a set S, the following generalized De Morgan’s laws hold, where
n ≥ 2. (See Exercises 82, 87, and 89.)
a. (A 1 c A 2 c c c A n )′ = A′ 1 d A′ 2 d c d A′ n
b. (A 1 d A 2 d c d A n )′ = A′ 1 c A′ 2 c c c A′ n
93. The operations of set union and set intersection can be extended to apply to an infinite family of sets. We
may describe the family as the collection of all sets A i , where i takes on any of the values of a fixed set I.
Here, I is called the index set for the family. The union of the family, d i[I
A i , is defined by
d i[I
A i = {x 0 x is a member of some A i }
The intersection of the family, t i[I
A i , is defined by
t i[I
A i = {x 0 x is a member of each A i }.
a. Let I = {1, 2, 3, …}, and for each i [ I, let A i be the set of real numbers in the interval (−1/i, 1/i ).
What is d i[I
A i ? What is t i[I
A i ?
b. Let I = {1, 2, 3 …}, and for each i [ I, let A i be the set of real numbers in the interval [−1/i, 1/i ].
What is d i[I
A i ? What is t i[I
A i ?
94. According to our use of the word “set,” if C is a subset of the universal set S, then every element of S either
does or does not belong to C. In other words, the probability of a member x of S being a member of C is
either 1 (x is a member of C ) or 0 (x is not a member of C ). C is a fuzzy set if every x [ S has a probability
p, 0 ≤ p ≤ 1, of being a member of C. The probability p associated with x is an estimate of the likelihood
that x may belong to C when the actual composition of C is unknown. Set operations can be done on fuzzy
sets as follows: If element x has probability p 1 of membership in C and probability p 2 of membership in D,
then the probability of x being a member of C c D, C d D, and C′ is, respectively, max( p 1 , p 2 ), min( p 1 , p 2 ),
and 1 − p 1 . (If we consider the statements x [ C and x [ D as propositional wffs A and B, respectively, with
certain probabilistic truth values, then the probability of x [ C c D is the probability that A ~ B is true. The
rules for fuzzy set operations then parallel the rules for fuzzy logic, discussed in Exercise 54, Section 1.1.)
Let S be a set of possible disease-causing agents, S = {genetics, virus, nutrition, bacteria, environment}.
The fuzzy sets AIDS and ALZHEIMERS are defined as AIDS = {genetics, 0.2; virus, 0.8; nutrition, 0.1;
bacteria, 0.4; environment, 0.3} and ALZHEIMERS = {genetics, 0.7; virus, 0.4; nutrition, 0.3; bacteria,
0.3; environment, 0.4}.
a. Find the fuzzy set AIDS c ALZHEIMERS.
b. Find the fuzzy set AIDS d ALZHEIMERS.
c. Find the fuzzy set (AIDS)′.
Exercises 95 and 96 complete the proof, begun in Section 2.2, that the second principle of induction, the first
principle of induction, and the principle of well-ordering are all equivalent.
95. The principle of well-ordering says that every nonempty set of positive integers has a smallest member.
Prove that the first principle of mathematical induction, that is,
1. P(1) is true
2. (4k)[P(k) true S P(k + 1) true]
f S P(n) true for all positive integers n
Sets, Combinatorics, and Probability
91. Prove that for subsets A 1 , A 2 , … , A n and B of a set S, the following generalized distributive properties hold,
where n ≥ 2. (See Exercises 87 and 89.)
a. B c (A 1 d A 2 d c d A n ) = (B c A 1 ) d (B c A 2 ) d c d (B c A n )
b. B d (A 1 c A 2 c c c A n ) = (B d A 1 ) c (B d A 2 ) c c c (B d A n )
92. Prove that for subsets A 1 , A 2 , … , A n of a set S, the following generalized De Morgan’s laws hold, where
n ≥ 2. (See Exercises 82, 87, and 89.)
a. (A 1 c A 2 c c c A n )′ = A′ 1 d A′ 2 d c d A′ n
b. (A 1 d A 2 d c d A n )′ = A′ 1 c A′ 2 c c c A′ n
93. The operations of set union and set intersection can be extended to apply to an infinite family of sets. We
may describe the family as the collection of all sets A i , where i takes on any of the values of a fixed set I.
Here, I is called the index set for the family. The union of the family, d i[I
A i , is defined by
d i[I
A i = {x 0 x is a member of some A i }
The intersection of the family, t i[I
A i , is defined by
t i[I
A i = {x 0 x is a member of each A i }.
a. Let I = {1, 2, 3, …}, and for each i [ I, let A i be the set of real numbers in the interval (−1/i, 1/i ).
What is d i[I
A i ? What is t i[I
A i ?
b. Let I = {1, 2, 3 …}, and for each i [ I, let A i be the set of real numbers in the interval [−1/i, 1/i ].
What is d i[I
A i ? What is t i[I
A i ?
94. According to our use of the word “set,” if C is a subset of the universal set S, then every element of S either
does or does not belong to C. In other words, the probability of a member x of S being a member of C is
either 1 (x is a member of C ) or 0 (x is not a member of C ). C is a fuzzy set if every x [ S has a probability
p, 0 ≤ p ≤ 1, of being a member of C. The probability p associated with x is an estimate of the likelihood
that x may belong to C when the actual composition of C is unknown. Set operations can be done on fuzzy
sets as follows: If element x has probability p 1 of membership in C and probability p 2 of membership in D,
then the probability of x being a member of C c D, C d D, and C′ is, respectively, max( p 1 , p 2 ), min( p 1 , p 2 ),
and 1 − p 1 . (If we consider the statements x [ C and x [ D as propositional wffs A and B, respectively, with
certain probabilistic truth values, then the probability of x [ C c D is the probability that A ~ B is true. The
rules for fuzzy set operations then parallel the rules for fuzzy logic, discussed in Exercise 54, Section 1.1.)
Let S be a set of possible disease-causing agents, S = {genetics, virus, nutrition, bacteria, environment}.
The fuzzy sets AIDS and ALZHEIMERS are defined as AIDS = {genetics, 0.2; virus, 0.8; nutrition, 0.1;
bacteria, 0.4; environment, 0.3} and ALZHEIMERS = {genetics, 0.7; virus, 0.4; nutrition, 0.3; bacteria,
0.3; environment, 0.4}.
a. Find the fuzzy set AIDS c ALZHEIMERS.
b. Find the fuzzy set AIDS d ALZHEIMERS.
c. Find the fuzzy set (AIDS)′.
Exercises 95 and 96 complete the proof, begun in Section 2.2, that the second principle of induction, the first
principle of induction, and the principle of well-ordering are all equivalent.
95. The principle of well-ordering says that every nonempty set of positive integers has a smallest member.
Prove that the first principle of mathematical induction, that is,
1. P(1) is true
2. (4k)[P(k) true S P(k + 1) true]
f S P(n) true for all positive integers n