v)  Consider the following propositions:

(1)  If the weather was nice and I was not tired then I went for a walk.

(2)  If the weather was not nice and I had enough money then I went to the cinema.

(3)  I did not go to the cinema.

(4)  I did not go for a walk.

(5)  I had enough money.

a)  Let

n = “The weather was nice”,

t =“I was tired”,

w =“I went for a walk”,

c =“I went to the cinema”,

m =“I had enough money”.

Write the propositions (1)– (5) in symbolic form using logical connec- tives.

b)  Use the rules of inference to deduce whether you were tired.  Show your working.

2. In parts i) and ii) of this question you should leave your answers in terms of powers, factorials and/or P and C notation.

i)  The English alphabet has 26 letters, of which 5 are vowels and 21 are consonants. We will write all our words using upper case (capital) letters. Repetition of letters in words is allowed.

Find the number of 12 letter words (strings) using the English alphabet:

a)  with no further restrictions;

b)  containing exactly 4 vowels and no repeated consonants;

c)  containing the subword “WATER” at least once

(e.g., “ZWATERZWATER” but not “ZWAZTERZZZZZ”).

ii)  Let  b1 , b2 , . . . , b14   be integers, with repetitions allowed. Define S = {(i, j) e 勿2   l  1 = i, j = 14,  i < j} .

a)  Write down the cardinality of  S .

b)  Prove that, for some  r e {0, 1, . . . , 44} , there are at least three pairs (i, j) e S  such that

bi + bj  = r    (mod 45) .

iii)  Consider the following statement:

A a e 勿 A b e 勿 3 x e 勿 ax = b  (mod 40).

a)  Write down the negation of this statement, and simplify your answer so that the negation symbol is not used. You may use the symbol  \= in your answer.

b)  Is the negation true or false? Justify your answer.

iv)  For all positive integers  n , let  an   be the number of ways to tile a  2 - n grid with the following tiles:

white

2 - 1

grey

2 - 2

white

2 - 2

black

2 - 2

The arrow on each tile must always point upwards ( 5 ).

a)  Write down  a1   and  a2  .

b)  Clearly explain why

an  = 2an ←1 + 3an ←2

for  n < 3 .

c)  Solve this recurrence relation subject to the initial conditions that you wrote down in part a).

3. i)  Consider the following graph  G  with vertices  S, V1 , V2 , . . . , Vn , T , in which each vertex  Vi   is adjacent to  S  and  T :

V1

V2

S T

Vn

G

a)  Determine the number of Euler paths from  S  to  T  in  G

α )  if n  is even;

β )  if n  is odd.

b)  How many cycles of length 4 does  G  contain as subgraphs?

c)  What is the degree of each region of  G ?

d)  State the number of Hamilton circuits in the planar dual  G=  .

ii)  Graphs  G1    and  G2    are each simple and each have vertex degree se- quence  4, 4, 4, 3, 3 . Explain why  G1   and  G2   are isomorphic.

iii)  Let  G  be a connected, simple, bipartite graph with vertex partition V = V1  u V2    with  lV1 l = lV2 l = n , and suppose that each vertex has degree 4.

a)  Determine the number of edges of  G , with explanation.

b)  Prove that  G  is not planar.