Mathematical Techniques for Computer Science
Section A
1. a) Show that for all i, j and k in Z, (3 marks)
j mod i = 0 and k mod i = 0 implies (j +k) mod i = 0
b) Consider the following binary operation on the set of binary strings of length eight,
where the ith symbol in
s~s
0
is
• 1 if the ith symbols of s and s0 are equal and
• 0 if they are different.
For example
00110101~10010001 = 01011011.
i) Is the given operation commutative? Give a reason for your answer.
(2 marks)
ii) Is this operation associative? Justify your answer. (4 marks)
c) Consider the following function which takes as its input a binary string and produces
as its output a binary string using the following two-step procedure:
• replace every 0 by 1 and every 1 by 0;
• count the number of symbols in the given string and put that number of 1s at
the end of the string.
For example, the string 0001101 becomes 11100101111111.
Is this function injective? Is it surjective? Justify your answers. (8 marks)
d) For the following functions from [1,∞) to R, give information about which ones
eventually dominates which other functions.
(i) n nlog(n+1)
(ii) n n
3
(iii) n 2
(iv) n 2
10n (3 marks)
Page 2 of 6
COMP11120
2. Somebody has implemented a program that produces a pseudo-random number in the
set {0,1,2,3}. They do this by sampling a stream of bits whenever the program is
called. They read two bits from the stream, and then convert those two bits by parsing
them as binary numbers. The intention is that every number should appear with the
same probability.
You have some doubts whether the probability distribution is as intended because you
suspect that when sampling two bits, the second bit is not independent from the first
one.
a) Assume the program produces numbers as intended. Give a probability space that
describes the given situation. (2 marks)
b) You look at the bit sampling process. Assume that the first bit sampled is equally
likely to be 0 or 1, but the probability of the second bit being different from the
first one is half the probability of them being equal. Give a probability space that
describes this situation. (2 marks)
c) For the situation from part b) calculate the conditional probability distribution given
that the first bit sampled is 1. (2 marks)
d) Given the situation from part b) calculate the conditional probability distribution
given that the second bit sampled is 1. (2 marks)
e) A random variable is created by running the program twice and adding up the two
numbers that result.
Give the expected values of this random variable, once for the distribution from
part a) and once for the distribution from part b). (2 marks)
f) You wish to test which of the two probability distributions from parts a) and b)
better describes the situation, so you aim to carry out Bayesian updating to find
out whether the implemented program matches the first or the second of these
distributions.
You run the program three times, obtaining the numbers 3, 1 and 0 in that order.
Carry out the corresponding calculations for Bayesian updating. What do you
conclude at the end of the process? (10 marks)
Page 3 of 6 [Next page →]
COMP11120
3. a) For each of the following statements state whether it is true or false. In each case
explain your answer. (8 marks)
(i) ¬(¬P ∧ Q) ≡ (P ∧ ¬Q)
(ii) A propositional formula can be both a tautology and be satisfiable.
(iii) A propositional formula can be both a tautology and a contradiction.
(iv) For propositional formulae A1, …An truth tables can be used to establish the
validity of a judgement A1,…,An ` A in propositional logic.
b) Consider this propositional formula:
(P ↔ Q) ∧
P → ¬(Q ∧ P)
.
(i) Use our CNF algorithm to transform the formula into conjunctive normal form.
(ii) Transform the formula into disjunctive normal form and simplify your answer
as much as possible.
Justify all the steps in your derivations. (2+3 = 5 marks)
c) Give a natural deduction proof for the following. (3 marks)
P ` Q → (P ∧ Q)
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 the two binary predicate symbols I,B, three
unary predicate symbols H,St,S, two constants JRL,Ref and a supply of variables
x, y,z,…. Assume the non-logical symbols are interpreted as follows.
I(x, y) means that x is an item in y
B(x, y) means that x borrows y
H(x) means that x is high-demand
St(x) means that x is a staff member at the Univ. of Manchester
S(x) means that x is a student at the Univ. of Manchester
JRL represents John Rylands Library
Ref represents the Reference Section
Express each of the following sentences as formulas. (4 marks)
(i) Items in the Reference Section cannot be borrowed.
(ii) There are items in the John Rylands Library which cannot be borrowed.
(iii) Borrowing high-demand items in the John Rylands Library is restricted to staff
and students of the University of Manchester.
Page 4 of
COMP11120
Rules of inference of our propositional natural deduction system
Conjunction elimination:
If A ∧ B is derivable from a set of formulas, then so is A, and also B.
Γ ` A ∧ B
Γ ` A
Γ ` A ∧ B
Γ ` B
Conjunction introduction:
If A is derivable from a set of formulas, and B is derivable from the same set, then
A ∧ B is derivable from this set as well.
Γ ` A Γ ` B
Γ ` A ∧ B
Disjunction introduction:
If A is derivable from a set, then so is A ∨ B, and also B ∨ A.
Γ ` A
Γ ` A ∨ B
Γ ` A
Γ ` B ∨ A
Disjunction elimination (proof by cases):
If A ∨ B is derivable from a set and C is derivable from the set along with A, and
also from the set along with B, then C is derivable from the set alone.
Γ ` A ∨ B Γ,A ` C Γ,B ` C
Γ ` C
Implication introduction:
If B is derivable from A and a set, then A → B is derivable from the set.
Γ,A ` B
Γ ` A → B
Implication elimination:
If A is derivable from a set, and A → B is derivable from the same set, then B is
derivable from this set.
Γ ` A Γ ` A → B
Γ ` B
Page 5 of 6 [Next page →]
COMP11120
Negation introduction (reductio ad absurdum):
If A and a set leads to a contradiction, then ¬A can be inferred from the set.
Γ,A ` ⊥
Γ ` ¬A
Negation elimination:
If A is derivable from a set, and also ¬A is derivable from the set, then anything
(including ⊥) is derivable from the set.
Γ ` A Γ ` ¬A
Γ ` B
Double negation introduction:
If A is derivable from a set, then ¬¬A is derivable from the same set.
Γ ` A
Γ ` ¬¬A
Double negation elimination:
If ¬¬A is derivable from a set, then A is derivable from the same set.
Γ ` ¬¬A
Γ ` A
Axiom (starting point):
A can always be inferred from A and a set of formulas.
Γ,A ` A
Weakening:
New assumptions may be introduced at any point in a derivation.
Γ ` B
Γ,A ` B
Order your professional paper with us. Click this link to get started.
