Discrete Mathematics Winter 2022 GTU Paper Solution | 3140708

by

Here, We provide Discrete Mathematics GTU Paper Solution Winter 2022. Read the Full DM GT&C GTU paper solution given below.

Discrete Mathematics GTU Old Paper Winter 2022 [Marks : 70] : Click Here

(a) A committee 5 persons, is to be formed from 6 men and 4 women. In how many ways this can be done when (i) at least 2 women are included, (ii) at most 2 women are included.

(i) To find the number of ways to form a committee with at least 2 women, we can use the principle of inclusion-exclusion.

The total number of ways to form a committee of 5 people from 10 is: 10C5 = 252

Now, we need to subtract the number of committees with 0 or 1 woman: 6C5 * 4C0 + 6C4 * 4C1 = 6 + 360 = 366

But we’ve double-counted the committees with 0 women and 0 men, so we need to add those back in: 6C0 * 4C5 = 0 Total = 252 – 366 + 0 = 114

Therefore, there are 114 ways to form a committee with at least 2 women.

(ii) To find the number of ways to form a committee with at most 2 women, we can count the number of committees with 0, 1, or 2 women, and add them up.

The number of committees with 0 women is: 6C5 * 4C0 = 6

The number of committees with 1 woman is: 6C4 * 4C1 = 360

The number of committees with 2 women is: 6C3 * 4C2 = 180

Total = 6 + 360 + 180 = 546

Therefore, there are 546 ways to form a committee with at most 2 women.

(b) If A ={4,5,7,8,10} , B={4,5,9} and C={1,4,6,9} , then verify that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

(c) Define Functionally complete set of connectives, Principal Disjunctive Normal Form (PDNF). Obtain PDNF for the expression ~(( p ˄ q ) ˅ ( ̴ p ˄ q ) ˅ ( q ˄ r ))

(a) Define Partial Order Relation. Illustrate with an example.

A partial order relation is a binary relation that is reflexive, antisymmetric, and transitive. In other words, it is a relation that can be used to compare elements of a set, such that each element is related to itself, and if element A is related to element B, and element B is related to element C, then element A is related to element C.

More formally, let R be a binary relation on a set A. Then R is a partial order relation if it satisfies the following three properties:

  1. Reflexivity: for all a ∈ A, aRa.
  2. Antisymmetry: for all a, b ∈ A, if aRb and bRa, then a = b.
  3. Transitivity: for all a, b, c ∈ A, if aRb and bRc, then aRc.

An example of a partial order relation is the “less than or equal to” relation on the set of natural numbers. Let N be the set of natural numbers. Then the relation “less than or equal to”, denoted by ≤, is a partial order relation on N, because it satisfies the three properties of a partial order relation:

  1. Reflexivity: for all n ∈ N, n ≤ n.
  2. Antisymmetry: for all m, n ∈ N, if m ≤ n and n ≤ m, then m = n.
  3. Transitivity: for all k, m, n ∈ N, if k ≤ m and m ≤ n, then k ≤ n.

For example, 2 ≤ 2, 2 ≤ 3, and 2 ≤ 4. However, 3 is not less than or equal to 2, so 3 ≤ 2 is not true. Similarly, if 2 ≤ 3 and 3 ≤ 4, then 2 ≤ 4.

(b) Define one – one function. Show that the function
f: R -> R , f (x) = 3x – 7 is one – one and onto both. Also find its inverse.

(c) Solve the recurrence relation aₙ₊₂-5aₙ₊₁+6aₙ = 2with initial condition a₀ = 1 and a₁ = -1 using method of undetermined coefficients.

(c) Use generating function to solve a recurrence relation aₙ = 3aₙ₋₁ + 2 with a₀ = 1.

(a) Define Partition of a Set. Let
A = {1,2,3,4,5} and R ={(1,2) , (1,1) , (2,1) , (2,2) , (3,3) , (4,4) , (5,5)}
be an equivalence relation on A.
Determine the partition for R⁻¹,if it an equivalence relation.

