# Shivaji University 2005 B.E Computer Science DMS - Question Paper

Sunday, 19 May 2013 05:00Web

Y-308

SECOND YEAR OF COMPUTER SCIENCE AND ENGINEERING (PART-

**1)**EXAMINATION, 2005

SHIVAJI UNIVERSITY, KOLHAPUR

DiscRETE MATHEMATICAL STRUCTURE

Day and Date: Wednesday, 30-05-2005 Total

**Marks:**100

**Time:**3.00p.m. To 6.00p.m.

Instructions:

**1)**Attempt any 3 ques. from every part.

**2)**Figures to right indicate full marks.

**SECTION-1**

**Q.1**

**a)**describe atomic statement. provide examples.[Marks 4]

**b)**What is connectivity? describe various basic connectives.[Marks 6]

**c)**describe and provide the truth table for the subsequent.[Marks 6=2*3]

**1.**Bidirectional

**2.**Conjunction

**3.**Conditional

**Q.2**

**a)**provide principle conjunctive disjunctive normal forms.[Marks 8=4*2]

**1)**(P AND Q) OR (~P AND R) OR (Q AND R)

**2)**P OR (~P IMPLIES (Q OR (~ Q IMPLIES R)) )

**b)**describe a void relation in set

**X.**provided set S = {1,2,3,……….10} and relation R on S where R={(x, y) | x + y=10}.Give the properties of R.[Marks 10]

**Q.3**

**a)**indicates the subsequent implications:[Marks 8=4*2]

**1)**(P IMPLIES Q) IMPLIES Q = P OR Q

**2)**((P OR ~P) IMPLIES Q) IMPLIES ((P OR ~P) IMPLIES R)=(Q IMPLIES R)

**b)**Draw the Hasse diagram of the subsequent sets under the partial ordering relation ’divides’.[Marks 8]

**1)**{1, 2, 3, 6, 12}

**2)**{3, 9, 27, 54}

**Q.4**

**a)**what is monoid? describe the subsequent with respect to monoids.[Marks 8=2*4]

**1.**Homomorphism

**2.**Isomorphism

**3.**Monomorphism

**b)**What is function? provide various kinds of functions with suitable example.[Marks 8]

**Q.5**Write a short notes on:[Marks 18=6*3]

**1)**Partitions and covering of set

**2)**POSET and Hasse diagram

**3)**Normal and principal normal forms

**SECTION-2**

**Q.6**describe the following:[ Marks 8=2*4]

**1)**Lattice

**2)**Sub-Boolean algebra

**3)**Lattice homomorphism

**4)**Complemented lattices

**b)**define the list structure representation of a graph for storage with suitable example.[Marks 8]

**Q.7**

**a)**discuss the inorder traversal algorithm for the tree structur

**e.**[Marks 8]

**b)**For the Boolean function F=XYZ+XYZ+XYZ provide the subsequent representations:[Marks 8=2*4]

**1.**Circuit diagram

**2.**The table

**3.**Truth table

**4.**K-map

**Q.8**

**a)**derives the reverse polish expression for the subsequent expressions: :[ Marks 8=4*2]

**1)**a + (b/

**c)***d

**2)**(a +

**b)**(c + d/

**e)*** f

**b)**What is diagraph? describe the following:[Marks 8]

**1.**asymmetric diagraph

**2.**converse of a diagraph

**3.**reflexive diagraph

**Q.9**

**a)**describe the subsequent w.r.t groups:[Marks 8=2*4]

**1.**Order

**2.**Identity

**3.**Abelian

**4.**Degree

**b)**Let I be the set of integers. Prove that the algebraic system (I, +)is abelian group.[Marks 8]

Q.10.Write a short notes on:[Marks 18=6*3]

**1.**PERT

**2.**Generation of fault matrix

Earning: Approval pending. |