Page 156 - Discrete Mathematics and Its Applications

2.2 Set Operations 135

Solution: The bit string that represents the set of odd integers in U, namely, {1, 3, 5, 7, 9}, has
a one bit in the first, third, fifth, seventh, and ninth positions, and a zero elsewhere. It is

10 1010 1010.

(We have split this bit string of length ten into blocks of length four for easy reading.) Similarly,
we represent the subset of all even integers in U, namely, {2, 4, 6, 8, 10}, by the string

01 0101 0101.

The set of all integers in U that do not exceed 5, namely, {1, 2, 3, 4, 5}, is represented by the
string

11 1110 0000. ▲

Using bit strings to represent sets, it is easy to find complements of sets and unions, inter-
sections, and differences of sets. To find the bit string for the complement of a set from the bit
string for that set, we simply change each 1 to a 0 and each 0 to 1, because x ∈ A if and only if
x/∈ A. Note that this operation corresponds to taking the negation of each bit when we associate
a bit with a truth value—with 1 representing true and 0 representing false.
EXAMPLE 19 We have seen that the bit string for the set {1, 3, 5, 7, 9} (with universal set {1, 2, 3, 4,
5, 6, 7, 8, 9, 10})is
10 1010 1010.

What is the bit string for the complement of this set?

Solution: The bit string for the complement of this set is obtained by replacing 0s with 1s and
vice versa. This yields the string
01 0101 0101,

which corresponds to the set {2, 4, 6, 8, 10}. ▲

To obtain the bit string for the union and intersection of two sets we perform bitwise Boolean
operations on the bit strings representing the two sets. The bit in the ith position of the bit string
of the union is 1 if either of the bits in the ith position in the two strings is 1 (or both are 1), and
is 0 when both bits are 0. Hence, the bit string for the union is the bitwise OR of the bit strings
for the two sets. The bit in the ith position of the bit string of the intersection is 1 when the bits
in the corresponding position in the two strings are both 1, and is 0 when either of the two bits
is 0 (or both are). Hence, the bit string for the intersection is the bitwise AND of the bit strings
for the two sets.

EXAMPLE 20 The bit strings for the sets {1, 2, 3, 4, 5} and {1, 3, 5, 7, 9} are 11 1110 0000 and 10 1010 1010,
respectively. Use bit strings to find the union and intersection of these sets.

Solution: The bit string for the union of these sets is

11 1110 0000 ∨ 10 1010 1010 = 11 1110 1010,

which corresponds to the set {1, 2, 3, 4, 5, 7, 9}. The bit string for the intersection of these sets
is

11 1110 0000 ∧ 10 1010 1010 = 10 1010 0000,

which corresponds to the set {1, 3, 5}. ▲