G51MCS MATHEMATICS FOR COMPUTER SCIENTISTS 2015-2016
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
G51MCS-E1
SCHOOL OF COMPUTER SCIENCE
A LEVEL 1 MODULE, AUTUMN SEMESTER 2015-2016
MATHEMATICS FOR COMPUTER SCIENTISTS
1. Questions on Logic, Sets, Functions, Matrices, and Relations.
(a) Let 
be the set {1,2,3} . The following relations are subsets of 
× 
,
R1 = {(x, y)| x ∈ A ˄ y ∈ A ˄ (x − y = 1)},
R2 = {(x, y)| x ∈ A ˄ y ∈ A ˄ (x − y ≥ 1)},
R3 = {(x, y)| x ∈ A ˄ y ∈ A ˄ ¬(x − y = 0)},
R4 = {(x, y)| x ∈ A ˄ y ∈ A ˄ ∀u ∃v (x + u = y + v)} where u and v are integers, and
R5 = {(x, y)| x ∈ A ˄ y ∈ A ˄ ∃u ∀v (x + u = y + v)} where u and v are integers.
(i) List all the elements in 
1 and 
2 .
[4 marks]
(ii) Draw a Venn diagram to show the relations among 
1 , 
2 and 
× 
.
[2 marks]
(iii) Represent relation 
3 using Boolean matrix. Explain whether it is symmetric.
[4 marks]
(iv) Are sets 
4 and 
5 finite? Is it true that 
4 = 
5? Show your work.
[6 marks]
(b) Let 
and 
be functions from 
= {1, 2, 3, 4} to 
= {
, 
, 
, 
} and from 
to 
, respectively,
with 
(1) = 
, 
(2) = 
, 
(3) = 
, and 
(4) = 
, and 
(
) = 2, 
(
) = 1, 
(
) = 3, and 
(
) = 2 .
(i) Is 
one-to-one? Is 
one-to-one?
[4 marks]
(ii) Is 
onto? Is 
onto?
[4 marks]
(iii) Which one 
and 
has an inverse function, and what is this inverse?
[4 marks]
(iv) Let 
: 
(
) → 
(
), where 
(
) = {
|∀
∈ 
, 
= 
(
)} . 
(
) and 
(
) are power sets.
Determine the values of 
({1,2}) and 
(∅) .
2. Questions on Numbers, Sequences, Matrices, and Induction.
(a) Assume 
, 
, 
, 
are integers, and 
≡ 
(mod 
) (i.e., 
is congruent to 
modulo 
).
(i) Show that if 
| 
, then 
≡ 
(mod 
) .
(ii) Let 
= 37 ∙ 53 ∙ 73 , 
= 211 ∙ 35 ∙ 59 . Find
multiple of 
and 
respectively.
[6 marks]
the greatest common divisor and the least common
[6 marks]
(b) List the first 4 terms of each of the following sequences.
(i) The 
-th term is given by ⌊
⁄2⌋ + ⌈
⁄2⌉ .
[6 marks]
(ii) The sequence whose first two terms are 1 and 5 and each subsequent term is the sum
of the two previous terms.
[6 marks]
(c) Suppose that 
= [
], where 
and 
are real numbers. Show that 
= [
] for every positive integer 
, using mathematical induction.
[9 marks]
3. Questions on Sets, Functions, Counting, and Probability.
(a) Let the set 
= {1, 2, . . . , 5} and the set 
= {0, 1} . Let 
: 
→ 
denote a total function from 
to 
, i.e., every element in 
is mapped to an element in 
.
(i) How many possible functions 
are there from 
to 
?
[6 marks]
(ii) Among the results in (i), how many functions are onto?
[6 marks]
(iii) Among the results in (i), how many functions are there that assign 0 to both 1 and 5? [6 marks]
(b) A pair of dice is rolled. The probability that a 4 appears on the first dice is 2/7, and the probability that a 3 appears on the second dice is 2/7 . Each of the other outcomes has probability 1/7 . What is the probability of 7 appearing as the sum of the numbers on the two dice?
[8 marks]
(c) Show that if seven integers are selected from {1,2,3,4,5,6,7,8,9,10}, there must be at least two pairs of these integers with the sum 11.
[8 marks]
2022-01-14