CS151 - Discrete Structures 1
Sample solutions to selected past exam questions
T. Naughton, Department of Computer Science, NUI Maynooth

SE119 January 2005 Q2(a)
· 31
· 8
· 19

SE119 January 2005 Q2(b)
Definitions injective and surjective are not part of the course this year. The answers to the remaining part of the questions are as follows.
· R is not a function.
· R is a function. Further, it is a bijection. Its inverse R^-1 is {(2,1), (3,2), (4,3), (5,4), (1,5)}

SE119 January 2005 Q2(c)
Not part of the course this year.

SE119 January 2005 Q2(d)
The domain of f is × . The range of f is _n = {0, 1, 2, ..., n-1}.
g(g(g(g(7)))) = g(g(g(6)))
                    = g(g(5))
                    = g(4)
                    = 1

SE119 January 2005 Q3(a)
f(13) = f(7) + 13
      = f(4) + 7 + 13
      = f(2) + 4 + 7 + 13
      = f(1) + 2 + 4 + 7 + 13
      = 1 + 2 + 4 + 7 + 13 = 27

SE119 January 2005 Q4(b)
Not part of the course this year.

SE119 January 2005 Q4(c)
· For all x there exists a y such that x+y=0 (True)
· There exists an x such that for all y   x+y=0 (False)

SE119 January 2005 Q4(d)
· (x (F(x) not S(x)) AND S(John)) not F(John)
· (x(P(x) AND S(x)) AND x (F(x) not S(x))) y(P(y) AND not F(y))

SE119 Autumn 2005 Q2(b)
i) A mapping is bijective if it is a function and its inverse is also a function (in CS151, functions are total functions by default)
ii)
· f^-1(x) = (x-2)/4
· f^-1(x) = 1/(x-3)
· f^-1(x) = {(3,0), (5,1), (0,2), (2,3), (4,4), (6,5), (1,6)}
iii)
· f muliplies by 4 then adds two so the inverse subtracts two then divides by 4 (the inverse of multiplication is division and the inverse of addition is subtraction)
· f gets the recipricol then adds 3 so the inverse subtracts 3 then gets the recipricol (the inverse of a recipricol is a recipricol)
· The mod operation cannot be inverted in general so we write out the inverse explicitly

SE119 Autumn 2005 Q2(c)
Not part of the course this year.

SE119 Autumn 2005 Q2(d)
· f _° g = f(g(x)) = floor(2x²)
· g _° f = g(f(x)) = (floor(2x))²

SE119 Autumn 2005 Q3(a)
f(4) = f(3) + 4
      = f(2) + 3 + 4
      = f(1) + 2 + 3 + 4
      = f(0) + 1 + 2 + 3 + 4
      = 0 + 1 + 2 + 3 + 4 = 10

SE119 Autumn 2005 Q4(a)
Not part of the course this year.

SE119 Autumn 2005 Q4(b)
Not part of the course this year.

SE119 Autumn 2005 Q4(c)
· All professional athletes play soccer
· Some professional athletes play soccer
· Every person is either a professinal athlete or plays soccer

The negation of each of these propositions is
· Not all professional athletes play soccer: x(P(x) AND not Q(x))
· No professional athletes play soccer: x (P(x) not Q(x))
· Some people are neither professional athletes nor play soccer: x(not P(x) AND not Q(x))

SE119 Autumn 2005 Q4(d)
· x(P(x) Q(x))
· x(P(x) AND Q(x))
· x(Q(x) P(x))
· x(P(x) AND Q(x))