SOLUTIONS TO THE EXAM FOR G51MCS, 2011-2012

Problem 1 consists in exercises that are identical to or small variations on
  ones that have been treated during the lectures.

Each of problems 2-5 is divided into 3 parts.
Part (a) is bookwork: a trivial exercise to test if the student studied
  the lecture notes;
Part (b) is an exercise of moderate difficulty similar to some that have
  been treated in class and in the lecture notes;
Part (c) is a more challenging exercise that requires some more advanced
  skills from the student.

QUESTION 1

(a)
(i)   B => ~C
(ii)  ~A /\ C => ~B
(iii) NO
(iv)  A  B  (B\/A)  ~(B\/A)  A/\~(B\/A)
      t  t  t       f        f
      t  f  t       f        f
      f  t  t       f        f
      f  f  f       t        f
(v)   NO

(b)
(i)   5
(ii)  2
(iii) 1
(iv)  false
(v)   false

(c)
(i)   true
(ii)  false
(iii) true
(iv)  false
(v)   true

(d)
(i)   daisy,cyclamen,tulip,orchid  (all of B)
(ii)  {}, {tulip}, {daisy}, {tulip,daisy}
(iii) true
(iv)  false
(v)   true

(e)
(i)   0
(ii)  8
(iii) 10
(iv)  4960
(v)   4

QUESTION 2

(a)
A B C  A=>B  (A=>B)=>C  A\/B  ~C  A\/B\/~C  ((A=>B)=>C)=>A\/B\/~C
t t t  t     t          t     f   t         t
t t f  t     f          t     t   t         t
t f t  f     t          t     f   t         t
t f f  f     t          t     t   t         t
f t t  t     t          t     f   t         t
f t f  t     f          t     t   t         t
f f t  t     t          f     f   f         f
f f f  t     f          f     t   t         t

NOT a tautology

(b)

1. ~A /\ B
2. A \/ ~B
  --------
3. ~A      /\E,1
4. B       /\E,1
     -------------
5.   A       Assumption
6.   False   ~E,3,5
     -------------
7.   ~B      Assumption
8.   False   ~E,7,4
     -------------
9. False    \/E,2,5-6,7-8

(c)

(C=>B)=>A
= ~(~C\/B)\/A         Definition of implication, twice
= (~~C/\~B)\/A        Second De Morgan law
= A\/(~~C/\~B)        Commutativity of disjunction
= (A\/~~C)/\(A\/~B)   Distributivity of disj. over conj.
= (~~C\/A)/\(~B\/A)   Comm. of disj., twice
= (~C=>A)/\(B=>A)     Definition of implication, twice

QUESTION 3

(a)
strangeFun(1) = 2
strangeFun(2) = 6
strangeFun(3) = 12
strangeFun(4) = 20

(b)
Base case, P(0) : strangeFun(0) = 0 by definition
                  0*(0+1) = 0       by arithmetic
           so P(0) is trivially true
Inductive step
  Induction hypothesis: Assume P(k) is true
                        strangeFun(k) = k*(k+1)
  We must prove P(k+1) : strangeFun(k+1) = (k+1)*(k+2)
  In fact we have:
    strangeFun(k+1)
    = 2*(k+1)^2 - strangeFun(k)   by definition of strangeFun
    = 2*(k+1)^2 - k*(k+1)         by induction hypothesis
    = (k+1)(2*(k+1) - k)          common factor (k+1)
    = (k+1)(k+2)                  arithmetic
Since we proved P(0) and P(k)=>P(k+1) for every k,
  by induction P(n) is true for all n.

(c)
The two coefficients are 5 and -3.

QUESTION 4

(a)
(A\(BuC)) u (B\(CuA)) u (C\(AuB))

(b)
Numbers in A: 5, 7, 11, 13, 19, 23
Numbers in B: 7, 11, 12, 13, 15, 19, 22
Numbers in C: 11, 22, 33
The numbers in the set from part (a) are:
  5, 12, 15, 23, 33

(c)
The values of the function are:
  f(0)=1, f(1)=0, f(2)=3, f(3)=0
(i) It is not a bijection.
(ii) f has the same value on 1 and 3
     (and never produces the value 2)

QUESTION 5

(a)
f(0) = 2     0^2 = 0 
f(1) = 4     1^2 = 1
f(2) = 3     2^2 = 4
f(3) = 1     3^2 = 4
f(4) = 0     4^2 = 1

(b)
The function f is bijective. Its inverse "finv" has the values:
finv(0)=4
finv(1)=3
finv(2)=0
finv(3)=2
finv(4)=1

(c)
f has a single orbit: 0 -> 2 -> 3 -> 1 -> 4 -> 0.
Therefore the least n such that f^n=id is 5.