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.
max points possible XXXXXXXXXXpoints
points obtained
Multiple-Choice Questions.
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.
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.
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
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
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.
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.
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
Wherever indicated, you must
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
.
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
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
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
Answered 2 days AfterApr 11, 2022

Solution

Parvesh answered on Apr 13 2022
CamScanner 04-14-2022 01.57.37
SOLUTION.PDF