1 (a)
Lets S={21, 22, 23, ?? 39, 40}. Determine the number of subset A of S such that:

i) |A|=5

ii) |A|=5 and the largest element in A is 30

iii) |A|=5 and the largest element is at least 30

iv) |A|=5 and the largest element is at most 30

v) |A|=5 and A consists only of odd integers.

i) |A|=5

ii) |A|=5 and the largest element in A is 30

iii) |A|=5 and the largest element is at least 30

iv) |A|=5 and the largest element is at most 30

v) |A|=5 and A consists only of odd integers.

10 M

1 (b)
Prove or disprove: For non-empty sets A and B, P(A∪B)=P(A)∪P(B) where P denotes power set.

5 M

1 (c)
In a group of 30 people, it was found that 15 people like Rasagulla, 17 like Mysorepak, 15 like Champakali, 8 like Rasagulla and Mysorepak, 11 like Mysorepak and Champakali, 8 like Champakali and Rasagulla and 5 like all three. If a person is chosen from this group, what is the probability that the person will will take exactly 2 sweets?

5 M

2 (a)
Verify that [p→(q→r)] → [(p→q)→ (p→r)] is tautology.

5 M

2 (b)
Write dual, negation, converse, inverse and contrapositive of the statement given below:

If Kabir wears brown pant. Then he will wear white shirt.

If Kabir wears brown pant. Then he will wear white shirt.

5 M

2 (c)
Define [ (puparrow q)Leftrightarrow
eg (pwedge q) ] Represent p∨q and p→q using only ↑.

5 M

2 (d)
Establish the validity or provider a counter example to show the invalidity of the following arguments:

[ i) egin{align*}&pvee q \ & eg pvee r \ & eg r \ &hline{ herefore q } end{align*} ] [ ii) egin {align*} &p\&p o r\&p o (qvee eg r)\ & eg qvee eg s \ &hline{ herefore s} end{align*} ]

[ i) egin{align*}&pvee q \ & eg pvee r \ & eg r \ &hline{ herefore q } end{align*} ] [ ii) egin {align*} &p\&p o r\&p o (qvee eg r)\ & eg qvee eg s \ &hline{ herefore s} end{align*} ]

5 M

3 (a)
For the universe of all polygons with three or four sides, define the following open statements:

i(x): all the interior angles of x are equal

h(x): all sides of x are equal

s(x): x is a square

t(x): x is a triangle

Translate each of the following statement into an English sentence and determine its truth value:

[ forall x[s(x)leftrightarrow (i(x)wedge h(x))] \ exists x[t(x) o (i(x)leftrightarrow h(x))] ]

Write the following statement symbolically and determine their truth values.

iii) Any polygon with three or four sides is either a triangle or a square

iv) For any triangle if all the interior angles are not equal, then all its sides are not equal.

i(x): all the interior angles of x are equal

h(x): all sides of x are equal

s(x): x is a square

t(x): x is a triangle

Translate each of the following statement into an English sentence and determine its truth value:

[ forall x[s(x)leftrightarrow (i(x)wedge h(x))] \ exists x[t(x) o (i(x)leftrightarrow h(x))] ]

Write the following statement symbolically and determine their truth values.

iii) Any polygon with three or four sides is either a triangle or a square

iv) For any triangle if all the interior angles are not equal, then all its sides are not equal.

8 M

3 (b)
Let p(x,y) denote the open statement x divides where the universe consists of all integers. Determine the truth values of the following statements. Justify your answers.

[ i) forall x forall y[p(x,y)wedge p(x,y) o (x=y)] \ ii) forall x forall y [p(x,y)vee p(x,y)] ]

[ i) forall x forall y[p(x,y)wedge p(x,y) o (x=y)] \ ii) forall x forall y [p(x,y)vee p(x,y)] ]

6 M

3 (c)
Prove that for every integer n, n

^{2}is even only if n is even.
6 M