A partition of a set A is a collection of non-empty subsets of A such that every element of A belongs to exactly one subset in the collection.

In this case, the equivalence relation R on A = {1, 2, 3, 4, 5} is given by:

R = {(1, 2), (1, 1), (2, 1), (2, 2), (3, 3), (4, 4), (5, 5)}

To find the partition of R⁻¹, we need to first find R⁻¹:

R⁻¹ = {(2, 1), (1, 1), (1, 2), (2, 2), (3, 3), (4, 4), (5, 5)}

Note that R⁻¹ is also an equivalence relation, since it is the inverse relation of an equivalence relation. To find the partition of R⁻¹, we can group together the elements that are related by R⁻¹.

Starting with the element 1, we can see that it is related to both 1 and 2 under R⁻¹, so we group them together:

{1, 2}

Next, we move on to 3, which is only related to itself under R⁻¹, so we put it in its own subset:

{3}

We continue with the remaining elements, which are only related to themselves under R⁻¹:

{4}

{5}

Therefore, the partition of R⁻¹ is:

{{1, 2}, {3}, {4}, {5}}

Note that this is a valid partition of A, since each element belongs to exactly one subset in the collection.

(b) Draw Hasse Diagram for the lattice (S₃₀, D) where S₃₀
is the set of divisors of 30 and D is the relation divides.

(c) Show that the set S of all matrices of the form
[ a b]
[-b a] where a b ∈ R ,
is a field with respect to matrix addition and matrix multiplication.

OR

(a) Define Semi Group, Monoid. Give an example of an algebraic structure
which is semi group but not monoid.

A semigroup is an algebraic structure consisting of a set and an associative binary operation defined on it. Formally, a semigroup is denoted as (S, ∗), where S is a non-empty set and ∗ is an associative binary operation on S.

A monoid is a semigroup with an identity element. Formally, a monoid is denoted as (S, ∗), where S is a non-empty set, ∗ is an associative binary operation on S, and there exists an identity element e ∈ S such that for any element a ∈ S, e ∗ a = a ∗ e = a.

An example of an algebraic structure that is a semigroup but not a monoid is the set of all positive integers under addition. Addition is an associative operation, but there is no identity element in this set.

(b) Consider the a relation R defined on A ={1,2,3}, whose matrix
representation is given below. Determine its inverse R⁻¹
and complement R’.
[1 0 0]
M(R) = [1 1 1]
[0 0 1]

(c) Define free variable and bound variable.
Rewrite the following argument using quantifiers, variables and predicate
symbols. Prove the validity of the argument.

“All healthy people eat an apple a day.
Ram does not eat apple a day.
Ram is not a healthy person.”

(a) Define Abelian group and prove that the set {0,1,2,3,4} is a finite abelian group under addition modulo 5 as binary operation.

An Abelian group is a set G together with a binary operation + such that the following conditions are satisfied:

  1. Closure: For all a, b in G, a + b is in G.
  2. Associativity: For all a, b, and c in G, (a + b) + c = a + (b + c).
  3. Identity: There exists an element e in G such that for all a in G, a + e = e + a = a.
  4. Inverse: For every element a in G, there exists an element b in G such that a + b = b + a = e.
  5. Commutativity: For all a and b in G, a + b = b + a.

Now, let’s prove that the set {0,1,2,3,4} is a finite Abelian group under addition modulo 5.

  1. Closure: For any two elements a and b in {0,1,2,3,4}, a + b is also in {0,1,2,3,4}. This is because if we add any two numbers in {0,1,2,3,4} and take the result modulo 5, the result will still be in {0,1,2,3,4}.
  2. Associativity: Addition modulo 5 is associative, meaning that (a + b) + c = a + (b + c) for all a, b, and c in {0,1,2,3,4}.
  3. Identity: The element 0 is the identity element of the group, since for any element a in {0,1,2,3,4}, a + 0 = 0 + a = a.
  4. Inverse: For every element a in {0,1,2,3,4}, there exists an element b in {0,1,2,3,4} such that a + b = b + a = 0. For example, 1 + 4 = 4 + 1 = 0.
  5. Commutativity: Addition modulo 5 is commutative, meaning that a + b = b + a for all a and b in {0,1,2,3,4}.

