COMP1017(G51MCS) MATHEMATICS FOR COMPUTER SCIENTISTS 2016-2017
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP1017(G51MCS)-E1
SCHOOL OF COMPUTER SCIENCE
A LEVEL 1 MODULE, AUTUMN SEMESTER 2016-2017
MATHEMATICS FOR COMPUTER SCIENTISTS
1. Questions on Number theory, Logic, Sets, and Functions.
(a) For a non-empty tuple of positive integers 
1, 
2, ⋯ , 
, let
CD(
1, 
2, ⋯ , 
) = {
∈ ℕ: ∀1 ≤ 
≤ 
, 
|
}
be the set of natural numbers that are common divisors of all 
1, 
2, ⋯ , 
.
(i) Using the Fundamental Theorem of Arithmetic (FTA), find CD(420, 200, 315) .
[4 marks]
(ii) Prove or give a counter example that for positive integers 
1, 
2, 
3 , if CD(
1, 
2, 
3) = {1},
then CD(
1 ∙ 
2, 
3) = {1}, where 
1 ∙ 
2 denotes the multiplication of 
1 and 
2 .
[6 marks]
(iii) Without using the FTA, prove that for positive integers 
and 
′ , if CD(
, 
′) = {1} then,
for all integers 
,
(
∙ 
′)|
↔ 
|
∧ 
′|
[7 marks]
(b) Let 
= {
1 = 2, 
2 = 3, 
3 = 5, ⋯ , 
} be the set of the first 
prime numbers. For example, 
5 = {2, 3, 5, 7, 11} . Let 
) = {
∈ ℕ: ∀0 ≤ 
≤ 
, ∃0 ≤ 
≤ 
∈ ℕ, 
∈ 
, 
= 
1
1 ∙ 
2
2 ∙ ⋯ ∙ 
∙ ⋯ ∙ 
} be the set of integers that can be factorised into the multiplication of the first 
prime numbers, where the multiplicity of each prime number is less than or equal to a positive integer 
.
(i) Given an example of the integer 
∈ 
and explain why it is valid.
[4 marks]
(ii) Specify the cardinality of 
Show your work.
[4 marks]
(iii) Let 
(
) denote the power set of 
. Define the function 
: 
) → 
(
) such that 
(
) = {
∈ 
: ∀0 ≤ 
≤ 
, 
> 0, 
= 
1
1 ∙ 
2
2 ∙ ⋯ ∙ 
∈ 
)
} .
Show that 
is surjective (i.e., onto) but not injective (i.e., not one-to-one).
[9 marks]
2. Questions on Logic, Sets, Induction, and Relations.
(a) A set 
is defined recursively by
Basic step: 0 ∈ 
Recursive step: if 
∈ 
, then 
+ 3 ∈ 
and 
+ 5 ∈ 
.
(i) Determine the set 
∩ {
∈ ℤ: 0 < 
< 12} .
[5 marks]
(ii) Prove that every integer 
≥ 8 is contained in 
.
[8 marks]
(b) Let 
= {
, 
} . Define a binary relation σ on 
(
) the power set of 
, by 
σ 
if and only if 
⊆ 
.
(i) Specify 
× 
and |
(
)| .
[4 marks]
(ii) How many different binary relations can be defined on the set 
? Show your work.
[4 marks]
(iii) Is σ reflexive, antisymmetric, and/or transitive? Explain your answer.
[6 marks]
(iv) Represent the relation σ as a Boolean matrix 
, and determine 
2 . Show your work. [6 marks]
3. Questions on Sets, Counting, and Probability.
(a) Suppose that 
and 
are events from a sample space 
. Denote the probability of 
and 
as 
(
) and 
(
) respectively.
(i) Let 
= {
1, 
2, 
3, 
4, 
5}, 
= {
1, 
2, 
4}, and 
= {
2, 
5} . Assuming each sample 
, 
= 1, ⋯ ,4 is equally likely but 
5 happens as twice likely as the rest of the samples. Determine the values of 
(
) and 
(
) respectively. Justify your answer.
[5 marks]
(ii) Under the same conditions given in (i), determine the conditional probability 
(
|
) .
Justify your answer.
[4 marks]
(iii) Given that 
(
) ≠ 0 and 
(
) ≠ 0, show that if 
(
|
) < 
(
), then 
(
|
) < 
(
) .
[7 marks]
(b) A committee of five is to be chosen randomly from a collection of 4 women and 8 men.
(i) How many different committees of five people can be formed? Justify your answer.
[5 marks]
(ii) How many different committees of five can be formed, if at least two men and at least
two women are to be on the committee of five? Justify your answer.
[8 marks]
(iii) What is the probability that there are exactly 3 women and two men chosen, given that
the constraints in part (ii) hold?
[4 marks]
2022-01-14