Code: C-10                                                                          Subject: DISCRETE STRUCTURES

Time: 3 Hours                                                               June 2006                                       Max. Marks: 100

 

NOTE: There are 9 Questions in all.

·      Question 1 is compulsory and carries 20 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.

·      Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.

·      Any required data not explicitly given, may be suitably assumed and stated.

 

 

Q.1       Choose the correct or best alternative in the following:                                         (2x10)

       

a.       In propositional logic which one of the following is equivalent to pq

 

                   (A)                                           (B)  

(C)                                               (D) 

       

b.      Which of the following statement is true:

 

(A)    Every graph is not its own sub graph.                                                                        

(B)    The terminal vertex of a graph are of degree two.

(C)    A tree with n vertices has n edges.                                                                            

(D)    A single vertex in graph G is a sub graph of G.

            

c.       Pigeonhole principle states that AB and  then:                          

 

(A)    f is not onto                                  (B)  f is not one-one

(C) f is neither one-one nor onto          (D)  f may be one-one

 

             d.   The probability that top and bottom cards of a randomly shuffled deck are both aces is:

 

(A)                                   (B)

(C)                                  (D)    

 

             e.   The number of distinct relations on a set of 3 elements is:

                  

(A)     8                                                  (B)  9                     

(C)  18                                                (D)  512

 

             f.    A self complemented, distributive lattice is called

 

(A)     Boolean Algebra                          (B)  Modular lattice

(C)  Complete lattice                           (D)  Self dual lattice

 

 

 

 

             g.   How many 5-cards consists only of hearts?

 

(A)     1127                                            (B)  1287

(C)  1487                                            (D)  1687

 

             h.   The number of diagonals that can be drawn by joining the vertices of an octagon is:

 

(A)    28                                                (B) 48

(C) 20                                                 (D) 24

 

             i.    A graph in which all nodes are of equal degrees is known as:

 

(A)   Multigraph                                    (B) Regular graph

(C) Complete lattice                            (D) non regular graph

 

             j.    Which of the following set is null set?

 

(A)                                                (B)  

(C)                                                (D)  

 

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 

  Q.2     a.   Simplify the Boolean function:

                                                                                    (8)

 

             b.   Is the following argument valid?  If valid, construct a formal proof, if not explain why. 

                   “If wages increases, then there will be inflation.  The cost of living will not increase if there is no inflation.  Wages will increase.  Therefore, the cost of living will increase.

                   (Let p =  wages increase, q = inflation, r = cost of living will increase)                  (8)

 

  Q.3     a.   A speaks truth in 80% of the cases and B speaks truth in 60% of the cases.  Find the probability of the cases of which they are likely to contradict each other in stating the same fact.                              (8)       

 

             b.   Let  and  is defined as  is a function.  If so find that whether it is one to one or bijection?    (8)                                                             

 

  Q.4     a.   Prove by induction

                   1.1! + 2.2! + …….+n.n! = (n+1)! – 1                                                               (8)

 

             b.   In the word ‘MANORAMA’

                   (i)        Find the number of permutations formed taking all letters.

(ii)                Out of these the number of permutations with all A’s together.

(iii)               Find the number of permutations which start with A and end with M.                      (8)

 

  Q.5     a.   Prove that a graph G is a tree iff G has no cycles and .                      (8)

                                                                             

             b.   If A and B are two subsets of a universal set then prove that

                                                                                                                   (8)

 

  Q.6     a.   A man has four friends.  In how many ways can he invite one or more friends to tea party?              (8)

 

             b.   If R is a relation  defined by  iff a + d = b + c, show that R is an equivalence relation.                                                                (8)

 

  Q.7     a.   Minimize the Boolean expression (by algebraic method)

                    and then draw the circuit diagram using only NAND gate.                 (8)   

 

             b.   Design an automaton which accepts only even numbers of 0s and even number of 1’s.                    (8)

       

  Q.8     a.   Consider the context free grammar

                  

                   (i)    Show how the string aa + a* can be generated by this grammar.

                   (ii)   Construct a parse tree for this string.

                   (iii)   What language is generated by this grammar.                                              (8)          

 

             b.   For any relation R in a set A, we can define the inverse relation  by  iff .  Prove that

(i)                  As a subset of A x A, =.

(ii)                R is symmetric iff R =  .                                                      (8)

 

  Q.9     a.   Write Prim’s Algorithm.                                                                                     (6)

 

             b.   Draw a diagraph for each of the following relation

                   (i)   Let  and let

                   (ii)  Let  and Let , wherever y is divisible by x.

                   (iii) Determine which of the relations are reflexive, which are transitive, which are symmetric and which are anti symmetric.                                           (4, 4, 2)