### Assignment 1 (due 4/2/2003)

The following problems are from Section 1.1 of the text:
Problem 3(d)
Prove or disprove the following: if d|(a b), then either d|a or d|b.

Problem 5
Write down the converse of the following statement about integers:
If x and y are odd, then x-y is even.
Is the statement you wrote down true or false? Prove your answer.

Problem 8(b)
Prove that x y is odd if and only if x is odd and y is odd.

### Assignment 2 (due 4/4/2003)

The following problems are from Section 1.2 of the text:
Problem 2
Describe each of the following sets in terms of a property of its elements:
(b) {1, 3, 5, 7, 9, 11, 13, 15}
(d) {1, 4, 9, 16, 25, 36, 49, 64}

Problem 6
Write down the power set for each of the following sets:
(a) { x, y, z, w }
(d) { ∅ }

Problem 12
For each of the following expressions, use a Venn diagram representing a universe U and two subsets A and B:
(a) A'.
(b) B'.
(c) (AB)'
(d) A'∩B'
(e) A'∪B'
(f) (AB)'
Note: The notation A' means the complement of A with respect to U.

Problem 15
Given three sets A, B, and C. Suppose the the union of the three sets has cardnality 280. Suppose also that |A| = 100, |B| = 200, and |C| = 150. And suppose we also know |AB| = 50, |AC| = 80, and |BC| = 90. Find the cardinality of the intersection of the three sets.

Problem 25
Prove that A∪(BC) = (AB)∩(AC).

### Assignment 3 (due 4/7/2003)

The following problems are from Section 1.3 of the text:
Problem 11
Try to describe each of the following languages in some way.
(a) {a, b}* ∩ {b, c}*
(b) {a, b}* - {b}*

Problem 16
Prove each of the following statements about combining set operations with Cartesian product.
(b) (A-BC = (A×C)-(B×C)

### Assignment 4 (due 4/9/2003)

The following problems are from Section 1.3 of the text:
Problem 4(b)
Draw a picture of the directed graph that corresponds to the following binary relation:
{(a, b), (b, b), (b, c), (c, a)}

Problem 6
Given the following graph
(a) Write down one breadth-first traversal that starts at vertex f.
(b) Write down one depth-first traversal that starts at vertex f.

Problem 8
Given the algebraic expression
a × (b + c) - (d / e)
Draw a picture of the tree representation of this expression. Then convert the tree into a list representation of the expression.