DISCRETE MATHEMATICAL STRUCTURES

Multiple Choice Questions

MODULE-1
S. No Question CO PO Marks
1 Which of the following propositions is tautology? CO1 PO1 2

a) (p v q)→q
b) p v (q→p)
c) p v (p→q)
d) Both (b) & (c)
2 Which of the following is/are tautology? CO1 PO1 2
a) avb→b^c

b) a^b→bvc

c) a v b → (b → c)

d) None of these

3 Identify the valid conclusion from the premises CO1 PO1 2

Pv Q, Q → R, P → M, ˥M
a) P ^ (R v R)

b) P ^ (P ^ R)

c) R ^ (P v Q)

d) Q ^ (P v R)

4 Which of the following is a declarative statement? CO1 PO1 2

a) It's right

b) He says

c) Two may not be an even integer

d) I love you

5 P → (Q → R) is equivalent to CO1 PO1 2

a) (P ^ Q) → R

b) (P v Q) → R
 c) (P v Q) → ˥R

d) None of these

6 The truth value of the statement p  q is true when CO1 PO1 2

both p and q are
a) False
b) True
c) True or false
d) None of these
7 The truth value of the statement 2+3=6 is CO1 PO1 2
a) T
b) F
c) T and F
d) None of these
8 The value of p  q is false when CO1 PO1 2
a) P is T and q is F
b) P, q both are true
c) P, q both are false
d) None of these
9 The rule of inference p, p  q then q is known CO1 PO1 2
as
a) Contradiction
b) Bi-conditional
c) Modus ponens
d) Modus Tollens
10 The converse of the statement p  q is CO1 PO1 2
a) q  p
b) p  q
c) q  p
d) None of these
11 Which of the following property is called 2
Absorption property of Lattice?

a) a  (b  c )  a
b) b) a  (c  c )  c
c) c ) a  (b  a )  b
d) d) a  (b  a )  a
 MODULE-2
S. No Question CO PO Marks
1 The recurrence relation of the CO2 PO1 2
Fibonacci sequence is
a) f n  f n1  f n  2
b) f n  2 f n 1
c) 2 f n  f n  2
d) None of these
2 The ‘divides relation’ on the set of integers is CO2 PO1 2
a) Symmetric
b) Antisymmetric
c) Equivalence
d) None of these
3 The number of reflexive relations on the set with CO2 PO1 2
‘n’ elements
a) 2 n ( n 1)
b) 2 n
c) 2 ( n 1)
d) None of these
4 Which of the following relation is equivalence CO2 PO1 2
a) x  y
b) x  y
c) x  y mod 3
d) None of these

5 Let A = {1, 2, 3} and let R = {(1, 1), (2, 2), (3, 3), (1, CO2 PO1 2
3), (3, 2), (1, 2)}. Then R is
a) reflexive and symmetric but not transitive
b) reflexive and transitive but not symmetric
c) symmetric and transitive but not reflexive
d) an equivalence relation

6 Let A {a, b, c} and let R = {(a, a)(a, b), (b, a)}. Then, CO2 PO1 2
R is
a) reflexive and symmetric but not transitive
b) reflexive and transitive but not symmetric
c) symmetric and transitive but not reflexive
d) an equivalence relation.
7 Hasse diagrams are drawn for CO2 PO1 2

a) partially ordered sets

 b) lattices

c) Boolean Algebra
2

d) none of these

8 Let D30 = {1, 2, 3, 5, 6, 10, 15, 30} and relation be a CO2 PO1 2
partial ordering on D30. The lub of 10 and 15
respectively is

a) 30

b) 15

c) 10

d) 6

9 Which of the following integer is equivalence CO2 PO1 2

class to 1 modulo 4
a) -7
b) 6
c) 4
d) 2

10 Which of these are poset? CO2 PO1 2

a) Z ,  
b) Z ,  
c) Z ,  
d) None of these

11 If the recurrence relation is defined as CO2 PO2 2

a n  3a n 1  2 with a 0  1 then a 3 is
a) 17
b) 37
c) 53
d) 27
 12 The number of positive integers not exceed 100 CO2 PO2 2
