DHANALAKSHMI SRINIVASAN

COLLEGE OF ENGINEERING
COIMBATORE-641105

Department of Science and Humanities

Subject Faculty: Mr. M. Soundharan, AP/ Mathematics
Subject Code & Name: MA3354 & Discrete Mathematics
Branch: B.E. CSE
Year/Sem: II /III Academic Year:2023-2024

QUESTION BANK

Unit-I Logic and Proofs

DNF & CNF

( P  Q) ( P  Q) .
1. Obtain DNF & CNF of

P → ( ( P → Q )   ( Q  P ) )
2. Obtain DNF & CNF of

Q  ( P  Q )  ( P  Q )
3. Obtain DNF & CNF of

P  (Q  R )  ( P → Q )
4. Obtain DNF & CNF of

5. Obtain the DNF for

( P → (Q  R ))  (( P → Q )  R )

6. Obtain the DNF for

(Q  ( P  R ))  (( P  R )  Q )
PDNF & PCNF

1. Obtain PCNF of (Q → P)  ( P  Q) and hence obtain its PDNF.

2. Obtain the Principal Disjunctive and Conjunctive normal forms [PDNF & PCNF] Using truth table.

(i) [P → (Q R)]  [ P → ( Q  R)] (ii) (P → R )  (Q  P)

3. Without constructing the truth table obtain the product of sum of canonical form [PCNF] and sum of
the products canonical form. [PDNF].

(i) (P → R )  (Q  P) (ii) ( P  Q)  (P  R)  (O R)

4. Find the PCNF and PDNF of ( P  R )  ( P  Q ) Using truth table.

5. Obtain the PDNF and PCNF of ( P  Q )  ( P  R ) using truth table and without using truth table.

6. Obtain PDNF of ( P  Q )  ( P  R )  ( Q  R ) . Also find PCNF using truth table.

TAUTOLOGY

1. To prove [ P → (Q → R)] → [( P → Q) → ( P → R)] is tautology.

2. Show that
(P Q)  ( P  ( Q  R))  ( P   Q)  ( P   R) is a tautology without using truth table.

3. Without using truth table, show that Q  ( P  Q)  (P  Q) is tautology.

( )
4. Determine whether Q  ( P → Q ) → P is a tautology without using truth table.

5. Show that (P  (Q  R))  (Q  R)  (P  R)  R is a tautology without using truth table.

EQUIVALENCE LAWS
1. Show that ( P  Q)  ( P  Q)  ( P  Q) without constructing the truth table
2. Prove that ( P → Q)  (Q → R) → (P → R)

3. Without constructing the truth table show that P → (Q → P)  P → (P → Q)

P → ( Q → R )  P → ( Q  R )  ( P  Q ) → R
4. Show that
5. Construct the truth table for

(P  (Q  R))  ((Q  R)  (P  R))

6. Construct the truth table for ( P  (Q  R) )  ( (Q  R)  ( P  R) )

7. Show that ( P  Q) → (P  (P  Q))  ( P Q)

DIRECT & INDIRECT METHODS

1. Show that P follows logically from the premises  ( P  Q ) , ( Q  R ) , R

2. Prove that P → Q, Q → R, R, P  ( J  S )  J  S

3. Show that R  ( P  Q ) is a valid conclusion from the premises P  Q, Q → R, P → M , M

4. Show that S  R is tautologically implied by ( P  Q )  ( P → R )  ( Q → S )

5. Show that A → D follows logically from the premises. A → B  C , B → A, D → C

6. Prove that P → Q, Q → R, S → R, P  S are inconsistent.

7. Prove that the premises A → ( B → C ) , D → ( B  C ) , ( A  D ) are inconsistent.

8. Using Indirect method, show that P → Q, Q → R, P  R  R

9. Using Indirect method, prove that P → R, Q → S , P  Q  S  R

10. Using Indirect method, show that S → Q, R,S R, R Q  P

11. Show that the following statements constitute a valid argument. If there was rain, then travelling
was difficult. If they had umbrella, then travelling was not difficult. They had umbrella. Therefore, there
was no rain.
12. Show that the hypothesis, “It is not sunny this afternoon and it is colder than yesterday”, “we will
go swimming only if it is sunny”. “If we do not go swimming, then we will take a canoe trip” and “if
we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by
sunset”.
13. Construct an argument to show that the following premises to show that the following premises
imply the conclusion "It rained". "If it does not rain or if there is
no traffic dislocation, then the sports day will be held and the cultural programme
will go on"; "If the sports day is held, the trophy will be awarded" and "The trophy
was not awarded".

UNIT-II COMBINATORICS

MATHEMATICAL INDUCTION
n(n + 1)
1. Prove by induction method, 1 + 2 + 3 + ... + n = ;n 1
2
n(n + 1)(2n + 1)
2.Show that 12 + 22 + 32 + ... + n 2 = ; n  1 by mathematical induction.
6

3. Use mathematical induction to show that 12 + 2 + 22 + 32 + ... + n2 = 2n+1 − 1; n  1

