Hall Ticket Number:

Subject Code: 22MA401BS R22

TEEGALA KRISHNA REDDY ENGINEERING COLLEGE

(UGC- AUTONOMOUS)
[Link] II Year II Semester Regular/Supplementary Examinations, April – 2025
DISCRETE MATHEMATICS
(Common to CSE, IT, AIML, CSG)
Date: 28.04.2025 SESSION: FN
Time: 03 Hours Max. Marks: 60
Note: i) Student should verify the subject name, subject code, regulation and semester on the question paper. Any discrepancy, inform to the Invigilator immediately.
ii) Enter your Hall Ticket Number on this question paper in the space provided immediately after receiving the question paper from the Invigilator.
iii) This question paper contains two parts A and B.
iv) Part A is compulsory which carries 10 marks. Answer all questions in Part A.
v) Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 10 marks and may have a, b as sub questions.
BT
[Link] Questions Marks Unit CO
Level
s
PART- A

Q.1. (a) What is the truth value of (p∨¬p) for any proposition p? 1 I 2 1

(b) Find the contrapositive of the statement: "If it rains, then the ground is wet." 1 I 2 1

(c) If A={1,2} and B={2,3}, find A∪B. 1 II 2 2

(d) Define an injective (one-to-one) function. 1 II 1 2

(e) In Boolean algebra, what is the complement of 0? 1 III 2 3

(f) Define a lattice. 1 III 1 3

(g) Find the value of 5C2. 1 IV 2 4

(h) Expand (a+b)2 using the binomial theorem. 1 IV 1 4

(i) How many edges does a tree with 10 vertices have? 1 V 2 5

(j) What is the degree of every vertex in a complete graph K5? 1 V 2 5

PART- B

Q.2. (a) Prove that (p ∨ (q ∧ r)) → ((p ∨ q) ∧ (p ∨ r)) is a tautology. 5 I 5 1

(b) Construct a formal proof using predicate calculus inference rules: Given 5 I 6 1
∀x (P(x) → Q(x)) and ∀x (Q(x) → R(x)), prove ∀x (P(x) → R(x)).

OR
Q.3. (a) Obtain the principal conjunctive normal form (PCNF) of (p ↔ q). 5 I 3 1

(b) Translate the statement into logical notation and negate it: 'Some students 5 I 3 1
like only math.'

Q.4. (a) Let A = {1,2,3} and B = {4,5}. Find all relations from A to B that are 5 II 3 2

functions and determine which are injective.

(b) If f: A → B and g: B → C are both bijective functions, prove that g ∘ f is also 5 II 5 2

bijective.
OR
Q.5. (a) Draw the Hasse diagram of the partially ordered set (P(S), ⊆) 5 II 2 2

where S = {a, b, c}.

(b) Prove DeMorgan’s law for sets: (A ∪ B)' = A' ∩ B'. 5 II 4 2

 Hall Ticket Number:

Subject Code: 22MA401BS R22

Q.6. (a) Show that the set of all positive rational numbers forms an abelian group 5 III 3 3

under the composition defined by a*b=(ab)/2

(b) Let (S, *) be a semigroup. If a * a = a for all a ∈ S, show that (S, *) is a band. 5 III 4 3

OR

Q.7. (a) Find the complement of the given Boolean expression, 5 III 5 3

for all x, y: x + (x' ⋅ y) = x + y.

(b) Determine whether the set of non-zero real numbers under multiplication 5 III 4 3

forms a group.

Q.8. (a) Find the number of ways to arrange the letters of the word 'ENGINEERING' 5 IV 3 4

such that no two identical letters are adjacent.

(b) Expand (2x - 3y)5 completely using the Binomial Theorem. 5 IV 3 4

OR

Q.9. (a) How many permutations of the word 'BANANA' are there? 5 IV 2 4

(b) Find the coefficient of x⁵y³ in the expansion of (2x + 3y)8. 5 IV 3 4

Q.10. (a) Find all the spanning trees of a graph with vertices V = {A, B, C} and edges 5 V 3 5

{(A,B), (B,C), (C,A)}.

(b) State and prove Euler's formula for planar graphs and use it to verify 5 V 5 5

planarity of a given graph with V = 6, E = 10, F = 6.

OR
Q.11. (a) State and prove the Handshaking Theorem. 5 V 5 5

(b) Using Kruskal’s algorithm, find minimal spanning tree of the weighted graph 5 V 4 5

given below:

*****