which are divisible by both 3 and 5 are
a) 7
b) 6
c) 8
d) None of these
13 The characteristic equation of the recurrence CO2 PO1 2
relation a n  a n 1  2 a n  2 is
a) r 2  r  2  0
b) r 2  r  2  0
c) r2 r 2  0
d) r 2  r  2  0
14 Which of the following is trail solution for the particular CO2 PO1 2
solution of the recurrence relation a n  a n 1  2 a n  2  7 n
a) Kn7 n
b) Kn 2 7 n
c) Kn 7
d) K 7n

MODULE-3
S. No Question CO PO Marks
1 If (G, .) is a group such that a2 = e, ∀ a ∈ G, then G CO3 PO1 2
is
a) semi group
b) abelian group
c) non abelian group
d) None of these
2 The set of all real numbers under the usual CO3 PO1 2
multiplication operation is not a group since

a) multiplication is not a binary operation

b) multiplication is not associative
c) identity element does not exist
d) zero has no inverse
3 The inverse of - i in the multiplicative group, {1, - 1, CO3 PO1 2
i , - i} is

a) 1
b) -1
c) I
d) -i
4 In the group (G, .), the value of (a- 1 b)- 1 is CO3 PO1 2

a) ab-1

b) b- 1a

c) a-1b

d) ba-1

5 If (G, .) is a group, such that (ab)2 = a2 b2 ∀ a, b ∈ G, CO3 PO1 2

then G is a/an

a) commutative semi group

b) abelian group

c) non-abelian group

d) none of these

6 In the group G = {2, 4, 6, 8) under multiplication C03 PO2 2

modulo 10, the identity element is

a) 6
b) 8
c) 4
d) 2
7 A self-complemented, distributive lattice is called CO3 PO2 2

a) Boolean algebra

b) Modular lattice

c) Complete lattice

d) Self dual lattice

8 Principle of duality is defined as CO3 PO2 2

a) ≤ is replaced by ≥
 b) LUB becomes GLB

c) all properties are unaltered when

≤ is replaced by ≥

d) all properties are unaltered when

≤ is replaced by ≥ other than 0 and 1
element.

9 The absorption law is defined as CO3 PO1 2

a) a * ( a * b ) = b

b) a * ( a ⊕ b ) = b

c) a * ( a * b ) = a ⊕ b

d) a * ( a ⊕ b ) = a

10 A subset H of a group(G,*) is a group if CO3 PO1 1

a) a,b ∈ H ⇒ a * b ∈ H
b) a ∈ H⇒ a-1 ∈ H
c) a,b ∈ H ⇒ a * b-1 ∈ H
d) H contains the identity element

11 If every element of a group G has its own inverse, CO3 PO1 2

then G is
a)abelian
b) finite
c) normal
d) infinite
12 CO3 PO1 2
13 C03 PO2 2
14 CO3 PO1 2
15 CO3 PO1 2

MODULE-4
S. No Question CO PO Marks
1 A path in graph G, which contains every vertex of CO4 PO1 2
G once and only once ?

a. Euler tour
b. Hamiltonian Path
 c. Euler trail
d. Hamiltonian tour

2 A minimal spanning tree of a graph G is.... ? CO4 PO1 2

a. A spanning sub graph

b. A tree
c. Minimum weights
d. All of above

3 A vertex of a graph is called even or odd depending CO4 PO1 2

upon?

a. Total number of edges in a graph is even or

odd
b. Total number of vertices in a graph is even
or odd
c. Its degree is even or odd
d. None of these

4 The chromatic number of the graph K 7 is CO4 PO1 2

a) 5
b) 7
c) 8
d) None of these
5 The chromatic number of the graph K m ,n is CO4 PO1 2
e) m
f) 3
g) 2
h) n
6 The chromatic number the planner graph is not C04 PO1 2
more than
a) 3
b) 4
c) 2
d) None of these
7 The sum of degrees of all the vertices is CO4 PO1 2

a) Two times the number of vertices

b) Two times the number of edges
c) Three times the number of vertices
d) Three times the number of edges

8 Which of the following graph is not planner CO4 PO2 2

 a) K 4
b) K 5
c) K 3
d) None of these
9 If G is a connected planner simple graph with v- C04 PO1 2
vertices and e-edges, where v  3 then
a) e  3v  6
b) e  4v  6
c) v  3e  6
d) None of these
10 The vertex of degree 1 is called as CO4 PO1 2
a) Pendent vertex
b) Isolated vertex
c) Singular vertex
d) None of these
11 The chromatic number of the graph C7 is CO4 PO1 2
a) 4
b) 6
c) 7
d) 3

