Total No. of Questions 18] [Total No. of Pages 02
M.Sc. DEGREE EXAMINATION, MAY 2018
First Year
COMPUTER SCIENCE
Discrete Mathematical Structures
Time 3 Hours Maximum Marks :70
SECTION A
Answer any three questions. x 15 45)
Q1) Quantify the following arguments into predicate form:
Some integers are divisible by 3.
ii) All real numbers are complex numbers.
iii) Every living thing is a plant or an animal.
iv) Everybody likes somebody.
Prove that p→q) ≡ are logically equivalent.
Q2) Let x∈ x 12} be the universal set and A B
11,12} and C are the subsets of . Find the sets
(ΑU UC) ii) (AU BUC) .
Q3) If R and S are equivalence relations on a set A. Prove that R I S is an
equivalence Relation.
Draw the Hasse diagram representing the positive divisors of 36.
Q4) In any group by proving the inverse of every element is unique.
Show that 1 1 1 b a,b G − − − ∀ ∈ .
Show that in Boolean algebra, 1 1 ac a b bc.
Q5) Show that the following graphs are isomorphic.
Show that the following graph contains Euler's circuit.
SECTION B
Answer any five of the following questions. x 4 20)
Q6) Obtain the principle of conjunctive normal form of ↔ .
Q7) Show that R →S can be drawn from the premises P→(Q P and Q.
Q8) Let x-2 and 3x for x Find g o f and f o h o g.
Q9) Prove that every subgroup of a cyclic group is cyclic.
Q10) Let U … A B 7}. Find A Δ
A B and B A.
Q11) Write about any four Boolean function.
Q12) State and explain about four color problem.
Q13) Determine the order of the graph G in the following cases:
G is cubic graph with 9 edges.
G is regular with 15 edges.
SECTION C
Answer all questions. x 1
Q14) Define rule of inference.
Q15) Define lattice.
Q16) What is recursive function?
Q17) Define sub group.
Q18) Define bipartite graph.