1 1 1 1
4. Use mathematical induction to show that + + + ... +  n; n  2
1 2 3 n
n
3n+1 − 1
5. Use mathematical induction to show that  3m =
m =0 2

6. Show that n3 + 2n is divisible by 3.

7. Use mathematical induction to show that
(n + 1)(2n + 1)(2n + 3)
12 + 32 + 52 + 7 2 + ... + (2n + 1) 2 = ;n  0
3
8. Use mathematical induction to show that 1.1!+ 2.2!+ 3.3!+ ... + n.n ! = ( n + 1)!− 1; n  1
 RECURRENCE RELATION
1. Find the solution to the recurrence relation an = 6an −1 − 11an −2 + 6an −3 with initial conditions
a0 = 2, a1 = 5, a2 = 15 .

2. Solve the recurrence relation an = −3an −1 − 3an −2 − an −3 given that a0 = 5, a1 = −9, a2 = 15

3.Obtain the solution to the recurrence relation an = 2an−1 + 5an−2 − 6an−3 with initial conditions
a0 = 7, a1 = −4, a2 = 8 .

4. Solve the recurrence relation

S (n) − 4S (n − 1) − 11S (n − 2) + 30S (n − 3) = 0; S (0) = 0;S(1) = −35;S(2) = −85

5. Find the solution to the recurrence relation an = −3an −1 − 3an −2 − an −3 with initial conditions

a0 = 1, a1 = −2, a2 = −1

GENERATING FUNCTION TO SOLVE THE RECURRENCE RELATION

1. Use generating function to solve the recurrence relation an+2 − 2an+1 + an = 2n with initial

condition a0 = 2, a1 = 1

2. Solve the recurrence relation by using generation function

S (n) = S(n − 1) + 2(n − 1);S(0) = 3,S(1) = 1

3. Use generating function to solve the recurrence relation an = 4an−1 − 4an−2 + 4n ;n  2 with
initial condition a0 = 2, a1 = 8 .

4. Use generating function to solve the recurrence relation an + 3an−1 − 4an −2 = 0; n  2 with
initial condition a0 = 3, a1 = −2 .

5. Use generating function to solve the recurrence relation an − 5an−1 + 6an −2 = 0; n  2 with
initial condition a0 = 0, a1 = 1 .

THE INCLUSION AND EXCLUSION PRINCIPAL

1. Find the number of integers between 1 to 100 that are not divisible by any of the integers
2,3,5 or 7.
2. Determine the number of positive integers n, 1  n  2000 that are not divisible by2,3 or 5
but divisible by 7.
3. Find the number of integers between 1 to 250 that are not divisible by any of the integers
2,3,5 or 7.
4. State and Prove the pigeonhole principle.
5. The generalization / extension of the pigeonhole principle.

6. For m  Z + and m-odd, prove that there exist a positive integer n such that m divides 2n−1
7. Prove that a positive integer greater than 1 is either a prime number or it can be written as
product of prime numbers.
8. A survey of 500 from a school produced the following information. 200 play volleyball, 120
play hockey. 60 plays both volleyball and hockey. How many are not playing either volleyball
or hockey?
9. In a survey of 100 students, it was found that 30 studied Mathematics, 54 studied Statistics,
25 studied operation Research, 1 studied all the three subjects. 20 studied Mathematics and
Statistics, 3 studied Mathematics and Operation Research and 15 studied Statistics and
Operation Research. (i) How many students studied none of these subjects? (ii) How many
students studied only Mathematics?
10. Out of 100 students in a college, 38 play tennis, 57 play cricket and 31play hockey, 9 play
cricket and hockey, 10 play hockey and tennis, 12 play tennis and cricket. How many play (i)
All three games. (ii) Just one game. (iii) Tennis and cricket but not hockey.
11. A total of 1232 students have taken a course in Tamil, 879 have taken a course in Telugu
and 114 have taken a course in Hindi. Further103 have taken a course in both Tamil and
Telugu,23 have taken a course in Tamil and Hindi and 14 have taken a course in Telugu and
Hindi. If 2092 students have taken atleast one of the Tamil, Telugu and Hindi, how many
students have taken a course in all three languages.

UNIT-III GRAPHS
Part-B
1. State and prove The Handshaking theorem.
2. The number of odd degree vertices is always even.
n(n − 1)
3. The maximum number of edges in a simple graph with n vertices is .
2

n2
4. Show that if G is a bipartite simple graph with v-vertices and e-edges, then e  .
4
5.Prove that a simple graph with n-vertices must be connected if it has more than
(n − 1)(n − 2)
edges.
2
(n − k )(n − k + 1)
6. A simple graph with n-vertices and k-components can have atmost edges.
2
7. A connected graph is Euler graph. If and only if each of its vertices is of even degree.
8. Given an example of a graph which is i) Eulerian but not Hamiltonian, ii) Hamiltonian but
not Eulerian, iii) Both Eulerian and Hamiltonian and iv) Non-Eulerian and Non-Hamiltonian.
V (G )
9. Prove that if G is a simple graph with atleast three vertices and  (G )  then G-is
2
Hamiltonian.