12 A connected multi graph has an Euler path but not C04 PO1 2
Euler circuit if and only if it has
a) Exactly two vertices of even degree
b) Exactly two vertices of odd degree
c) Every vertex of odd degree
d) All the above
13 Which of the following is Euler’s formula of planner CO4 PO1 2
graph

a) r = v-e + 2
b) r = e- v + 2
c) e= r – v + 2
d) none of the above

14 A tree with n vertices has CO4 PO1 2

a) n -2 edges
b) n – 1 edges
c) n-3 edges
d) n eges

15 Kruskal’s algorithm helps to find CO4 PO1 2

 a) shortest path
b) minimum spanning tree
c) planner graph
d) isomorphism of graphs

Short Questions
Module-1
S. No Question CO PO Marks
1 Write the truth table of p  q CO1 PO1 2
2 Write the truth table of  p  q    p  q  CO1 PO1 2
3 Write the truth table of  p  q    p  q  CO1 PO1 2
4 Define contradiction, and Tautology CO1 PO1 2
5 Show that ( p  q ) and p  q are logically CO1 PO1 2
equivalent
6 Symbolize the statement “everyone in the final- CO1 PO1 2
year class has a cellular phone”.

7 Explain the Hypothetical Syllogism CO1 PO1 2

8 Determine the converse and contra positive of CO1 PO1 2
the statement “if it rains today, I will go to college
tomorrow”

9 Determine the truth table of ( p   q )   q CO1 PO1 2

10 Given that the value of p  q is false, determine CO1 PO1 2

the value of (  p   q )  q .
11 Determine the absorption law of logical CO1 PO1 2
equivalence s
 12 Determine the following predicate in symbolic form CO1 PO2 2
“someone in your class has visited Agra
13 Express the statements into logical expressions by CO1 PO2 2
using predicates and quantifiers
“Everyone in your class has a cellular phone”,
“somebody in your class seen a foreign movie”
“there is a person in your class cannot swim
14 Express the sentence “every student in the class CO1 PO2 2
likes mathematics” with predicates and
quantifiers.

15 Translate the statement “Every real number except CO1 PO2 2

zero has a multiplicative inverse” using nested
quantifiers.
16 Write the rule of inference “Modus Ponens” CO1 PO1 2
17 Write the rule of inference “Modus Tollens” CO1 PO1 2
18 Write the rule of inference “ Hypothetical syllogism” CO1 PO1 2
19 Write the rule of inference “Resolution” CO1 PO1 2
20 Define Universal and Existential quantification CO1 PO1 2

Module-2
S. No Question CO PO Marks
1 CO2 PO1 2
1
Find out the generating function of
1  ax 2
2 Establish the generating function of the sequence CO2 PO1 2
2,2,2,2,2,2
3 1 CO2 PO2 2
Find the coefficient of x 10 in the expansion of
1  2 x 
4 Find out the general form of the solution of a linear CO2 PO1 2
homogeneous recurrence relation, if its Auxiliary
equation has the roots -1,-1,-1,2,2,5,5,7
5 Find out the recurrence relation of the Fibonacci CO2 PO2 2
sequence
6 Find out the solution of the recurrence relation CO2 PO2 2
a n  6a n 1  9a n  2
7 What form does a particular solution of the linear non CO2 PO2 2
 homogeneous recurrence relation

a n  4 a n 1  4a n  2  2 n
8 What form does a particular solution of the linear non CO2 PO1 2
homogeneous recurrence relation

a n  a n 1  a n 2  (3n  1)
9 Suppose that S = {1, 2, 3, 4, 5, 6}. The collection of CO2 PO2 2
the sets A = { 1,2,3 } ,

B = {4, 5} and C = {6} forms a partition of S. then

