Second semester BCA Degree Examination 202 DISCRETE MATHEMATICS Model Question Paper (2007 Admission onwards)mg university

Time: 3Hrs Maximum marks:75

                                     PART A

                      Answer any Ten questions

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 2 sets and for three sets
5. State the first five laws of Boolean algebra
6.State the Demorgan’s laws for the propositions.
7.Write the two classic rules of inference in propositional calculus
8. Define the quantifiers used in predicate calculus with examples.
9 Define with example (a) spanning tree (b) planar graphs
10.What is the principle of optimality.
11.What are the different types 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 defined by f(x)=2x+1 and g(x)=x2-2.
Compute 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 three teams ,so that
each team contains four students? (4 marks)
(b)In how many ways ,a party of 4 or more can be selected from 10 persons?
(5 marks)
OR
16(a)5 men and 4 women are to be seated in a row. Find the number of arrangements if
no two women are to sit next to each 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 everything is a man only if everything is a giant (3marks)
OR
20(a) Explain 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. Explain Warshall’s algorithm and Floyd’s algorithm (9 marks)