STUDENTSFOCUS.

COM

VALLIAMMAI ENGEINEERING COLLEGE

(S.R.M.NAGAR, KATTANKULATHUR-603 203)

DEPARTMENT OF MATHEMATICS

QUESTION BANK

III SEMESTER
MA8351- DISCRETE MATHEMATICS
Regulation – 2017
Academic Year 2018- 2019

Prepared by
Mr.N.Sundarakannan , Assistant Professor/ Mathematics
Mrs.V.Nagarani , Assistant Professor/ Mathematics
Mrs.A.Karpagam , Assistant Professor/ Mathematics

1
 STUDENTSFOCUS.COM

VALLIAMMAI ENGEINEERING COLLEGE

S.R.M.NAGAR, KATTANKULATHUR-603 203

B.TECH. INFORMATION TECHNOLOGY

QUESTION BANK

SUBJECT : MA8351 / DISCRETE MATHEMATICS

SEMESTER / YEAR : III Semester / II year IT

UNIT I - LOGIC AND PROOFS

Propositional Logic – Propositional equivalences - Predicates and Quantifiers – Nested Quantifiers –
Rules of inference - Introduction to proofs – Proof methods and strategy.
PART-A
Bloom’s
Q.No. Question Taxonomy Domain
Level
Construct the truth table for the compound proposition
1. BTL -1 Remember
(𝑝 → 𝑞) ↔ (¬𝑝 → ¬𝑞).
Construct the truth table for the compound proposition
2. BTL -3 Apply
(𝑝 → 𝑞) → (𝑞 → 𝑝).
What are the contra positive, the converse and the inverse of the conditional
3. BTL -2 Understand
statement “If you work hard then you will be rewarded”.
4. Find the truth table for the statement 𝑝 → ¬𝑞. BTL -1 Remember
5. Give the truth value of 𝑇 ↔ 𝑇 ⋀ 𝐹. BTL -1 Remember
Write the symbolic representation and give its contra positive statement of
6. BTL -2 Understand
“If it rains today, then I buy an umbrella” .
7. When do you say that two compound propositions are equivalent ? BTL -1 Remember
8. ( (𝑞
Show that 𝑝 → 𝑟) ∧ → 𝑟)𝑎𝑛𝑑 (𝑝 ∨ 𝑞) → 𝑟 are logically equivalent. BTL -4 Analyze
9. Show that the propositions 𝑝 → 𝑞 𝑎𝑛𝑑 ¬𝑝 ∨ 𝑞 are logically equivalent. BTL -4 Analyze
10. Without using truth table show that 𝑝 → (𝑞 → 𝑝) ⟺ ¬𝑝 → (𝑝 → 𝑞). BTL -3 Apply
11. Show that (𝑝 → (𝑞 → 𝑟)) → ((𝑝 → 𝑞) → (𝑝 → 𝑟)) is a tautology. BTL -3 Apply
12. Is ¬𝑝 ∧ (𝑝 ∨ 𝑞)) → 𝑞 a tautology? BTL -5 Evaluate
13. Using the truth table, show that the proposition 𝑝 ∨ ¬(𝑝 ∧ 𝑞) is a tautology. BTL -3 Apply
Given 𝑃 = {2,3,4,5,6}, state the truth value of the statement
14. BTL -4 Analyze
(∃𝑥 ∈ 𝑝)(𝑥 + 3 = 10 ).
Let 𝐸 = {−1,0,1,2} denote the universe of discourse. If 𝑃(𝑥, 𝑦) = 𝑥 + 𝑦 +
15. BTL -4 Analyze
1, find the truth value of (∀𝑥)(∃𝑦)𝑃(𝑥, 𝑦).
Find a counter example, if possible, to these universally quantified
statements, Whose the universe of discourse for all variables consists of all
16. BTL -2 Understand
integers. (a) ∀𝑥∀𝑦 (𝑥 2 = 𝑦 2 → 𝑥 = 𝑦).
(b) ∀𝑥∀𝑦 (𝑥𝑦 ≥ 𝑥).
What are the negations of the statements ∀𝑥 (𝑥 2 > 𝑥) 𝑎𝑛𝑑
17. BTL -1 Remember
∃𝑥 (𝑥 2 = 2)?
18. Write the negation of the statement(∃𝑥)(∀𝑦)𝑃(𝑥, 𝑦). BTL -1 Remember
19. Give an indirect proof of the theorem “ If 3𝑛 + 2 is odd, then n is odd. BTL -2 Understand
2
 STUDENTSFOCUS.COM
