DISTANCE EDUCATION
M.Sc. Years Integrated) DEGREE EXAMINATION,
MAY 2017.
DISCRETE MATHEMATICS
Time Three hours Maximum 100 marks
SECTION A — 8 40 marks)
Answer any FIVE questions.
1. Write the following statement in symbolic form
If tigers have wings then the earth travels round
the sun.
Kannan can write the examinations if and only if he
pays the fees.
2. Construct the truth table for .
3. In the set of integers we define aRb iff a b is even Is R
is an equivalence relation?
4. If f x y and g y z and if gof is one-to-one then f
is one-to-one. Is g onto if gof is on-to?
5. Show that the set of all rationals Q except 1 with the
operation defined by a b a b is an
abelian group?
6. Let be a semigroup. Let be an algebraic
structure. If there exists an on to mapping f
such that for any f f f then show
that is a semi group?
Sub. Code
15
DE-732
2
Sp 1
7. Prove that the monoid homomorphism preserves the
property of invertibility?
8. Define regular graph. Prove that the sum of the degrees
of the points of a graph G is twice the number of edges in

SECTION B — × 15 60 marks)
Answer any FOUR questions.
9. Show that
P Q R
Determine whether Q P is a
tautology.
10. Given S and a relation R on S defined by
R show that R is not
transitive?
Let R denote a relation on the set of ordered pairs of
positive integers such that iff x yu
show that R is an equivalence relation?
11. Prove that composition of functions is associative.
Let f A B be a bijection. Hence show that
f B A is also a bijection and f
12. Prove that any two right co-sets of H in G are either
disjoint or identical.
13. Prove that the intersection of any two normal
subgroups of a group is normal subgroup.
prove that every subgroup of an abelian group is
normal.
DE-732
3
Sp 1
14. Define
Finite graph
Multi graph
Pseudo graph
Simple graph.
Draw all the sample graphs of one, two and three
vertices.
In any graph G prove that the number of vertices of
odd degree is even.
15. Prove that a graph is a tree iff it is minimally
connected.
Prove that a graph with vertices edges
and no circuit is connected?