关键词 > G51MCS
G51MCS MATHEMATICS FOR COMPUTER SCIENTISTS 2015-2016
发布时间:2022-01-14
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]