Bhavnagar University 2008 B.Sc Computer Science MATHEMATICAL FOUNDATIONS OF - Question Paper

M.Sc. (Computer Science) DEGREE EXAMINATION, MAY 2008.
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
(2007 onwards)
Time : 3 hours Maximum : 100 marks
part A — (10 ? three = 30 marks)
ans ALL the ques..
1. Verify whether is a tautology.
2. Symbolize the expression ‘‘All the world loves a lover’’.
3. Define a power set and provide an example.
4. Show that .
5. Explain Hashing function.
6. Show that the functions and for are inverse of every other.
7. Define homomorphism of semigroups and monoids and provide examples.
8. Define a simple graph, null graph and a weighted graph.
9. Define a field and provide an example.
10. Define a terminal node of a tree and level of any node and provide an example.
part B — (4 ? 10 = 40 marks)
ans any 4 ques..
11. Obtain the principal disjunctive normal form of .
12. Explain relation matrix and the graph of a relation.
13. Define composition of relation and state and prove the associative legal regulations for composition of relations?
14. Define a sub group and prove that a non empty subset S of a group G will be a subgroup of G if and only if , whenever .
15. Let g be a homomorphism from a group to a group and k be the kernel of g and be the image set of g in H. Then is isomorphic to . Prove.
16. Define a path matrix (reachability matrix) with an example and write down the properties of a path matrix.
part C — (2 ? 15 = 30 marks)
ans any 2 ques..
17. (a) Write every of the subsequent in symbolic form. (Assume that the universe consists of literally every thing).
(i) All men are giants
(ii) No men are giants
(iii) Some men are giants
(iv) Some men are not giants. (8)
(b) Prove that the relation ‘‘congruence modulo m’’ over the set of positive integers in an equivalence relation. (7)
18. (a) State and prove Lagrange’s theorem. (8)
(b) Using characteristic function prove that
. (7)
19. (a) Explain the subsequent with examples :
(i) Simple path
(ii) Cycle
(iii) Strong component
(iv) Binary tree. (8)
(b) Define a subring with an example and show that the ring of even integers is a subring of the ring of integers. (7)

Earning:   Approval pending.