0
Discrete Mathematical Structures : Question Paper Jun 2014 - Computer Science Engg. (Semester 3) | Visveswaraya Technological University (VTU)

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 a0=1, a1=2, a2=3 and an=an-1 +an-2+an-3 for n≥3. Prove that an=≤3n for all positive integrs n.(6 marks) 4 (b) Find an explicit definition of the sequence defined by a1=7, an=2an-1+1 for n≥2.(7 marks) 4 (c) The Lucas number are defined recursively by L0=2, L1=1 and Ln=Ln-1+L-2 for n≥2. Evaluate L2 to L10.(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 R1 be a relation from A to B defined by R1={(1,x), (2,x), (3,z)} and R2 and R3 be relation from B and C, defined by R2={(w,5),(x,6)}, R3={(w,5),(w,6)}. Find R1⋅R3.(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: z23 → z26 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 z6 is no an integral domain.(7 marks)

0  upvotes

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More