IS2 Sample Exam Questions IS2 Sample Exam Questions

Question 1
(b) (i) (Øp ) Ùq    (ii) Ø( p Úq) º (Øp ) Ù(Øq)    (iii) (Øp) Ú( p Ù(Øq))
(c) Prove p Ú(p Ùq) º p by constructing the appropriate truth table.

p q (p Ùq) p Ú(p Ùq)
T T T T
T F F T
F T F T
F F F T

(d) p = ``6 is even.''    q = ``2 divides 7.''    r = ``5 is prime. ''
If 6 is even then 2 does not divide 7 º p ® (Øq) .
Either 5 is prime or 2 divides 7 º r Úq.
But 5 is prime º r.
Therefore 6 is odd (and not even) º Øp.
To check the validity of the argument you must check if

(( p ® (Øq)) Ù(r Úq) Ù(r)) ® (Øp)
this can be done using a truth table.

p q r Øq p ® Øq r Úq ( p ® Øq) Ù(r Úq)
T T T F F T F
T T F F F T F
T F T T T T T
T F F T T F F
F T T F T T T
F T F F T T T
F F T T T T T
F F F T T F F

( p ® Øq) Ù(r Úq) Ù(r) Øp (( p ® Øq) Ù(r Úq) Ù(r)) ® (Øp)
F F T
F F T
T F F
F F T
T T T
F T T
T T T
F T T

(e) There is a bird which cannot fly º $x (B(x) Ù(ØF(x))
Not all birds can fly. º Ø("x B(x) ® F(x))

Question 2
(b)

Æ, A = {1}, B = {1, 3}, C = {1, 5, 9}, D = {1, 2, 3, 4, 5}, E = {1, 3, 5, 7, 9}, U = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Insert the correct symbol Ì or \not Ì between each pair of sets
(i) Æ Ì A
(ii) A Ì B
(iii) B \not Ì C
(iv) B Ì E
(v) C\not Ì D
(vi) C Ì E
(vii) D\not Ì E
(viii) D Ì U
(c) Let A = { 1, 2, 3, 4, 5 }, B = {4, 5, 6, 7}, C = {5, 6, 7, 8, 9}, D = {1, 3, 5, 7, 9}, E = {2, 4, 6, 8}, F = {1, 5, 9}. Find the following sets
(i) A ÈB = {1,2,3,4,5,6,7}
(ii) B Ç[`D] = B Ç{2,4,6,8} = {4,6}
(iii) A \B = A -B = {1,2,3}
(iv) E
(v) [`D] ÈF = {2,4,6,8} È{1,5,9} = Æ
(d) Consider the following binary relation on the set A = { 1, 2, 3, 4, 5}.
R = {(1, 2), (1, 5), (2, 2), (2, 3), (2, 4), (3, 1), (4, 4), (5, 4), (5,5)}
(i) Give the directed graph of R.
(ii) Give the matrix representation of R.
(I did these in class, and they are easy enough, so I'm not going to bother writing out the solutions here.)
(e) Let D = { a, b, c, d} Consider the relation on D given by
R = {(a, a), (a, b), (b, a), (b, b), (c, c),(c, d), (d, c) (d, d)}

This relation is reflexive since (a,a), (b,b), (c,c), (d,d) are all elements of the relation.
The relation is symmetric since (x,y) Î R (x,y Î D) implies (y,x) Î R. e.g. (a,b) Î R implies (b,a) Î R.
The relation is not anti-symmetric since (a,b) Î R and (b,a) Î R and a ¹ b.
The relation is transitive since (x,y) Î R and (y,z) Î R implies (x,z) e.g. (a,b) Î R and (b,a) in R implies (a,a) Î R.
Therefore the relation R is an equivalence relation because it is relexive, symmetric and transitive. It is not a partial order since it is not anti-symmetric.

The equivalence classes are:

E[a]
=
{y Î D | (y,a) Î R} = {a,b)}
E[b]
=
{y Î D | (y,b) Î R} = {a,b)}
E[c]
=
{y Î D | (y,c) Î R} = {a,c)}
E[d]
=
{y Î D | (y,d) Î R} = {a,d)}

Question 3
(b) Let f and g be functions defined as follows:

f: R ® R
   
f(x) = 3x2 + 7
g: R ® R
   
g(x) = 2x - 4
evaluate
(i) (f o g) (x)
(f o g) (x)
=
f(g(x))
=
f(2x-4)
=
3(2x-4)2 +7
=
3(2x-4)(2x-4) +7
=
3(4x2 -8x -8x +16) +7
=
3(4x2 -16x +16 +7
=
12x2 -48x +48 +7
=
12x2 -48x +55
(g o f) (x)
=
g(f(x))
=
g(3x2 +7)
=
2(3x2 +7) -4
=
6x2 +14 -4
=
6x2 +10
(f o f) (x)
=
f(f(x))
=
f(3x2+7)
=
3(3x2+7)2 +7
=
3(3x2+7)(3x2+7) +7
=
3(9x4 +21x2 +21x2 +49) +7
=
3(9x4 +42x2 +49) +7
=
27x4 +126x2 +147 +7
=
27x4 +126x2 +154
(f o f o g ) (x)
=
f(f(g(x)))
=
f(12x2 -48x +55)
=
3(12x2 -48x +55)2 +7
=
3((12x2 -48x) +55)2 +7
=
3((12x2 -48x)2 +55(12x2-48x) + 55(12x2-48x) + (55)2) +7
=
3((12x2 -48x)(12x2-48x) +110(12x2-48x) + 3025) +7
=
3((12x2 -48x)(12x2-48x) +1320x2-2640x + 3025) +7
=
3((144x4 -12(48)x3 -12(48)x3+2304x2) +1320x2-2640x + 3025) +7
=
3(144x4 -1152x3 +2304x2 +1320x2-2640x + 3025) +7
=
3(144x4 -1152x3 +3624x2 -2640x + 3025) +7
=
432x4 -3456x3 +10872x2 -7920x + 9075 +7
=
432x4 -3456x3 +10872x2 -7920x + 9082
(c) For the following recursively defined sequence
t(1) = 2        t(n) = t(n-1) + 2n -1,  n > 1
evaluate the first 5 terms.
t(1)
=
2
t(2)
=
t(1) + 2(2) -1 = 2 + 4 -1 = 5
t(3)
=
t(2) + 2(3) -1 = 5 + 6 -1 = 10
t(4)
=
t(3) + 2(4) -1 = 10 + 8 -1 = 17
t(5)
=
t(4) + 2(5) -1 = 17 + 10 -1 = 26
(d) True for n = 1 since t(1) = 2 and using the formula given t(1) = (1)2 + 1 = 1+1 = 2.
Assume true for n = k i.e. t(k) = k2+1. We now need to use this to show that t(k+1) = (k+1)2 +1. Using the expression from (c) the left hand side here is
t(k+1)
=
t(k)+2(k+1) -1
=
t(k)+2k+2 -1
=
t(k)+2k+1
=
k2+1+2k+1     using the assumption that the formula is true for n = k
=
k2+2k+2
We now look at the right hand side of the expression t(k+1) = (k+1)2 +1:
(k+1)2 +1
=
(k+1)(k+1) +1
=
k2 + 2k +1 +1
=
k2 + 2k +2
As the left hand side is the same as the right hand side we have shown the expression is true for n = k+1. Hence, by the principle of mathematical induction the formula is true for all n.

File translated from TEX by TTH, version 2.10.
On 14 May 1999, 20:07.