STUPIDSID
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, n2 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 gof: A→A.
ii) Write an invertible function f: A→C and find its inverse.
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 R1={(1,x), (2,w), (3,z)} a relation from A to B, R2={(w,p), (z,q), (y,s), (x,p)} a relation from B to C.
i) What is the composite relation R1⋅R2 from A to C?
ii) Write relation matrices M(R1), M(R2) and M(R1⋅R2)
iii) Verify M(R1)⋅M(R2)=M(R1⋅R2)
i) What is the composite relation R1⋅R2 from A to C?
ii) Write relation matrices M(R1), M(R2) and M(R1⋅R2)
iii) Verify M(R1)⋅M(R2)=M(R1⋅R2)
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 (x1, y1)R(x2, y2) iff x1+y1=x2+y2.
i) Verify that R is an equivalence relation on A.
ii) Determine the equivalence class [(1,3)].
iii) Determine the partition included by R.
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-1a-1.
6 M
8 (c)
Find multiplicative inverse of each (non-zero) element of Z7.
6 M
More question papers from Discrete Mathematical Structures