Discrete Structure and Graph theory Sessional-1 Paper

Roll No………………..     

 VISION INSTITUTE OF TECHNOLOGY, ALIGARH  

Session 2015-16         B .Tech. 2^nd year (3^rdSEM) Internal Sessional-1   

Sub-DS&GT(NCS-302)                                              Branch-CS   Max.Mark-50                                                   Max.Time-2 hrs

                                   




                                          Section-A

QNo-1 Attempt any two questions from the following: (2x10=20)

a)      What is Relation? Explain properties of Relation with example. 

b)      Let R={(1,2),(2,3),(3,1)} and A={1,2,3},Find the reflexive, symmetric  And transitive closure of R. 

c)        Let R={(1,2),(3,4),(2,2)} and S={(4,2),(2,5),(3,1),(1,3)} find ROS,SOR,  RO (SOR), (ROS) OR, ROR, SOS, and ROROR.

                                          Section-B

QNo-2 Attempt any three questions from the following:  (3X5=15)

a)      If A, B, C be sets, then prove the following.

A-(B È C) = (A-B) Ç(A-C)

b)      State and prove Demorgan’s laws.

(I). (AÈB)’=A’ÇB’ (ii).  (AÇB)’=A’ÈB’

c)       For any set A and B, prove that  P (AÇB) = P (A) ÇP (B)

d)      If A, B and C are sets then

(I). A× (BÈC) = (A×B) È(A×C) (ii). A× (BÇC) = (A×B) Ç(A×C)

                                          Section-C

QNo-3 Attempt any three questions from the following:  (3X5=15)

a)      What is Symmetric difference of Sets? If A= {1, 2, 3, 4, 5} and

 B= {4, 5, 6, 7, 8} then find the following-

(I). AÈB    (ii). BÈC (iii). A-B (IV). B-A

b)      Let R be the relation on set A = {a, b, c, d} and  R= {(a, b), (b, c), (d, c), (d, a), (a, d), (d, d)}. Determine Reflexive, Symmetric and Transitive Closure of R.

c)       Let A= {1,2,3} and B= {p, q, r} and let R={(1,p),(1,r),(2,q),(3,q)}

        And S= {(p, y), (q, x), (r, z)} Compute ROS.

d)      Prove that AÇ(B-C)A-(BÇC)