Discrete Mathematical Structures - Jun 2014

Computer Science Engg. (Semester 3)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1 (a) For any three set A,B,C, prove that A∩(B∪C)=(A∩B)∪(A∩C).(6 marks) 1 (b) Among the integers from 1 to 200, find the number of integers that are:
i) not divisible by 5
ii) divisible by 2 or 5 or 9
iii) not divisible by 2 or 5 or 9(7 marks) 1 (c) A problem is given to four students A,B,C,D whose chances of solving it are 1/2, 1/3, 1/4, 1/5 respectively. Find the probability that the problem is solved.(7 marks) 2 (a) Define a tautology and contradiction. Prove that, for any propositions p,q,r, the compound proposition [(p→q) ∧ (q→r)] → (p→r) is a tautology.(6 marks) 2 (b) Define the dual of logical statement. Verify the principle of duality for the following logical equivalence: [¬ (p∧q)→ ¬ p∨(¬ p∨q)]⇔ ( ¬ p∨q)(7 marks) 2 (c) Define converse, inverse and contra-positive of a conditional with truth table. Write down the contra-positive of [p→(q→r)] with:
i) only one occurrence of the connective →
ii) no occurrence of the connective →(7 marks) 3 (a) Negate and simplify each of the following:
i) ∃x, [p(x)∨q(x)]
ii) ∀x, [p(x)∧ ¬ q(x)]
iii) ∀x, [p(x)→q(x)](6 marks) 3 (b) Establish the validity of the following argument:
[ ?egin {align} &forall x, [p(x)vee q(x)] \ &forall x, [ left { eg p(x)wedge q(x) ight } o r(x)] \ hline& herefore forall x, [ eg r(x) o p(x)] end{align} ](6 marks) 3 (c) Prove that every even integer n with 2≤n≤26 can be written as a sum of atmost three perfect squares.(7 marks) 4 (a) Let a₀=1, a₁=2, a₂=3 and a_n=a_n-1 +a_n-2+a_n-3 for n≥3. Prove that a_n=≤3ⁿ for all positive integrs n.(6 marks) 4 (b) Find an explicit definition of the sequence defined by a₁=7, a_n=2a_n-1+1 for n≥2.(7 marks) 4 (c) The Lucas number are defined recursively by L₀=2, L₁=1 and L_n=L_n-1+L_-2 for n≥2. Evaluate L₂ to L₁₀.(7 marks) 5 (a) Suppose A, B, C⊆Z X Y with A={(x,y)|y=5x-1}; B={(x,y)|y=6x}; C={(x,y)|3x-y=-7}. Find: [ i) Acap B \ ii) B cap C \ iii) overline{overline{A}cup overline{C}}\ iv) overline{B}cup overline{C} ](6 marks) 5 (b) Define stirling number of second kind. Find the number of ways of distributing four distinct objects among three identical containers with some containers possibly empty.(7 marks) 5 (c) If f:A→B, g:B→C, and h:C→D are three functions then prove that (h⋅g)⋅f=h⋅(g⋅f)(7 marks) 6 (a) Let A={1,2,3,4}, B={w,x,y,z} and C={5,6,7}. Also let R₁ be a relation from A to B defined by R₁={(1,x), (2,x), (3,z)} and R₂ and R₃ be relation from B and C, defined by R₂={(w,5),(x,6)}, R₃={(w,5),(w,6)}. Find R₁⋅R₃.(6 marks) 6 (b) Find the number of equivalence relation that can be defined on a finite set A with |A|=6(7 marks) 6 (c) For A={a,b,c,d,e}, the Hasse diagam for the poset (A,R) is as shown below.
i) Determine the relation matrix for R.
ii) Construct the diagraph for R (7 marks) 7 (a) Define subgroup of a group. Let G he a group and let J={x ∈ G|xy=yx for all y ∈ G}. Prove that J is a subgroup of G.(6 marks) 7 (b) State and prove Lagrange's theorem.(7 marks) 7 (c) The word C=1010110 is sent through a binary symmetric channel. If p=0.02 is the probability of incorrect receipt of a signal, find the probability that C is received as r=1011111. Determine the error pattern.(7 marks) 8 (a) The parity check matrix for an encoding function E: z₂³ → z₂⁶ given by [ H=?egin{bmatrix} 1&0 &1 &1 &0 &0 \1 &1 &0 &0 &1 &0 \1 &0 &1 &0 &0 &1 end{bmatrix} ] i) Determine the associated generator matrix
ii) Does this code correct all single errors in transmission?(6 marks) 8 (b) Prove that the set z with binary operations ⊕ and ⊙ defined by x⊕y=x+y-1; x⊙y=x+y-xy is a cumulative ring.(7 marks) 8 (c) Show that z₆ is no an integral domain.(7 marks)