20. Prove that 𝑝, 𝑝 → 𝑞, 𝑞 → 𝑟 ⟹ 𝑟 BTL -6 Create
PART – B
1.(a) Prove that ((𝑝 ∨ 𝑞) ∧ ¬(¬𝑝 ∧ (¬𝑞 ∨ ¬𝑟))) ∨ (¬𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∧ ¬𝑟) is a
BTL -2 Understand
tautology
1. (b) Show that (𝑝 → 𝑞), (𝑟 → 𝑠), (𝑞 → 𝑡), (𝑠 → 𝑢), ¬(𝑡 ∧ 𝑢), (𝑝 → 𝑟) ⟹ ¬𝑝 BTL -2 Understand
2. (a) Check whether (¬𝑝 ∧ (𝑝 → 𝑞)) → ¬𝑞 is a tautology? BTL -2 Understand
Show that (∃𝑥)(𝑃(𝑥) ∧ 𝑄(𝑥)) ⟹ (∃𝑥)𝑃(𝑥) ∧ (∃𝑥)𝑄(𝑥).
2.(b) BTL -2 Understand
Is the converse true?
Show that ∀𝑥(𝑃(𝑥) → 𝑄(𝑥)), ∀𝑥(𝑅(𝑥) → ¬𝑄(𝑥)) ⟹
3. (a) BTL -2 Understand
∀𝑥(𝑅(𝑥) → ¬𝑃(𝑥))
Write the symbolic form and negate the following statements.
1. Everyone who is healthy can do all kinds of work.
2. Some people are not admired by everyone.
3.(b) BTL -3 Apply
3. Everyone should help his neighbors or his neighbors will not help
him.
4. Everyone agrees with someone and someone agrees with everyone
Without constructing the truth tables, obtain the principle disjunctive
4. (a) BTL -1 Remember
normal form of (¬𝑝 → 𝑟) ∧ (𝑞 ↔ 𝑟)
Show that 𝑟 → 𝑠 can be derived from the premises
4.(b) BTL -3 Apply
𝑝 → (𝑞 → 𝑠), ¬𝑟 ∨ 𝑝 𝑎𝑛𝑑 𝑞
Establish this logical equivalences, where A is a proposition not involving
5. (a)
any quantifiers. Show that (∀𝑥𝑃(𝑥)) ∧ 𝐴 ≡ ∀𝑥(𝑃(𝑥) ∧ 𝐴)𝑎𝑛𝑑 (∃𝑥𝑃(𝑥)) ∧ BTL -3 Apply
𝐴 ≡ ∃𝑥(𝑃(𝑥) ∧ 𝐴)
Show that ∃ 𝑥𝑃(𝑥) ∧ ∃ 𝑥 𝑄(𝑥) and ∃ 𝑥(𝑃(𝑥) ∧ 𝑄(𝑥)) are not logically
5.(b) BTL -4 Analyze
equivalent
Show that (¬𝑃 ∧ (¬𝑄 ∧ 𝑅)) ∨ (𝑄 ∧ 𝑅) ∨ (𝑃 ∧ 𝑅) ⇔ 𝑅 without using truth
6.(a) BTL -1 Remember
table.

6.(b) Show that ∀ 𝑥𝑃(𝑥) ∧ ∃ 𝑥 𝑄(𝑥) is equivalent to ∀ 𝑥 ∃𝑦 (𝑃(𝑥) ∧ 𝑄(𝑦)) BTL -3 Apply

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 do not go
7. (a)
swimming then we will take a canoe trip” and “ If we take a canoe trip, then BTL -4 Analyze
we will be home by sunset”. Lead to the conclusion “we will be home by
sunset”.
7. (b) Prove that √2 is irrational by giving a proof by contradiction. BTL -4 Analyze
Show that the conclusion
8. (a) ∀𝑥(𝑃(𝑥) → ¬𝑄(𝑥)) follows from the premises ∃𝑥(𝑃(𝑥) ∧ 𝑄(𝑥)) → BTL -2 Understand
∀𝑦(𝑅(𝑦) → 𝑆(𝑦)) and ∃𝑦(𝑅(𝑦) ∧ ¬𝑆(𝑦))
8.(b) Prove that (𝑃 ⟶ 𝑄) ∧ (𝑅 ⟶ 𝑄) ⇔ (𝑃 ∨ 𝑅) ⟶ 𝑄) BTL -2 Understand
9. (a) Show that ∀𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) ⟹ ∀𝑥𝑃(𝑥) ∨ ∃𝑥𝑄(𝑥) by indirect method. BTL -1 Remember
Show that the statement “Every positive integer is the sum of squares of
9.(b) BTL -1 Remember
three integers” is false.
10.(a) Using indirect method of proof, derive 𝑃 ⟶ ¬𝑆 from the premises 𝑃 ⟶
BTL -1 Remember
(𝑄 ∨ 𝑹), 𝑄 → ¬𝑃, 𝑆 → ¬𝑅 𝑎𝑛𝑑 𝑃.
10.(b) Without using truth table find PCNF and PDNF of BTL -2 Understand

3
 STUDENTSFOCUS.COM
[𝑃 ⟶ (𝑄 ∧ 𝑅)] ∧ [¬𝑃 → (¬𝑄 ∧ ¬𝑅)].
Prove that the premises 𝑃 ⟶ 𝑄, 𝑄 ⟶ 𝑅, 𝑅 ⟶ 𝑆, 𝑆 ⟶ ¬𝑅 and 𝑃 ∧ 𝑆 are
11. (a) BTL -1 Remember
inconsistent.
Show that the premises “One student in this class knows how to write
program in JAVA”, and “Everyone who knows how to write the
11. (b) BTL -1 Remember
programme in JAVA can get a high paying job imply a conclusion
“someone in this class can get a high paying job” .
Show that (¬𝑃 ⟶ 𝑅) ∧ (𝑄 ↔ 𝑃) ⟺ (𝑃 ∨ 𝑄 ∨ 𝑅) ∧ (𝑃 ∨ ¬𝑄 ∨ 𝑅) ∧ (𝑃 ∨
12. (a) BTL -2 Understand
¬𝑄 ∨ ¬𝑅) ∧ (¬𝑃 ∨ 𝑄 ∨ 𝑅) ∧ (¬𝑃 ∨ 𝑄 ∨ ¬𝑅).
Use the quantifiers to express following statements. 1. there is a student in
the class who can speak Hindi.2.every student in this class knows how to
12. (b) drive a car.3.some student in this class knows has visited Alaska but not BTL -6 Create
visited Hawaii.4.all students in this class have learned at least one
programming language.
13. (a) Obtain the PDNF and PCNF of (𝑃 ∧ 𝑄) ∨ (¬𝑃 ∧ 𝑅) BTL -1 Remember
Prove that A⟶ ¬𝐷 is a conclusion from the premises
13.(b) BTL -1 Remember
𝐴 ⟶ 𝐵 ∨ 𝐶, 𝐵 ⟶ ¬𝐴 𝑎𝑛𝑑 𝐷 ⟶ ¬𝐶by using conditional proof.
Show that 𝑅 ∧ (𝑃 ∨ 𝑄)is a valid conclusion from the premises 𝑃 ∨ 𝑄, 𝑄 →
14. (a) BTL -4 Analyze
𝑅, 𝑃 → 𝑀, ¬𝑀
14. (b) Show that that ∃ 𝑥 𝑃(𝑥) ⟶ ∀𝑥 𝑄(𝑥) ⇒ ∀𝑥 (𝑃(𝑥) ⟶ 𝑄(𝑥)) BTL -2 Understand
UNIT II -COMBINATORICS
Mathematical induction – Strong induction and well ordering – The basics of counting – The
pigeonhole principle – Permutations and combinations – Recurrence relations – Solving linear
recurrence relations – Generating functions – Inclusion and exclusion principle and its applications
.
PART- A
Bloom’s
Q.No. Question Taxonom Domain
y Level
1. State the principle of strong induction. BTL -1 Remember
𝑛(𝑛+1)
2 Use mathematical induction to show that 1 + 2 + 3 + ⋯ + 𝑛 = BTL -2 Understand
2

