Madurai Kamraj University (MKU) 2006 B.Sc Computer Science Mathematical Foundation I - Question Paper

(7 pages)
1727/MAA NOVEMBER 2006
MATHEMATICAL FOUNDATION – I

(For those who joined in July 2006)
Time: 3 hours Maximum: 10 marks
ans ALL ques..
PART A-(10×1=10 marks)

All ques. carry equal marks.
1. 2 sets A and B are stated to be disjoint if AnB = ————————.

(a) A (b) B
(c) f (d) None.

2. Let f: A ? B and g: B ? C be 2 one-one functions. Then gof is

(a) one-one
(b) onto
(c) one-one and onto
(d) neither one-one nor onto.

3. p ? (q? r) = ——————.

(a) ( p ? q) ?(q? r) (b) ( p ? q) ?(q? r)
(c) ( p ? q) ?(q?r) (d) ( p ? q) ?(q?r)

4. The conjunction of the statements p : it is raining, q : a triangle has 3 sides
is p? q : ——————.

(a) It is raining
(b) A triangle has 3 sides
(c) It is raining or a triangle has 3 sides
(d) It is raining and a triangle has 3 sides.

5. A square matrix A is stated to be singular if ¦A¦= ——————.

(a) 0 (b) 1
(c) two (d) none.

6. If A and B are nonsingular matrices of order n, then (AB)-1 = —————.

(a) A-1 B-1 (b) B-1A-1
(c) AB-1 (d) A-1B.


7. The degree of the isolated point of a graph is

(a) 0 (b) 1
(c) 2 (d) none.

8. If V is a cut-point of a connected graph G, then G-V is

(a) connected (b) disconnected
(c) regular (d) complete.

9. If a tree has 10 vertices, then number of edges is

(a) 10 (b) 2
(c) nine (d) 5.

10. Every Hamiltonian graph is

(a) 2-connected (b) Eulerian
(c) 5-connected (d) 3-connected.

PART B – (5×6=30 marks)
All ques. carry equal marks.

11. (a) if ? and s are equivalence relations described on a set S, prove that
?ns is an equivalence relation.
Or
(b) describe group and provide an example.

12. (a) Construct the truth table for p?(q ? r).
Or
(b) Verify whether (p?q)?p is a tautology.

13. (a) Show that the system of equations
x+2y+z=11
4x+6y+5z=8
2x+2y+3z=19
is inconsistent.
Or

two -3 1
(b) Show that the matrix A= 3 one 3
-5 two -4
Satisfies the formula A(A-I)(A+2I)=0.



14. (a) Prove that in any graph , the number of points of odd degree is even.
Or
(b) obtain the incidence matrix of the graph G provided below:




15. (a) If G is Hamiltonian then for every nonempty proper subset s of V(G), prove that
w( G-S)=|s| when w(H) denotes the number of components in any graph H.
Or
(b) Prove that every tree has a centre consisting of either 1 point or 2 adjacent point.

PART C-(5×12=60 MARKS)
All ques. carry equal marks.

16. (a) State and prove De Morgan’s laws in set theory.
Or
(b) Let G be a group. Prove that
(i) identity element of G is unique
(ii) for any a € G, the inverse of a is unique.

17. (a) Draw the parsing tree for the formula.
(((+P)?(q?q))?(+(p ? q)))
Or
(b) Prove that:
(i) +(p? q)?(p?q)?+(p?q)
(ii) +(p ? q)?(p?+q)?(+p?q)

18. (a) Fine the inverse of the matrix
one 0 2
A= three one -1 using elementary operations.
-2 one three
Or
(b). state and prove Cayley Hamilton theorem.
19. (a) Prove that the maximum number of lines among all p point graph with no triangles is [p2/4].
Or
(b) Prove that a line x of a connected graph G is a bridge if and only if x is not on any cycle of G.

20. (a) Prove that the subsequent statements are equivalent of r a connected graph G.
(i) G is Eulerian.
(ii) Every point of G has even degree.
(iii) The set of edges of G can be partitioned into cycles.
Or
(b). Let G be a (p,q) graph. Prove that the subsequent statements are equivalent:
(i) G is a tree.
(ii) Every 2 points of G are joined by a unique path.
(iii) G is connected and p=q+1.
(iv) G is acyclic and p=q+1.s

Earning:   Approval pending.