Jawaharlal Nehru Technological University Kakinada 2008 B.Tech Computer Science and Engineering mathematical foundations of computer sciences - Question Paper

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
( Common to Computer Science & Engineering, info Technology
and Computer Science & Systems Engineering)
Time: three hours Max Marks: 80
ans any 5 ques.
All ques. carry equal marks
? ? ? ? ?
1. (a) Show that the principal disjunctive normal form of the formula:
P ? ( ~ P ? (Q ? ( ~ Q ? R))) is: S( 1, 2, 3, 4, 5, 6, 7).
(b) Show that the principal conjunctive normal form of the formula:
(P ? (Q ? R)) ? ( ~ P ? ( ~ Q ? ~ R)) is ? ( 1, 2, 3, 4, 5, 6). [8+8]
2. indicates that the subsequent set of premises are inconsistent using indirect method of
proof:
P ? Q,Q ? R, ~ (P ? R), P ? R ? R. [16]
3. (a) Draw the Hasse diagram of: ( P(S), = ), where P(S) is power set of the set S
= {a, b, c}.
(b) How many relations are there on a set with ‘n’ elements? If a set A has ‘m’
elements and a set B has ‘n’ elements, how many relations are there from A
to B? If a set A = {1, 2}, determine all relations from A to A. [6+10]
4. (a) Prove that the intersection of 2 submonoids of a monoid is a monoid.
(b) Show that the function f from (N, +) to (N, *), where N is the set of all natural
numbers, de?ned by f(x) = 2x ?x ? N. [8+8]
5. (a) In how many di?erent orders can three men and three women be seated in a row of 6
seats if:
i. anyone may sit in any of the seats
ii. the ?rst and last seats must be ?lled by men
iii. men and women are seated alternatively
iv. all members of the identical sex seated in adjacent seats.
(b) How many six digit numbers are there with exactly 1 5? [8+8]
6. obtain a general expression for a solution to the recurrence relation
an - five an-1 + six an-2 = n(n-1) for n>=2. [16]
7. (a) If G is a non directed graph with 12 edges. Suppose that G has six vertices of
degree three and the rest have degree less than 3. Determine the minimum no of
vertices.
(b) If we know the degree of vertices of a non-directed graph G. Is it possible? to
determine the order and size of the G? discuss with example. [8+8]
8. (a) Write the rules for constructing Hamiltonian paths and cycles.
1 of 2Code No: 07A3BS04 Set No. 2
(b) Write the di?erence ranging from Hamiltonian graphs and Euler graphs. [8+8]

Earning:   Approval pending.