Name: NIM: Class:

Assignment CLO 1: Relation, Function, and

Recurrence
Discrete Mathematics (CII1G3/CPI1G3)
Second Term 2021-2022
Instructions:

1. This assignment is due Friday, March 25, 2022 at 5:00 p.m.. Please submit your work to the corre-
sponding submission slot in LMS CeLOE. You need to submit a readable .pdf file of this assignment to
the provided submission slot in CeLOE. You can contact your class instructor for more detailed infor-
mation. Please make sure that your file size do not exceed the maximum file size allowed.

2. Please upload your assignment to the LMS CeLOE under the file name: A1-<student ID>.pdf,
for example: A1-1301219999.pdf.

3. You may submit this assignment in one the following form:

a. You print this assignment and write your answer using HB/2B pencil or pen with blue/black ink
(handwritten answer). You may add additional A4-sized papers. Afterwards you submit the scan/photograph
of this assignment.
b. You use a .pdf editing tools and write your answer directly using blue/black colored writing.
c. You copy the problem from this assignment to a text/word processing program and type your answer
neatly.
d. You rewrite the problem from this assignment in an A4-sized paper and submit the scan/photograph
of your work.

4. All problems in this assignment are adapted from the textbooks. The problems are written in English.
If you are a student in a regular class, you may answer the problems in Bahasa Indonesia. However,
if you are a student in international class, your answers must be written in English—otherwise your
assignment will not be graded. You may ask your class instructor or teaching assistant for helping you
understanding the problem, but you should not ask them to give the solution of any problem.

5. Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on
the clarity with which you express them.

6. This assignment consists of 9 problems, Problems 1, 2, and 5 are worth 12 points each, Problems 3 and
4 are worth 8 points each, Problems 6, 8, and 9 are worth 10 points each, and Problem 7 is worth 18
points.

7. Please retain yourself from copying answers from elsewhere without understanding the steps. Such an
attitude will not enhance your knowledge. This assignment is an individual evaluation.

8. Important: late submission without reasonable explanation will not be graded.

page 1 of 10
Problem 1 (12 points) Suppose R is a relation on the set of all integers where aRb if and only if a2 = b4 ,
for a; b 2 Z. Complete the following table for the property of R and provide a relevant reason for each
answer.
Part Property Yes/No (0.5 point)
a) Reflexive
b) Irreflexive
c) Symmetric
d) Asymmetric
e) Anti-symmetric
f) Transitive

Each justification is worth 1.5 points.

A NSWER :

page 2 of 10
Name: NIM: Class:

Problem 2 (12 points) Suppose R is a relation on A = f1; 2; 3; 4g represented by the following digraph:

Figure 1: A digraph representing relation R.

Complete the following table for the property of R and provide a relevant reason for each answer.
Part Property Yes/No (0.5 point)
a) Reflexive
b) Irreflexive
c) Symmetric
d) Asymmetric
e) Anti-symmetric
f) Transitive

Each justification is worth 1.5 points.

A NSWER :

page 3 of 10
Problem 3 (8 points) Suppose R and S are two relations over A = f1; 2; 3g represented by the following
digraphs:

Digraph for relation R. Digraph for relation S.

