## 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_{0}=1, a_{1}=2, a_{2}=3 and a_{n}=a_{n-1} +a_{n-2}+a_{n-3} for n≥3. Prove that a_{n}=≤3^{n} for all positive integrs n.(6 marks)
**4 (b)** Find an explicit definition of the sequence defined by a_{1}=7, a_{n}=2a_{n-1}+1 for n≥2.(7 marks)
**4 (c)** The Lucas number are defined recursively by L_{0}=2, L_{1}=1 and L_{n}=L_{n-1}+L_{-2} for n≥2. Evaluate L_{2} to L_{10}.(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_{1} be a relation from A to B defined by R_{1}={(1,x), (2,x), (3,z)} and R_{2} and R_{3} be relation from B and C, defined by R_{2}={(w,5),(x,6)}, R_{3}={(w,5),(w,6)}. Find R_{1}⋅R_{3}.(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_{2}^{3} → z_{2}^{6} 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_{6} is no an integral domain.(7 marks)