Discrete Mathematics Structure

Represent the symmetric difference of two sets by Venn diagram.

Define the properties of Partial Order Relation.

What is Pigeonhole Principle?

Obtain the DNF of the proposition (p → q) ∧ (~p ∧ q).

Explain Quantifiers. Also write properties of quantifiers.

Find the least upper bound of {2, 9} and greatest lower bound of {60, 72}, if it exists, of the poset ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, /).

What is a generating function? Give example.

Show that the multiplicative group G = {1, -1, i, -i} is cyclic. Find its generators.

State the Kuratowski's theorem.

What is the difference between path and circuit? Define Hamiltonian path and circuit.

Participation in sports is compulsory in a college. In a class of 80 students, 60 play football, 40 play basketball. Find : (i) how many play both the games (ii) how many play football only

Let A = {1, 2, 3, 4} and consider the partition P = {{1, 2, 3}, {4}} of A. Obtain the equivalence relation R on A determined by P.

State the converse, inverse and contrapositive of the statement "If today is Easter, then tomorrow is Monday". Also construct truth table.

Solve the recurrence relation : a_r = 2a_{r-1} - a_{r-2}, r ≥ 2, with a_0 = 1, a_1 = 2.

Define the following : (i) Permutation groups (ii) Normal subgroup (iii) Homomorphism group (iv) Isomorphism group

Prove that 1^3 + 2^3 + .... + n^3 = [n(n+1)/2]^2 , n ≥ 1 by mathematical induction.

Find the chromatic polynomial, chromatic number and number of ways of proper coloring with minimum colors of the given graph : a square with vertices a,b,c,d and a diagonal edge.

Out of 250 failed students, 128 failed in Maths, 87 in Physics and 134 in aggregate, 31 failed in Maths and Physics, 54 failed in aggregate and in Maths, 30 failed in aggregate and in Physics. Find how many candidates failed : (i) In all three subjects (ii) In Maths not in Physics (iii) In aggregate but not in Maths (iv) In Physics but not in aggregate or Maths (v) In the aggregate or in Maths, but not in Physics

(a) Define tautology and prove the following : (p → q) → (~q → ~p) is tautology. (b) Define fallacy and prove the following : (p ∧ q) ∧ ~(p ∧ q) is a fallacy. (c) Prove the following : (i) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (ii) p ↔ q ≡ (p → q) ∧ (q → p)

Use generating functions to solve the recurrence relation a_r - 7a_{r-1} + 10a_{r-2} = 0 for r ≥ 2 where a_0 = 10 and a_1 = 41.

Consider an algebraic system (G, ), where G is the set of all non-zero real numbers and is a binary operation defined by a b = ab / 4, show that (G, ) is an abelian group.

(a) Find the shortest path and its length between the vertices a and h in the following weighted graph. (b) Define and explain the following by suitable example : (i) Isomorphism of graphs (ii) Planar graphs