Page 159 - Discrete Mathematics and Its Applications

138 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

60. How many elements does the successor of a set with n b) What combination of A and B represents the equip-
elements have? ment that will be used by both departments if both
Sometimes the number of times that an element occurs in an departments use the same equipment?
unordered collection matters. Multisets are unordered collec- c) What combination of A and B represents the equip-
tions of elements where an element can occur as a member ment that the second department uses, but the first de-
partment does not, if both departments use the same
more than once. The notation {m 1 · a 1 , m 2 · a 2 ,...,m r · a r }
denotes the multiset with element a 1 occurring m 1 times, el- equipment?
ement a 2 occurring m 2 times, and so on. The numbers m i , d) What combination of A and B represents the equip-
i = 1, 2,...,r are called the multiplicities of the elements ment that the university should purchase if the depart-
a i , i = 1, 2,...,r. ments do not share equipment?
Let P and Q be multisets. The union of the multisets P Fuzzy sets are used in artificial intelligence. Each element
and Q is the multiset where the multiplicity of an element is in the universal set U has a degree of membership, which
the maximum of its multiplicities in P and Q. The intersec- is a real number between 0 and 1 (including 0 and 1), in a
tion of P and Q is the multiset where the multiplicity of an fuzzy set S. The fuzzy set S is denoted by listing the elements
element is the minimum of its multiplicities in P and Q. The with their degrees of membership (elements with 0 degree of
difference of P and Q is the multiset where the multiplicity membership are not listed). For instance, we write {0.6 Alice,
of an element is the multiplicity of the element in P less its 0.9 Brian, 0.4 Fred, 0.1 Oscar, 0.5 Rita} for the set F (of fa-
multiplicity in Q unless this difference is negative, in which mous people) to indicate that Alice has a 0.6 degree of mem-
case the multiplicity is 0. The sum of P and Q is the multiset bership in F, Brian has a 0.9 degree of membership in F, Fred
where the multiplicity of an element is the sum of multiplic- has a 0.4 degree of membership in F, Oscar has a 0.1 degree
ities in P and Q. The union, intersection, and difference of of membership in F, and Rita has a 0.5 degree of membership
P and Q are denoted by P ∪ Q, P ∩ Q, and P − Q, respec- in F (so that Brian is the most famous and Oscar is the least
tively (where these operations should not be confused with famous of these people). Also suppose that R is the set of rich
the analogous operations for sets). The sum of P and Q is people with R ={0.4 Alice, 0.8 Brian, 0.2 Fred, 0.9 Oscar,
denoted by P + Q. 0.7 Rita}.
61. Let A and B be the multisets {3 · a, 2 · b, 1 · c} and 63. The complement of a fuzzy set S is the set S, with the
{2 · a, 3 · b, 4 · d}, respectively. Find degree of the membership of an element in S equal to
a) A ∪ B. b) A ∩ B. c) A − B. 1 minus the degree of membership of this element in S.
d) B − A. e) A + B. Find F (the fuzzy set of people who are not famous) and
62. Suppose that A is the multiset that has as its elements R (the fuzzy set of people who are not rich).
the types of computer equipment needed by one depart- 64. The union of two fuzzy sets S and T is the fuzzy set
ment of a university and the multiplicities are the number S ∪ T , where the degree of membership of an element in
of pieces of each type needed, and B is the analogous S ∪ T is the maximum of the degrees of membership of
multiset for a second department of the university. For this element in S and in T . Find the fuzzy set F ∪ R of
instance, A could be the multiset {107 · personal comput- rich or famous people.
ers, 44 · routers, 6 · servers} and B could be the multiset 65. The intersection of two fuzzy sets S and T is the fuzzy
{14 · personal computers, 6 · routers, 2 · mainframes}. set S ∩ T , where the degree of membership of an element
a) What combination of A and B represents the equip- in S ∩ T is the minimum of the degrees of membership
ment the university should buy assuming both depart- of this element in S and in T . Find the fuzzy set F ∩ R
ments use the same equipment? of rich and famous people.

2.3 Functions

Introduction

In many instances we assign to each element of a set a particular element of a second set (which
may be the same as the first). For example, suppose that each student in a discrete mathematics
class is assigned a letter grade from the set {A, B, C, D, F}. And suppose that the grades are A
forAdams, C for Chou, B for Goodfriend, A for Rodriguez, and F for Stevens. This assignment
of grades is illustrated in Figure 1.
This assignment is an example of a function. The concept of a function is extremely impor-
tant in mathematics and computer science. For example, in discrete mathematics functions are
used in the definition of such discrete structures as sequences and strings. Functions are also
used to represent how long it takes a computer to solve problems of a given size. Many computer
programs and subroutines are designed to calculate values of functions. Recursive functions,