## Discrete Mathematical Structures - Dec 2012

### 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 set A, B, C, D prove by using the laws that

(A∩B)∪(A∩B∩C∩D) ∪(A∩B)=B(6 marks)
**1 (b)** If S. T⊆U. Prove that S and T are disjoint if and only if S∪T=SΔT.(4 marks)
**1 (c)** In a survey of 120 passengers, an airline found that 48 preferred ice cream with their meals, 78 preferred fruits and 66 preferred coffee. In addition, 36 preferred any given pair of these and 24 passengers preferred them all. If two passenger are selected at random from the survey sample of 120, what is the probability that

i) they both preferred only coffee with their meals

ii) they both preferred exactly two of three offerings.
(6 marks)
**1 (d)** A student visits a sport club everyday from Monday to Friday after school hours and plays on of the three games: Cricket, Tennis and Football. In how many ways can he play each of the three games at least once during a week (from Monday to Friday)?(4 marks)
**2 (a)** Define Tautology. Prove that, for any proposition p,q,r the compound proposition [(p→q)∧(q→r)] → (p→q) is tautology using truth table.(6 marks)
**2 (b)** Prove that following logical equivalence without using truth table

[ (p o q)wedge [qwedge (rvee
eg q)]Leftrightarrow
eg (qvee p) ](4 marks)
**2 (c)** Define the dual of a logical statement. Write down the dual of

[ [(pvee T_0)wedge (qvee F_0)]vee [(rwedge s)wedge T_0] ](4 marks)
**2 (d)** Simplify the following switching network. [Refer Fig.Q2(d)]
(6 marks)
**3 (a)** [ If p(x): xge 0, q(x): x^2ge 0, r(x):x^2-3x-4=0, s(x):x^2-3>0, ] find the truth values of the following:

[ i) exists x[p(x)wedge q(x)] \ ii) forall x[p(x) o q(x)] \ iii) forall x [q(x) o s(x)] \ iv) forall x [r(x)vee s(x)] \ v) exists x,[p(x)wedge r(x)] \ vi) forall x, [r(x) o p(x)] ](6 marks)
**3 (b)** Negative and simplify each of the following:

[ i) forall x, [p(x)wedge
eg q(x)] \ ii) exists x, [ left { p(x)vee q(x)
ight } o r(x)] ](4 marks)
**3 (c)** 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 (d)** Given R(x,y): x+y is even where the variables x and y represent integers write down the following in words:

i) ∀x, ∃y p(x,y)

ii) ∃x, ∀y p(x,y)(4 marks)
**4 (a)** Prove than 4n<(n^{2} -7), for all integers n≥6.(6 marks)
**4 (b)** Obtain a recursive definition for the sequence {a_{n}} in each of the following:

i) a_{n}=5n

ii) a_{n}=2-(-1)^{n}(4 marks)
**4 (c)** Prove that every positive integers n≥24 can be written as a sum of 5's and/or 7's.(6 marks)
**4 (d)** IF F_{0}, F_{1}, F_{2}??.. Are Fibonacci numbers, prove that [ sum^{n}_{i=0}F^2_1=F_n imes f_{n-1} ] for all positive integers n.(4 marks)
**5 (a)** Prove that a function f:A→B is invertible if and only if it is one-to-one and onto.(6 marks)
**5 (b)** Define Stirling number of second kind and evaluate S(8,6)(4 marks)
**5 (c)** Let f, g, h be functions from z to z define by f(x)=x-1, g(x)=3x, [ h(x)=left{egin{matrix}0 &if x is even \1 &if x is odd end{matrix}
ight. ]

Determine (f o (g o h)) (x) and ((f o g) o h)(x) and verify that f o (g o h)=(f o g)o h.(6 marks)
**5 (d)** Show that if any (n+1) numbers from 1 to 2n are chosen, then of them will have their sum equal to (2n+1).(4 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}oR_{2} and R_{1}oR_{3}.(6 marks)
**6 (b)** Let A={1,2,3,4,5,6,7,8,9,10,11,12}. On this set define the relation R by (x,y)∈ R if and only if (x-y) is a multiple of 5. Verify that R is an equivalence relation.(4 marks)
**6 (c)** Let (A, R_{1}) and (B, R_{2}) be points. On A×B, define the relation R by (a,b)R(x,y) if aR_{1}x and bR_{2}y. Prove that R is partial order.

(6 marks)
**6 (d)** Consider the Hasse diagram of a poset (A, R) given in Fig.Q6(c) below.

if B={c,d,e}

i) all upper bounds if B

ii) all lower bounds of B

iii) the least upper bound of B

iv) all greatest lower bound of B.(4 marks)
**7 (a)** Define subgroup of a group, Prove that H is a subgroup of a group G, if and only if, for all a,b ∈ H, ab ∈ H and ∀ a ∈ H, a^{-1}∈H.(6 marks)
**7 (b)** What is group homomorphism and group isomorphism? Give example for each.(4 marks)
**7 (c)** State and prove Lagrange's theorem.(6 marks)
**7 (d)** A binary symmetric channel has probability P=0.05 of incorrect transmission. If the word C=011011101 is transmitted. What is the probability that i) single error occurs ii) a double error occurs iii) three errors occurs no two of them consecutive?(4 marks)
**8 (a)** Prove that the set Z with binary operation ⊕ and &# 8857; defined by x⊕y=x+y-1, x⊙=x+y-xy is commutative ring with unity,(6 marks)
**8 (b)** Explain briefly the encoding of a message.(4 marks)
**8 (c)** The generator matrix for an encoding function, [ E:Z^3_2 o Z^6_2 ] is given by [ G=egin{bmatrix}1 &0 &0 &1 &1 &0 \0 &1 &0 &0 &1 &1 \ 0&0 &1 &1 &0 &1 end{bmatrix} ]

i) Find the code words assigned to 110 and 010

ii) Obtain the associated parity-check matrix.

iii) Hence decode the received words: 110110, 111101.(6 marks)
**8 (d)** Show that Z_{5} is an integral domain.(4 marks)