AMIETE – CS (NEW SCHEME)   –   Code: AC65

 

Subject: DISCRETE STRUCTURES

Flowchart: Alternate Process: JUNE 2010Time: 3 Hours                                                                                                     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 the best alternative in the following:                                  (210)

       

             a.  Every cyclic group is

 

                  (A) Abelian                                          (B) Non Abelian group

                  (C) May or May not be abelian             (D) cannot say

 

             b. If a set has n elements then its power set has   

 

                  (A)  n! elements.                                  

                  (B)  2n elements.

                  (C)  n elements.                                   

                  (D) (n+1) elements.

 

             c.  The compound proposition  (pq) ↔ is  

 

                  (A) Contradiction                                 (B) Contingency

                  (C) Tautology                                       (D) All are not correct

 

             d.  Addition theorem of probability for Mutually Exclusive events A and B is     

 

                  (A) P(AB) = P(A) + P(B)               

                  (B) P(AB) = P(A) + P(B) –P(A∩B)

                  (C) P(A∩B) = P (A) + P (B)               

                  (D) P(A∩B) = P (A) +P(B) – P(AB)

 

             e.  A function f: A →B is said to be one-one if   

 

                  (A) If x1, x2 A → f (x1), f (x2) B and

                        If x1 = x2  f (x1) = f (x2)              

                  (B) If x1, x2 A→ f (x1), f (x2) B and

                        If  x1 ≠ x2  f (x1) = f (x2)

                  (C) If x1, x2 A→ f (x1), f (x2) B and

                         If x1 = x2  f (x1) ≠ f (x2)            

                  (D) If x1, x2 A  f(x1), f(x2) B and

                         If f(x1) = f(x2) then x1 = x2

 

             f.   An Abelian group G must satisfy 

 

                  (A) Associating Law                             (B) Commutative Law

                  (C) Inverse axiom                                 (D) Identity axiom.

 

             g. Let A = B = C = R, the set of real numbers. Consider f: A → B : g : B→  C and  f (a) = (2a+1), g (b) = b/3 then (f o g) (-2) is 

 

                  (A) 1/3                                                 (B) 0

                  (C) -1/3                                               (D) 2/3

 

             h.  The conditional compound statement p→ q has a truth value ‘F’ when                               

 

(A)  p is True and q is True                    (B) p is True and q is False                                   

                  (C) p is False and q is False                  (D) p is False and q is True.

 

             i.   In how many ways we can arrange the letters A, B, C, D, E, F, G, contain the string BCD.

 

                  (A) 7!                                                   (B) 7

                  (C) 5                                                    (D) 5!

 

             j.   If G is a finite Group and H is a subgroup of G then the Lagrange’s theorem slates

 

                  (A) o(H)/o(G)                                      (B) o(G)/o(H)

                  (C) o(H)= o(G)                                    (D)All are Incorrect

 


Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

 


  Q.2     a.   Thirty cars are assembled in a factory. The options available are a music system, an air conditioner and power windows. It is known that 15 of the cars have a music system, 8 have air conditioners and 6 have power windows. Further 3 have all options. Determine at least how many cars do not have any option at all.                                                                                                                           (8)

                  

             b.   Three students X, Y and Z write an examination. Their chances of passing are 1/2, 1/3 and 1/4 respectively. Find the probability that (i) all of them pass (ii) at least one of them passes.                         (8)

 

Q.3     a.   Check whether the compound proposition   

 [ P®(q ® r)] ®(p®q) ® (p® r) is a tautology or not.                                   (8)

            

b.      Prove the following for logical equivalences

      (p®q) Ù [q Ù(rq)]  (qp).                                                             (8)

            

 Q.4      a.   Show that the hypothesis “If you sent me an e-mail message, then I will finish writing the program.” “If you do not send me an e-mail message, then I will go to sleep early” and “if I go to sleep early, then t will wake up feeling refreshed” lead to the conclusion “ if I do not finish writing the program, then I will wake up feeling refreshed.                                                                                                          (8)

                   

             b.   Verify the validity of the argument “All men are Mortal.” “Sachin is a man.” Therefore “Sachin is Mortal.”                                                                                                                            (8)

       

   Q.5    a.   Prove by mathematical induction the following:

                    12 + 22 + 32 +……n2 = {n(n+1)(2n+1)}/6.                                                        (8)

                  

b.      Let P1, P2, ……Pn be propositions: Then prove that

      (P1P2….Pr)  (Pr+1  Pr+2 …..Pn)                                  (8)

            

  Q.6     a.   Define (i) Reflexive (ii) Symmetric (iii) Transitive properties of Relations with an example.               (8)

 

             b.   Define partial order and poset. If R is a relation on the set A = {1, 2, 3, 4} defined by x R y if x/y. Prove that (A, R) is a poset and draw its Hussey diagram.                                                                  (8)

 

 Q.7      a.   Define subgroup of a group G.

                   Prove the statement, If H is subgroup of G, then for all a, bH we have

                   ab-1H.                                                                                                             (8)

 

             b.   Prove that any two left (or right) cosets of a subgroup H of G are either disjoint or       identical.                                                                                                         (8)

                  

  Q.8     a.  If f: A→ B and g: B→C are Bijective function then (g o f)-1 = f-1 o g-1.                  (8)

 

             b.  Let A = B =C =R, the set of all real numbers. Consider the following functions f: A→B: g: B→C and f (a) = (2a+1):g (b) = b/3 verify (g o f)-1 =  f -1o g-1.                                                                                   (8)

            

 
  Q.9     a.   The generator matrix for an encoding function

                    E:  Z23 → Z26 is given by

(i)   Find the code words                                        

     assigned to 110 and 010

(ii)    Obtain the associated parity cheek matrix.

(iii) Hence decode the received words 110110.

                                                                                                                                                            (8)

                                     

 
 

             b.   Prove that the set z with binary operations   and     de  define by x y

                       = x+ y -1: x y = x+ y x y is a Ring.                                                                                                       (8)