Question 1
(a) Express the proposition ``Either my program runs and it contains no bugs, or my program
contains bugs'' in symbolic form.
(b) Write down English sentences for the converse and contrapositive of the following
proposition ``If a graphics driver is not available then my program cannot run.''
(c) Show that the following argument ``If n > 10 when the subroutine call statement is reached
then the subroutine is called. The subroutine is called. Therefore n > 10 when the subroutine
call statement is reached'' can be put in symbolic form as [( p® q) Ùq] ® p. By
constructing a truth table test the validity of this argument, that is whether it is a
tautology or not.
Question 2
(a) Let A = { 2, {4,5},4}. Which of the statements are incorrect and state why?
(i) {4,5} Ì A, (ii) {4,5} Î A, (iii) {{4,5}} Ì A.
(b) Let A = { 1, 2, 3, 4, 5 }, B = {2,4,6} and C = {1,3,5}. Find the following sets
(i) A ÈB, (ii)A ÇB, (iii) (A ÇB) ÇC.
(c) Define the cardinality of a finite set. State the Principle of inclusion and exclusion for
two finite sets. In a group of 180 students studying computing 95 can program in Pascal and 76
can program in Lisp. If 50 can program in both Pascal and Lisp, how many of the students cannot
program in either of these languages?
(d) Show that the relation defined by R = {(a,a), (b,b), (c,c), (a,b), (b,a)} on
{a,b,c} is an equivalence relation. Find the matrix representation of R.
Question 3
(a) State the Principle of Mathematical Induction.
(b) Find a recursive expression for the output of the following algorithm.
| 1. Input n |
| 2. value ¬ 1 |
| 3. For i = 1 to n do |
| 3.1 j ¬ i +1 |
| 3.2 value ¬ value +j |
| 4. Output i, value |
Question 1
(a) Define Logic and write a brief note on its importance in computer science.
(b) Formulate the symbolic expression in words using
p: Today is Monday.
q: It is raining. r: It is hot.
(i) p ® q , (ii) Ø(p Úq ) « r.
(c) Verify de Morgan's law of logic Ø(p Ùq) º Øp ÚØq
using a truth table.
Question 2
(a) Define a function.
(b) Determine whether the following are functions. For those that are state the domain,
codomain and range.
(i) { (1,a), (1,b), (2,c), (3,b)}
(ii) { (a,a), (b,b), (c,c), }
(c) A function f: {1,2,3,4,5} ® {0,1,2,3,4} is defined by the rule f(n) is
the remainder after 3n is divided by 5. Draw the arrow diagram for this function.
Hence state whether f is one-to-one or onto. Does it have an inverse f-1 and if
so what is f-1?
(d) Let X be the set of all names of students in a database maintained by a university
(Assume that no two students have the same name.) Let Y be the set of ID numbers of the
students. The functions f and g are defined as follows:
f: X ® Y f(x) = ID number of student with name x.
g: Y ® N g(y) = age (in year) of student with ID number y.
(i) Describe the functions g o f and f-1
(ii) Explain why g-1 does not exist.
Question 3
(a) Define a sequence of real numbers.
(b) For the following recursively defined sequence:
| |||||||||||||
|