Scribd
Upload
21 views2 pages

Discrete Mathematics Exam Paper 2024

Uploaded by

hacker88779910
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views2 pages

Discrete Mathematics Exam Paper 2024

Uploaded by

hacker88779910
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Code No: A63L1 R 22

BVRAJU INSTITUTE OF TECHNOLOGY, NARSAPUR


(UGC - AUTONOMOUS)
II B. Tech I Semester Regular Examinations, Jan/Feb 2024
DISCRETE MATHEMATICS
(CSE (ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING))
Time: 3 Hours Max Marks: 60
Note: This Question Paper contains two Parts A and B
 Part A is compulsory which carries 10 marks. Ten questions from five units. Answer all questions in Part
A at one place only.
 Part-B consists of 5 Questions (numbered from 2 to 6) carrying 10 marks each. Each of these questions
is from one unit and may contain a, b, c as sub-questions. For each question there will be an either/or
choice (that means there will be two questions from each unit and the student should answer only one
question).

PART – A (10x1 = 10 Marks)


1. Marks Bloom Level CO
a Define Tautology. 1 2 1
b Convert the statement “No bird can fly” into notation by using 1 2 1
quantifiers.
c Define an equivalence relation. 1 2 2
d Define bijective function. 1 2 2
e Define Monoid. 1 2 3
f Define Boolean ring. 1 2 3
g Define Pigeon hole principle. 1 2 4
h 𝑛 𝑛 𝑛 𝑛 1 2 4
What is the value of ( ) + ( ) + ( ) + ⋯ + ( ).
0 1 2 𝑛
i Define degree of a vertex. 1 2 5
j How many edges in a complete bipartite graph 𝐾𝑚,𝑛 . 1 2 5

PART – B (5x10 = 50 Marks)


Marks Bloom Level CO
2 .a 1. Construct the truth table of the proposition 5 3 1
[(𝑝 → 𝑟) ∧ (𝑞 → 𝑟)] → [(𝑝 ∨ 𝑞) → 𝑟].
2. Show that 𝑤 can be derived from the premises 5 3
¬ 𝑡 → ¬ 𝑟, ¬ 𝑠, 𝑡 → 𝑤, 𝑟 ∨ 𝑠.
OR
2.b 1. Find the principal disjunctive normal form of 5 3 1
𝑝 → [(𝑝 → 𝑞) ∧ ¬ (¬ 𝑞 ∨ ¬ 𝑝)].
2. Show that 5 3
(𝑝 → 𝑞) ∧ (𝑞 → 𝑟) ⇒ (𝑝 → 𝑟)

***
3.a 1. Let 𝐴 = {1,2,3,4,5,6,7,8,9,10} and 5 4 2
𝑅 = {(𝑥, 𝑦) / 𝑥 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑦 , 𝑤ℎ𝑒𝑟𝑒 𝑥, 𝑦 ∈ 𝐴} be a relation on 𝐴.
Then find the elements in 𝑅 and check what are the properties
does the relation 𝑅 satisfies.
2. Let 𝐴 = {1,2,3,4,5,6}. Then find the equivalence relation on 𝐴 5 3
̅̅̅̅̅
which generates the partition {1, ̅̅̅̅ , 4,6
2 , 3,5 ̅̅̅̅}.

OR
3.b 1. Construct the Hasse diagram of the poset (𝑃(𝑋), ⊆), where 5 3 2
𝑋 = {1,2,3}.
2. Define transitive closure of a relation and find the transitive
closure of the relation 5 3
𝑅 = {(𝑎, 𝑎), (𝑎, 𝑏), (𝑏, 𝑐), (𝑐, 𝑑), (𝑐, 𝑒), (𝑑, 𝑒)}.
***
4.a 1. Define the following concepts with an example. 6 3 3
a. Cyclic group. b. Lattice. c. Complimented Lattice.
2. Prove that, if every Group (G,*) has its own inverse then the 4 4
group is abelian.