4 (a)
[ Prove sum^{n}_{i=1}dfrac {1}{i(i+1)}=dfrac {n}{n+1} forall nepsilon z^+ ]

6 M

4 (b)
[ Prove 2^n3 and n epsilon z^+ ]

6 M

4 (c)
Define an integer sequence recursively by

[ a_0=a_1=a_2=1 \ a_n+a_{n+1}+a_{n-3} forall n ge 3 ] [ Prove that a_{a+2}ge left ( sqrt{2} ight )^n forall nge 0 ]

[ a_0=a_1=a_2=1 \ a_n+a_{n+1}+a_{n-3} forall n ge 3 ] [ Prove that a_{a+2}ge left ( sqrt{2} ight )^n forall nge 0 ]

8 M

Let A={α,β,γ}, B={θ,η, C={λ,μ,v}.

5 (a)
Find (A∪B)×C, A∪(B×C), (A×B)∪C and A×(B∪C).

8 M

5 (b)
Give a example of a relation from A to B × B which is not a function.

4 M

5 (c)
How many onto functions are there from (i) A to B, (ii) B to A?

2 M

5 (d)
i) Write a function f: A→C and a function g:C→A. Find g

ii) Write an invertible function f: A→C and find its inverse.

_{o}f: A→A.ii) Write an invertible function f: A→C and find its inverse.

6 M

6 (a)
Let A={1,2,3,4}, B={w,x,y,z} and C={p,q,r,s}. Consider R

i) What is the composite relation R

ii) Write relation matrices M(R

iii) Verify M(R

_{1}={(1,x), (2,w), (3,z)} a relation from A to B, R_{2}={(w,p), (z,q), (y,s), (x,p)} a relation from B to C.i) What is the composite relation R

_{1}⋅R_{2}from A to C?ii) Write relation matrices M(R

_{1}), M(R_{2}) and M(R_{1}⋅R_{2})iii) Verify M(R

_{1})⋅M(R_{2})=M(R_{1}⋅R_{2})
6 M

6 (b)
Let A={1,2,3,6,9,12,18} and define a relation R on A as xRy iff x|y. Draw the Hasse diagram for the poset (A, R).

6 M

6 (c)
Let A={1,2,3,4,5}×{1,2,3,4,5} and define R as (x

i) Verify that R is an equivalence relation on A.

ii) Determine the equivalence class [(1,3)].

iii) Determine the partition included by R.

_{1}, y_{1})R(x_{2}, y_{2}) iff x_{1}+y_{1}=x_{2}+y_{2}.i) Verify that R is an equivalence relation on A.

ii) Determine the equivalence class [(1,3)].

iii) Determine the partition included by R.

8 M

7 (a)
Define a binary operation * on Z as x*y=x+y-1. Verify that (Z, *) is an abelian group.

7 M

7 (b)
Let f:G→H be a group homomorphism onto H. If G is an abelian group, prove that H is also abelian.

7 M

7 (c)
The encoding function [ E:Z^2_2 o Z^5_2 ] is given by the generator matrix [ G=egin{bmatrix}1 &0 &1 &1 &0 \0 &1 &0 &1 &1 end{bmatrix} ]

i) Determine all the code words.

ii) Find the associated parity-check matrix H.

i) Determine all the code words.

ii) Find the associated parity-check matrix H.

6 M

8 (a)
[ If egin{bmatrix} a&b \c &d end{bmatrix}epsilon M_2(R), prove that egin{bmatrix} a&b \c &d end{bmatrix} ] is a unit of this ring if and only if ad-bc≠0

8 M

8 (b)
Let R be a ring with unity and a,b be units in R. Prove that ab is a unit of R and that (ab)

^{-1}=b^{-1}a^{-1}.
6 M

8 (c)
Find multiplicative inverse of each (non-zero) element of Z

_{7}.
6 M

More question papers from Discrete Mathematical Structures