CSE 321: Discrete Structures
Assignment #1
March 29, 2000
Due: Wednesday, April 5

Reading Assignment: Rosen, pp. 76 - 78, Sections 2.3-2.5

Problems:

1.

Section 1.3, exercise 6, parts b and c.

2.

Section 1.3, exercise 10, parts b and d.

3.

Section 1.3, exercise 12, parts f, i and j.

4.

Give the negation of each of the following statements:

• All good students study hard.
• No males give birth to their young.
• No students in mathematics are unable to use a computer.
• $\forall x \exists y~ x = y^2$

5.

Let Q(A,B) be the statement $A\subseteq B$. If the universe of discourse for both A and B is all sets of integers, what are the truth values of the following? Justify your answers.

• $(\forall A) (\exists B) Q(A,B)$
• $(\forall B) (\exists A) Q(A,B)$
• $(\exists A) (\forall B) Q(A,B)$
• $(\forall A) (\forall B) Q(A,B)$

6.

Which of the following statements are true?

• $\{x\} \subseteq \{x\}$
• $\{x\} \in \{x, \{x\}\}$
• $\{x\} \in \{x\}$
• $\{x, \{x\}\} \subseteq {\cal P}(\{x\})$

7.

Carefully prove the following implications.

• $(A \cup B = B) \rightarrow (A \subseteq B)$
• $(A \cap B = A) \rightarrow (A \subseteq B)$

8.

Section 1.6, Problem 12

9.

Let $f: {\cal R}\rightarrow {\cal R}$, where f(x) = x³ and $g: {\cal R}\rightarrow {\cal R}$, where g(x) = x - 3. Give expressions for $f\circ f$, $f\circ g$, $g\circ f$ and $g\circ g$.

10.

Extra Credit Section 1.6, Problem 20.