OR
4.b 1. Define the following concepts with an example. 6 3 3
a. Group. b. Homomorphism. c. Isomorpism.
2. Prove that, for a group (𝐺,∗) 4 4
i) Identity Element is unique
ii) (a*b)-1 = b-1 * a-1 (where a-1 is inverse of a)
***
5.a 1. Define multinomial theorem and find the coefficient of 5 3 4
𝑥 2 𝑦 3 𝑧 4 𝑤 5 in (𝑥 + 5𝑦 − 2𝑧 − 6𝑤)14 .
2. If there are 200 faculty members that speak French, 50 that speak 5 3
Russian, 100 that speak Spanish, 20 that speak French and
Russian, 60 that speak French and Spanish, 35 that speak
Russian and Spanish, while only 10 speak French, Russian and
Spanish, then find how many speak either French or Russian or
Spanish.
OR
5.b 1. Find the coefficient of 𝑥 9 𝑦 6 in (5𝑥 + 3𝑦)15 and (2𝑥 − 9𝑦)15 . 5 3 4
2. Find the number of ways a three digit number can be formed 5
from the numbers 2,3,5,7,8,9 with and without repetition. 3
***
6.a 1. Check the following graphs are isomorphic or not. 5 3 5

2. Show that K5 is not Planar. 5 3


OR
6.b 1. Define the following graphs with an example. 5 3 5
a. Complete b. Bipartite c. Chromatic number.
2. Define Kruskal’s algorithm with an example. 5 3

***

Common questions

Powered by AI

The number of edges in a complete bipartite graph Km,n is calculated as m*n. A complete bipartite graph is a graph that divides its vertices into two disjoint sets, such that there are no edges within each set, and every possible edge that could connect a vertex from one set to a vertex from the other set is present .

The sum (n choose 0) + (n choose 1) + (n choose 2) + ... + (n choose n) equals 2^n. This is because each term (n choose k) represents the number of ways to choose k elements from a set of n elements, and the sum of these terms represents the number of subsets of a set with n elements, which is 2^n .

A tautology is a statement in propositional logic that is always true, regardless of the truth values of the individual propositions involved. It is a formula that evaluates to true under every possible valuation of its propositional variables .

An equivalence relation is a binary relation that is reflexive, symmetric, and transitive. This means that for any elements a, b, and c in a set, a relation R on set A satisfies: 1) Reflexive: aRa, 2) Symmetric: if aRb then bRa, and 3) Transitive: if aRb and bRc then aRc .

The pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. An example is if you have 10 pigeons and 9 pigeonholes, at least one pigeonhole must contain more than one pigeon .

A bijective function is a relation with both injective and surjective properties. It means that every element of the function's codomain is mapped by exactly one element of its domain. In other words, the function is both one-to-one (injective) and onto (surjective).

The degree of a vertex in a graph is defined as the number of edges that are incident to that vertex. In an undirected graph, this is simply the count of edges connected to the vertex .

The multinomial theorem is a generalization of the binomial theorem for more than two variables. It states that any power of a sum of variables can be expanded into a sum of terms, each of which is a product of a multinomial coefficient and integer powers of the variables. To find the coefficient of x^2y^3z^4w^5 in (x+5y-2z-6w)^14, you would use the formula for the multinomial coefficient which encompasses all permutations of these variables fitting the expansion pattern, specifically calculating individual contributions by each variable's raised power from the total .

Kruskal's algorithm finds a minimum spanning tree for a connected weighted graph. Its real-world applications include designing an efficient layout for electrical networks, water supply networks, and computer networks. The algorithm sorts all the edges of the graph in increasing order by cost, and then connects nodes without forming any cycle to construct the minimum spanning tree .

The statement 'No bird can fly' can be represented using quantifiers as: ∀x (Bird(x) → ¬Fly(x)). This means for all objects x, if x is a bird, then x cannot fly .

You might also like