Discrete Structures

# HW #9 — §2.2: Set Operations

 Last Update: 7 November 2010 Note: or material is highlighted

All exercises come from, or are based on exercises from, the Rosen text.

Each HW problem's solution should consist of:

All solutions must be handwritten.

 PUT YOUR NAME, DATE, RECITATION SECTION, & "HW #9" AT TOP RIGHT OF EACH PAGE; STAPLE MULTIPLE PAGES

1. (3 points each, total = 12 points)

p. 130: 4 a–d

• You are given 2 sets and asked to compute their union, intersection, and set differences.

2. (3 points)

p. 130: 14

• You are given the intersection and set differences of two sets and asked to compute what the two sets are.
• Suggestion: Use a Venn diagram to help you picture the sets.

3. (3 points each; total = 6 points)

p. 131: 16 a, b

• You are asked to prove two set equalities concerning union and intersection.

4. (3 points)

p. 131: 24

• You are asked to prove a set equality concerning set difference.
• Suggestion: This is easiest to prove by using the fact that S –T = S ∩ (‾T), along with the Distributive Law (p. 124, Table 1).
• Hint: Start by expressing the right-hand side of the equation in terms of ∩ and ‾ .

5. (3 points each; total = 6 points)

1. Read the definition on p. 131, column 2, of the symmetric difference of two sets. Then express this definition in the language of first-order predicate logic plus set theory;
i.e., find a predicate P such that A ⊕ B =def {x | P(x)}.

2. Do p. 131: 32.

6. (6 points each; total = 12 points)

p. 131, #48 a, b

• You are asked to find the infinite unions and intersections of two sequences of sets.
• Hint: Compute A1, A2, A3, A4, …, to see what patterns you can find that might help you compute the answers.

Total points = 42

```A       41-42
A-      38-40
B+      36-37
B       34-35
B-      31-33
C+      29-30
C       24-28
C-      20-23
D+      15-19
D        8-14
F        0- 7
```

 DUE: AT THE BEGINNING OF LECTURE, FRI., NOV. 12