3 Use mathematical induction to show that 𝑛! ≥ 2𝑛+1 , 𝑛 = 1,2,3, … BTL -2 Understand

4 What is well ordering principle? BTL -1 Remember
5 How many permutations are there in the word MISSISSIPPI? BTL -5 Evaluate
6 State the Pigeonhole principle. BTL -1 Remember
What is the number of arrangements of all the six letters in the word
7 BTL -5 Evaluate
PEPPER?
8 How many permutations of {a,b,c,d,e,f,g} starting with a? BTL -1 Remember
9 In how many ways can all the letters in MATHEMATICAL be arranged? BTL -3 Apply
Find the minimum of students needs to guarantee that 5 of them belongs to
10 BTL -4 Analyze
the same subject if there are 5 different major subjects
11 How many different bit strings are there of length seven? BTL -1 Remember
Twelve students want to place order of different ice creams in a ice cream
12 parlor, which has six type of ice creams. Find the number of orders that the BTL -4 Analyze
twelve students can place.
13 How many permutations are there in the word MALAYALAM? BTL -3 Apply

4
 STUDENTSFOCUS.COM
14 Find the recurrence relation for the Fibonacci sequence. BTL -2 Understand
Find the recurrence relation satisfying the equation
15 BTL -2 Understand
𝑦𝑛 = 𝐴(3)𝑛 + 𝐵(−4)𝑛
Solve the recurrence relation 𝑦(𝑘) − 8𝑦(𝑘 − 1) + 16𝑦(𝑘 − 2) = 0, 𝑘 ≥
16 2, 𝑤ℎ𝑒𝑟𝑒 𝑦(2) = 16 𝑎𝑛𝑑 𝑦(3) = 80. BTL -3 Apply

17 Find the recurrence relation of the sequence 𝑠(𝑛) = 𝑎𝑛 , 𝑛 ≥ 1 BTL -1 Remember

Find the number of non-negative integer solutions of the equation
18 BTL -6 Create
𝑥1 + 𝑥2 + 𝑥3 = 11
Determine whether the sequence {𝑎𝑛 } is a solution of the recurrence
19 relation𝑎𝑛 = 2𝑎𝑛−1 − 𝑎𝑛−2, n=2, 3, 4, … where 𝑎𝑛 = 3𝑛 for every non BTL -5 Evaluate
negative integer 𝑛.
What is the solution of the recurrence relation
20 BTL -5 Evaluate
𝑎𝑛 = 6𝑎𝑛−1 − 9𝑎𝑛−2 𝑤𝑖𝑡ℎ 𝑎0 = 1, 𝑎1 = 6
PART-B
1.(a) Using induction principles prove that 𝑛3 + 2𝑛 is divisible by 3. BTL -3 Apply
Show that if n and k are positive integers then(𝑛+1 𝑘
𝑛
) = (𝑛 + 1)(𝑘−1 )⁄𝑘.
1. (b) Use this identity to construct an inductive definition of the binomial co- BTL -1 Remember
efficient.
If we select ten points in the interior of an equilateral triangle of side 1 ,
2. (a) show that there must be atleast two points whose distance apart less than BTL -2 Understand
1/3 .
From a club consisting of six men and seven women, in how many ways
we select a committee of (1) 3 men and 4 women? (2) 4 persons which has
2.(b) BTL -2 Understand
at least one woman? (3) 4 persons that has at most one man?
(4) 4 persons that has both sexes?
There are three files of identical red, blue and green balls, where each files
contains at least 10 balls. In how many ways can 10 balls be selected? (1)
3. (a)
If there is no restriction. (2) If at least 1 red ball must be selected. (3) If at BTL -2 Understand
least 1 red, at least 2 blue and at least 3green balls must be selected. (4) If
at most 1 red ball is selected.
Prove by mathematical induction that
3.(b) 𝑛(𝑛 + 1)(2𝑛 + 1) BTL -1 Remember
12 + 22 + 32 + ⋯ + 𝑛2 =
6
State the strong induction (the second principle of mathematical induction).
4. (a)
Prove that a positive integer >1 is either a prime number or it can be BTL -4 Analyze
written as product of prime numbers.
If n pigeonholes are occupied by (𝑘𝑛 + 1) pigeons, where k is a positive
integer, prove that at least one pigeonhole is occupied by (𝑘 + 1) or more
4.(b) BTL -3 Apply
pigeons. Hence, find the minimum number of m integers to be selected
from 𝑆 = {1, 2,3 … 9} so that the sum of two of m integers is even.
Use mathematical induction to show that
5. (a) 1 1 1 BTL -2 Understand
+ +⋯+ > √𝑛, 𝑛≥2
√1 √2 √𝑛
In how many ways can six boys and four girls be arranged in straight line
5.(b) BTL -4 Analyze
so that no two girls are sit together.
6. (a) How many bits of string of length 10 contain
BTL -6 Create
1. Exactly four 1’s 2. At most four 1’s 3. At least four 1’s 4. An equal
5
 STUDENTSFOCUS.COM
