Discrete Mathematics for Computer Science

486 CHAPTER 8 Discrete Probability

(b) Since E is the disjoint union of (E N) F) and (E n F), the Additive Principle implies

statement (b).

(c) Since the Ai's form a partition of Q2, set E can be written as the union of the pairwise

disjoint sets (E n Ai). Hence, statement (c) follows from the Additive Principle.

(d) Expressing events E, F, and (E U F) as unions of disjoint events and applying the

Additive Principle gives

P(E U F) = P(E - F) + P(F - E) + P(E n F)

P(E) = P(E - F) + P(E n F)

P(F) = P(F - E) + P(E n F)

Adding together the expressions for P (E) and P (F) gives

P(E) + P(F) = P(E - F) + P(F - E) + 2P(E n F)

Comparison with the expression for P(E U F) shows that

P(E) + P(F) = P(E U F) + P(E n F)

Statement (d) is just a rearrangement of this last equation. 0

The proof of Theorem 1 (d) is identical in form to the proof of the theorem found in

Section 1.5.2. In particular, the idea of expressing a set as a union of other, pairwise disjoint

sets is used in both places. The difference is that in Chapter 1, the numbers of elements in

the sets are counted, whereas here, the probabilities of the elements are totaled. Thus, in

Chapter 1, each element contributes a 1 to the total, whereas here, each element contributes

its probability to the total.

The next example shows the usefulness of expressing an event as a disjoint union of

other events.

Example 12. What is the probability that a card drawn at random from a 52-card deck

will be an Ace or a spade?

Solution. We take Q2 to be the 52-element set of cards and model drawing a card at

random by assigning a uniform probability density. The event E of getting an Ace or a

spade can be written as E = A U S where A is the set of four Aces and S is the set of 13

spades. The intersection A n S = {the Ace of Spades}. Hence, by Theorem 1(d),

P(E) = P(A) + P(S) - P(A n S)

4 13 1

52 52 52

4

13

Sometimes it is easy to evaluate the probability that an event does not occur. This

immediately gives the probability that it does occur, as the next result shows.

Theorem 2. (Probability of the Complement) Suppose E is an event in a sample

space Q, and let E = Q - E. Then,

P(E) = I - P(E)