Discrete Computational Structures Homework Assignment #4

CS 230 : Discrete Computational Structures

Homework Assignment #4

Suggested Reading: Rosen Sections 2.1 - 2.3; Lehman et al. Chapter 4.1, 4.3, 4.4.
For the problems below, explain your answers and show your reasoning.
1. [6 Pts] Let A and B be non-empty sets. Prove that if A 6= B, then A × B 6= B × A.
The definition of the Cartesian Products described would be {(a, b)|a ∈ A ∧ b ∈ B}
and {(b, a)|b ∈ B ∧ a ∈ A}. If A 6= B, then there exists some (a, b) and (b, a) that are
not equal. QED
2. [4 Pts] Prove that (A ∪ B) − C = (A − C) ∪ (B − C) using iff arguments and logical
equivalences.
(A ∪ B) − C
iff (x ∈ A ∨ x ∈ B) ∧ x 6∈ C Definition of ∪, Difference
iff ((x ∈ A ∧ x 6∈ C) ∨ (x ∈ B ∧ x 6∈ C)) Distribution
iff (A − C) ∪ (B − C) Definition of ∪, Difference; QED
3. [8 Pts] Disprove the statements below.
(a) If (1) A ∪ C ⊆ B ∪ C then (2) A ⊆ B.
Suppose A = {1}, B = {2}, and C - {1}
A ∪ C = {1}, B ∪ C = {1, 2} therefore A ∪ C ⊆ B ∪ C (1) is satisfied.
However, A 6⊆ B; (1) does not imply (2). QED
(b) If (1) A ∩ C ⊆ B ∩ C then (2) A ⊆ B.
Suppose A = {1, 2}, B = {2}, and C = {2}
A ∩ C = {2}, B ∩ C = {2} therefore A ∩ C ⊆ B ∩ C (1) is satisfied.
However, A 6⊆ B; (1) does not imply (2). QED
4. [8 Pts] Prove by contradiction that if (U) A ∪ C ⊆ B ∪ C and (I) A ∩ C ⊆ B ∩ C then
A ⊆ B.
(1) Suppose A 6⊆ B. By definition, ∀x(x ∈ A → x 6∈ B).
(2) Assuming x ∈ A, this means that x is also in A ∪ C, which is a subset of B ∪ C.
(3) (2) implies that x ∈ B ∨ x ∈ C To prove this, x ∈ B ∧ x ∈ C must be true.
(4) Unfortuantely, if x ∈ A, then x 6∈ B. (4) Contradicts (3), so A must be a subset
of B. QED
5. [8 Pts] Prove that (H) (A∪B)−(A∩B) = (A−B)∪(B −A) using subset argument.
You may not use logical equivalences in your proof. Use general proof techniques like
‘proof by contradiction’ and ‘proof by cases’.
(1) LHS of (H) is simply removing all common elements of A and B from the combination of A and B.
(2) RHS of (H) can be read as the combination of removing common elements of A
and B from A and from B.
(3) Combining everything in (2), we get that this combination will not contain common elements of A and B, but everything that is not common.
(4) (1) and (3) are equivalent in English; QED
6. [4 Pts] Prove that f(n) = 5n + 9 is one-to-one, where the domain and co-domain of
f is Z
+. Show that f is not onto.
f is definitely not onto because there exists a positive integer, for example 2, in the
co-domain that can’t be an output.
f is one-to-one if ∀x ∈ Z
+, ∀y ∈ Z
+(f(x) = f(y) → x = y)
5x + 9 = 5y + 9
5x = 5y
x = y
QED
7. [4 Pts] Prove that f(m, n) = m + n + mn is onto, where the domain of f is Z × Z
and the co-domain of f is Z. Show that f is not one-to-one.
Let y ∈ Z. If y = f(n, m), then y = m + n + mn. This implies that n =
y−m
1+m
and
m =
y−n
1+n
. so for every y ∈ Z, there exists some m, n ∈ Z such that f(m, n) = y. QED
f is not one-to-one because inputs (1,0) and (0,1) have the same output 1.
8. [8 Pts] Let g be a total function from A to B and f be a total function from B to C.
(a) If f ◦ g is one-to-one, then is g one-to-one? Prove or give a counter-example.
(1) Suppose g ◦ f and g is one-to-one.
(2) g(x) = g(y) for arbitrary x, y ∈ A
(3) Composing: f(g(x)) = f(g(y))
(4) Taking the inverse of f ◦ g of both sides gives x = y. This is consistent with
supposition (1). QED
(b) If f ◦ g is onto, then is g onto? Prove or give a counter-example.
Counter-example: If the output of f is just a one element set, then f ◦g will always
be onto, regardless of g. QED
For more practice, work on the problems from Sections 2.1 - 2.3; Lehman et al. Chapter 4.1,
4.3, 4.4.