https://www.rgpvonline.

com

Total No. of Questions : 8] [1] [Total No. of Printed Pages : 4

Roll No ..................................

CS/CT/CO/CI/IT-302-CBGS
B.Tech., III Semester
Examination, June 2020
Choice Based Grading System (CBGS)
Discrete Structures
Time : Three Hours
Maximum Marks : 70
Note: i) Attempt any five questions.
{H$Ýht nm±M àíZm| H$mo hb H$s{OE&
ii) All questions carry equal marks.
g^r àíZm| Ho$ g_mZ A§H$ h¢&
iii) All parts of each question to be attempted at one place.
g^r àíZm| Ho$ g^r ^mJm| H$mo EH$ hr ñWmZ na hb H$s{OE&
iv) In case of any doubt or dispute the English version
question should be treated as final.
{H$gr ^r àH$ma Ho$ g§Xho AWdm {ddmX H$s pñW{V ‘| A§JO
o« r ^mfm
Ho$ àíZ H$mo A§{V‘ ‘mZm Om¶oJm&
1. a) If U is a universal set and its two subsets A and B, then
prove that ( A ∪ B )′ = A′ ∩ B′ 7
¶{X U EH$ universal set h¡ Am¡a BgHo$ Xmo g~goQ> A Am¡a B h¡ Vmo
gm{~V H$[a¶o- ( A ∪ B)′ = A′ ∩ B′
b) If A = {1, 4} , B = {4,5} , C = {5,7} , determine 7
¶{X A = {1, 4} , B = {4,5} , C = {5,7} , {ZYm©[aV H$[a¶o-
i) ( A × B) ∪ ( A × C )
ii) ( A × B) ∩ ( A × C )
CS/CT/CO/CI/IT-302-CBGS PTO

https://www.rgpvonline.com
 https://www.rgpvonline.com

[2]

2. a) Prove by mathematical induction- 7

‘¡W‘o{Q>³g B§S>³eZ go gm{~V H$[a¶o&
1 1 1 1 n
+ + + ... + =
1.3 3.5 5.7 ( 2n − 1)( 2n + 1) 2n + 1
b) Define Semi group. Prove that every sub group of a cyclic
group G is cyclic. 7
go[‘. (Semi) g‘wh (group) n[a^m{fV H$[a¶o& gm{~V H$a| {H$
M{H«$¶ (cyclic) g‘wh G Ho$ ha Cn (sub) MH«$s¶ (cyclic) h¢&
3. a) Show that the rule of hypothetical syllogism is valid. 7
{XImE± {H$ hm¶nmoWo{Q>H$ {g„mo{Og‘ H$m {Z¶‘ ‘mݶ h¡&
p→q
q→r
p→r
b) Prove that the proposition is a tautology. 7
gm{~V H$[aE {H$ àñVmd tautology h¡
( p ∨ ∼ q ) ∧ ( ∼ p∨ ∼ q ) ∨ q
4. a) Test the validity of argument : 7
VH©$ H$s d¡YVm H$m narjU H$[aE:
if it rains,Ram will be sick
It did not rain
∴ Ram was not sick
b) Prove that G and H are Isomorphic 7
gm{~V H$[a¶o G Am¡a H Bgmo‘moa{’$H$ (Isomorphic) h¡-
a
1 2
b
6 3 c
e
5 4 f H d
CS/CT/CO/CI/IT-302-CBGS Contd...
PTO

https://www.rgpvonline.com
 https://www.rgpvonline.com

[3]

5. a) Let L = {1, 2,3, 4,5} be the lattice shown below. Find all
sub lattices with three or more elements. 7
‘mZm {H$ L = {1, 2,3, 4,5} ZrMo lattice {XIm¶m J¶m h¡, VrZ Am¡a
A{YH$ VËd Ho$ gmW g^r Cn b¡{Q>gog (Lattices) H$mo {ZH$m{b¶o&
5

2 3 4

b) Define the followings with examples: 7

i) Multi graph ii) Isomorphic graph
iii) Eulerian graph
CXmhaUm| Ho$ gmW {ZåZ{b{IV H$mo n[a^m{fV H$[aE :
i) ‘ëQ>rJ«m’$ ii) Isomorphic J«m’$
iii) Eulerian J«m’$

6. a) Let A = {a, b, c, d } and P(A) its power set. Draw Hasse

diagram of ( P ( A ) ,⊆ ) . 7
‘mZm {H$ A = {a, b, c, d } Am¡a P(A) BgH$m nm°da goQ> h¡, Vmo
( P ( A ) ,⊆ ) H$m h¡e aoIm{MÌ ~ZmBE&
b) Determine the discrete numeric function corresponding

to the generating function A ( z ) =

(1 + z)
2
. 7
(1 + z ) 4
OZaoqQ>J ’§$³eZ go g§~{§ YV {S>g{H«$Q> g§»¶mË‘H$ ’§$³eZ {ZYm©[aV
H$[aE&

A ( z) =
(1 + z)
2

(1 + z ) 4
CS/CT/CO/CI/IT-302-CBGS PTO

https://www.rgpvonline.com
 https://www.rgpvonline.com

[4]

7. a) What is Graph coloring? Define chromatic number give

any one example to explain your answer. 7
J«m’$ H$b[a¨J ³¶m h¢? H«$mo‘{o Q>H$ Z§~a H$mo g‘PmBE& AnZo CÎma H$mo
g‘PmZo Ho$ {b¶o CXmhaU Xr{O¶o&
b) Solve the recurrence relation :
ar − 7 ar −1 + 10ar −2 = 0 given a0 = 0 and a1 = 6 . 7
recurrence relation H$mo hb H$[aE-
ar − 7 ar −1 + 10ar −2 = 0 given a0 = 0 and a1 = 6 .

8. a) Find the shortest path between a and z in the graph shown

below. 7
ZrMo {X¶o J¶o J«m’$ H$m emQ>}ñQ> nmW {ZH$m{b¶o a go z VH$ Ho$ ~rM
‘|
b 4 e

3 2
3 4
2 c
a z
6
2 2
3

d 4 f

b) Write short notes. 7

i) Posets
ii) Lattices
iii) Permutation and combination
g§{já {Q>ßn{U¶m± {b{I¶o&
i) nmogQo >² g
ii) b¡{Q>gg o
iii) na‘wQ>oeZ Ed§ H$m°på~ZoeZ

******
CS/CT/CO/CI/IT-302-CBGS PTO

https://www.rgpvonline.com