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