Total No. of Questions [Total No. of Pages 02
M.C.A. DEGREE EXAMINATION, MAY- 2018
First Year
DISCRETE MATHEMATICS
Time Hours Maximum Marks :70
SECTION A
Answer any three of the following questions. x 15 45)
Q1) Prove that, for any three propositions the compound proposition
p→q) p→r) is tautology.
Obtain principle disjunctive normal form of the following.
p→q)
Q2) Prove that 1 1 1 f g f − − − o o where f :Q→Q such that f 2x and
g :Q→Q such that x+2 are two functions.
On the set of integers, the relation R is defined by "aRb" if and only if
is even integer". Show that R is an equivalence relation.
Q3) Solve the following recurrence relations:

1 0 2 2 1 n
n n a a n a −
ii)
1 2 3 2 for 2 n n n a a a n − − −
Q4) A non-empty subset S of G is a sub group of iff for any pair of
elements b∈ S.
Let G be the set of all nonzero real numbers, for a*b show that
is Abelian group.
Q5) What is partial order and partial order set? Draw Hasse diagram for poset
where A is the power set of A.
SECTION B
Answer any five of the following questions. x 4 20)
Q6) Prove that the logical equivalence of p p→q) ≡ p
Q7) Show that ≡ ∀xP(x) ∧∀xQ(x) .
Q8) In how many ways can 4 mathematics books, 3 history books, 3 chemistry books
and 2 sociology books be arranged on the shelf so that all books of the same
subject are together?
Q9) What are the reflexive, symmetric and transitive relations?
Q10) Let x−2, 3x for x∈ R where R is set of real numbers.
Find gof, hof.
Q11) Show that the semi group and where E is the set of even integers are
isomorphic.
Q12) Solve the linear recurrence relation: a0 4an-1 5an-2 with a1 a2 6.
Q13) Let G be group and let c ∈ then show that:
ab=bc⇒b=c
ii) b-1a-1
SECTION C
Answer all of the following questions. x 1
Q14) Define monoid.
Q15)Define Lattice.
Q16) Define binary relation.
Q17) Define disjunctive normal form.
Q18) What is generating function.