CS-07    DISCRETE MATHEMATICS  JUNE 1998
 

Time: 3 Hours

Max. Marks: 75

Note:  Question no. 1 is compulsory.  Answer any three from the rest

1. . In about one short paragraph, explain the meaning of the following words or phrase :
    (i)   Tautology
    (ii)   Automatic proving of theorems
    (iii)  Predicates
    (iv)   Adjacency matrix of a graph
    (v)   Partition of a set
    (vi)  i-v fuzzy set
2. (a). Prove that if R be an equivalence relation in a set A, then R-1 is also an equivalence relation in A.
  (b). If A = {14,  15}, B = {16, 17} and C = {17, 18} find {A x B} U {B x C}.
3.   What are chains ?  Outline the proof of the theorem that every chain is a distributive lattice.
4. (a). What is a bipartite graph ?  What is a complete bipartite graph ?  Illustrate with an example of each.
  (b). State Cayley's theorem regarding spanning trees. How many spanning trees will be there for the following graph :
   
5.   Define and explain with examples the concept of a finite state machine. What are transition diagrams ?  Draw the transition diagram of a serial binary adder.
6. (a). Define and illustrate with examples, the meaning of membership function in a fuzzy set. Draw a diagram to illustrate what the  membership function of a 'crisp' set would look
like ?
  (b). If x = {51, 52, 53, 54}
    then what is the value of A U B ?