Therefore, the set {0,1,2,3,4} under addition modulo 5 is a finite Abelian group.

(b) Define even permutation. Show that the permutation
(1 2 3 4 5 6) (1 2 3 4 5 6)
(5 6 2 4 1 3) is odd and (6 3 4 5 2 1) is even.

(c) Define Principal Ideal. Find all the principal Ideal of the ring
[{0,1,2,3,4,5},+₆,x₆].

OR

(a) Define cut vertex. List out all the cut vertices of the graph given in Figure 1.

A cut vertex is a vertex of a graph whose removal would disconnect the graph. In other words, if we remove a cut vertex from a graph, the graph would become disconnected.

To find the cut vertices of the given graph, we can use the following algorithm:

  1. For each vertex v in the graph, remove v and check if the resulting graph is disconnected.
  2. If the graph is disconnected, then v is a cut vertex.

Using this algorithm, we can see that the cut vertices of the given graph in Figure 1 are:

  • Vertex 1
  • Vertex 3
  • Vertex 5

(b) Define adjacency matrix and path matrix of a graph. Find out adjacency
matrix for the graph given in Figure 1.

(c) Define the terms: Simple Graph, Multi – Graph, Weighted Graph, Degree
of a vertex, in degree and out degree of a vertex. Illustrate each with an
example.

OR

(a) State Lagrange’s theorem and find out all possible subgroups of group
[{1,-1,i,-i},x].

Lagrange’s theorem states that for any finite group G and any subgroup H of G, the order of H divides the order of G.

In the group [{1,-1,i,-i},x], there are several subgroups:

  1. {1}: This is the trivial subgroup, consisting only of the identity element.
  2. [{1,-1},x]: This subgroup consists of the identity element and the two elements -1 and 1.
  3. [{1,-1,i,-i},x]: This is the full group, consisting of all four elements.
  4. [{1,-1},x], [{1,i},x], [{1,-i},x], [{1,i,-1,-i},x]: These are the four subgroups of order 2, each consisting of the identity element and one other element.

Note that Lagrange’s theorem applies to each of these subgroups, since each subgroup has an order that divides the order of the full group [{1,-1,i,-i},x], which is 4.

(b) Define Eulerian graph, Planar Graph.
Justify whether the graph given in Figure 1 is Planer or not using Euler’s
formula.

(c) Define Binary tree, Spanning tree, Minimal Spanning tree, Find the
minimal spanning tree for the weighted graph given in Figure 2.

OR

(a) Define Cyclic group, Normal subgroup. Illustrate with an example.

A cyclic group is a group generated by a single element. That is, a group G is cyclic if there exists an element a in G such that every element of G can be written as a power of a.

For example, the group of integers under addition is cyclic, generated by the element 1. That is, every integer can be written as a power of 1. Similarly, the group of nth roots of unity under multiplication is cyclic, generated by the element e^(2πi/n).

A normal subgroup H of a group G is a subgroup that is invariant under conjugation by elements of G. That is, for any g in G and h in H, the element g⁻¹hg is also in H.

For example, in the group of integers under addition, any subgroup is normal. In the group of 2×2 invertible matrices under matrix multiplication, the subgroup of matrices with determinant 1 is normal.

(b) Form a binary search tree for the data 16,24,7,5,8,20,40,3.

(c) Explain Post order traversal. Given the postorder and inorder traversal of
a binary tree, draw the unique binary tree.
Postorder: d e c f b h i g a
Inorder: d c e b f a h g i.

“Do you have the answer to any of the questions provided on our website? If so, please let us know by providing the question number and your answer in the space provided below. We appreciate your contributions to helping other students succeed.”