DISCRETE MATHEMATICS QUESTION BANK

UNIT-1

FUNCTIONS & RELATIONS

SHORT ANSWER QUESTIONS:(5 MARKS)

1 ) Let A be any finite set and P(A) be the power set of A.⊆ be the inclusion relation on the elements
of P(A). Draw the Hasse diagrams of ( P(A),⊆) for i) A = {a} ii) A = {a,b} iii) A = {a,b,c} iv) A =
{a,b,c,d}.

2) Let A = B = {x/ -1≤ 𝑥 ≤ 1} for each of the following functions state whether it is injective,
surjective or bijective
2𝑥+3
a) f(x) = IxI b) g(x) = sinπx c) h(x) =
5

3) Show that the relation R={ (a,a),(a,b),(b,a),(b,b)(c,c)} on A={a,b,c} is an equivalence relation and
find A/R also find partitions of A.

4) Let f:R→ 𝑅, 𝑔: 𝑅 → 𝑅, where R is the set of real numbers be given by f(x) = 𝑥 2 − 2 and g(x) =
x+4 find fog and gof. State whether these functions are bijective or not.

5) Prove that the relation R defined by “a is congruent to b modulo m” on the set of integers is an
equivalence relation.

6) Define the following : (a) recursive function (b) Total function

(c) Partial function.

7) Draw the Hasse diagram representing the positive divisors of 45.

8) If R denotes a relation on the set of all ordered pairs of positive integers by (a,b)R(c,d) iff ad=bc
,show that ‘R’ is an equivalence relation.

9) Let X= {1,2,3,4,5,} and relation R={(x,y)/x>y}.Draw the graph of ‘R’ and also give its matrix.

10) What is Compatibility relation and Write the procedure to find maximal compatibility blocks.
11) Draw the Hasse diagram representing the positive divisors of 36.
12) Show that the relation ‘R’ defined by (a,b) R (c,d) iff a+d=b+c is an equivalence relation.

13) If X= {1,2,3,4} and R= {(x,y) /x<y} .Draw the graph of ‘R’ and also give its matrix.

VERY SHORT ANSWER QUESTIONS (2 MARKS)

1) If R is a relation on the set A={ 1,2,3,4} defined by x R y if x exactly divides y .Prove that
(A,R) is a poset.
2) Let f and g be functions from R to R defined by f(x)=ax+b ,g(x)= 1-x+ x2 .If (gof) =9x2-
9x+3,determine a,b.
3) Let D24= {1,2,3,4,6,8,12,24} and the relation “ I “ exactly divides be a partial ordering
relation on D24.Then draw the Hasse Diagram of (D24,I).
4) Consider the function f: R to R defined by f(x)= 2x+5, another function g(x)=(x-5)/2.Prove
that g is inverse of f.
 5) Let R= { [1,1] [2,2] [3,3] [4,4] [5,5] [1,2] [2,1] [5,4] [4,5]} be the equivalence relation on A
= {1,2,3,4,5}. Find equivalence classes and A/R.
6) Find the inverse of the function f(x) = ex defined from R to R+.
7) If A = {1,2,3,4,5,6,7,8,9,10,11,12} and R= { (x,y)/x-y is multiple of 5} find the partition of
A.
8) Let f(x)=x+2, g(x) = x-2, h(x) =3x find i) fog ii) fogoh.
𝑥 2+1
9) Determine whether f(x) = 𝑥 2+2 is bijective or not.
10) Give an example of relation which is symmetric but neither reflexive nor anti symmetric nor
transitive.

UNIT-2

COUNTING PRINCIPLES

SHORT ANSWER QUESTIONS (5 MARKS)

1) Use Mathematical Induction to prove the following generalization of one of Demorgan’s

laws

(⋂𝑛𝑗=1 𝐴𝑗 )′ = ⋃𝑛𝑗=1 𝐴𝑗′ where A1,A2,A3,………An are subsets of universal set U.

2) Prove that if a/bc and (a,b)=1 then a/c.