find the corresponding equivalence relation
10 Construct the Hasse diagram for the poset CO2 PO1 2
( {1,2,3,4 } , /).
11 Determine the maximum and minimal elements of CO2 PO1 2
the poset ( {2, 4,5,10,12,20,25}, / )
12 Explain with an example of a relation which is CO2 PO1 2
neither symmetric nor anti symmetric on any set
A.
13 let R = {(2,1),(2,3),(3,1),(3,4),(4,1),(4,3) } find R
2 CO2 PO1 2
14 Find the equivalence classes of 1 mod 8 on the set CO2 PO1 2
of integers
15 Determine many integers below 100 are divisible CO2 PO1 2
by neither 5 nor 7
16 Determine many integers below 100 are divisible CO2 PO1 2
by ethier 7 or 11
17 Define transitive closure of a relation R CO2 PO1 2
18 Show that the “divides” relation on the set of positive CO2 PO1 2
integers is not an equivalence relation.
19 Define lexico graphic order CO2 PO1 2
20 Which elements of the poset ({2,4,5,10,12,20,25},/) are CO2 PO1 2
maximal and which are minimal
21 Let ‘S’ be a set. Determine greatest and least elements CO2 PO1 2
of the poset ( P ( S ),  )

Module-3
S. No Question CO PO Marks
1 Define modular lattice CO3 PO1 2
2 Prove the absorption property of lattice CO3 PO1 2
3 If D30 is the set of positive divisors of 30. Is it a CO2 PO1 2
Boolean lattice under the relation a divides?
Justify your answer.
4 Define abelian group CO3 PO1 2
5 Let G be a group congaing four elements, then prove CO3 PO1 2
 that there exist at least one element other than identity
which has its own inverse
6 CO3 PO2 2
Define the principle of duality in lattice
7 Define Boolean lattice CO3 PO1 2
8 In a distributive lattice. if b  c  0 then showthat b  c CO3 PO2 2
9 Define disjunctive and conjunctive normal forms CO3 PO1 2
10 Show that a lattice is distributive if for any elements CO3 PO2 2
a,b,c in a lattice ( a  b )  c  (c  b )  a
11 Give an example of a set which contains four elements CO3 PO1 2
and which forms a group under multiplication. Justify
your answer.
12 Give an example of a set which contains three elements CO3 PO1 2
and which forms a group under multiplication. Justify
your answer.
13 Give an example of a set which contains two elements CO3 PO1 2
and which forms a group under addition. Justify your
answer
14 Define normal subgroup CO3 PO1 2
15 Define isomorphism of groups CO3 PO1 2
16 Define kernel of isomorphism CO3 PO1 2
17 Let ‘f’ be a homomorphism from the group G to a group CO3 PO2 2
H then show that f (e)  e ' where e is identity of G an
e ' is identity of H
18 Let ( A , *) be a group and a and b belongs to A. then CO3 PO2 2
show that a * b   b * a
1 1 1

19 Define cyclic group and generator of cyclic group CO3 PO1 2

20 Show that any subgroup of a cyclic group is cyclic CO3 PO2 2
21 Show that the intersection of two normal subgroups is CO3 PO2 2
normal

Module-4
S. No Question CO PO Marks
1 Define Handshaking theorem of graphs CO4 PO1 2
2 Show that in a directed graph CO4 PO2 2

 deg
v V

(v )   deg
v V

(v )

3 Define Bi-partite graph and give an example CO4 PO1 2

4 Define complete Bi-partite graph and draw K 3,3 CO4 PO1 2

5 Define Isomorphism of graphs C04 PO1 2

6 Define complement of a graph CO4 PO1 2
7 Write the necessary conditions for isomorphism of two CO4 PO1 2
graphs
8 Give an example of two graphs which satisfies the CO4 PO1 2
 necessary conditions but not isomorphic.
9 Define Euler circuit. CO4 PO1 2
10 Define Hamilton circuit. CO4 PO1 2
11 Show that a connected multi graph has an Euler path CO4 PO2 2
but not Euler circuit if it has exactly two vertices of odd
degree
12 Define DIRAC’S theorem of Hamilton graphs CO4 PO1 2
13 Define ORE’S theorem of Hamilton graphs CO4 PO1 2
14 Define planner Graph CO4 PO1 2
15 State Euler’s formula for planner graph CO4 PO1 2
16 The planner representation of a simple graph with 4 CO4 PO2 2
vertices split the plane in to 2 regions then how many
edges it has?

17 Suppose that a connected planner graph has 20 CO4 PO2 2

