Kannur University 2009 B.C.A Computer Application Second semester 202 DISCRETE MATHEMATICS Model - Question Paper

PART A
ans any Ten ques.
1.Define a partial order relation with an example
2.Prove that the union of transitive relation is not transitive.
3.State the principle of mathematical induction
4.Write inclusion and exclusion principle for two sets and for 3 sets
5. State the 1st 5 laws of Boolean algebra
6.State the Demorgan's laws for the propositions.
7.Write the 2 classic rules of inference in propositional calculus
8. describe the quantifiers used in predicate calculus with examples.
9 describe with example (a) spanning tree (b) planar graphs
10.What is the principle of optimality.
11.What are the various kinds of tree searching ?
12.Prove that the graph K 3,3 is not coplanar.
(3*10=30 marks)
PART B
(Answer all Questions)
13(a)Define a relation R on N by x R y = (x-y) is divisible by 5. Prove that R is an
Equivalence relation (5 marks)
(b)Let the functions f and g be described by f(x)=2x+1 and g(x)=x2-2.
calculate fog and gof (4 marks)
OR
14.Explain the Hamming codes. (9 marks)
15(a)Find the number of ways that 12 students can be partitioned into 3 teams ,so that
every team contains 4 students? (4 marks)
(b)In how many ways ,a party of four or more can be opted from 10 persons?
(5 marks)
OR
16(a)5 men and four women are to be seated in a row. obtain the number of arrangements if
no 2 women are to sit next to every other (4 marks)
(b)Prove that nCr-1 + nCr. = (n+1)Cr (5 marks)
17(a)Check whether ( P? Q )?(( P v R )?(Q v R ) is a tautology or not (5 marks)
(b)Explain reductio ad absurdum method with an example (4 marks)
OR
18(a) Show that R?S can be derived from premises P? (Q? S)., +(RvP) and Q
(5marks)
(b) Construct the truth table for ( (p ? q ) ? ( q ? r ) ) ?( p ? r) (4marks)
19(a)Explain the rules for converting predicate calculus (6 marks)
(b)Express the statement in symbolic form
"If all men are giants then every thing is a man only if every thing is a giant (3marks)
OR
20(a) discuss the resolution principle in predicate calculus (5 marks)
(b)Prove that ( ? x ) P(x) ? ( ? x ) Q(x) will not imply ( ?x)( P(x) ? Q(x) ) (4marks)
21 (a) State and prove Euler's theorem for Euler cycles (9 marks)
OR
22. discuss Warshall's algorithm and Floyd's algorithm (9 marks

Earning:   Approval pending.