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.