• Attempt any five questions.
• All questions carry equal marks.
Prove that P(A) ⊆ P(B) if and only if A ⊆ B.
Suppose that R is the relation on the set of strings of English letters such that aRb if and only if l(a) = l(b), where l(x) is the length of the string x. Is R an equivalence relation?
Illustrate the concept of an inverse function. Let f : Z → Z be such that f(x) = x + 1. Is f invertible? if it is then what is its inverse?
Define group. Explain the properties of groups.
Let S = N × N. Let * be the operation on S defined by (a, b) * (a', b') = (aa', bb').
i) Define f : (S, *) → (Q, ×) by f(a, b) = a/b. Show that f is a homomorphism.
ii) Find the congruence relation ∼ in S determined by the homomorphism f, that is, where x ∼ y if f(x) = f(y).
Show that the ((p ∨ q) ∧ ¬p) → q compound proposition is a tautology.
Use existential and universal quantifiers to express the statement. "No one has more than three grandmothers" using the propositional function G(x, y), which represents "x is the grandmother of y."
Discuss the 6 tuple notation of finite state machine M with an example.
Consider the complete weighted graph G in the following figure with 5 vertices. Find a Hamiltonian circuit of minimal weight.
Discuss the various applications of graph colouring.
State Euler's formula for a planar graph. Give an example of a planar graph with 5 vertices and 5 regions and verify Euler's formula for your example.
Consider the set A = {4, 5, 6, 7}. Let R be the relation ≤ on A. Draw the directed graph and the Hasse diagram of R.
Consider the lattice M in the following figure.
i) Find the non-zero join irreducible elements and atoms of M.
ii) Is M distributive and complemented?
Discuss in brief any two of the following:
i) Partial ordering relation
ii) Cosets
iii) Disjunctive normal form
iv) Pigeonhole principle
