COMP11120
Faculty of Science and Engineering
DEPARTMENT OF COMPUTER SCIENCE
Mathematical Techniques for Computer Science
Faculty of Science and Engineering
DEPARTMENT OF COMPUTER SCIENCE
Mathematical Techniques for Computer Science
Start time: 9.00 on 22/01/2021
Duration: 2 hours
Upload deadline: 12.00 noon on 22/01/2021
1. Consider the set G given by
G = {m + ni ∈ C | m; n ∈ Z};
that is the set of those complex numbers whose real and imaginary parts are integers.
a) Consider the binary operation on G which, for x, y in G is defined as follows:
x * y = x · i · y
where we use the multiplication operation from the complex numbers.
Is this operation associative? Justify your answer. (4 marks)
b) Consider the function
N : G 
N
z 
| z | 2 ;
where we use the usual absolute function for complex numbers. Justifying each step show that for z; z0 ∈ G we have that (4 marks)
N(z · z') = Nz · Nz'.
c) Consider the function N : G 
N from part b). Is this function injective? Is it surjective? Justify your answers. (6 marks)
d) We have addition and multiplication operations on G which work in the usual way for complex numbers. The unit of addition is 0, and that of multiplication is 1.
Show that a number x ∈ G has a multiplicative inverse if and only if it is in the set {1; — 1; i; — i}.
Hint: You may find part b) useful for this. (4 marks)
e) Show that the number 2 is not prime in G, by showing that it can be written as the product of two numbersin G \ {1; — 1; i; — i}. (2 marks)
2. Chocolate bars with different flavours wrapped in yellow, orange and red packaging are offered at a party.
There are three bags with varying numbers of bars of the various colours of packaging:
|
Bag |
yellow |
orange |
red |
|
A B C |
3 |
1 |
4 |
|
5 |
3 |
2 |
|
|
0 |
6 |
4 |
a) For bag A give a probability space that describes the situation. (2 marks)
b) Somebody offers you one of the bags, but you don’t know which one. You’re allowed to draw a chocolate bar out of the bag, but you can’t look inside. What is the probability that you will draw an orange bar? (2 marks)
c) We define three random variables XA , XB and XC by assigning numbers to the colours, with yellow being 1, orange 2, and red 3, for randomly drawing a bar out of a bag A, B and C respectively. What is the expected value of XB? (2 marks)
d) Draw the cdf for XC . (2 marks)
e) We define a new random variable
Y = XA + XB + XC:
Give the conditional distribution for Y given that the bar drawn out of bag A is yellow. (2 marks)
f) Your friend is offered one of the bags, and again you don’t know which bag it is. Without being allowed to look into the bag he draws out a chocolate bar, which has a red wrapper.
He doesn’t like that flavour, so he drops the bar back into the bag. He is allowed to draw another chocolate bar without looking, and this time it is one with orange wrapping.
Carry out Bayesian updating based on your friend’s two random draws. Which bag do you think he was likely offered? (10 marks)
3. a) i) Using truth tables determine whether the following holds, or not. (2 marks)
(¬P → T) 三 P
ii) State what other method can be used to answer this question, and very briefly say how (but you do not need to give a full alternative argument). (2 marks)
b) Consider this propositional formula.
B → ((C → A) → (A ^ B))
i) Use our CNF algorithm to transform this formula into conjunctive normal form. (4 marks)
ii) Simplify your answer as much as possible. (2 marks)
c) Give a natural deduction proof for the following. (4 marks)
((P ^ Q) → P) → R -R
Use the inference rules of our natural deduction system, which are given on the last pages of this exam paper.
d) Consider the first-order language with one ternary predicate symbol A, five binary predicate symbols SI; TP; CV; F;R, three unary predicate symbols H ; P;D, one constant John and a supply of variables x;y; z; .... Assume the non-logical symbols are interpreted as follows.
A(x;y; z) means that x is admitted by y to z
SI(x;y) means that x is staying in y
TP(x) means that x has tested positive
CV(x;y) means that x can be visited by y
F(x;y) means that x is a friend of y
R(x;y) means that x is a relative of y
H(x) means that x is a hospital
P(x) means that x is a patient
D(x) means that x is a doctor
John is interpreted as the person John
Express each of the following sentences as formulas. (6 marks)
i) Every patient staying in hospital must have been admitted by a doctor.
ii) John has been tested positive but has not been admitted to any hospital.
iii) Every patient can be visited by their friends and relatives.