Discrete Mathematics for Computer Science

24 CHAPTER 1 Sets, Proof Templates, and Induction

We can define the elements of two sets that are not in their intersection in terms of

unions, intersections, and complements of the sets. After the definition of this set, we

will show that the operation of forming this set satisfies both the commutative and the

associative law.

Definition 7. Let A and B be sets. The set

A G B = (A - B) U (B - A)

is the symmetric difference of A and B.

Example 8. Let A = {1, 2,3,41 and B ={3, 4,5, 6}. Then, A • B = {1, 2,5,61.

Some obvious facts about the symmetric difference are collected in Theorem 9.

Theorem 9.

(a) For any set A, we have A B 0= A.

(b) For any set A, we have A EA = 0.

(c) For any two sets A and B it follows that A E B = B & A.

Proof. (a) and (b) follow directly from the definition.

(c) SinceAEB=(A-B) U(B-A)=(B-A)U(A-B)=B ®A

the result follows. U

In Theorem 9(c), it is shown that E is a commutative operation. The next theorem

shows how you prove that symmetric difference is also an associative operation.

Theoreml0. A E(BDC)=(AEB)EDC.

Proof

(A E B) E C = ((A ED B) - C) U (C - (A E B))

= (((A - B) U (B - A)) - C) U (C - ((A - B) U (B - A)))

To simplify the proof, we will reduce the two terms on the right side separately. When we

have reduced these two terms, we can combine the reductions to complete a reduction of

(A G B) q C.

The first step will be to replace various expressions of the form X - Y with X n Y

where X and Y represent any pair of the sets A, B, and C:

((A - B) U (B - A)) - C = ((A n B) U (B n A)) n C

=(An W n C) U (An B n C) (Distributive Law)

The second term involves a few more steps than the first term:

C - ((A - B) U (B - A)) = C n ((A n B) U (B nA))

= C n ((A n B) n (B Af A)) (DeMorgan's Law)

= C n ((A U B) n (B U A)) (DeMorgan's Law and A = A)

= C n (((A U B) A B) U ((A U B) n A)) (Distributive Law)

= C n (((A n B) U (B n B)) U ((A n A) U (B A A))) (Distributive Law)