number of 0’s and 1’s
6.(b)A Prove by mathematical induction that 6𝑛+2 + 72𝑛+1 is divisible by 43, for
BTL -1 Remember
each positive integer n.
7. (a) Let m be any odd positive integer. Then prove that there exist a positive
BTL -1 Remember
integer n such that m divides 2𝑛 − 1
7. (b) Prove that in a group of six people at least three must be mutual friends or
BTL -1 Remember
at least three must be mutual strangers.
A total of 1232 students have taken a course in Spanish, 879 have taken a
course in French and 114 have taken a course in Russian. Further 103 have
taken courses in both Spanish and French, 23 have taken courses in both
8. (a) BTL -1 Remember
Spanish and Russian and 14 have taken courses in both French and
Russian. If 2092 students have taken at least one Spanish, French and
Russian, how students have taken a course in all three languages?
8.(b) Prove that the number of subsets of a set having n elements is 2𝑛 BTL -1 Remember
Solve the recurrence relation
9.(a) BTL -3 Apply
𝑎𝑛 = −3𝑎𝑛−1 − 3𝑎𝑛−2 − 𝑎𝑛−3 with 𝑎0 = 5, 𝑎1 = −9 𝑎𝑛𝑑 𝑎2 = 15.
Find the solution to the recurrence relation𝑎𝑛 = 6𝑎𝑛−1 − 11𝑎𝑛−2 + 6𝑎𝑛−3
9.(b) BTL -1 Remember
with initial conditions𝑎0 = 2, 𝑎1 = 5 𝑎𝑛𝑑 𝑎2 = 15
Solve the recurrence relation
10.(a) BTL -1 Remember
𝑎𝑛+1 − 𝑎𝑛 = 3𝑛2 − 𝑛, 𝑛 ≥ 0, 𝑎0 = 3

Use the method of generating function to solve the recurrence relation

10.(b) BTL -3 Apply
𝑎𝑛 = 4𝑎𝑛−1 − 4𝑎𝑛−2 + 4𝑛 ; 𝑛 ≥ 2 𝑔𝑖𝑣𝑒𝑛 𝑡ℎ𝑎𝑡 𝑎0 = 2 𝑎𝑛𝑑 𝑎1 = 8.

Solve 𝐺(𝑘) − 7 𝐺(𝑘 − 1) + 10𝐺(𝑘 − 2) = 8𝑘 + 6, for 𝑘 ≥ 2

11.(a) BTL -5 Evaluate
𝑆(0) = 1, 𝑆(1) = 2.
Solve the recurrence relation 𝑎𝑛 = 3𝑎𝑛−1 + 2, 𝑛 ≥ 1, 𝑤𝑖𝑡ℎ 𝑎0 = 1 by
11.(b) BTL -5 Evaluate
the method of generating function.
Find the number of integers between 1 to 250 that are not divisible by any
12.(a) BTL -5 Evaluate
of the integers 2,3,5 and 7
Determine the number of positive integer n, 1 ≤ 𝑛 ≤ 2000 that are not
12.(b) BTL -2 Understand
divisible by 2, 3 or 5 but are divisible by 7.
Use the method of generating function to solve the recurrence relation
13.(a) BTL -3 Apply
𝑠𝑛 + 3𝑠𝑛−1 − 4𝑠𝑛−2 = 0, where 𝑛 ≥ 2, 𝑠0 = 3, 𝑠1 = −2
13.(b) Find the generating function of Fibonacci sequence. BTL -5 Evaluate
A factory makes custom sports cars at an increasing rate. In the 1st
Month only one car made, in the 2 nd month two cars are made, and so on
14.(a) with n cars made in the n th month.(1) Set up the recurrence relation for the BTL -6 Create
number of cars produced in the first n month by this factory.
(2) How many cars are produced in the 1styear?
Find all solutions of the recurrence relation 𝑎𝑛 − 2𝑎𝑛−1 = 2𝑛2 , 𝑛 ≥ 1,
14.(b) BTL -5 Evaluate
𝑎1 = 4.

UNIT III -GRAPHS

Graphs and graph models – Graph terminology and special types of graphs – Matrix representation of
graphs and graph isomorphism – Connectivity – Euler and Hamilton paths.
PART – A

6
 STUDENTSFOCUS.COM
Bloom’s
Q.No. Question Taxonomy Domain
Level
1. Define complete graph and draw 𝐾5 BTL -1 Remember
2. Define a regular graph. Can a complete graph be a regular graph? BTL -1 Remember
3. How many edges are there in a graph with 10 vertices each of degree 6? BTL -2 Understand
4. Define pseudo graphs. BTL -1 Remember
5. Define strongly connected graph. BTL -1 Remember
6. State the handshaking theorem. BTL -1 Remember
7. Prove that the number of odd degree vertices is always even. BTL -2 Understand
Represent the given graph using an adjacency matrix.

8. BTL -5 Evaluate

9. Define isomorphism of directed graph BTL -1 Remember

10. Define connected graph and a disconnected graph with example. BTL -1 Remember
Let G be the graph with 10 vertices. If four vertices has degree four and six
11. BTL -1 Remember
vertices has degree five , then find the number of edges of G.
How many edges does a graph have if it has vertices of degree
12. BTL -3
5, 2, 2, 2, 2, 1? Draw such a graph.
Use an incidence matrix represents the graph.

13. BTL -3 Apply

0 1 0
14. Draw the graph with the following adjacency matrix(1 0 1) BTL -2 Understand
0 1 0
15. Define a Hamilton path of 𝐺. BTL -2 Understand
What should be the degree of each vertex of a graph G if it has Hamilton
16. BTL -4 Analyze
circuit?
17. Define complete bipartite graph . BTL -6 Create
State the necessary and sufficient conditions for the existence of an Eulerian
18. BTL -4 Analyze
path in a connected graph.
For which values of 𝑛 do the graphs 𝐾𝑛 𝑎𝑛𝑑 𝐶𝑛 have an Euler path but no
19. BTL -4 Analyze
Euler circuit?
20. Does the graph have a Hamilton path? If so find such a path. BTL -6 Create

7
 STUDENTSFOCUS.COM

PART – B
Prove that the number of vertices of odd degree in a graph is always BTL -1
1.(a) Remember
even.
Prove that the maximum number of edges in a simple disconnected
1. (b) BTL -2 Understand
graph G with n vertices and k components is (𝑛 − 𝑘)(𝑛 − 𝑘 − 1)⁄2
Prove that a connected graph 𝐺 is Euler graph if and only if every
2. (a) BTL -1 Remember
vertex of 𝐺is of even degree.
Prove that a simple graph is bipartite if and only if it is possible to
2.(b) assign one of two different colors to each vertex of the graph so that BTL -2 Understand
no two adjacent vertices are assign the same color.
Examine whether the following pair of graphs are isomorphic or not.
Justify your answer.

