CPSC 3115 Discrete Structures in Computer Science
Homework Set 1 Due Thursday, January 20, 2005.

SHOW ALL OF YOUR WORK. DO NOT WRITE ANY ANSWERS ON THIS SHEET.

NOTE: Questions 1 – 5 are worth 15 points each. Question 6 is worth 25 points.

For the first few problems, we use the following sets.
X = {0, 1, 2, 3} Y = {2, 3, 4, 5} Z = {4, 5, 6, 7}

1. Find the following set unions
a) X È Y
b) X È Z
c) X È Y È Z evaluate as (X È Y) È Z

ANSWER:
a) X È Y = {0, 1, 2, 3} È {2, 3, 4, 5} = {0, 1, 2, 3, 4, 5}.
Note that the elements 2 and 3 are in both sets, but not repeated in the union.

b) X È Z = {0, 1, 2, 3} È {4, 5, 6, 7} = {0, 1, 2, 3, 4, 5, 6, 7}.

c) X È Y È Z = {0, 1, 2, 3} È {2, 3, 4, 5} È {4, 5, 6, 7}
(X È Y) È Z = {0, 1, 2, 3, 4, 5} È {4, 5, 6, 7} = {0, 1, 2, 3, 4, 5, 6, 7}

Everybody answered the first question correctly.

2. Find the following set intersections.
a) X Ç Y
b) X Ç Z
c) X Ç Y Ç Z evaluate as (X Ç Y) Ç Z

a) X Ç Y = {0, 1, 2, 3} Ç {2, 3, 4, 5} = {2, 3}

b) X Ç Z = {0, 1, 2, 3} Ç {4, 5, 6, 7} = Æ, the empty set.

c) X Ç Y Ç Z = {2, 3} Ç {4, 5, 6, 7} = Æ, the empty set.

NOTE: It is better to write Æ than { }, which is also correct.
The set {Æ} is not the empty set, but the set containing one member.
The one member of {Æ} is the set Æ, which itself contains no members.

3. Prove or disprove: X Í Z.

ANSWER:
X = {0, 1, 2, 3} and Z = {4, 5, 6, 7}
If X Í Z, then it follows that x Î X implies x Î Z.
To show not X Í Z, it suffices to find one x Î X with x Ï Z.
There are four valid arguments
0 Î X but 0 Ï Z

1 Î X but 1 Ï Z

2 Î X but 2 Ï Z

3 Î X but 3 Ï Z

NOTE: The statement that “None of the members of X is included in Z” is
obviously correct and sufficed for full credit, but really is too vague.
Just pick one element of X and show it not to be in Z.

4. Let set R = {A, B, C} and set S = {0, 1}. Find the Cartesian product R ´ S.

ANSWER: R ´ S = { (A, 0), (A, 1), (B, 0), (B, 1), (C, 0), (C, 1) }
Note that |R| = 3, |S| = 2, and that |R ´ S| = |R|·|S| = 3·2 = 6.

NOTE: S ´ R is not the same as R ´ S.
S ´ R = { (0, A), (0, B), (0, C), (1, A), (1, B), (1, C) }

5. Find the power sets P(R) and P(S) for R = {A, B, C} and set S = {0, 1}.

ANSWER: P(R) = { Æ, {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C} }

P(S) = { Æ, {0}, {1}, {0, 1} }.

NOTE: If |X| = S, then |P(X)| = 2^S,

6. For the graph G drawn below.
a) Find the vertex set V(G).
b) Find the edge set E(G).
c) Find the Cartesian product V(G) ´ V(G).
d) Show that E(G) Ì V(G) ´ V(G).
This involves showing both that E(G) Í V(G) ´ V(G) and E(G) ¹ V(G) ´ V(G),
alternately that E(G) Í V(G) ´ V(G), but not V(G) ´ V(G) Í E(G).

ANSWER:

a) V(G) = {1, 2, 3, 4, 5}

b) Presumably the graph is not a directed graph, so
E(G) = { (1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (4, 5) }

c) V(G) ´ V(G) = { (1, 1), (1, 2), (1, 3), (1, 4), (1, 5),
(2, 1), (2, 2), (2, 3), (2, 4), (2, 5),
(3, 1), (3, 2), (3, 3), (3, 4), (3, 5),
(4, 1), (4, 2), (4, 3), (4, 4), (4, 5),
(5, 1), (5, 2), (5, 3), (5, 4), (5, 5) }

d) Show that E(G) Ì V(G) ´ V(G), with the set inclusion being proper.
(1, 2) Î E(G) and (1, 2) Î V(G) ´ V(G), and
(1, 3) Î E(G) and (1, 3) Î V(G) ´ V(G), and
(2, 3) Î E(G) and (2, 3) Î V(G) ´ V(G), and
(2, 4) Î E(G) and (2, 4) Î V(G) ´ V(G), and
(2, 5) Î E(G) and (2, 5) Î V(G) ´ V(G), and
(3, 5) Î E(G) and (3, 5) Î V(G) ´ V(G), and
(4, 5) Î E(G) and (4, 5) Î V(G) ´ V(G), so E(G) Í V(G) ´ V(G).

But (3,4) Î V(G) ´ V(G) and (3, 4) Ï E(G), so not V(G) ´ V(G) Í E(G),
hence E(G) Ì V(G) ´ V(G), with the set inclusion being proper.

NOTE: One could claim that since (x, y) Î E(G) only if x Î V(G) and y Î V(G)
that (x, y) Î E(G) implies (x, y) Î V(G) ´ V(G), so E(G) Í V(G) ´ V(G).
Also |E(G)| = 7 and |V(G) ´ V(G)| = 25, so obviously E(G) ¹ V(G) ´ V(G).