Total No. of Questions 18] [Total No. of Pages 03
M.Sc. DEGREE EXAMINATIONS, MAY 2017
(First Year)
COMPUTER SCIENCE
Discrete Mathematical Structures
Time 3 Hours Maximum Marks 70
SECTION A
Answer any Three questions × 15 45)
Q1) Prove that, for any three propositions r the compound proposition
p p
is tautology
Show that R → S can be drawn from the premises P → → ¬R P and Q.
Q2) State and describe rules of inference.
Show that the statement " 2 irrational" by prove by contradiction.
Q3) Let A be a set and relation R on A is as Is
R
Reflexive
ii) Symmetric
iii) Transitive
If R and S are equivalence relations on a set A. Prove that R∩S is an equivalence
Relation
Q4) Prove that the intersection of any two subgroups of a group G is again subgroup
of G.
Show that in any Boolean algebra, ac a′b+bc.
Q5) Find the Adjacency matrix and Incidence matrix of the following graph
State and explain graph coloring problem.
SECTION B × 4 20)
Answer any five questions
Q6) Write the statement in symbolic form then negate statements.
"Some Drivers do not obey the speed limit"
Q7) Using truth table prove that P Q ≡
Q8) Let X and R be a relation defined as y)∈R if and only if x − y
is divisible by 3. Find the elements of relation of R.
Q9) If A and B are any two sets, then − Φ.
Q10) In a lattice state and prove the laws idempotent, commutative.
Q11) Prove that the intersection of any two subgroups of a group G is again in subgroup of
G.
Q12) Check whether the graphs G and H are Isomorphic or not
Q13) Explain about Chromatic number with example.
SECTION C
Answer all questions. × 1
Q14) Define clause form.
Q15) What is Hasse diagram?
Q16) Define homomorphism.
Q17) Define cyclic graph
Q18)Define Eulerian path