3. (a)
BTL -5 Evaluate

Let 𝛿(𝐺)𝑎𝑛𝑑 △ (𝐺) denotes minimum and maximum degrees of all

3.(b) the vertices of 𝐺 respectively. Then show that for a non-directed graph BTL -3 Apply
2|𝐸|
𝐺, 𝛿(𝐺) ≤ |𝑉| ≤△ (𝐺)
Examine whether the following two graphs G and G’ associated with
the following adjacency matrices are isomorphic.
0 1 0 1 0 0 0 1 0 0 1 0
4. (a) 1 0 1 0 0 1 1 0 1 0 0 0 BTL -2 Understand
0 1 0 1 0 0 and 0 1 0 1 0 1 .
1 0 1 0 1 0 0 0 1 0 1 0
0 0 0 1 0 1 1 0 0 1 0 1
[0 1 0 0 1 0] [0 0 1 0 1 0]
Define isomorphism .Establish an isomorphism for the following the

4.(b) BTL -4 Analyze

graphs.
5. (a) For any simple graph 𝐺, the number of edges of 𝐺 is less than or equal
𝑛(𝑛−1) BTL -1 Remember
to 2 , where n is the number of vertices in 𝐺.
5.(b) Derive a connected graph has an Euler trail if and only if it has at most BTL -5 Evaluate

8
 STUDENTSFOCUS.COM
two vertices of odd degree.
6. (a) Prove that the complement of a disconnected graph is connected. BTL -2 Understand
Show that the following graphs 𝐺 and 𝐻 are not isomorphic.

6.(b) BTL -3 Apply

Define Isomorphism between the two graphs. Are the simple graphs
with the following adjacency matrices isomorphic?
0 1 0 0 0 1 0 1 0 0 0 1
7. (a) 1 0 1 0 1 0 1 0 1 0 0 1
0 1 0 1 0 1 and 0 1 0 1 1 0 BTL -1 Remember
0 0 1 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 1 0 1
[1 0 1 0 1 0] [1 1 0 0 1 0]

7. (b) If a graph G has exactly two vertices of odd degree there is a path
BTL -6 Create
joining these two vertices.
8. (a) Define 1. Complete graph. 2. Complete bipartite graph with example. BTL -1 Remember
8.(b) Show that the following graphs are isomorphic. BTL -4 Analyze

9. (a) Give an example of a graph which is 1. Eulerian but not Hamiltonian BTL -1 Remember
2. Hamiltonian but not Eulerian 3. Hamiltonian and Eulerian 4.
Neither Hamiltonian nor Eulerian
9.(b) How many paths of length four are there from 𝑎 to 𝑑 in the simple BTL -5 Evaluate
graph 𝐺 given below.

10.(a) 𝑛(𝑛−1) BTL -4 Analyze

Show that the complete graph 𝐾𝑛 contain different Hamilton
2
cycle.
9
 STUDENTSFOCUS.COM
10.(b) Briefly explain about sub graph with example. BTL -1 Remember
Using adjacency matrix examine whether the following pairs of graphs BTL -3 Apply
11.(a) 𝐺 𝑎𝑛𝑑 𝐺 1 given below are isomorphism or not.

11.(b) Briefly explain about walks with example. BTL -1 Remember

12.(a) Draw the complete graph 𝐾5 with vertices A, B, C, D, E. Draw all BTL -6 Create
complete sub graph of 𝐾5 with 4 vertices.
12.(b) The adjacency matrices of two pairs of graph as given below. Examine BTL -5 Evaluate
the isomorphism of 𝐺 and 𝐻 by finding a permutation matrix.𝐴𝐺 =
0 0 1 0 1 1
[0 0 1] 𝐴𝐻 = [1 0 0]
1 1 0 1 0 0
13.(a) The sum of all vertex degree is equal to twice the number of edges (or) BTL -4 Analyze
the sum of the degrees of the vertices of 𝐺 is even.
13.(b) Write the adjacency matrix of the digraph 𝐺 = BTL -1 Remember
(𝑣 , 𝑣 ), (𝑣1 , 𝑣2 ), (𝑣2 , 𝑣4 ), (𝑣3 , 𝑣1 ), (𝑣2 , 𝑣3 ), (𝑣3 , 𝑣4 ), (𝑣4 , 𝑣1 ),
{ 1 3 }.
(𝑣4 , 𝑣2 ), (𝑣4 , 𝑣3 )
Also draw the graph
14.(a) Prove that the following statements are equivalent for a simple BTL -2 Understand
connected graph.1.G is Eulerian. 2. Every vertex of 𝐺 has even degree.
14.(b) Explain cut edges and cut vertices with suitable example. BTL -1 Remember

UNIT –IV: ALGEBRAIC STRUCTURES

Algebraic systems – Semi groups and monoids - Groups – Subgroups – Homomorphism’s – Normal
Subgroup and cosets – Lagrange’s theorem – Definitions and examples of Rings and Fields.
PART-A
Bloom’s Domain
Q.No. Question Taxonom
y Level
Define semigroup and monoid. Give an example of a semigroup which
1. BTL -1 Remember
is not a monoid.
2. Give an example of sub semigroup. BTL -2 Understand
Show that semi-group homomorphism preserves the property of
3. BTL -3 Apply
idempotency.
Find the idempotent elements of 𝐺 = {1, −1, 𝑖, −𝑖} under the binary
4. BTL -2 Understand
operation multiplication
5. Prove that identity element in a group is unique. BTL -1 Remember
6. Prove that monoid homomorphism preserves invertibility. BTL -2 Understand
7. State any two properties of a group. BTL -1 Remember
Let Z be agroup of integers with binary operation * defined by 𝑎 ∗ 𝑏 =
8. BTL -2 Understand
𝑎 + 𝑏 − 2 for all 𝑎, 𝑏 ∈ 𝑍. Find the identity element of the group 〈𝑍,∗〉.
Prove that if 𝐺 is abelian group,
9. BTL -5 Evaluate
then for all 𝑎, 𝑏 ∈ 𝐺, (𝑎 ∗ 𝑏)2 = 𝑎2 ∗ 𝑏 2
10
 STUDENTSFOCUS.COM
