Adv Discrete Mathematics-I - BU 2022 Question Paper

Download Original PDF

Get the official Barkatullah University print version scanned document.

🤝 Help Your Juniors!

Have previous year question papers that aren't on our website? Help the next batch of students by sending them to us! With your consent, we will proudly feature your name as a Top Contributor on our platform.

Submit Papers 📩

EF-445

M.A./M.Sc. 1^st Semester (Reg./Pvt./ATKT)

Examination, 2021-22

Maths

Paper - V (i)

Adv. Discrete Mathematics-I

Time : 3 Hours]

[Maximum Marks : Reg. 85

Pvt. 100

Note :- Attempt all questions. All questions are compulsory.

SECTION - 'A'

Objective Type Questions

1. Choose the correct answer: 15×1=15

(i) Let L = {1, 2, 3, 6, 9, 18} be a lattice under divisibility relation, then cover of 3 are

(a) 3, 6

(b) 3, 9

(d) 9, 18

(ii) The number of elements of any finite Boolean algebras is

(a) 2^k for some k ≥ 1

(b) (2k)! for some k ≥ 1

(d) k(k-1)/2 for some k ≥ 1

(iii) Maximum number of edges in a simple graph with 12 vertices is:

(a) 44

(b) 55

(d) 77

(iv) Every linear graph having n vertices, the number of edges will be:

(a) n

(b) n - 1

(d) n(n-1) / 2

(v) a + ab = a is called:

(a) Idempotent law

(b) Absorption law

(d) None of these

(vi) The number of elements of any finite Boolean algebra is:

(a) 2n, for some n ∈ I

(b) n², for some n ∈ I

(d) n(n - 1), for some n ∈ I

(vii) A graph G with n vertices, (n-1) edges and no circuit is:

(a) Connected

(b) Disconnected

(d) None of these

(viii) A tree with n vertices has:

(a) n edges

(b) (n - 1) edges

(d) (n - 2) edges

(ix) The maximum number of edges in a simple graph with n vertices is:

(a) n

(b) (n - 1)!

(d) None of these

(x) A connected graph G is a Eulerian graph if the degree of every vertex in G is:

(a) Odd

(b) Even

(d) None of these

SECTION - 'B'

Short Answer Type Questions

5×5=25

1. Prove that every finite semigroup has an idempotent element.

Show that for any commutative monoid <M, *> the set of idempotent elements of M forms a submonoid.

2. A homomorphism g from <G, *> onto <G', ∆> with kernel K is an isomorphism iff K = {e}.

Let L be the set of all factors of 12 and let "l" be the divisibility relation on L. Show that (L, |) is a lattice.

3. Prove that in any Boolean algebra B, dual of a ≤ b is b ≤ a.

Show that the Boolean function r+ (s. (s' + t). r' + (s.t)) is replaced by the following net:

4. Minimize the function

Z = c[ (c+abc) + b(acd + d(a+ce)]

5. If the intersection of two paths in a graph is a disconnected graph, then show that the union of the two paths has at least one circuit.

State Kruskal's Algorithms for minimum spanning tree.

SECTION - 'C'

Long Answer Type Questions

9×5=45

1. Prove that the direct product of any two lattices is a semi-group.

Let <S, *> and <T, *> be two subgroups.

2. Define bounded lattice and show that if {r, t, ...} is finite lattice, then L as bounded.

Let L be a lattice. For any a, b, c ∈ L, show that

(i) a + (b * c) ≤ (a + b) * (a + c)

(ii) a * (b + c) ≥ (a * b) + (a * c)

3. Find complete canonical form in three variables and show that its value is 1.

Define Boolean algebra as lattice and construct logic circuit with the help of logic gates corresponding to Boolean function f(x, y, z) = xy'z' + xy.

4. Let G be a simple graph with n vertices. If G has k components, then prove that the maximum number of edges that G can have are

(n - k)(n - k + 1) / 2

5. Define complete bipartite graph and show that a complete bipartite graph K_m,n is planar if m or n is less than or equal to 2.

State and prove Euler's formula for connected planar graph.