3) State and Prove Division algorithm theorem using well ordering principle.
4) Describe set of rooted trees recursively?
5) Show that if a,b,c are integers such that a/b and a/c then a/mb+nc where m, n are integers.
6) Use Mathematical Induction to show that 1+2+22 + 23 + ⋯ … … … + 2𝑛 = 2𝑛+1 − 1
7) Write the Procedure for Euclidean algorithm to find gcd of two numbers.
8) Describe full binary tree recursively.
9) Prove that there are infinitely many primes.
10) Define modular arithmetic? Prove that the integers a,b are congruent modulo m iff there is
an integer k such that a=b+km, where m is a positive integer.

VERY SHORT ANSWER QUESTIONS

1) State fundamental theorem of arithmetic hence find the prime factorization of 810.
2) Write prime numbers less than 150.
3) Write the properties of gcd.
4) State and prove Euclid’s lemma.
5) Define Fibonacci numbers recursively.
6) Explain about Mathematical Induction.
7) Explain pair wise relatively primes with an example.
8) Define Mersenne prime numbers.
9) Write the properties of divisibility.
10) Define well ordering principle.
UNIT-3

MATHEMATICAL LOGIC

SHORT ANSWER QUESTIONS(5 MARKS)

1) Find PCNF without Constructing truth table (P→(Q∧R)) → (~ P→ (~ Q∧ ~R))

2) Use truth table to prove the following argument

p→~q
r→p
q
∴ ~𝑟

3) Find PDNF by constructing its PCNF of (Q v P)⋀ (QVR)∧ (∼ (PV R) V ∼Q))

4) Find whether the following argument is valid or not
“ No Engineering student is bad in studies “
“Anil is not bad in studies”

Therefore “ Anil is an engineering student”

5) Without constructing truth table find PDNF of
{(P →(Q ∧ R)) ∧ (~ Q∧∼ 𝑅 )}
6) Prove that the following argument is valid:
“all dogs are carnivorous. “
“some animals are dogs.”

Therefore” some animals are carnivorous”.

7) Is the following Conclusion valid derive from contradiction method.
~𝑞
p→q
p⋁t
∴𝑡

8)Construct PCNF of (P⇔ 𝑄) → R.

9)Obtain CNF of ((𝑃 → 𝑄)⋀ ∼ 𝑄) → ~𝑃

10)Obtain DNF of (𝑄 → 𝑃)⋀(~𝑃⋀𝑄)

11) Find PDNF by constructing the PCNF of (Q v P)⋀ (QVR)∧ (∼ (PV R) V ∼Q)).
12) Prove that for any three propositions P,Q,R the compound proposition (𝑃 → (𝑄 → 𝑅)) →
((𝑃 → 𝑄) → (𝑃 → 𝑅)) is a tautology by 𝑖) with truth table ii) with laws of logic.
13) Show that the following set of premises are inconsistent
𝑃 → 𝑄, 𝑃 → 𝑅, 𝑄 → ~𝑅, 𝑃
 14) Check the validity of the following argument
All integers are rational numbers.
Some integers are powers of 5.
Therefore, some rational numbers are powers of 5.

VERY SHORT ANSWER QUESTIONS

1) Construct the truth table of (PVQ) → P.
2) Write the rule of disjunctive amplification of predicates.
3) Construct the truth table of (P∧Q)→P.
4) Write the rule of Modus tollens of predicates.
5) Write the rule of Modus Pones of predicates.
6) If p: A circle is a conic, q: 5 is a real number, r: Exponential series is convergent.
Express the compound propositions p→(q⋁ r), p ∧ (∼ q) in words.
7) Show that the following argument is consistent
pVq

∼p
_________
∴𝐶
__________
8) Write a short notes on DNF and CNF.
9) Express the statement in words: “Every student in class has studied Calculus.” Using
quantifiers.
10) Show using truth table that the statements ( p → q) and (∼ p V q ) are logically
equivalent.

UNIT -4 GROUPS

SHORT ANSWER QUESTIONS(5 MARKS)

