Discrete Mathematical Structures - Jun 2013

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) Define a set proper subset and power set, with an example for each.(6 marks) 1 (b) A survey of 500 television viewers of a sports channel produced the following information: 285 watch cricket, 195 watch hockey, 115 watch football, 45 watch cricket and football, 70 watch cricket and hockey, 50 watch hokey and football and 50 do any of the three kinds of games.
i) How many viewers in the survay watch all three games?
ii) How many watch exactly one of the sports?(7 marks) 1 (c) The probability that a contractor will get a plumbing contract is 2/3 and the probability that he will not get an electric contract is 5/9. If the probability of getting at least one contract is 4/5. What is the probability that he will get both the contracts?(7 marks) 2 (a) Define a tautology and contradiction. Prove that the proposition [(p→r) ∧ (q→r)] → (p∨q) → r] is a tautology.(6 marks) 2 (b) Prove the following logical equivalences using laws of logic
i) [(∼p∨∼q) → (p∧q∧r)] ⇔ p∧q
ii) p→ (q→r)⇔(p∧q)→r.(7 marks) 2 (c) Define converse, inverse and countrapositive of a conditional with truth table. Also state the converse, inverse and contrapositive of the following statement.
"If a triangle is not isosceles, then it is not equilateral".(7 marks) 3 (a) Write down the following proposition in symbolic form find its negation:
"All integers are rational numbers and some rational numbers are not integers".(6 marks) 3 (b) Show that the following argument is valid. NO engineering student of first or second semester studies logic
<u> Anil is an engineering student who studies logic </u>
Therefore Anil is not in second semester.(7 marks) 3 (c) Give i) direct proof ii) an indirect proof iii) proof by contradiction for the following statement:
"If n is an odd integer, then n + g is an even integer".(7 marks) 4 (a) State the induction principle. Prove the following result by mathematical induction: "For every positive integer n, 5 divides n⁵-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) If L₀, L₁, L₂??. Are Lucas numbers, prove that
[ L_n=left [ dfrac {1+sqrt{5}}{2} ight ]^n + left [ dfrac {1-sqrt{5}}{2} ight ]^n ](7 marks) 5 (a) For any non-empty A, B, C prove the following:
i) (A∩B)×C=(A×C)∩(B×C)
ii) A×(B-C)=(A×B)-(A×B).(6 marks) 5 (b) Define a binary relation. Let A={1,2,3,4,6} and R a relation on A defined by a^Rb if and only if a is a multiple of b. Represent R as a set ordered pairs. Draw the digraph of R. Write the matrix of R.(7 marks) 5 (c) Define an equivalence relation. Let N be the set of all natural numbers, On N×N, the relation R is defined as (a,b)^R (c,d) if and only if a+b=d+c, show that R is an equivalence relation. Find the equivalence class of the element (2,5).(7 marks) 6 (a) Let f:z→z be defined by f(a)=a+1 for a∈z. Show that f is a bijection.(6 marks) 6 (b) Find the number of ways of distributing four district objects among three identical containers with some containers (s) possibly empty.(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 transmissions?(6 marks) 8 (b) For the following encoding function, find the minimum distance between the code words. Indicate the error-detecting and error-correcting capabilities of each code.
E:z₂³ → z₂⁶ defined by
E(0 0 0)=000111
E(0 0 1)=001001
E(0 1 0)=010010
E(0 1 1)=011100
E(1 0 0)=100100
E(1 0 1)=101010
E(1 1 0)=110001
E(1 1 1)=111000(7 marks) 8 (c) Prove that the set z with binary operation ⊕ and ⊙ defined by x⊕y=x+y-1, x⊙y=x+y-xy is commutative ring.(7 marks)