Anna University Coimbatore 2011 B.E Computer Science and Engineering 080230017 - discrete mathematics - Question Paper
ANNA UNIVERSITY OF TECHNOLOGY, COIMBATORE B.E. / B.TECH. DEGREE EXAMINATIONS : NOV / DEC 2011
REGULATIONS : 2008 FIFTH SEMESTER : CSE 080230017 - DISCRETE MATHEMATICS Time: 3 Hours Max . Marks : 100
PART - A
(10 x 2 = 20 Marks )
ANSWER ALL QUESTIONS
1. Construct the truth table for (p v q )( p a q)
2. Show that the qV( pVq)V(pAq)statement is a tautology.
3. Symbolise the statement All men are giants
4. Define quantifiers
5. If A and B are finite sets show that n( A u B) = n( A) + n( B) - n( A n B)
6. Show that in any Boolean Algebra (a + b)(a'+ c) = ac + a'+ bc
7. Define a characteristic function of a set
8. State whether the function f(x) = 5x2 + 7 is injection, surjection or bijection on R, the set of real numbers.
9. Define a normal subgroup of a group.
10. If the minimum distance between two code words is 7, then find how many errors can be detected and how many errors can be corrected?
PART - B
( 5 x16 = 80 MARKS )
ANSWER ALL QUESTIONS
11a) (i) Find pdnf of P v ( P (Q v ( Q R))) without using truth table.
(ii) Use the indirert method to show that r 7q, r v s, s 7q, p q 7p.
1
(OR)
11 b) (i) Construct the truth table for ((p v q) a ((p r) a (q r))) r (ii) Using direct method prove (p q) r, p a s, q a t r
12a) (i) Prove that (3x) (P(x)aS(x)) , (Vx)(P(x) R(x)) (3x) (R(x)aS(x))
(ii) By indirect method, prove that (Vx) (P(x) v Q(x)) (Vx) (P(x) v (3x) Q(x).
(OR)
12b) (i) Prove that (3x) M(x) follows logically from the premises (Vx)(H(x) M(x)) and (3x) H(x).
(ii) Prove the following implication
Vx(P(x) Q(x) a Vx(Q(x) R(x) Vx(P(x) R(x)
13a) (i) If R is the relation on the set of positive integers such that (a, b) e R if and only if a2 + a is even, prove that R is an equivalence relation.
(ii) If {L,<} is a Lattice, then for any a,b,ce l prove that
a a (b v c) > (a a b) v (a a c)
(OR)
13b) (i) Define the relation P on {1,2,3,4} by P = {(a,b)/|a -b| = l}. Determine the adjacency matrix of P2 (ii) Simplify the Boolean expression ((x1 + x2) + (x1 + x3)) x1.x2
14a) (i) Let f:r r and g:r r where R is the set of real numbers, find f g and g f, if f (x) = x2 - 2 and g (x) = x+4 (ii) Show that the function f (x, y) == xy is a primitive recursive function.
(OR)
14b) (i) Show that f: R _ {3} R _ {1} given by f (x) =-is a bijection
x _ 3
(ii) Using characteristic function show that ( a u b) = a n b
15a) (i) If H is a subgroup of g such that x2 e H for every x e G prove that H is a normal subgroup of G
2 4
(ii) Find the minimum distance of the encoding function e = B2 B4 given by e(00) = 0000, e(10) = 0110, e(01) = 1011, e(11) = 1100
(OR)
15b) (i) If (G, ) is an abelian group then for all a, b e G, show that if (ab)n = aVbn.
(ii) Prove that a code can correct all combinations of k or fewer errors if and only if the minimum distance between any two code word is atleast 2k+1
end*****
3
|
Attachment: |
| Earning: Approval pending. |