vertices, each of degree 3. In to how many regions does
a representation of this planner graph split the plane?
18 Suppose that a connected planner graph has 30 edges. CO4 PO2 2
If a planner representation of this graph divides the
plane in to 20 regions. How many vertices does this
graph have?
19 Define graph colouring CO4 PO1 2
20 Define Chromatic number CO4 PO1 2
21 State the FOUR COLOR THEOREM CO4 PO1 2
22 Define Spanning Tree CO4 PO1 2

Long Questions 5 Marks

Module-1
S. No Question CO PO Marks
1 for the set of premises what relevant conclusion CO1 PO2 7
can be drawn

“All foods that are healthy to eat do not

taste good”
“Tofu is healthy to eat”
“You only eat what tastes good”
“You do not eat Tofu”
“Cheeseburgers are not healthy to eat”

2 CO1 PO1 8
Show that ( p  q)   p  r  and p  q  r  are
 logically equivalent

3 Show that ( p  q)  q  r   ( p  r ) is a CO1 PO1 7

Tautology.
4 Show that the hypothesis “it is not sunny this CO1 PO2 8
afternoon and it is colder than yesterday” “ we will
go to swimming only if it is sunny” “ if we do not go
to swimming then we will take a canoe trip” and “
if will take a canoe trip then we will be home by
sunset” leads to the conclusion “we will be home by
sunset”

5 CO1 PO1 7
Show that ( p  q)   p  r  and p  q  r  are
logically equivalent

6 CO1 PO1 7
Show that ( p  r )  q  r  and  p  q  r are
logically equivalent

7 Show that the hypothesis “if you send me an email CO1 PO2 8
message, then I will finish writing the program” “if you
do not send me an email message, then I will go to sleep
early” and “if I go to sleep early, then I will wake up
feeling refreshed” leads to a conclusion “if I do not
finish writing the program then I will wake up feeling
refreshed”
8 Show that the premises “ A student in this class has not CO1 PO2 8
read the book,” and everyone in this class passed the
first exam,” implies the conclusion “someone who
passed the first exam has not read the book”.
9 Show that if ‘n’ is an integer and n3+5 is odd, then CO1 PO2 7
‘n’ is even by method of contraposition.

10 Prove by method of induction that, (11)n+1 +(12)2n-1 CO1 PO2 8

is divisible by 133, for any integer ‘n’

11 Show that 2 n  n 3 for n  10 by method of CO1 PO2 7

induction.

12 Prove by method of induction that, (4)n+1 +(5)2n - 1 is CO1 PO2 8

divisible by 21, for any integer ‘n’
 13 Prove that 2 is an irrational number by method CO1 PO2 7
of contradiction.

14 3(5 n 1  1) CO1 PO2 8

Prove that 3  3.5  3.5 2  ........  3.5 n 
4
whenever n is a non-negative integer by method of
induction.
15 Show by method of induction that 6 n  2  7 2 n 1 is CO1 PO2 8
divisible by 43 for all positive integers n

Module-2
S. No Question CO PO Marks
1 Find the solution of the recurrence relation CO2 PO2 8
a n   3a n 1  3a n  2  a n 3 with initial conditions
a 0  1, a 1   2 , a 2   1

2 Find the solution of the recurrence relation CO2 PO2 7

a n  6a n 1  11a n  2  6a n3 with initial conditions
a 0  2, a 1  5 , a 2  15

3 Find the transitive closure of the relation CO2 PO2 7

R = { (a,b),(b,c), (c,a) (c,b)} defined on the set A =

{a,b,c}.using Warshall’s algorithm.

4 Find the solution of the recurrence relation CO2 PO2 8

a n  6a n 1  9a n  2  3 n

5 Find the solution of the recurrence relation CO2 PO2 8

a n  a n 1  a n 2  (n  3)
6 Find out the solution of the recurrence relation CO2 PO2 7
a n  6a n 1  9a n  2
by using generating function.
Find the Hassae diagram of the poset  pa, b, c,   .
7 CO2 PO2 7
Where p{a,b,c} is the power set of {a,b,c}.And also find
the least and greatest elements of it.
8 Use Warshall’s algorithm to find the transitive closure CO2 PO2 8
of the relation
R = {(b,c),(b,e),(c,e),(d,a),(e,b),(e,c) }defined on the set
{a,b,c,d,e}.

