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² -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)ⁿ(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₀, F₁, F₂??.. 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₁ 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₁oR₂ and R₁oR₃.(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₁) and (B, R₂) be points. On A×B, define the relation R by (a,b)R(x,y) if aR₁x and bR₂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₅ is an integral domain.(4 marks)