10. Show that every cyclic group is abelian. BTL -4 Analyze
11. Prove or disprove: Every subgroup of an abelian is normal. BTL -4 Analyze
If 𝑎 is a generator of a cyclic group𝐺, then show that 𝑎−1 is also a
12. BTL -6 Create
generator of 𝐺.
13. Show that (𝑍5 , +5 ) is a cyclic group. BTL -6 Create
14. Find the left cosets of {[0], [3]} in the addition modulo group (𝑍6 , +6 ). BTL -3 Apply
15. Define kernel of a homomorphism. BTL -1 Remember
16. State Lagrange’s theorem. BTL -1 Remember
17. Define a ring and give an example BTL -1 Remember
Prove that the order of an element 𝑎 of a group 𝐺 is the same as that of
18. BTL -1 Remember
its inverse (𝑎−1 )
19. Give an example of a ring which is not a field. BTL -6
20. Define integral domain and give an example. BTL -4 Analyze
PART – B
Show that group homomorphism preserves identity, inverse, and sub BTL -1
1.(a) Remember
group
If (G,*) is a finite cyclic group generated by ab element 𝑎𝜖𝐺 and is of
1.(b) order n then 𝑎𝑛 = 𝑒 so that 𝐺 = {𝑎, 𝑎2 , … 𝑎𝑛 (= 𝑒)} . Also n is the least BTL -2 Understand
positive integer for which 𝑎𝑛 = 𝑒.
Prove that the intersection of two subgroups of a group 𝐺 is again a BTL -2
2.(a) Understand
subgroup of 𝐺
Let 𝐺 be a group and 𝑎 ∈ 𝐺. Let 𝑓: 𝐺 → 𝐺 be given by
2.(b) 𝑓(𝑥) = 𝑎𝑥𝑎 −1 , ∀ 𝑥 ∈ 𝐺. Prove that 𝑓 is an isomorphism of BTL -2 Understand
𝐺 onto 𝐺
Show that 𝑀2 , the set of all 2𝑋2 non singular matrices over 𝑅 is a group
3.(a) BTL -6 Create
under usual matrix multiplication. Is it abelian?
Show that the union of two subgroups of a group G is again a subgroup
3.(b) BTL -4 Analyze
of 𝐺 if and only if one is contained in the other.
4. (a) State and prove Lagrange’s theorem BTL -4 Analyze
If 𝑆 = 𝑁𝑋𝑁, the set of ordered pairs of positive integers with the
operation ∗ defined by (𝑎, 𝑏) ∗ (𝑐, 𝑑) = (𝑎𝑑 + 𝑏𝑐, 𝑏𝑑) and if
4.(b) BTL -5 Evaluate
𝑓: (𝑆,∗) → (𝑄, +) is defined by 𝑓(𝑎, 𝑏) = 𝑎⁄𝑏, show that 𝑓 is a semi
group homomorphism.
Prove that the set 𝑍4 = {0,1,2,3} is a commutative ring with respct ot
5. (a) BTL -1 Remember
the binary operation +4 𝑎𝑛𝑑 ×4
Determine whether 𝐻1 = {0, 5, 10} 𝑎𝑛𝑑 𝐻2 = {0, 4, 8, 12}are subgroups
5.(b) BTL -5 Evaluate
of 𝑍15 .
6. (a) Discuss Ring and Fields with suitable examples. BTL -4 Analyze
6.(b) State and prove the fundamental theorem of group homomorphism BTL -1 Remember
7. (a) Find the left cosets of the subgroup 𝐻 = {[0], [3]} of the group [Z6, +6]. BTL -5 Evaluate
7. (b) If G is a group of prime order, then G has no proper subgroups. BTL -6 Create
8. (a) Prove that the necessary and sufficient condition for a non-empty subset BTL -1 Remember
H of a group (𝐺,∗)to be a subgroup is 𝑎, 𝑏 ∈ 𝐻 ⇒ 𝑎 ∗ 𝑏 −1 ∈ 𝐻
8.(b) Let 𝑓: 𝐺,∗) → (𝐻,△) be group homomorphism then show that 𝐾𝑒𝑟(𝑓) is BTL -4 Analyze
a normal subgroup.
9. (a) Prove that every subgroup of a cyclic group is cyclic. BTL -5 Evaluate
11
 STUDENTSFOCUS.COM
9.(b) If (𝐺,∗) is an abelian group and if ∀ 𝑎, 𝑏 ∈ 𝐺. Show that BTL -5 Evaluate
(𝑎 ∗ 𝑏)𝑛 = 𝑎𝑛 ∗ 𝑏 𝑛 , 𝑓𝑜𝑟 𝑒𝑣𝑒𝑟𝑦 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 𝑛
10.(a) Define a cyclic group. Prove that any group of prime order is cyclic. BTL -6 Create
10.(b) Let (𝐻, ∙)be a subgroup of (𝐺, ∙). BTL -3 Apply
Let 𝑁 = {𝑥 /𝑥 ∈ 𝐺, 𝑥𝐻𝑥 −1 = 𝐻}. Show that (𝑁, ∙)is a subgroup of 𝐺.
11.(a) Prove that in a group G the equations BTL -3 Apply
𝑎 ∗ 𝑥 = 𝑏 𝑎𝑛𝑑 𝑦 ∗ 𝑎 = 𝑏 have unique solutions for the unknowns 𝑥 and
𝑦 as 𝑥 = 𝑎 −1 ∗ 𝑏, 𝑦 = 𝑏 ∗ 𝑎−1 when 𝑎, 𝑏 ∈ 𝐺.
11.(b) 𝑎 𝑏 BTL -1 Remember
Prove that the set of all matrices [ ]forms an abelian group with
−𝑏 𝑎
respect to matrix multiplication.
12.(a) If 𝑓: 𝐺 → 𝐺 ′ be a group homomorphism and 𝐻 is a subgroup of 𝐺 ′ , then BTL -2 Understand
𝑓 −1 (𝐻) is a subgroup of 𝐺
12.(b) Show that(𝑄 + ,∗) is an abelian group where ∗ is defined as 𝑎 ∗ 𝑏 = BTL -1 Remember
𝑎𝑏⁄2, ∀𝑎, 𝑏 ∈ 𝑄 +
13.(a) Show that the group ({1, 2, 3, 4}, 𝑋5 ) is cyclic. BTL -6 Create
13.(b) 1 0 −1 0 1 0 −1 0 BTL -2 Understand
Prove that 𝐺 = {( ),( ),( ),( )} forms an
0 1 0 1 0 −1 0 −1
abelian group under matrix multiplication.
14.(a) Prove that the set {1, −1, 𝑖, −𝑖} is a finite abelian group with respect to BTL -1 Remember
the multiplication of complex numbers.
14.(b) State and prove Cayley’s theorem. BTL -1 Remember

