CS/CT/CO/IT/CI (CSIT)-302 – Discrete Structure

Explain the following:

i) Euler Graph

ii) Isomorphic graphs

iii) Minimal spanning tree

iv) Height of the tree

Let Z be the group of integers with binary operation * defined by a * b = a + b - 2, for all a, b ∈ Z. Find the identity element of the group ⟨Z, *⟩.

Prove that the Complement of each element in a Boolean Algebra B is unique.

Let A be any finite set and P(A) be the power set of A. ⊆ be the inclusion relation on the elements of P(A). Draw the Hasse diagrams of (P(A), ⊆) for the following:

i) A = {a}

ii) A = {a, b}

iii) A = {a, b, c}

iv) A = {a, b, c, d}

i) Prove that p ∧ q ⇒ q ∨ p is a Tautology.

ii) Show that (p ∨ q) ∧ (¬p) ∧ (¬q) is a contradiction.

Explain complete digraph and Euler Graph using suitable example of both.

Define planar graph. Prove that for any connected planar graph, v - e + r = 2 where v, e, r is the number of vertices, edges, and regions of the graph respectively.

Prove that the relation R defined by "a is congruent to b modulo m" on the set of integers is an equivalence relation.

Prove that 5²ⁿ - 1 is divisible by 24, where n is any positive integer.

Draw the Hasse diagram representing the positive divisors of 36 and 45.

Show that the relation 'R' defined by (a, b) R (c, d) iff a + d = b + c is an equivalence relation.

Explain various Rules of Inference for Propositional Logic.

Show that every Cyclic group is Abelian. Prove that a lattice with 5 elements is not a Boolean algebra.

Define Pigeon hole Principle. Write the contra positive of the implication: "if it is Sunday then it is a holiday."

Prove that G = {0, 1, 2, 3, 4, 5, 6} is an abelian group of order 7 with respect to addition modulo 7.

Prove or disprove that intersection of two normal subgroups of a group G is again a normal subgroup of G. Define subgroup, normal subgroup, Quotient group, with an example for each.