DISCRETE MATHEMATICS – Anna University Previous year Model Question Paper Nov/Dec 2011 for CSE dpt (5th Semester)...

Posted by R.Anirudhan

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Fifth Semester
Computer Science and Engineering
MA 2265 — DISCRETE MATHEMATICS
(Regulation 2008)
Time : Three hours Maximum : 100 marks
PART A — (10 × 2 = 20 marks)
1. Show that the propositions p ? q and p ? q are logically equivalent.
2. Give an indirect proof of the theorem “If 3n + 2 is odd, then n is odd”.
3. Write the generating function for the sequence 1, , , , , …. 2 3 4 a a a a
4. Use mathematical induction to show that n! ? = + n n 2 , 1 1, 2, 3, …
5. When is a simple graph G bipartite? Give an example.
6. Define complete graph and give an example.
7. Define homomorphism and isomorphism between two algebraic systems.
8. When is a group (G , *) called abelian?
9. Let A = {a, b, c} and ?(A ) be its power set. Draw a Hasse diagram of
< ?(A ), ? > .
10. When is a lattice called complete?

PART B — (5 × 16 = 80 marks)
11. (a) (i) Using indirect method of proof, derive p ? s from the
premises p ? (q ? r ), q ? p, s ? r and p. (8)
(ii) Prove that 2 is irrational by giving a proof using contradiction.
(8)
Or
(b) (i) Show that ?x(P(x ) ? Q(x )) ? (?x P(x )) ? (? ×Q(x )) by indirect
method of proof. (8)
(ii) Show that the statement ‘‘Every positive integer is the sum of
the squares of three integers” is false. (8)
12. (a) (i) If n Pigeonholes are occupied by (kn + l) pigeons, where k is
positive integer, prove that at least one Pigeonhole is occupied
by
(k + l) or more Pigeons. Hence, find the minimum number of m
integers to be selected from S = {1,2, …, 9} so that the sum of
two
of the m integers are even. (8)
(ii) Solve the recurrence relation 3 , 0, 3. 0
Or
b) (i) Use mathematical induction to show that ….
n
(8)
(ii) Use the method of generating function to solve the recurrence
relation
4 4 4 ; 2, 1 2 = ? + ? ? ? a a a n n
n n n given that 0 a = 2 and 8 1 a = . (8)
13. (a) (i) Determine which of the following graphs are bipartite and which
are not. If a graph is bipartite, state if it is completely bipartite.(8)
(ii) Using circuits, examine whether the following pairs of graphs
G1, G2 given below are isomorphic or not : (8)
Or
(b) (i) Prove that the maximum number of edges in a simple
disconnected graph G with n vertices and k components is
2
(n ? k )(n ? k + 1)
. (10)
(ii) Find an Euler path or an Euler circuit, if it exists in each of the
three graphs below. If it does not exist, explain why? (6)
14. (a) (i) Let (S , *) be a semigroup. Then prove that there exists a
homomorphism S g : S ? S , where , o S S is a semigroup of
functions from S to S under the operation of (left) composition.(8)
(ii) Prove that every finite group of order n is isomorphic to a
permutation group of order n. (8)
Or
(b) (i) Prove that the order of a subgroup of a finite group divides the
order the group. (10)
(ii) Prove the theorem : Let G, * be a finite cyclic group generated
by an element a ? G . If G is of order n, that is, | G | = n, then
a e n = , so that { , , , …, } 2 3 G a a a a e n = = . Further more n is a
least positive integer for which a e n = . (6)
15. (a) (i) If P(S) is the power set of a set S and ?, ? are taken as join and
meet, prove that P(S ), ? is a lattice. Also, prove the modular
inequality of a Lattice L, ? , viz for any a, b, c ? L ,
a ? c ? a ? (b ? c) ? (a ? b) ? c. (10)
(ii) In any Boolean algebra, show that ab’+a’ b = 0 if and only if
a = b.
(6)
Or
(b) (i) Prove that Demorgan’s laws hold good for a complemented
distributive lattice L, ?,? , viz (a ? b)’ = a’ ? b’ and
(a ? b)’ = a’ ? b’ . (8)
(ii) In any Boolean algebra, prove that the following statements are
equivalent : (8)
(1) a + b = b
(2) a • b = a
(3) a’+b = 1 and
(4) a • b’ = 0 .