UNIT-V LATTICES AND BOOLEAN ALGEBRA

Partial ordering – Posets – Lattices as posets – Properties of lattices - Lattices as algebraic systems – Sub lattices
– Direct product and homomorphism – Some special lattices – Boolean algebra.

PART-A
Bloom’s
Q.No. Question Taxono
my Level
Draw a Hasse diagram of ⟨𝑋, ≤⟩ where 𝑋 = {1,2,3,4,6,8,12,24}and R
1. BTL -1 Remember
be a division relation. Find the Hasse diagram of the poset <X,R>
Show that the least upper bound of a subset B in a poset ⟨𝐴, ≤⟩is unique
2. BTL -2 Understand
if it exists.
Let 𝐴 = {𝑎, 𝑏, 𝑐}and 𝜌(𝐴) be its power set, draw a Hasse diagram of
3. BTL -1 Remember
⟨𝜌(𝐴), ⊆⟩.
4. State distributive lattice. BTL -1 Remember
Check whether the posets {(1, 3, 6, 9), 𝐷} and {(1, 5, 25, 125), 𝐷}are
5. BTL -4 Analyze
lattices or not. Justify your claim.
6. Show that the absorption laws are valid in a Boolean algebra. BTL -1 Remember
7. Define sub lattice. BTL -1 Remember
8. Define lattice homomorphism. BTL -1 Remember
9. Give an example of a lattice that is not complemented. BTL -2 Understand
10. In a lattice (𝐿, ≤), prove that 𝑎⋀(𝑎⋁𝑏) = 𝑎, ∀𝑎, 𝑏 ∈ 𝐿 BTL -2 Understand
11. When is a lattice called complete? BTL -3 Apply
12. Give an example of a distributive lattice but not complete. BTL -4 Analyze
13. Define Boolean Algebra. BTL -1 Remember

12
 STUDENTSFOCUS.COM
14. Show that in a Boolean Algebra 𝑎𝑏 ′ + 𝑎′ 𝑏 = 0 𝑖𝑓𝑓 𝑎 = 𝑏 BTL -5 Evaluate
15. Prove the Boolean identity 𝑎. 𝑏 + 𝑎. 𝑏 ′ = 𝑎. BTL -5 Evaluate
16. Is a Boolean Algebra contains six elements? Justify your answer. BTL -4 Analyze
17. What values of the Boolean variables 𝑥 𝑎𝑛𝑑 𝑦 satisfy 𝑥𝑦 = 𝑥 + 𝑦 ? BTL -3 Apply
18. State the De Morgan’s laws in Boolean algebra. BTL -4 Analyze
19. Find the values, if any, of the Boolean variable 𝑥 that satisfy 𝑥. 1 = 0 BTL -3 Apply
20. How many different Boolean functions are there of degree 7? BTL -6 Create
Part – B
1.(a) Show that every non-empty subset of a lattice has a least upper bound BTL -2
Understand
and a greatest lower bound.
Prove that in a Boolean Algebra(𝑎 ∨ 𝑏)′ = 𝑎′ ∧ 𝑏 ′ and
1. (b) BTL -2 Understand
(𝑎 ∧ 𝑏)′ = 𝑎′ ∨ 𝑏 ′
Examine whether the lattice given in the following Hasse diagram is
distributive or not?
2. (a)

Evaluate

