Discrete Structures

# HW #8

 Last Update: 20 March 2009 Note: or material is highlighted

Reminder: Each HW problem solution should consist of:

• a restatement of the entire problem (you may copy it word for word),
• followed by a complete solution with all intermediate steps shown.

All exercises are from §2.2 (set operations).

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

Let A = {a, b, c, d, e} and B = {a, e, i, o, u}. Find

1. A ∪ B
2. A ∩ B
3. A – B
4. B – A

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

(This is problem 16d, e on p. 131.)
Let A, B be sets. Prove each of the following, justifying each step.

1. A ∩ (B – A) = ∅
2. A ∪ (B – A) = A ∪ B

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

Let A, B be sets.
Then the symmetric difference of A and B (denoted A ⊕ B)  =def the set containing those elements in either A or B, but not in both A and B.

1. 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. Find {a, c, e} ⊕ {a, b, c}.

4. (3 points each, total = 12 points; for full credit, you must show your work, not just your answer.)

Hint: Compute A0, A1, A2, A3, …, to see what patterns you can find that might help you compute the answers.

Find i ∈ N Ai and i ∈ N Ai, if, for every i ∈ N,

1. Ai = {i, 2i, 3i, …}.
2. Ai = {i, i2, i3, …}

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 BEGINNING OF LECTURE, FRIDAY, MARCH 27