Periyar University 2006 B.Sc Mathematics DISCRETE - Question Paper
Sunday, 27 January 2013 02:55Web
B.Sc. DEGREE EXAMINATION, APRIIVMAY 2006.
Sixth Semester
Maths (CA)
DiscRETE MATHEMATICS
Time : 3 hours Maximum : 100 marks
PART A — (10 x two = 20 marks)
ans ALL ques..
1. Construct the truth table for (P -> Q) A (Q -> P).
2. Symbolize the expression "All the world loves a lover".
3. Let .T= {1,2,3,4} and R = {<1, 1>,<1, 4>,<4,1>, < 4, four >,< 2, two >, < 2, three >,< 3, two >,< 3, three >}. Write the matrix and sketch the graph.
4. Let J? and ^be 2 relations on a set of positive integers 7.
R = [
obtain R°RoR, RoSoR.
5. Define monoid homomorphism.
6. Define regular grammar.
7. Define sub-Boolean algebra.
8. Show that (*J *x\ *x\ *x\)@(x\ *x\ *x\ *xA)®
{x\ * x\ * X3 * X4 ) © (jcj * ^ * ^3 * ^4 ) = x\ * xj .
9. Define finite-state machine.
10. Define a nondeterministic finite automation.
PART B — (5 x four = 20 marks) ans ALL ques..
11. (a) find the principal conjunctive normal form
of the formula ^given by
C}P->R>A(Q£P).
Or
(b) Show that (PVQ)AC]PAC]PAQ)^>C]PAQ).
12. (a) describe injective and bijective mapping.
Or
(b) Represent the subsequent relations using graph. xRy A yRz A ZRX , xRy A yRy.
13. (a) describe situation sensitive and situation free
grammar.
Or
(b) L(G) = {anbncn\n>l }
G = ({S,B,C),{a,b,c),S,Q)
aB -> ab, bB -> bb, bC -> be, cC -> cc]
Write the derivation for the string a2 b2 c2.
14. (a) Mention the properties of lattices.
Or
(b) Write the subsequent Boolean expression in an equivalent sum-of-products canonical form in 3 variables x1, x2 and x3.
(i) xx*x2 (ii) xl@x2.
15. (a) Draw the transition diagram for serial adder.
Or (b) Define:
(i) Reducing finite state machine (ii) Finite state homomorphism.
PART C — (5 x 12 = 60 marks) ans ALL ques..
16. (a) Show that
(i) (Er)(/U) A &*)) => (3x)J\x) A {3x)&x)
(ii) M/Kx) -» &*)) A U)( &x) -> ftx))
=> UX/Kx) -> Mx))
Or
(b) Show that:
x{/\x) v #») => .r /W v (3;r)#»
17. (a) describe maximal compatibility block of a
relation.
Let the compatibility relation on a set
[xltx2, ,x6) be provided by the matrix.
x2 1
xs 1 1
x4 0 0 1
x5 0 0 one 1
JTg 1 0 1 0 1
JC, *2 *3 *4 X5
Draw the graph and obtain the maximal compatibility blocks of the relation.
Or
Ct>) LetA be a provided finite set and pi AT) its power set. Let c be the inclusion relation on the element of p(A). Draw Hasse diagrams of (p(A),c) for
(i) A = {a)
(ii) A = {a,b)
(iii) A = {a,b,c]
(iv) A = {a,6,c,d}.
18. (a) State and prove Euler's theorem.
Or
(b) discuss the translation of infix string to polish using an example.
19. (a) Use the Karnaugh map representation to obtain
a minimal sum-of-products expression of the subsequent
function.
f(a,b,c,d) = £(0,1, 2, 3,13,15).
Or
(b) discuss the representation of Boolean function using a cube and using Karnaugh map.
20. (a) Let M - {{a, b), {qo,qx,q2\,q0,S,{qi}) be a nondeterministic finite state acceptor where S is provided by:
S(q0,a) = {q0iqi} d(Qo,b) = {q2) ^(q0Ja) = (q0,g1) 6{qvb) = {q0}
S(q2,b)~{qx,q2}.
Construct an equivalent deterministic finite state acceptor.
Or
(b) Design a finite state acceptor that will accept the set of natural numbers x which are divisible by 3. Also draw the transition diagram of the machine
| Earning: Approval pending. |
