1. The logical binary operation NAND, denoted |, is defined by

p | q = ~ (p ^ q).

(a) (2 marks) Write down the truth table for ~ (p | q). Show all working.

(b) (3 marks) Prove, using truth tables or otherwise, that (p | p) = (~ p). Show all working.

(c) (3 marks) Prove, using truth tables or otherwise, that ((p | p) | (q | q)) = p ^ q . Show all working.

3.   (a) (2 marks) Let A = {0, 1, 2, 3, 4}, B = {3, 4, 5, 6} and C = {1, 2, 4, 5, 7} and let

R = ((A - B) ∩ (A - C)) n (B ∩ C ∩ A).

List the elements of the set R.

(b) (2 marks) Let X = p(0) and Y = p(p(0)).  List the elements of each of the following sets.

(i) X

(ii) Y

(iii) X ∩ Y

(iv) X n Y

4. (5 marks) Prove that |Z+  x Z+ | = |Z+ |.

5.   (a) (4 marks) Let a be an integer such that the remainder is 1 when a is divided by 4. Prove that when a4  is divided by 16 the remainder is also 1.

(b) (4 marks) Use Euclid’s Algorithm to verify that gcd(2000, 1713) = 1.  Clearly show all steps in the execution of the algorithm.

6. (8 marks) Use mathematical induction to prove that the following statement is true.

For all integers n > 0, 3n  < (n + 3)!

7.  Consider the function f : Q ∩ [1, o) - Q ∩ [2, o) given by

f (x) = (x - 1)2 + 2 for all x e Q ∩ [1, o).

(a) (4 marks) Prove that the function f is injective.

(b) (3 marks) Prove that the function f is not surjective.

8.  Consider the relation ρ on Z given by

aρb if and only if (a - b)(a + b) = 4k for some k e Z.

(a) (6 marks) Prove that ρ is an equivalence relation.

(b) (2 marks) Determine the number of equivalence classes of ρ . Justify your answer.

9.   (a) (1 marks) Determine whether the groups (Z, +) and (R - {0}, .) are isomorphic. Justify your answer.

(b) (3 marks) Determine whether the groups (Z4 , +), (Z5  - {[0]}, .) are isomorphic.  Justify your answer.

(c) (4 marks) Find a subset S of Z10  such that (S, .) is a group of order 4 (where . denotes multiplication modulo 10). Justify your answer.

10. For this question, you may leave your answers as expressions involving factorials.

(a) (2 marks) How many distinct arrangements can be made of the letters of the word WOOLLOONGABBA?

(b) (3 marks) If the letters of the word WOOLLOONGABBA are permuted at random, what is the probability that we get the same word back?

(c) (3 marks) How  many  distinct  arrangements  are  there  of  the  letters  of  the  word WOOLLOONGABBA such that exactly one of the following is true?

● The two As are not next to each other.

● The two Bs are not next to each other.

● The two Ls are not next to each other.

11.   (a) (4 marks) Let T be a tree on p vertices where p > 11, T has precisely six vertices of degree

1 and precisely four vertices of degree 3.  Determine the degree of each of the remaining p - 10 vertices of T.

(b) (4 marks) Let d be a positive integer and let T be a tree such that T has a vertex of degree d. Prove that T has at least d vertices of degree 1.