Table of Points for marking purposes. Do not write in this table. multiple-choice true-or-false short-answer long-answer TOTAL max points possible XXXXXXXXXXpoints points obtained Multiple-Choice...

Table of Points for marking purposes. Do not write in this table.
multiple-choice true-or-false short-answer long-answer TOTAL
max points possible XXXXXXXXXXpoints
points obtained
Multiple-Choice Questions.
Write your choice in the answer box. No justification is needed.
Q1. Let A = {1, 2} and let B = {s, t, u, v, w}. How many injective functions are there
from A to B?
A. 20 B. 25 C. 32
D. 0 E. 10 F. None of the previous answers.
Answer: [2 points]
Q2. Let R be the equivalence relation on the set A = {�6,�2, 0, 1, 4, 5, 6, 7, 15} defined by
xRy ()
⇣
x ⌘ y (mod 5) or x ⌘ �y (mod 5)
⌘
Which one (if any) of the following statements is true?
A. {�6, 6} is an equivalence class with respect to R.
B. [�2]R = [6]R.
C. P =
�
{�6,�2}, {0}, {1, 4, 5, 6, 7, 15}

is the partition of A into equivalence classes.
D. P =
�
{�6, 1, 4, 6}, {�2, 7}, {0, 5, 15}

is the partition of A into equivalence classes.
E. 4R7.
F. None of the above.
Answer: [2 points]
2
Q3. One of the following statements is false. Which one?
A. A \ (B [ C) = (A \ B) [ (A \ C)
B. A \ (B [ C) = A [ (B [ C)
C. A [ (B \ C) = A \ (B \ C)
D. (A [ B) \ C = (A \ C) [ (B \ C)
E. (A [B) [ C = (A [B) \ C
Answer: [2 points]
Q4. How many strings of length 6 with symbols from {a, b, c, d, e} start with ‘ace’ or end with
‘ee’ ? (this is inclusive or)
A. 755 B. 36 C. 750 D. 35 E. 745 F. 34
Answer: [2 points]
3
Q5. Let G be a graph with 7 vertices and 10 edges. If every vertex of G has degree 2 or 3, then
how many vertices of each degree does G have?
A. G has 0 vertices of degree 2 and 7 vertices of degree 3.
B. G has 1 vertex of degree 2 and 6 vertices of degree 3.
C. G has 2 vertices of degree 2 and 5 vertices of degree 3.
D. G has 3 vertices of degree 2 and 3 vertices of degree 3.
E. G has 4 vertices of degree 2 and 3 vertices of degree 3.
F. No such graph exists.
Answer: [2 points]
Q6. How many binary strings of length 7 contain at least 5 zeros?
A. 21 B. 32 C. 96 D. 4 E. 49 F. 29
G. None of the above.
Answer: [2 points]
4
True-or-False Questions.
Circle the co
ect responses. No justification is needed.
Q7. Consider the following three graphs: [1.5 points]
G H L
Circle the co
ect responses.
G is a tree. T F
H is a forest. T F
L is a tree. T F
Q8. Consider the following sets: [3 points]
S =
�
Ø, 1, {1}

and T =
�
1, {Ø, 1}

Circle the co
ect responses.
|S ⇥ T | = 9. T F
�
{1}

✓ S T F
|S \ T | = 2 T F
�
{1}, {1}
�
2 T ⇥ S T F
|S [ T | = 4 T F
|P(T )| = 4 T F
5
Q9. Consider the following relation on the set : [2 points]
xRy () x(1 + y) is even.
What properties does the relation R possess? Circle the co
ect responses.
R is reflexive. T F
R is symmetric. T F
R is antisymmetric. T F
R is transitive. T F
Q10. Consider the following propositions with atomic variables x and y: [2.5 points]
P1 : x ^ ¬y
P2 : ¬x _ ¬y
P3 : x ! y
C : y ! x
Circle the co
ect responses.
The set {P1, P2, P3} is a consistent set of propositions. T F
The set {P1, P2} is a consistent set of propositions. T F
The argument (P1 ^ P2 ^ P3) ! C is a valid argument. T F
The compound proposition P1 ^ P2 ! C is a tautology. T F
Compound propositions P1 and ¬P3 are logically equivalent. T F
6
Short-Answer Questions.
Write your final answer in the answer box.
Wherever indicated, you must
iefly justify your answers to receive full marks.
Q11. Let a, b. and c be propositional variables.
Give a disjunctive normal form (DNF) for the following compound proposition:
P : (a $ b) ^ (b _ ¬c)
DNF for P :
Justification: [1.5 points]
7
Q12. Fully evaluate the following expression:
✓
9
6
◆
+
✓
9
7
◆
=
Justification: [1.5 points]
Q13. Consider the following sequence:
(0, 1, 2, 3, 4, 5, 5)
(a) Does there exist a graph with the above degree sequence? Circle: YES NO
If so, draw an example of such a graph; otherwise,
iefly explain why no such graph
exists.
(b) Draw an example of a tree whose degree sequence is (1, 1, 1, 1, 3, 3).
No justification is needed. [2 points]
8
Q14. Determine the coe�cient of
1
x8
in the expansion of
✓
3x2 +
5
x4
◆10
.
Your answer may include unevaluated factorials, binomial coe�cients, powers, products,
or sums.
Coe�cient of x
�8
:
Justification: [2.5 points]
9
Q15. Give an example of a compound proposition P such that
• P consists of the propositional variables x, y, and z (all three variables must be
used).
• P contains only the logical connectives ¬ and ! and P must contain both these
connectives.
• P is a contradiction (justification required below).
Make sure your proposition P contains only the variables x, y, and z, the logical con-
nectives ¬ and ! and appropriate parentheses.
P =
Justification that P is a contradiction: [2 points]
10
Q16. Let f : ! ⇥ be a function defined by f(x) = (x3, x4). [3.5 points]
Answer the following questions regarding the above function f .
To justify your answers, either give a proof or a concrete numerical counterexample.
Is f is injective? Circle: YES NO
Justification (proof or counterexample):
Is f is surjective? Circle: YES NO
Justification (proof or counterexample):
Is f is invertible? Circle: YES NO
No justification is needed for this part.
11
Q17. Which of the following four graphs are bipartite? [2 points]
For each graph, circle the co
ect response and justify your answer by either giving a prope
2-colouring of the graph, or by indicating an odd cycle in the graph.
G Is G bipartite? Circle: YES NO
H Is H bipartite? Circle: YES NO
K Is K bipartite? Circle: YES NO
L Is L bipartite? Circle: YES NO
12
Long-Answer Questions.
Detailed solutions are required.
Q18. Let m be a positive integer.
Give a proof by contradiction of the following statement:
Statement:
If 3m+1 ma
les are placed into m jars, then at least one jar will contain at least 4 ma
les.
[5 points]
13
Q19. Use Mathematical Induction to prove that
(2n)! is a multiple of 2n+1 for all integers n � 2.
Clearly state the proposition to be proved, Basis of Induction, Induction Hypothesis, and
Induction Step. Clearly indicate where the Induction Hypothesis is used in your proof.
[5 points]
14
Q20. Use a truth tree to determine whether or not the proposition P below is a tautology. If
you claim that P is not a tautology, give all counterexamples.
P :
�
c _ (b ! ¬a)
�
$ ¬(a ^ b)
Clearly indicate the root of the tree. Use the
anching rules precisely as taught in class. Do
not use equivalences. Do not skip steps or combine
anching rules. Make sure your truth
tree is fully grown.
Complete truth tree:
Is P a tautology? Circle: YES NO
If you circled NO, give all counterexamples:
[5 points]
15
Q21. Define a binary relation R on the set A = {binary strings of length 4} as follows:
For all strings s, t 2 A,
sRt if and only if s and t have the same number of ones.
(a) Prove that R is an equivalence relation.
(b) Give the equivalence class of the string s = ‘1010’ with respect to the relation R.
h
‘1010’
i
R
=
[5 points]
16
Q22a. Consider the following two graphs: [4 points]a
c
d
e
f
G
z
xw
v
u
y
H
Are G and H isomorphic? If so, give an isomorphism between them and verify that you
function is an isomorphism; otherwise, clearly explain why they are not isomorphic.
Q22b. Now consider these two graphs:
5 6 7 8
1 2 3 4
K
w x y z
s t u v
L
Are K and L isomorphic? If so, give an isomorphism between them and verify that you
function is an isomorphism; otherwise, clearly explain why they are not isomorphic.
17
Extra page for scrap work.
:-)
18