Reg. No.
B.Tech. DEGREE EXAMINATION, NOVEMBER 2017
30. a. Solve the recurrence relatio1 on - 4or_t + 4an_2 = (n +l)2n wlth a0 = 0 and, a, = 1. Third/ Fourth/ Fifth Semester
(oR) 15MA3O2 _ DISCRETE MATHEMATICS
b.i Solve an-3an-1=l,n2land as = 1 using generating function. (For the candidates admitted during the academic year 2015 - 2016 onwards)
Note:
(i) Part - A should be answered in OMR sheet within first 45 minutes and OMR sheet should be handed
ii. State and prove Lagrange's theorem. over to hall invigilator at the end of 45tr minute.
(ii) Part - B and Part - C should be answered in answer booklet.
( n\2
31'a'i Prove that the number of edges in a bipartite graph with n vertices is atmost Time: Three Hours Max. Marks: 100
l;)
ii. Construct the binary tree whose in order and post order traversals are DCEBFAHGI and
PART-A(20x1:20Marks)
DECFBHIGA respectively.
Answer ALL Questions
1. p -+ q is logically equivalent to
(oR) (A) 1p -+1q (B) lq -+1p
b. Find the minimum spanning tree for the fotlowing weighted graph using Kruskal's (C) p -+1q (D) 1p -+ q
algorithm.
2. p-+(q-->p)=
v 5x (A) T (B) F
x
2
-] (c) p-+q (D) p^q
1
B F
E
3.
G
6
,d 4
The dual of
(A) (pv q) nr
(1pv a) n F is
(B) (1p nq)u F
(c) (p-q)nF (D) (1p->q)vr
32.a.i State and prove distributive inequalities in a lattice. 4. The negation of "every city in Tamilnadu is clean".
(A) Every city in Tamilnadu is not clean '(B) Some city in Tamilnadu are not clean
ii. If S, is the set of all divisors of the positive integer and D is the relation defined by aDb if (C) Every city in Tamilnadu is clean (D) Every city in Tamilnadu are dirty
and only if a divides
b, prove that Da2 = {S+z,D} is a complemented lattice by f,rnding the
complements of all the elements. 5. A relation R from a non-empty set A to a non - empty set B is a
(A) Subset of AxB (B) Subset of AxA
(oR) (C) Subset of BxB (D) Subset of BxA
b.i State and prove DeMorgan's law in Boolean algebra.
6. In a poset, the greatest and least element, if they exist, are
ii' (A) Exactly two (B) Zero
f ( x-v-z\
Simpliff the Boolean expression JvJ'/L' = *f ,. r(* - *)1. (C) Unique (D) More than one
7. tr A={1,23} andB={o,b,c} and f ={(t,o),(2,b),(3,t),(4,6)}, thenthe function is
(A) Neither1-lnoronto (B) 1-lbutnotonto
(C) Onto but not I - 1 (D) Bothl-landonto
8. Assuming that repetitions are not permiffed, how many four-digit numbers can be formed
from 1,2,3,4,5,6.....
(A) 360 (B) ls
(c) 20 (D) 460
Page 4 of 4 16NF3/4/515MA302 Page 1of 4 16NF3/4/515MA302
9. The generating function of the sequence l, I, I..... is given by
(A) (r + x)-r (B) (r +,)-2 PART - B (5 x 4:20 Marks)
(c) (r -,)-' (o) (r - *)-' Answer All-Y FIVE Questions
2t. Construct the truth table for
10. The recurrence relation of Fibonacci sequence is (7p -1q)*(q <->r)
(A) Fn= Fn-r* Fr-2,n) 0 (B) Fn: Fn-r- Fn-2, n) 0
(C) Fn = Fn-r* Fn-2, n) 2 (D) Fn = Fn-r- Fr-2, n) 2 22. Show that 'r' can be derived from the premises Pv {1, P )r, q ->r .
23. Prove that (A - C) a(C - A) = Q analltically.
11. The generator of a cyclic group {1'1i, -i} is
(A) 1, i (B) -r, - i
(c) i,-i' (D) r,-i 24. If R is the relation of A={t,Z,l\ such that (o,b)e R if and only if a+b = eyene find the
relational matrix Mp, Mp-1andllp.
12. The inverse element of any element 4a)) h the group of integers Z with the operator *
defined,by a* b = a + b + 2Y a,b e Z is 25. Show that {L 3,5,7\ is an abelian goup under muttiplication modulo 8.
(A) -2 (B) 2
(C) a+4 (D) -a4 26. If any disconnected graph has exactly two vertices of odd degree, show that there is a path
joining these two vertices.
13. A vertex with zero indegree is called as
(A) Sink (B) Source
(C) Terminal (D) Out degree 27. In a Boolean algebr4 show that (a+b)'=a'.b' .
14' The value of the prefix expression + - t 32t n / 8- 42 is PART-C(5 xl?= 60Marks)
(A) (B) Answer ALL Questions
0 s
(c) -s (D) 2
28. a. Show that the premises "one student in this class knows how to write programs in JAVA"
and "everyone who known how to write programs in JAVA can get a high-paying job" imply
15. A connected graph without any circuit is called as
(A) Leaf (B) Flower the conclusion "someone in this class can get a high-paying job".
(C) Tree (D) Loop
(oR)
16. A maximum height of a 11 vertex binary tree is b.i. Using CP-ruIe, derive p+(q-+s) form the premises p-+(O-+r) and q -+(r -+").
(A) 4 (B) 5 (8 Marks)
(c) 3 (D) 6
ii' Using mathematical induction, show that ln >zn-r for n>7. (4 Marks)
17 . AII Boolean algebras of order 2n are
(A) Isomorphic to each other (B) Homorphic to each other 29.a.i Let R =
(C) Non-isomorphic to each other (D) Non-homomorphic to each other {(L l),(L r), (r, s),(2,3),(2,4),(3,3), (3, s),(4,2),(4,4),(s,+)} ue a retarion on a
set A={1,.2,3,4,5\. Find transitive closure using Warshall's algorithm. (8
18. Dominance laws are Marks)
(A) a+l= 0and a.0=l (B) a +l:1 and a.0 = 0
(C) o+l=aanda.0=a (D) a+q=2aatda.0:0 ii. Draw the Hasse diagram for the partial ordering relation {(1, a) I A cB} on a power set
P(^9) where S = {a,b, c}. (4 Marks)
19.
{t, =} av b = b
In a lattice
(A) if and only if a<b (B) if and only if a-b (oR)
(C) if and only if a>b (D) if and only if b<b b.i Show that composition of invertible functions is invertible.
20. Every finite lattice is ii. If we select 10 points in the interior of an equilateral triangle of side 1, show that there must
(A) Bounded (B) Unbounded
(C) Infinite lattice (D) Uncountable lattice
be atleast two points whose distance apart
'a is less than fr .
Page2 of 4 16NF3/4/515MA302 Page 3 of4 16NF3/4/5t5MA3o2
b.i IfA:{1,2,3,4,5},B:{1,2,3,8,9}andf:A-+Bandg:A-+Aaredefinedasf:{(1,8),(3,9), Reg. No.
(4,3),Q,l),(5,2)l andg= {(1,2), (3,1),(2,2),(4,3),(5,2)},then f og, g"f and g"g findif
B.Tech. DEGREE EXAMINATION, MAY 2018
,, 1"1"tt,j, composition tunction is associative. First to Sixth Semester
30'a' Solu.therecurrencerelation ar*2-6an*y+gan-3(2n)+7(3n),n >0, giventhatao=1 andar=4. 15MA3O2 _ DISCRETE N,IATHEMATICS
(For the candidates admitted during the academic year 2015 - 2016 onwards)
(oR) Note:
b.i Use the method of generating function to solve the reculrence relation (D Part - A should be answered in OMR sheet within first 45 minutes and OMR sheet should be handed over to
hall invigilator at the end of 45d minute.
an - 3ar-1+ 1; /i > l, given that ag = I . (ii) Part - B and Part - C should be answered in answer booklet.
ii. If G is an abelian group with idenfity 'e', then prove that a1l the elements x of G satisfuing the Time: Three Hours Max. Marks: 100
equationl: e form a subgroup H o.f G.
PART -A (20 x 1 :20 Marks)
3I .a.i Prove that the number of vertices of odd degree in an undirected graph is even Answer ALL Questions
ii. Find the minimum spanning tree for the gmph using Kruskal's algorithm. 1. The of a preposition is generally forrned by introducing the word 'NOT' at the proper
place
(A) Conjunction @) Disjunction
(C) Negation @) Conditional
The contrapositive of q-+p is
(A) p-+q (B) lp-+'rq
(c) Tq-+7p @) 'rp-+q
3. The negation of 'A11 roads lead to Denmark' is
b. List the order in which the vertices ofthe tree given below are processed using preorder inorder
(A) Some roads don't's lead to Denmark (B) Every road doesn't lead to Denmark
and post order traversal.
(C) Some roads lead to Denmark @) Everv road leads to Denmark
4. The duatity law of (p n q)v I is
(A) (p xq) nT (B) (p nq)v T
(C) (pv q) rF (D) (p nq)v F
5. If A: {a,b} andB: {1,2},thenthe elements ofB x Aare
(A) {(r, (t,t),12,"),{z,D} @) {(o, 1), (t,,t),{o,z),{t,z)\
"),
(c) {(", o), 1u,o),{n,D,to,o)\ (D)
{(r, r), (r,
z),(2,t),(2,D}
6. If 'n' pigeors are accommodated in 'm' pigeon holes and-n >m, then one of the pigeon hole is
must contain atleast
32.a.i. tf(f,<)isalattice,thenforany4b,ceL,provethat an(bvc)>(anb)v(aac) (A) |
l-n-l l+lI
(B)
l* )
l tl l*,
ii. If S" is the set of all divisors of the positive integer 'n' and D is the relation of 'division', then L* ) (D)L+].,
prove that {SZ+, D} is a lattice. (c) I m-rl
l- l+l
(oR) ln-l
b.i State and prove Demorgan's law in Boolean algebra.
7. rc,q.-11,2,3,4\,8-{x,y,z} and f ={(t,r)12, y)(t,z)(+,x)} thentnetunctionf is
ii. Simplify the foltowing expression using Boolean algebra. (A) Both 1-1 and onto (B) 1.1 but not onto
xfy+z(xy+xz)'f (C) Onto but not 1-1 @) Neither 1-l noronto
Page 4 of4 r6MF1-6/15MA302 Page 1of4 16MF1-6/15MA302
8.
lff :R-+Rand g:R-+R definedby f(x)-x2 -2andg(x) 20. Simplification of Boolean expression (a+b)(a+c) is
=x+4,thengof ig
(A) 4x+8 (B) x2 +t4 (A) az +ac+ab+bc (B) a+bc
(C) x2 +8x+14 @) x2 +2 (C) a+ac @) a2 +b"
9. Given the sequence 4, 12,36,108.... the recurrence is
PART-B(5x4-20Marks)
(A) an-1 =3an,n) 0 (B) an = 4ar-1,n21
Answer AI,{Y FM Questions
(C) an*1=3an,n)l (D) an= 4an_1,n) 0 21. Construct the truth table for (1 f n
6 -+ q)) -+ 1 P .
10. The generating firnction ofsequence 1, 1, 1, ..... is given by 22. If R is the relation on the set of ordered pairs of positive integers such that (4 b), (c, d)eR
(A) I (B) I wherever ad : bc, show that R is an equivalence relation.
l+x 1-x 23. Prove that the identity element of a group (G, *) is unique.
(c) 1 @)l
24.
(1- r)' x
1 1. The characteristics equation is J (K) - 4J (K - l) + 4 J (K - 2) : 0 is
(A) (B) a2
o2 -4o-4_0 -4a+4=0
(C) a2 +4=g (D) o2
-4=O
12. The solution of S(rK) + 5.S(( - 1) = 0; S(0) = 6 is
(A) 6(-5)' (B) s(6)'
(c) 6(s), @) sloY-t 25. Find the complements, if they exists, of the elements a, b, c of the lattice, whose Hasse diagram is
given below. Can the lattice be complemented?
13. The vertex with zero in-degree is called ,
(A) Sink (B) Source
(C) Terminal @) Out degree
14. A circuit ofa graph G is called circuit ifit includes each edge ofG exactly once.
(A) Hamiltonian @) Konisberg
(C) Closed @) Eulerian
o
15. A tree with 'n' vertices has edges.
(A) nCz
(B) nP:
26. Demonstrate the 'r' is a valid inference from the premises p ) e, q -+ r and p.
(C) n-l @) n!
27. DrawtheHassediagramrepresentingthepartialordering r-{@,b)ladivides b} on{1,2,3,4,
16. If a vertex 'v' ofa tree has no children it is called 6,8,12].
(A) Pendant vertex @) Non-terminal vertex
(C) Descendant (D) Root PART - C (5 x 12: 60 Marla)
Answer ALL Questions
17. A partially ordered set {L, <} in which every pair of elements has a least upper bound and a
greatest lower bound is 28.a.i Show that p -+ ^s
can be derived from the premises 1 p, q, 1 q v r, r -+ s using CP rule.
(A) Lattice (B) Join
(C) Boolean @) Complement ii. Prove by mathematical induction tfrut !+l+.....+-. 1- - = "n .
1.2 2.3 n(n+l) n+l
18. Idempotent laws are (oR)
(A) a*a=aanda.a:0 (B) a*a=0anda.a=a b. Show that the premises "one sfudent in this class knows how to write progftrms in JAVA" and
(C) a + a: a and a.a: a (D) a+a:0anda.a=0 "everyone who knows how to write programs in JAVA can get a high-paying job" imply the
conclusion "someone in this class can get a high-payingjob".
19. Every finite lattice is
(A) Bounded (B) Unbounded 29. a. Let.R-{(t,t),(r,:),(1,4),(2,2),(3,4),(4,1)}bearelationdefinedonA: {1,2,3,4}.Findthe
(C) Infinite lattice (D) Uncountable lattice transitive closure of R using Warshall's algorithm. Also find the reflexive and symmetric closure
ofR.
(oR)
Page 2 of4 16MF1{/t5N,L{302 Page 3 of ,l l6MFl-6/15N44302