10. Show that if G is a self-complementary simple graph with V (G) = V vertices, then V  0
or 1(mod 4) .
11. Let G be a simple undirected graph with adjacency matrix A with respect to the ordering
v1 , v2 , v3 ,..., vn Prove that the numbers of different walks of length r from vi to v j equal the
entry of Ar where r-is a positive integer.
12.. Determine which of the following graphs are bipartite and which are not. If a
graph is bipartite, state if it is completely bipartite.

13. Define a sub-graph. Find all the subgraphs of the following graph by deleting an
edge.

14. Define Adjacency matrix of the graphs below.

15. State the necessary condition for two graphs to be isomorphic. Show that the
following two graphs are isomorphic.
16. Check whether the following graphs are isomorphic or not.

17. Determine whether the graphs given below are isomorphic.

18. Define Isomorphism. Establish an isomorphism for the following graphs

19. Define isomorphism between two graphs. Are the simple graphs with the
following adjacency matrices isomorphic?

20. Draw the complete graph K5 with vertices A, B, C, D, E. Draw all complete sub
group of K5 with 4 vertices.
 Unit-IV Algebraic Structures
Part-B
1. If (G , ) is a finite group, then prove that order of any subgroup divides the order of the
group. [OR] State and Prove Lagrange’s theorem on groups.
2. Prove that group homomorphism preserves identity and inverse.
3. Show that in a cycle group every subgroup is a normal subgroup.
4. Show that the kernel of a group homomorphism is a normal subgroup of the group.
5. Show that a non-empty subset H of a group (G , ) is a subgroup of G if and only if
a * b −1  H for all a, b  H

6. Prove that intersection of two normal subgroups of a group G is again a normal subgroup
of G.

7. Prove that G = [1],[2],[3],[4] is an abelian group under multiplication modulo 5.

8. Let  S ,*  be a semigroup such that for x, y  S , x * x = y where S =  x, y then prove

that (i ) x * x = y * x;(ii) y * y = y

9. Prove that every subgroup of a cyclic group is cyclic. [OR] If (G , ) is a cyclic group, then
every subgroup of (G , ) is also a cyclic group.

10. Prove that every finite group of order n is isomorphic to permutation group of degree n.
[OR] State and prove Cayley’s theorem.
11. Define monoid. Give an example of a semi subgroup that is not a monoid. Further prove
that for any commutative monoid (M, ) the set of idempotent elements of M form a sub
monoid.
12. Fundamental theorem on homomorphism of groups.

13. Show that ( Q+ ,*) is an abelian group, where * is defined by a * b =

ab
, a, b  Q +
2
14. Show that if every element in a group is its own inverse, then the group must be abelian.
15. Let (G , ) be a group and let H be a normal subgroup of G. If G / H be the set
aH | a  G then show that (G / H , ) is a group, where aH  bH = (a * b) H for all
aH , bH  G | H further, show that there exists a natural homomorphism f : G → G | H

16. Prove that (a * b) −1 = b −1 * a −1 for any a, b in a group (G , ) .

17. Let f : G → H be a homomorphism from the group (G , ) to the (H,  ) Prove that the
kernel of f is a normal subgroup of G.

18. Prove that the group homomorphism preserves the identity element.

19. If (G , ) is an abelian group. Show that (a * b)n = a n * b n , a, b  G where n is positive

integer.
 UNIT-V Lattices and Boolean Algebra
PART-B
1. Lat (A; R) be a partially ordered set. Then show that A; R −1 ) is also partially set,
where R −1 is defined as R −1 = (a, b)  A A/ (b, a)  R .
2. Show that in a lattice "isotone property" and "distributive inequalities" are true.
3. Show that the complemented and distributive lattice, the following are true.
a  b  a * b = 0  a  b = 1  b  a
4. Show that every chain is distributive lattice.
5. Define a modular lattice and prove that every distributive lattice is modular but not
conversely.
6. In a Boolean Algebra, show that ( a * b ) = a  b & ( a  b ) = a * b
7. State and prove De Morgan’s laws in complemented and distributive lattice.
8. State and prove distributive inequalities in lattices.
9. Define modular lattice. Prove that a lattice L is modular iff
x, y  L, x  ( y *( x  z ) ) = ( x  y)*( x  z )
10. Let  L,*,   and  S , ,   be any two lattices with the partial orderings  and 
respectively. If g is a lattice homomorphism, then g preserves the partial ordering.
11. Show that in a Boolean algebra
a  b  a b = 0  a b =1 b  a
12. In a complemented and distributive lattice, prove that complement of each element is
unique.
13. Show that every chain is modular.
14. Show that the De Morgan’s law is valid in a Boolean Algebra.
15. Let be a distributive lattice and a, b  L; if a  b = a  c & a  b = a  c then show that
b=c