1) Construct composition table for the roots of equation x4= 1 and Show that it is a group with
respect to operation multiplication.
2) Prove that every finite group of order ‘n’ is isomorphic to permutation group of degree ‘n’.
3) If ‘G’ is a group then prove that (a-1)-1=a.
4) Prove that G ={0,1,2,3,4} is an abelian group of order 5 with respect to addition modulo 5.
5) Show that Q1 (rational numbers other than1) is an infinite abelian group with respect to *
defined by a*b=a+b-ab, where a,b are rational numbers.
6) Prove that the identity element of a group “G’ is same as identity element of its subgroup H.
7) Prove that in a group its identity element, inverse element are unique.
8) State and prove Lagrange’s theorem on cosets.
9) Prove that G ={0,1,2,3,4,5,6} is an abelian group of order 7 with respect to addition modulo
7.
 10) Define subgroup, normal subgroup, Quotient group, left and right cosets with an example for
each.
11) Prove that set of non-singular matrices of order 2 x 2 is a group but not an abelian group
under multiplication.

VERY SHORT ANSWER QUESTIONS(2 MARKS)

1) Show that binary operation * defined on (R,*) where x*y=xy is not associative.
2) Define a) Normal subgroup of a group b) Quotient group.
3) Define cyclic group with an example.
4) If aob=a+b+ab ∀ a,b∈Z ,show that (Z,0) is a semi group.
5) Find the order of each element in the group {1, −1, 𝑖, −𝑖}.
6) If a, b ∈ group G, then prove that (𝑎𝑏)−1 =b-1 a-1
7) Show that the cube roots of unity forms a group with respect to multiplication.
8) Define a) Left coset of subgroup H in G. b) Right coset of subgroup H in G.

9) Define a) Index of a coset. b) If H={1,-1} is a subgroup of the group G={1,-1,I,-i},then find the
index of H in G.

10) Define permutation group and degree of a permutation group.

UNIT 5

GRAPH THEORY

SHORT ANSWER QUESTIONS(5 MARKS)

1) Define graph coloring and chromatic number of a graph and find the chromatic
number of
𝑖)𝐾3,3 ii) cycle with even number of vertices.
2) Define the following terms. Give one suitable example for each

i) Euler circuit ii) Hamiltonian graph.

3) State and prove Euler’s theorem on plane graphs.
4) Define isomorphism of graphs. What are the steps followed in discovering the
isomorphism.
5) Define dual and Isomorphism of graphs with example.
6) State and prove fundamental theorem of graph theory.
 7) Explain Eulerian and Hamiltonian graphs with examples, also draw the graphs of the
following

i)Eulerian but not Hamiltonian

ii)Hamiltonian but not Eulerian

8)Two graphs with the following adjacency list are given, Find whether G and H are
isomorphic or not
Graph G Graph H -
vertices Adjacent Vertices Adjacent
vertices vertices

P q,s a b,c,d

Q p,r,s b b,d

R q,t c a,d

S p,q,t d a,b,c

T s e D

9)Write incident matrix and adjacency matrix to the graph whose adjacency list is given
by
vertices Adjacent
vertices

a b,e

b a,c,d,

c b,d

d e,b,c,

e a,d

9) Two graphs with the following adjacency list are given, show that they are isomorphic to each
other
Graph G Graph H
vertices Adjacent Vertices Adjacent
vertices vertices

A b,c k L

B a L k,m,n

C a,d,e m l

D c n l,o
 E c O n

10) If ‘𝐺’ be a graph with |𝑉|=n vertices and |𝐸| edges then prove that∑𝑛𝑖=1 deg (𝑣𝑖 )= 2E
11) Write the conditions to construct dual of the graph and construct dual of the following graph
whose adjacency list is given :
Vertices Adjacent
vertices

A b,c

B a,c,e

C a,d,e,b

D C

E b,c

VERY SHORT ANSWER QUESTIONS (2 MARKS)

1) Define complete bipartite graph with example.

2) Define the following terms with suitable example i) Complete graph ii) Regular graph.
3) Define isomorphism of two graphs.
4) Define the following terms with suitable example i) Subgraph ii) Spanning graph.
5) Define the following sub graphs of a graph a) Closed Walk and Open walk b) Trail
6) Define dual of a planar graph and explain it through an example.
7) Define Chromatic number of a graph. Explain it through an example.
8) Draw K5 complete graph.
9) Let G be a 4-regular connected planar graph having 16 edges. Find the number of regions of
G.
10) State fundamental theorem of graph theory.