Question 1

(a)  Express each of the statements in propositional logic using the propositions

M = “Maths is invented” and C = “Computing is invented”.

1. Maths is invented but Computing is not.

2.  Computing is invented if Maths is too.

3. Neither Maths nor Computing is invented.

(b)  Use a truth table to prove or disprove the following equivalence.  Also give an

example of an English language sentence corresponding to the first statement.

¬ (P ∧ (Q ^ R))

is logically equivalent to

(¬P) ^ (¬Q ^ ¬R).

Question 3

(a) Fill in the missing parts of this proof that

3x.(P (x) → Q(x)) ∧ Ay .(Q(y) → R(y)) ∧ Ax.P (x) → 3x.R (x)

The goal is to derive 3x.R (x) from the premises.

1. 3x.(P (x) → Q(x))

2. Ay .(Q(y) → R (y))

3. ***

4. P (a) → Q(a)

5.  Q(a) → R (a)

6.  P (a)

7.  Q(a)

8. R (a)

9. *** QED

premise

premise

premise

1, exist elimination

*, ***

3, forall elimination

***

5,7, modus ponens

*, exist introduction

Prove that the sum of two consecutive integers will always be odd.

Question 4

(a) Use induction to show that 11n +4 is divisible by 5 for all positive natural numbers n.

(b) Use induction to show that for any set with |S| = n we have |℘(S)| = 2n  (where ℘(S) is the power-set of S).

Question 5

(a)  Let A = {1, 3, {1, 3, 10}} and B = {∅ , 1, 10, {1, 2, 10}}. Write down the following

sets, using correct bracketing.

A ∩ B =

A n B =

(b) Prove or disprove that (C ∩ D) n D = D for any sets C and D .

Question 6

(a) For each of the following, state whether it is possible to have a function meeting

the criteria given, explain why or why not, and if it is possible, give an example.  6 marks i. A function f : N≥0  → N≥0  which is not surjective.

ii. A function f : N≥0  → Z which is injective.

iii. A function f : Q → Q which is bijective.

(b) For each of the following functions, state whether it is injective, surjective, and/or               bijective, and why. 

i. The function f (n) = 2n, mapping from integers to integers.

ii. The function q(ϕ), with codomain N≥0, which maps any formula of predicate logic to the number of quantifiers in that formula.

Question 7

The following directed graph shows a relation R over a set X , where X = {a, b, c, d, e}.

Answer the following questions about R.

(a) Is R a partial order? Explain why or why not.

(b) Describe changes which you could make to R (that is, addition or removal of pairs —or no change, if it already is) which would make it a partial order.

(c) Is (the original unchanged version of) R an equivalence relation? Explain why or why not.

(d) Describe changes which you could make to R (that is, addition or removal of pairs — or no change, if it already is) which would make it an equivalence relation. State

how many equivalence classes arise from the resulting relation.

Question 8

(a) Explain what is meant by the terms countable and uncountable applied to sets.

Give a concrete example of each.                                              

(b) Let S be the set of all functions with {0, 1} as the domain and the integers Z as

the co-domain. Is S countable? Justify your answer.             

Question 9

(a)  Draw a non-deterministic finite state machine for the input alphabet

A = {a, o, b, n, p, q, w} that recognises exactly all words which include the three

letter string bap.

(b) Draw a deterministic finite state machine to recognise the same language as 9(a).  5 marks

Question 10

(a)  Give a regular expression for the set of all strings of 0s and 1s containing exactly

three 0s.                                                                           

(b) Does the string 011100101 belong to the regular set 01* 10* (11* 0)*  ? Justify your

answer.

Prove that if A is a regular set with alphabet I , then the language defined by taking the set difference I* − A is also regular.

Question 11

Briefly explain the typical use of the Pumping Lemma for Regular Languages.

Use the Pumping Lemma for Regular Languages to prove that the language all binary strings that have equal numbers of 0s and 1s is not regular.

Question 12

(a)  Give a description for a Turing machine that recognises numbers divisible by three. Assume the Machine acts on a unary encoding where “1” is 1, “11” is 2,

“111” is 3... It should output a “1” on the tape if the number is divisible, and a 0 if it is not. The input encoding cannot represent 0.

Are there languages which can be recognized by Turing machines, but not by push-down automata? Give reasons for your answer, at least one example if there are any, and an explanation of how a Turing machine might recognize it.