BTL -5
If 𝑃(𝑆) is the power set of a non-empty set 𝑆, prove that
2.(b) BTL -2 Understand
{𝑃(𝑆),∪,∩,\, 𝜙, 𝑆}is a Boolean Algebra.
If 𝑆𝑛 is the set of all divisors of the positive integer 𝑛 and 𝐷 is the
3. (a)
relation of ‘division’, prove that {𝑆30 , 𝐷} is a lattice. Find also all the BTL -1 Remember
sub lattices of {𝑆30 , 𝐷} that contain six or more elements.
3.(b) Show that every chain is a distributive lattice. BTL -4 Analyze
In a complemented and distributive lattice, then prove that complement
4. (a) BTL -4 Analyze
of each element is unique.
If 𝑎, 𝑏 ∈ 𝑆, 𝑆 = {1, 2, 3, 6} 𝑎𝑛𝑑 𝑎 + 𝑏 = 𝐿𝐶𝑀 (𝑎, 𝑏),
4.(b) 𝑎. 𝑏 = 𝐺𝐶𝐷 (𝑎, 𝑏) 𝑎𝑛𝑑 𝑎′ = 6⁄𝑎 , show that {𝑆, +,∙ , ′ 1, 6} is a BTL -3 Apply
Boolean Algebra.
5. (a) Show that a complemented, distributive lattice is a Boolean Algebra. BTL -4 Analyze
Show that De Morgan’s laws hold in a Boolean Algebra that is show
5.(b) ̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅ BTL -2 Understand
that 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑥 𝑎𝑛𝑑 𝑦 , (𝑥 ∨ 𝑦) = 𝑥̅ ∧ 𝑦̅ and (𝑥 ∧ 𝑦) = 𝑥̅ ∨ 𝑦̅
Let 〈𝐿, ≤〉 be a lattice in which * and ⨁ denotes the operations of meet
6. (a) BTL -2 Understand
and join respectively. For any 𝑎, 𝑏 ∈ 𝐿 , 𝑎 ≤ 𝑏 ⇔ 𝑎 ∗ 𝑏 = 𝑎⨁𝑏 = 𝑏
6.(b) Show that every totally ordered set is a lattice. BTL -3 Apply
Show that in a lattice if 𝑎 ≤ 𝑏 ≤ 𝑐, then
7. (a)
(1) (𝑎⨁𝑏) = 𝑏 ⋆ 𝑐 and BTL -5 Evaluate
(2) (𝑎 ∗ 𝑏)⨁(𝑏 ∗ 𝑐) = 𝑏 = (𝑎⨁𝑏) ∗ (𝑎⨁𝑐).
7. (b) Show that in a Boolean algebra 𝑥 ∨ 𝑥 = 𝑥 𝑎𝑛𝑑 𝑥 ∧ 𝑥 = 𝑥 BTL -6 Create
8. (a) Show that a lattice homomorphism on a Boolean Algebra which BTL -1 Remember
preserves 0 and 1 is a Boolean homomorphism.
8.(b) In a Boolean Algebra. Show that BTL -2 Understand
(𝑎 + 𝑏 ′ )(𝑏 + 𝑐 ′ )(𝑐 + 𝑎′ ) = (𝑎′ + 𝑏)(𝑏 ′ + 𝑐)(𝑐 ′ + 𝑎)
9. (a) Let 𝐿 be a lattice, where 𝑎 ∗ 𝑏 = 𝑔𝑙𝑏(𝑎, 𝑏), 𝑎⨁𝑏 = 𝑙𝑢𝑏(𝑎, 𝑏), ∀𝑎, 𝑏 ∈ BTL -1 Remember
𝐿. Then both binary operators ∗ 𝑎𝑛𝑑 ⨁ defined as in 𝐿satisfy
13
 STUDENTSFOCUS.COM
commutative law, associative law, absorption law and idempotent law.
9.(b) Let 〈𝐿, ≤〉 be a lattice. For any 𝑎, 𝑏, 𝑐 ∈ 𝐿 the following properties hold BTL -4 Analyze
good. If 𝑏 ≤ 𝑐 ⇒ 𝑖) 𝑎 ∗ 𝑏 ≤ 𝑎 ∗ 𝑐 𝑖𝑖) 𝑎⨁𝑏 ≤ 𝑎⨁𝑐
10.(a) Consider the lattice D105 with the partial ordered relation divides then BTL -2 Understand
1. Draw the Hasse diagram of D105
2. Find the complement of each element of D105
3. Find the set of atoms of D105
4. Find the number of sub algebras of D105.
10.(b) Show that in a distributive and complemented lattice BTL -2 Understand
𝑎 ≤ 𝑏 ⇔ 𝑎 ∗ 𝑏 ′ = 0 ⇔ 𝑎′ ⨁𝑏 = 1 ⇔ 𝑏 ′ ≤ 𝑎′
11.(a) If 𝑃(𝑆) is the power set of a set 𝑆 and ∪, ∩ are taken as join and meet, BTL -1 Remember
prove that ⟨𝑃(𝑆), ⊆⟩ is a lattice. Also, prove that the modular inequality
of a lattice (𝐿, ≤),
For any 𝑎, 𝑏, 𝑐 ∈ 𝐿, 𝑎 ≤ 𝑐 ⇔ 𝑎 ∨ (𝑏 ∧ 𝑐) ≤ (𝑎 ∨ 𝑏) ∧ 𝑐.
11.(b) In any Boolean algebra, show that 𝑎𝑏 ′ + 𝑎′ 𝑏 = 0 𝑖𝑓𝑓 𝑎 = 𝑏. BTL -5 Evaluate
12.(a) Let D30 = {1,2,3,5,6,10,15, 30} and Let the relation R be divisor on BTL -5 Evaluate
D30. Find 1. All lower bounds of 10 and 15.
2. the GLB of 10 and 15
3. all upper bounds of 10 and 15
4. LUB of 10 and 15.
5. Draw the Hasse Diagram.
12.(b) In any Boolean algebra, prove that the following statements are BTL -5 Evaluate
equivalent: 1. 𝑎 + 𝑏 = 𝑏 2. 𝑎. 𝑏 = 𝑎 3. 𝑎′ + 𝑏 = 1 4. 𝑎. 𝑏 ′ = 0
13.(a) Show that in a lattice if 𝑎 ≤ 𝑏 𝑎𝑛𝑑 𝑐 ≤ 𝑑, BTL -1 Remember
Then 𝑎 ∗ 𝑐 ≤ 𝑏 ∗ 𝑑 𝑎𝑛𝑑 𝑎⨁𝑐 ≤ 𝑏⨁𝑑.
13.(b) In a distributive lattice prove that 𝑎 ∗ 𝑏 = 𝑎 ∗ 𝑐 𝑎𝑛𝑑 𝑎⨁𝑏 = 𝑎⨁𝑐 BTL -1 Remember
Imply𝑏 = 𝑐.
14.(a) Let 〈𝐿, ≤〉 be a Lattice. For any 𝑎, 𝑏, 𝑐 ∈ 𝐿 the following inequalities BTL -6 Create
known as distributive inequality hold.
(i) 𝑎⨁(𝑏 ∗ 𝑐) ≤ (𝑎⨁𝑏) ∗ (𝑎⨁𝑐)
(ii) 𝑎 ∗ (𝑏⨁𝑐) ≤ (𝑎 ∗ 𝑏)⨁(𝑎 ∗ 𝑐)
14.(b) Prove the absorption law 𝑥(𝑥 + 𝑦) = 𝑥 using the the identities of BTL -3 Apply
Boolean algebra.

*****************

14