## 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 *i*th 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.