(a). [2 points] Write the matrices that correspondingly represent the relations R and S (i.e., MR and
MS ).
1
(b). [2 points] Write the matrices that correspondingly represent the relations R (or :R) and S (i.e.,
MR and MS 1 ).
1 1
(c). [2 points] Write the matrices that correspondingly represent the relations R [ S and R \ S (i.e.,
MR[S 1 and MR\S 1 ).

(d). [2 points] Write the matrices that correspondingly represent the relations R S and S R (i.e., MR S
and MS R ).

A NSWER :

page 4 of 10
Name: NIM: Class:

Problem 4 (8 points) Suppose R and S are two relation on A = f1; 2; 3; 4g defined as follows:

aRb if and only if 2a b, for a; b 2 A

aSb if and only if a b 1, for a; b 2 A .

(a). [2 points] Write the relations R and S in ordered pairs notation (set notation).
1 1
(b). [2 points] Write the relations R and S in ordered pairs notation (set notation).
1 1 1
(c). [2 points] Write the relations (S R) and R S in ordered pairs notation (set notation).

(d). [2 points] Write the matrices M(S R) 1 and M(S R)

1 .

A NSWER :

page 5 of 10
Problem 5 (12 points) Suppose g = f(1; b) ; (2; c) ; (3; a) ; (4; b)g is a function from A = f1; 2; 3; 4g
to B = fa; b; c; dg and f = f(a; q) ; (b; r) ; (c; p) ; (d; s)g is a function from B = fa; b; c; dg to C =
fp; q; r; sg.

(a). [3 points] Determine whether g is: (1) injective, (2) surjective, and (3) bijective. Explain your
answer!

(b). [3 points] Determine whether f is: (1) injective, (2) surjective, and (3) bijective. Explain your
answer!

(c). [3 points] Write the function f g : A ! C in ordered pairs notation (i.e., f g = f: : :g).

(d). [3 points] Determine whether f g is: (1) injective, (2) surjective, and (3) bijective. Explain your
answer!

A NSWER :

page 6 of 10
Name: NIM: Class:

n 4
Problem 6 (10 points) Suppose f; g : Z ! Z where f (n) = 7 and g (n) = 7n + 4.

(a). [2 points] Calculate f (11) and f (12).

(b). [2 points] Is there any n 2 Z such that g (n) = 12?

(c). [2 points] Is f bijective? Explain your answer!

(d). [2 points] Is g bijective? Explain your answer!

(e). [2 points] Calculate (g f g f ) (13).

A NSWER :

page 7 of 10
Problem 7 (18 points) Suppose f; g; h : Z ! Z are functions defined as follows:

n 5
f (n) = 4n + 5, g (n) = , and h (n) = (f g) (n) .
4

(a). [6 points] Determine whether f is: (1) injective, (2) surjective, and (3) bijective. Explain your
answer!

(b). [6 points] Determine whether g is: (1) injective, (2) surjective, and (3) bijective. Explain your
answer!

(c). [6 points] Determine whether h is: (1) injective, (2) surjective, and (3) bijective. Explain your
answer!

A NSWER :

page 8 of 10
Name: NIM: Class:

Problem 8 (10 points) Observe the following excerpt of a Python program:

def b(n):
if n == 0: return 2
elif n == 1: return 3
else: return 2*b(n-2)-b(n-1)
The above program computes the following recursive function

bn = 2bn 2 bn 1 for all n 2 with b0 = 2 and b1 = 3. (1)

(a). [3 points] Calculate b2 , b3 , and b4 . (Remark: be careful, the recurrence is bn = 2bn 2 bn 1 and
NOT bn = 2bn 1 bn 2 .)

(b). [3 points] Write the characteristic equation that corresponds to (1) and determine its roots.

(c). [3 points] Find the general solution of (1) with initial conditions b0 = 2 and b1 = 3.

(d). [1 point] Use the result in (c). to compute b10 . Express the result as an integer. (Hint: 210 = 1024,
3 339 = 1017.)

A NSWER :

page 9 of 10
Problem 9 (10 points) Observe the following excerpt of a Python program:
def s(n):
if n == 0: return 1
elif n == 1: return 4
else: return 2*s(n-1) - s(n-2)
The above program computes the following recurrence

sn = 2sn 1 sn 2, for all n 2 with s0 = 1 and s1 = 4. (2)

(a). [3 points] Calculate s2 , s3 , and s4 .

(b). [3 points] Write the characteristic equation that corresponds to (2) and determine its roots.

(c). [3 points] Find the general solution of (2) with initial conditions s0 = 1 and s1 = 4.

(d). [1 point] Use the solution in (c) to calculate s2022 .

A NSWER :

page 10 of 10