SAMPLE QUESTION PAPER DISCRETE MATHS
|
|
Note: Attempt
All Questions. All questions carry equal marks.
Question 1 Attempt any four parts of the
following: [5
X 4 = 20]
(a) Show that 1 + 1 +
……………+ 1 =
n by induction. [5]
1.2
2.3 n(n+1)
n+1
(b) What do you mean by
Venn diagram? In a class 50 students, 28 play Cricket and 36 play hockey. Use
Venn diagram to find: [1+2+2]
(i)
how many play both the games?
(ii) how many play only
cricket?
(c) If R-1
and S-1 are the inverse of the relations R and S respectively, then
(RoS)-1
= S-1oR-1 or (SoR)-1=R-1oS-1 [5]
(d) Let X = {1, 2, 3,
4} and R = {<x, y> such that x>y} [2+2+1]
(i) Give ordered pairs
of R.
(ii) Draw graph of R.
(iii) Give the relation
matrix of R.
(e) Let A be the set of
all integers and a relation R defined as
R={(x, y) : x≡y(mod
m)}, m divide x – y, where m is a positive integer. Prove that R is an
equivalence relation. [5]
(f) If f: A → B and g : B → C be one-to-one
onto functions then gof is also one-to-one onto and (gof)-1= f-1og-1
. [5]
Question 2 Attempt any four parts of the
following: [5 X 4 = 20]
(a)
If R is a ring such that a2 = a
for all a Є R, prove that
(i)
a + a = 0 for all a Є R i.e., each element
of R is its own additive inverse.
(ii)
a + b = 0 a = b
a + b = 0 a = b
(iii)
R is a commutative ring.
[1.5+1.5+2]
(b) If G is
a group of even order, show that there exists an element a other than e such
that a2 = e. [5]
(c) Prove that the set {0, 1, 2, 3, 4, 5} is a
finite abelian group under addition modulo 6. What will happen if the set is
{1, 2, 3, 4, 5}? [3+2]
(d) State
and prove the Lagrange’s theorem. [5]
(e) If Zn
denotes the set of integers {0, 1, 2,………….., n-1} and * be binary operation on
Z such that a * b = the remainder of ab divided by n. [2+3]
(i)
Construct the table
for the operation * for n = 4 and
(ii)
Show
that (Zn, *) is a semi groups for any n.
(f) Show
that the set N of natural numbers is a semigroup under the operation x * y =
max (x, y). Is it a monoid? [3+2]
Question 3
Attempt any four parts of the
following: [5
X 4 = 20]
(a)
Hasse diagram of a poset (S, ≤) is given
below. If A = {2, 3, 4} is a subset of S, find upper bound, lower bound,
supremum and infimum of A. [1.5+1.5+1+1]
(b)
Draw the simplified circuit of the Boolean
expression a*b*c + a*b’*c + a’*b’*c and test the equivalence of two circuits. [3+2]
(c)
Prove that if a and b are elements in
bounded, distributive lattice and if a has a complement a’ then a v (a’ ^ b) = a v b and a ^ (a’ v b) = a ^ b.
[5]
(d)
Prove that every lattice in which ( a ^ b) v (b
^ c) v (c ^ a) =(a v b) ^ (b v c)
^ (c v a) holds for all a, b € L, is
modular. [5]
(e)
If (L, ^, v) is distributive complemented
lattice, then Demorgon’s laws (a v
b)’ = a’ ^ b’ and (a ^ b)’ = a’ v b’ hold for all a, b Є L. [5]
(f)
Express the following expression in DNF in
the smallest possible number of variable (x + y) (x + y’) (x’ + z). Also find
DNF in the variables x, y, z.
[3+2]
Question 4 Attempt
any
two parts of the following: [10 X
2 = 20]
(a)
(i) Prove the validity of the following
argument using truth table as well as without truth table: [2+3]
“If the market is free then
there is no inflation. If there is no inflation then there are price controls.
Since there are price controls therefore, the market is free”.
(ii)
Express the
statement (~(p v q)) v ((~p) ^ q) in simplest possible
form. [2.5]
(iii) Convert the expression y=ab +ac’ +bc into
standard SOP form. [2.5]
(b)
(i) Check the validity of the arguments using
rule of inference:
“If
there was a ball game then travelling was difficult. If they
arrived
on time then travelling was not difficult. They arrived
on time.
Therefore there was no ball game”. [5]
(ii)
Show that { [(p v q) r] ^
(~p)} (q r) is a tautology without using truth
table. [5]
Show that { [(p v q) r] ^
(~p)} (q r) is a tautology without using truth
table. [5]
(c)
Let A = {1, 2, 4, 8} & let ≤ be the
partial order of divisibility on A. Let A’ = {0, 1, 2, 3} and ≤’ be the usual
relation “less than or equal to” on integers. Show that (A, ≤) and (A’, ≤’) are
isomorphic posets.
[10]
Question
5 Attempt
any
two parts of the following: [10 X
2 = 20]
(a)
Solve the following recurrence relation ar
– 5ar-1 + 6ar-2 = 2r + r. [10]
(b)
Solve the following recurrence relation
using generating function:
Ln =Ln-1
+ n, (n≥2), L0 = 1, L1 = 2 [10]
(c)
Write shorts notes on the following: [3+4+3]
(i)
Planer graph
(ii)
Euler graph & Circuit
(iii)
Graph coloring
__________X__________
Comments
Post a Comment