DMS 2022 NEP Solved Question Paper (Discrete Mathematical Structures)
Click here to Download Discreate Mathematical Structure NEP 2022 Question Paper.
Section - A
1. Answer any Six question.
a. Define Tautology.
A compound proposition which is true for all possible truth values of its components is called as tautology(or a logical truth) .
b. If A={1,2,3,4} and B={4,5,6,7,8} then find i. AuB ii.AnB
- AuB = {1,2,3,4,5,6,7,8}
- AnB = {4}
c. Define permutation.
It is a mathematical technique to determine the number of possible arrangements in a set when the order of the arrangement matters.
- nPr = n! / (n -r)!
d. Define pigeonhole principle.
If m pigeons occupies n pigeon hole if m>n the two more pigeon occupies the same pigeon hole this statement is known as pigeonhole principle.
e. State well ordering principle.
It states that every non-empty subset of Z+ contains a smallest element.
- Ex : { S = {1,2,3,4} }
f. Define equivalence relation.
A relation r on a Set is said to be an equivalence relation if R is reflexive, symmetric and transitive.
- Ex : A = {a,b,c}
- R={(a,a)(a,b)(b,a)(b,b)(b,c)(a,c)(c,a)(c,b)(c,c)}
g. Define euler path.
An euler path is a path that goes through every edge of a graph exactly once that start and end vertex are different.
h. Define planar graph.
When a connected graph can be drawn without any edges crossing it is called planar.
Section - B
2. Answer any Three question of the following
a. Define i.Converse ii. Inverse. Write the converse and inverse of “if two triangles are congruent then they are similar”.
Solution :
i.Converse :
Converse of conditional statement “ if P then Q “ is a new statement formed by swaping the hypothesis and the conclusion of the original statement.
OR
q-àp is called the converse of p-àq.
ii.Inverse :
Inverse of a conditional statement “ if P then Q “ is a new statement formed by negating both the hypothesis and the conclusion of original statement.
OR
~p-à ~q is called the inverse or opposite of p-àq.
converse and inverse of “if two triangles are congruent then they are similar”.
1.Converse statement :
“ if two triangles are similar, then they are congruent.
2.Inverse statement :
“ if two triangles are not congruent then they are not similar”.
b. Show by means of truth table that i. ~(pvq) ~p^~q. ii. ~(p^q) ~pv~q
c. Test the validity of the Argument. “ If you work hard, then you will pass the course. If you pass the course, then you get a job, Therefore, if you work hard, then you get a job”.
Solution :
Premise 1 : If you work hard, then you will pass the course.
Premise 2: if you pass the course, then you get a job.
Conclusion : therefore, if you work hard, then you get a job.
While it is true that working hard can increase your chances of passing the course, and passing the course can increase your chances of getting a job,
It does not necessarily follow that working hard will guarantee you a job.
Hence ,
Therefore the given Argument is Invalid.
d. Prove by Direct Method. “If x is an even integer then x2 is an even integer”.
Solution :
Assume that x is an even integer. By definition this means that x can be expressed as 2n for some integer.
We can then express x square as follows :
X square = (2n) square = 4n^2
Since n is an integer, 4n^2 is also an integer.. Moreover, It can be expresses as 2 (2n^2), which shows that x square is an even integer.
Therefore , we have shown that if x is an even integer,
Then x square is also an even integer using the direct method.
3. Answer any Three question of the following
a. find the number of permutations of the word “KARNATAKA” and permutations if all A’s together “KARNATAKA” can be calculated using the formula of permutations.
Solution :
“KARNATAKA” can be calculated using the formula of permutation :
nPr = n!/(n-r)!
where n is the total number of objects, and r is the number of objects taken at a time.
Case 1:
In this case, we have 9 distinct latters in the word “KARNATAK”.
Therefore the total number of permutations of the word is :
9!/(9-9)!=9!/0!=362880.
Case 2 :
To find the number of permutations if all A’s are together. So e have 8 distinct objects to arrange we can treat the two A’s as a single object.
Therefore the number of permutations in this case is :
8!/(8-7)*2=8!/1!*2! = 20160.
Here, we divide by 2! Because the two A’s can be arranged themselves in 2! Ways.
b. Out of 17 players, 5 are bowlers how many ways a Cricket team can be formed using atleast 3 bowlers.
Solution :
The number of ways to select 3 ,4 or 5 bowlers from 5 bowlers is :
C(5,3)+C(5,4)+C(5,5)=10+5+1
= 16
Therefore 12 non-bowlers, and we need to select 8 players from them since a cricket team has “players and we have already selected 3 blowers .
The number of ways to select 8 players from 12 plyer is
C(12,8) = 495
There the total number of ways to form a cricket team using atleast 3 bowlers is :
16 * 495 = 7920
Hence ,
There are 7920 ways to perform a cricket team using atleast 3 bowlers out of 17 players with 5 bowlers.
c. In a class of 52 students, 30 are studying AI, 28 are studying ML and 13 are studying both subjects. How many in the class are studying at-least one of the subject? How many are studying neither of these subjects.
Solution :
1.To find the number of students who are studying at least one of the subjects,
we need to add the number of students studying AI and the number of students studying ML and then subtract the number of students studying both, as they have been counted twice:
Number of students studying at least one subject = number of students studying AI + number of students studying ML – number of students studying both
= 30 + 28 – 13
= 45
Therefore, 45 students are studying at least one of the subjects.
2.To find the number of students who are not studying either of the subjects,
we need to subtract the number of students studying at least one subject from the total number of students in the class:
Number of students studying neither subject = Total number of students in class – number of students studying at least one subject
= 52 – 45
= 7
Therefore, 7 students are not studying either of the subjects.
d.write a note on divide and conquer algorithms.
Solution :
Divide and conquer algorithms are commonly used in discrete mathematical structures to solve complex problems by breaking them down into smaller, more manageable subproblems.
These algorithms involve three steps:
- Divide: The problem is divided into smaller subproblems.
- Conquer: Each subproblem is solved recursively, usually using the same algorithm.
- Combine: The solutions to the subproblems are combined to solve the original problem.
- In discrete mathematical structures, divide and conquer algorithms are often used in algorithms for sorting, searching, and graph traversal.
- For example, the merge sort algorithm uses a divide and conquer approach to sort an array of numbers by dividing it into smaller subarrays, sorting the subarrays, and then merging them together to create a sorted array.
- Divide and conquer algorithms are particularly useful in discrete mathematical structures because they can be used to solve problems that would otherwise be too difficult to solve with other approaches.
- By breaking down the problem into smaller subproblems, the algorithm is able to reduce the computational complexity of the problem and make it more tractable.
4. Answer any Three question of the following
a. Prove by the method of Mathematical Induction. 1 + 2 + 3 + ……………………+n = n( n + 1 )/2.
Solution :
1 + 2 + 3 + ……………………+n = n( n + 1 )/2.
➔ let S(n) : 1+2+3+4+……………….+n=n( n+1 )/2.
For all integer n>=1
Step1 Base step :
We note that S(1) is the statement.
1=1/2 * 1(1+1)
1=1/2*2
Therefore 1=1.
Which is clearly true .
Step 2 Inductive step :
We assume that statement S(n) is true for n=k, where k is s integer and k>=1 .We assuming the following statement is true.
i.e. S(k) : 1+2+3+4+……………………….+k=k( k+1)/2
using this, defined that adding k+1 both sides.
(1+2+3+4+………………….+k)+( k+1 ) = k( k+1 )+(k+1)/2
= ( k+1 ) [1/2 * ( k+1 )] #take common ( k+1)
= ( k+1 ) [ k+2 /2]
=1/2 ( k+1 ) ( k+2 )
=1/2 ( k+1 ) ( k+1+1)
b. Let A = {a,b,c,d} where R = {(a,a),(a,d),(b,d)} and S={(a,d),(b,c),(b,d),(c,d)} . Find RoS, SoR, R2 and S2.
1.To find RoS, we need to take all pairs (x,z) such that there exists y in the set A such that (x,y) is in R and (y,z) is in S.
So we have:
For (a,d), we can use (a,a) from R and (a,d) from S.
For (b,c), there is no y in A that satisfies both (b,y) in R and (y,c) in S, so we can’t include this pair in RoS.
For (b,d), we can use (b,d) from both R and S.
For (c,d), we can use (a,d) from R and (c,d) from S.
Therefore, RoS = {(a,d),(b,d),(c,d)}.
2.To find SoR, we need to take all pairs (x,z) such that there exists y in the set A such that (x,y) is in S and (y,z) is in R.
So we have:
For (a,a), there is no y in A that satisfies both (a,y) in S and (y,a) in R, so we can’t include this pair in SoR.
For (a,d), we can use (d,a) from R and (a,d) from S.
For (b,d), we can use (d,b) from R and (b,d) from S.
For (c,d), there is no y in A that satisfies both (c,y) in S and (y,d) in R, so we can’t include this pair in SoR.
Therefore, SoR = {(a,d),(b,d)}.
3.To find R2, we need to compute the composition of R with itself:
R2 = {(a,a),(a,d),(a,b),(b,d)}
4.To find S2, we need to compute the composition of S with itself:
S2 = {(a,c),(a,d),(b,d),(b,c),(b,a),(c,d)}.
c. Let A={1,2,3,4} and R={(1,1)(1,2)(3,1)(2,1)(2,2)(3,1)(2,3)(3,2)(3,3)(4,4)} S.T.’R’ is an Equivalence Relation.
Solution :
To show that ‘R’ is an equivalence relation, we need to verify three properties:
i.Reflexivity:
For all x in A, (x,x) is in R.
We have (1,1), (2,2), (3,3), and (4,4) in R, so R is reflexive.
ii.Symmetry:
For all x, y in A, if (x,y) is in R then (y,x) is in R.
We have (1,2) and (2,1) in R, (2,3) and (3,2) in R, and (3,1) and (1,3) in R. Therefore, R is symmetric.
iii.Transitivity:
For all x, y, and z in A, if (x,y) is in R and (y,z) is in R, then (x,z) is in R.
We have (1,2) and (2,3) in R, so (1,3) must also be in R. Similarly, we have (3,1) and (1,2) in R, so (3,2) must also be in R. We also have (2,1) and (1,1) in R, so (2,1) must be in R.
Finally, we have (3,1) and (1,2) in R, so (3,2) must be in R. Therefore, R is transitive.
Since R is reflexive, symmetric, and transitive, it is an equivalence relation.
d. Write a note on Properties of Relation.
1.Reflexive Relation: A relation R on set A is said to be a reflexive if (a, a) ∈ R for every a ∈
Example: If A = {1, 2, 3, 4} then R = {(1, 1) (2, 2), (1, 3), (2, 4), (3, 3), (3, 4), (4, 4)}. Is a relation reflexive?
Solution: The relation is reflexive as for every a ∈ A. (a, a) ∈ R, i.e. (1, 1), (2, 2), (3, 3), (4, 4) ∈ R.
2.Symmetric Relation: A relation R on set A is said to be symmetric iff (a, b) ∈ R ⟺ (b, a)
Example: Let A = {1, 2, 3} and R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2)}. Is a relation R symmetric or not?
Solution: The relation is symmetric as for every (a, b) ∈ R, we have (b, a) ∈ R, i.e., (1, 2), (2, 1), (2, 3), (3, 2) ∈ R but not reflexive because (3, 3) ∉ R.
3.Antisymmetric relation : A relation R defined on a set A is said to be antisymmetric , if (a,b) ∈ R and a ~=b, the (b,a) ∉ R for all a,b ∈ to A.
Example: A = {1,2,3} by (a,b) belongs to R if a<=b.
R = {(1,1)(1,2)(1,3)(2,2)(2,3)(3,3)}
Here (1,2) ∈ R , but (2,1) ∉ R.
Therefore relation R is antisymmetric.
4.Transitive Relation : A relations R defined on a set A is said to be transitive.
If (a,b) ∈ R and (b,c) ∈ R -à (a,c) ∈ r for all a,b,c ∈ R.
Example: A ={1,2,3}
R = {(1,1)(2,2)(3,2)(3,3)}
Here a,b (2,3) or b,c (3,2)—à a,c(2,2)
5.Equivalence Relation :
A relation R on a set A is said to be an equivalence relation if R is reflexive , symmetric and transitive.
Example: A = {a,b,c}
R={(a,a)(a,b)(b,a)(b,b)(a,c)(c,a)(c,b)(c,c)}
a. find the number of permutations of the word “KARNATAKA” and permutations if all A’s together “KARNATAKA” can be calculated using the formula of permutations.
Solution :
“KARNATAKA” can be calculated using the formula of permutation :
nPr = n!/(n-r)!
where n is the total number of objects, and r is the number of objects taken at a time.
Case 1:
In this case, we have 9 distinct latters in the word “KARNATAK”.
Therefore the total number of permutations of the word is :
9!/(9-9)!=9!/0!=362880.
Case 2 :
To find the number of permutations if all A’s are together. So e have 8 distinct objects to arrange we can treat the two A’s as a single object.
Therefore the number of permutations in this case is :
8!/(8-7)*2=8!/1!*2! = 20160.
Here, we divide by 2! Because the two A’s can be arranged themselves in 2! Ways.
b. Out of 17 players, 5 are bowlers how many ways a Cricket team can be formed using atleast 3 bowlers.
Solution :
The number of ways to select 3 ,4 or 5 bowlers from 5 bowlers is :
C(5,3)+C(5,4)+C(5,5)=10+5+1
= 16
Therefore 12 non-bowlers, and we need to select 8 players from them since a cricket team has “players and we have already selected 3 blowers .
The number of ways to select 8 players from 12 plyer is
C(12,8) = 495
There the total number of ways to form a cricket team using atleast 3 bowlers is :
16 * 495 = 7920
Hence ,
There are 7920 ways to perform a cricket team using atleast 3 bowlers out of 17 players with 5 bowlers.
c. In a class of 52 students, 30 are studying AI, 28 are studying ML and 13 are studying both subjects. How many in the class are studying at-least one of the subject? How many are studying neither of these subjects.
Solution :
1.To find the number of students who are studying at least one of the subjects,
we need to add the number of students studying AI and the number of students studying ML and then subtract the number of students studying both, as they have been counted twice:
Number of students studying at least one subject = number of students studying AI + number of students studying ML – number of students studying both
= 30 + 28 – 13
= 45
Therefore, 45 students are studying at least one of the subjects.
2.To find the number of students who are not studying either of the subjects,
we need to subtract the number of students studying at least one subject from the total number of students in the class:
Number of students studying neither subject = Total number of students in class – number of students studying at least one subject
= 52 – 45
= 7
Therefore, 7 students are not studying either of the subjects.
d.write a note on divide and conquer algorithms.
Solution :
Divide and conquer algorithms are commonly used in discrete mathematical structures to solve complex problems by breaking them down into smaller, more manageable subproblems.
These algorithms involve three steps:
- Divide: The problem is divided into smaller subproblems.
- Conquer: Each subproblem is solved recursively, usually using the same algorithm.
- Combine: The solutions to the subproblems are combined to solve the original problem.
- In discrete mathematical structures, divide and conquer algorithms are often used in algorithms for sorting, searching, and graph traversal.
- For example, the merge sort algorithm uses a divide and conquer approach to sort an array of numbers by dividing it into smaller subarrays, sorting the subarrays, and then merging them together to create a sorted array.
- Divide and conquer algorithms are particularly useful in discrete mathematical structures because they can be used to solve problems that would otherwise be too difficult to solve with other approaches.
- By breaking down the problem into smaller subproblems, the algorithm is able to reduce the computational complexity of the problem and make it more tractable.
5. Answer any Three question of the following
a. Define a planar graph and graph Isomorphism.
1.Planar Graph :
- A planar graph is a type of graph that can be drawn on a two-dimensional plane in such a way that no two edges intersect except at their endpoints. This means that it is possible to represent the graph without any crossings, which makes it easier to visualize and manipulate.
2.Isomorphism :
- Two graphs are said to be isomorphic if they have the same structure, i.e., they have the same number of vertices, the same number of edges, and the same connectivity between vertices.
b. Define simple graph, Multi-graph, Directed and undirected graph.
1.Simple Graph:
- A simple graph is an undirected graph where there is at most one edge between any two vertices. That is, there are no self-loops (an edge from a vertex to itself) and no multiple edges (two or more edges between the same pair of vertices).
2.Multigraph:
- A multigraph is an undirected graph that allows multiple edges between the same pair of vertices. This means that there can be more than one edge connecting two vertices, and the edges may or may not have the same weight or direction.
3.Directed Graph:
- A directed graph, also called a digraph, is a graph where each edge has a direction associated with it. That is, the edges are ordered pairs of vertices, and the direction of the edge goes from the first vertex in the pair to the second vertex in the pair. This means that there can be edges in one direction but not in the other.
4.Undirected Graph:
- An undirected graph is a graph where the edges do not have any direction associated with them. That is, the edges are unordered pairs of vertices, and the connection between the vertices is symmetric. This means that there is no distinction between the two vertices in an edge.
c. i.Write the Recursive formula for the sequence 3,7,11,15,19,23……
The common difference equals:
D=a2-a1
D=7-4
4
The explicit formula of this sequence is:
an=3+(n-1)*4
The recursive formula of this sequence is:
an=a(n-1)+4
ii.Define In-Degree and Out-Degree.
1.In-degree:
- The in-degree of a vertex in a directed graph is the number of edges that are directed towards that vertex. In other words, it is the number of incoming edges to that vertex. It is denoted by “deg^-(v)”.
2.Out-degree:
- The out-degree of a vertex in a directed graph is the number of edges that are directed away from that vertex. In other words, it is the number of outgoing edges from that vertex. It is denoted by “deg^+(v)”.
d. Mention AuB & AnB operations on sets with Mathematical notation and Venn Diagram for each operation.
1. Union Operation :
a) The union of two sets A and B, denoted by A ∪ B, is the set of all elements that are in A or in B, or in both.
Mathematically: A ∪ B = {x : x ∈ A or x ∈ B}
Venn Diagram:
2. Intersection Operation :
b) The intersection of two sets A and B, denoted by A ∩ B, is the set of all elements that are in both A and B.
Mathematically: A ∩ B = {x : x ∈ A and x ∈ B}
Venn Diagram:
