1(a)
If A={1,4},B={4,5},C={5,7}, determine

i) (A×B)∪(A×C)

ii) (A×B)∩(A×C)

i) (A×B)∪(A×C)

ii) (A×B)∩(A×C)

2 M

1(b)
Let A={2,3,4} and B+{3,4,5,6,7}. Assume a relation R from A to B such that (x,y)∈ R when a divides 6.Determine R, its domain and range.

2 M

1(c)
Briefly explain the application of Pigeon hole principle using an example.

2 M

Solve any one question from Q.1(d) & Q.1(e)

1(d)
Show by mathematical induction:

\[1^{2}+3^{2}+5^{2}+\cdots+(2n-1)^{2}=\frac{n(2n+1)(2n-1)}{3}\]

\[1^{2}+3^{2}+5^{2}+\cdots+(2n-1)^{2}=\frac{n(2n+1)(2n-1)}{3}\]

7 M

1(e)
Let f:R→R be defined by

\[f(x)=\left\{ \begin{matrix} 2x+1, x \le 0 \\ x^2+1, x>0 \end{matrix} \right. \]

Let g:R→R be defined by

\[g(x)=\left\{\begin{matrix} 3x-7,x\le0\\x^3,x>0 \end{matrix}\right.\]

then find the composition gof

\[f(x)=\left\{ \begin{matrix} 2x+1, x \le 0 \\ x^2+1, x>0 \end{matrix} \right. \]

Let g:R→R be defined by

\[g(x)=\left\{\begin{matrix} 3x-7,x\le0\\x^3,x>0 \end{matrix}\right.\]

then find the composition gof

7 M

2(a)
Define semi group. Write its properties.

2 M

2(b)
Write short note: i) Mono-id ii) Normal subgroup

2 M

2(c)
Prove that every subgroup of a cyclic group G is cyclic

2 M

Solve any one question from Q.2(d) & Q.2(e)

2(d)
Prove that the set G={0,1,2,3,4,5} is a finite abelian group of order 6 with respect to addition module 6.

7 M

2(e)
Let(R,+,X)be a ring. The operation ⨂is defined by a ⨂b=a×b +b×a.Show that (R,+,X) is a commutative ring.

7 M

3(a)
Prove by truth table that the following is tautology-

(P↔q^r)⇒(~r→~p)

(P↔q^r)⇒(~r→~p)

2 M

3(b)
Obtain the principal disjunctive normal form of the following formula:~(p∨q)↔(p^q)

2 M

3(c)
Investigate the validity of the following argument.

2 M

Solve any one question from Q.3(d) & Q.3(e)

3(d)
Design DFA and NDFA accepting all strings over {0,1}, which end in 0 but do not contain 11 as substring.

7 M

3(e)
Prove the validity of the following argument;

"if Ram is selected in IAS examination, then he will not be able to go to London. Since Ram is going to London, he will not be selected in IAS examination".

"if Ram is selected in IAS examination, then he will not be able to go to London. Since Ram is going to London, he will not be selected in IAS examination".

7 M

4(a)
Prove that, in a graph total number of odd degree vertices is given but then number of even degree vertices may be odd.

2 M

4(b)
Distinguish between K-coloring of a graph and chromatic number of a graph.

2 M

4(c)
Define Euler and Hamiltonian graph with example.

2 M

Solve any one question from Q.4(d) & Q.4(e)

4(d)
Find minimum distance between two vertices K and L of graph, using /Dijkstra's algorithm.

7 M

4(e)
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.

7 M

5(a)
Let L={1,2,3,4,5} be the lattice shown below, Find all sub ,lattices with three or more elements.

2 M

5(b)
Write down the binomial theorem.

2 M

5(c)
Draw hasse diagram for the "less than or equal to" relation on set A={0,2,5,10,11,15}

2 M

Solve any one question from Q.5(d) & Q.5(e)

5(d)
Determine the particular solution of the recurrence relation latex

7 M

5(e)
Explain briefly:-

i)Posets ii) Permutation iii)combination iv) Total solutions

i)Posets ii) Permutation iii)combination iv) Total solutions

7 M

More question papers from Discrete Structures