Madurai Kamraj University (MKU) 2006 B.C.A Computer Application -1 DISCRETE MATHEMATICS - Question Paper

Time: 3 hours Maximum: 100 mark
PART A ans any 6 ques.. (6 x five =30 marks)

1. Let R = {(I, 2),(3, 4), (2, 2) } and S={(4, 2), (2,5),(3, 1),(1, 3)} obtain RoS, SoR R 0 (S 0
R) and S 0 (R 0 S).

2. Prove that {(x) =x / two is a partial recursive function.

3. describe free and bound variables with suitable examples.

4. Symbolize the expression "All the world loves lover”.

5. Consider the recurrence relation.3 C k - five C k-l + two C k-2 =C2 + five obtain the value of provided
that C3= two and C4= four .

6. discuss how will you find the solution of a recurrence relation using generating
functions.

7. Prove that there is 1 and only 1 path ranging from every pair of vertices in a tree.

8. Write any 3 characteristics of adjacency matrix of a graph.

9. discuss Karnaugh map with a suitable example.

10. provide a simple example of a Boolean algebra explaining the conditions satisfied by it.

PART B ans any 4 ques. (4 x 10 =40 marks)

11.Explain the Matrix and its properties.

12.Explain PCNF and Sum of product.

13. Check if the function {(x, y) = x - y is primitive recursive function.

14. find the generating function of the recurrence relation. ar =ar-l + ar-z with ao = 0,
al = 2, az = three .

15. Prove that a graph with n vertices, and no circuits is connected.

16. State and prove absorption properties of join and meet operations in a lattice.

PART C ans any 2 ques.. (2 x 15 =30 marks)

18. (a) Show that (x) (p (x) v Q (x)) =>(x) P (x) v (:Jx)Q (x).(b) Solve a(r)-5a(r-1)+6a(r-
2)=2r +r, r > two with a(O) = one and a(l) = 1.

19. (a) define an algorithm for generating all spanning trees of connected graph.
(b) Write a note on the applications of the Boolean algebra to the study of
switching theory.

Earning:   Approval pending.