• Attempt any five questions.
• All questions carry equal marks.
Show that the relation 'R' defined by (a, b) R (c, d) if a + d = b + c is an equivalence relation.
If X = {1, 2, 3, 4} and R = {(x, y) | x < y}. Draw the graph of 'R' and also give its matrix.
Prove that if R is an equivalence relation on a set A, show that R⁻¹ is also an equivalence relation on A.
What is Mathematical induction? Use mathematical induction to prove that: 1.1! + 2.2! + ... + n.n! = (n + 1)! - 1 where n is a positive integer.
Find the explicit formula for the Fibonacci numbers. Use fₙ = fₙ₋₁ + fₙ₋₂ as recursive condition and f₀ = 0 and f₁ = 1 as initial condition.
Draw the Hasse diagram representing the positive divisors of 36.
Prove that the set G = {0, 1, 2, 3, 4, 5, 6} is a finite abelian group of order 7 with respect to multiplication modulo 7 as the composition in G.
State the Lagrange's Theorem with example. Also explain Permutation and Symmetric Group.
Find PDNF by constructing its PCNF of (Q ∨ P) ∧ (Q ∨ R) ∧ (∼(P ∨ R) ∨ ∼Q).
Prove that for any three propositions P, Q, R the compound proposition (P → (Q → R)) → ((P → Q) → (P → R)) is a tautology by laws of logic.
Explain Tautologies, Contradiction and Contingencies with suitable examples.
Explain the method of proving theorems by direct, indirect, contradiction and by cases.
Give a simple condition on the weights of a graph that will guarantee that there is a unique maximal spanning tree for the graph.
Define Isomorphism of graphs. What are the steps followed in discovering the Isomorphism?
Explain Eulerian and Hamiltonian graphs with examples, also draw the graphs of the following:
i) Eulerian but not Hamiltonian
ii) Hamiltonian but not Eulerian
Prove that the sum of the degree of all the vertices in a graph G is equal to twice the number of edges in G.