9 Use generating function to solve the recurrence relation CO2 PO2 7

a k  3a k 1  2 with int ial condition a 0  1
10 Use generating function to solve the recurrence relation CO2 PO2 7
a k  5a k 1  6a k  2 with int ial condition a 0  6 and a1  30
11 Use generating function to solve the recurrence relation CO2 PO2 8
a k  a k 1  2a k  2  2 k with int ial condition a0  4 and a1  12
12 Use generating function to solve the recurrence relation CO2 PO2 8
k 1
a k  3a k 1  4 with int ial condition a 0  1

Module-3
S. No Question CO PO Marks
1 State and prove Lagrange’s theorem of finite groups. CO3 PO2 8
2 Prove that in a distributive lattice if an element has a CO3 PO2 7
complement then this complement is unique.

3 Let E ( x1 , x 2 , x 3 )  ( x1  x 2 )  ( x1  x3 )  ( x 2  x 3 ) be a CO3 PO2 8

Boolean expression. Find its disjunctive and
conjunctive normal forms
4 Let H and K are two normal sub-groups of a group G, CO3 PO2 7
then show that H  K is also normal
5 Show that the subgroup of an abelian group is normal CO3 PO2 7
6 If G  {1 ,  1, i,  i } and H  {1,  1} be a sub-group of CO3 PO2 7
G under the operation multiplication then find all
the left cosets of H in G.

7 Let G be a group congaing even number of CO3 PO2 7

elements, then prove that there exist at least one
element which has its own inverse.

8 Let a*H and b*H be two cosets of H in G. then Show CO3 PO2 7
that a*H and b*H are either identical or disjoint.
 9 The order of any subgroup of a finite group divides the CO3 PO2 8
order of the group.
10 Show that the kernel of the homomorphism of groups is CO3 PO2 8
normal subgroup
11 For any a, b.c and d in a lattice  A,   if a  b and c  d CO3 PO2 7
then show that a  c  b  d and a  c  b  d
12 Show that if meet operation is distributive over join CO3 PO2 7
operation then join operation distributive over meet
operation
13 State and prove demorgan’s property of distributive CO3 PO2 8
lattice
14 Let  A,   be a distributive lattice. show if a  x  a  y CO3 PO2 8
and a  x  a  y for some a then show that x  y
15 Let E ( x1 , x 2 , x3 )  ( x1  x 2 )  ( x1  x 3 ) be a Boolean CO3 PO2 8

expression. Find its disjunctive and conjunctive normal

forms

Module-4
S. Question CO PO Marks
No
1 Prove the Euler’s formula for the planner graph CO4 PO2 8
2 Show that in an undirected Graph the odd degree vertices CO4 PO2 8
are even number.

3 Prove that a connected multi-graph with at least two CO4 PO2 8

elements has an Euler circuit if and only if each of its
vertices has an even degree.
4 If G is a connected planner graph with e edges and v CO4 PO2 7
vertices, where v is greater than 3 then show that e  3v  6
5 If G is a connected planner graph with e edges and v CO4 PO2 7
vertices, where v is greater than 3 and no circuits of length 3
then show that e  2v  4
6 Let G be connected planner simple graph with e edges and v CO4 PO2 8
vertices. Let r be the number of regions in a planner
representation of G. then show that ‘ r = e-v+2’
7 Show that a tree with n vertices has n-1 edges. CO4 PO2 8
8 Determine the following graphs are isomorphic are not and CO4 PO2 7
justify your answer
9 CO4 PO2 8
find the shortest path from the vertex 0 to the vertex 4 by
using Dijkstra’s algorithm

10 find the shortest path from the vertex 1 to the vertex 6 by CO4 PO2 8
using Dijkstra’s algorithm

11 Find the minimum spanning tree of the following graph by CO4 PO2 8
using Prim’s’s algorithm.

12 Find the minimum spanning tree of the following graph by CO4 PO2 8
using Prim’s’s algorithm.

13 Find minimum spanning tree by prim’s algorithm CO4 PO2 8

14 Find minimum spanning tree by Kruskal’s algorithm CO4 PO2 8

15 Find minimum spanning tree by Kruskal’s algorithm CO4 PO2 8