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 da or db.
 Problem 5

Write down the converse of the following statement about integers:
If x and y are odd, then xy 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) (A∪B)'
(d) A'∩B'
(e) A'∪B'
(f) (A∩B)'
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 A∩B = 50,
A∩C = 80, and
B∩C = 90.
Find the cardinality of the intersection of the three sets.
 Problem 25

Prove that A∪(B∩C) = (A∪B)∩(A∪C).
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)
(AB)×C
= (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 breadthfirst traversal
that starts at vertex f.
(b) Write down one depthfirst 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.