SetsAndRelation
Question 1 
For the composition table of a cyclic group shown below
Which one of the following choices is correct?
a, b are generators
 
b, c are generators
 
c, d are generators
 
d, a are generators

Question 1 Explanation:
Each element of set can be written as a power of g in multiplicative notation, or as a multiple of g in additive notation. This element g is called a generator of the group.
We can observe that, a is an identity element. ( a *x = x ). An identity element cannot be a generator, as it cannot produce any other element ( always a*a*... = a).
Also, b*b =a, so it also cannot produce all other elements ( always b*b*... =a , where a is identify element).
c,d are able to produce other elements like { c*c =b, c*(c*c) = c*b= d, c*(c*(c*c))) = c*(c*b)= c*d=a. }. Similar with d.
We can observe that, a is an identity element. ( a *x = x ). An identity element cannot be a generator, as it cannot produce any other element ( always a*a*... = a).
Also, b*b =a, so it also cannot produce all other elements ( always b*b*... =a , where a is identify element).
c,d are able to produce other elements like { c*c =b, c*(c*c) = c*b= d, c*(c*(c*c))) = c*(c*b)= c*d=a. }. Similar with d.
Question 2 
If P, Q, R are subsets of the universal set U, then (P∩Q∩R) ∪ (P^{c}∩Q∩R) ∪ Q^{c }∪ R^{c} is
Q^{c} ∪ R^{c}
 
P ∪ Q^{c} ∪ R^{c}
 
P^{c} ∪ Q^{c} ∪ R^{c}
 
U 
Question 2 Explanation:
Given, (P∩Q∩R)∪(P^{c}∩Q∩R)∪Q^{c}∪R^{c}
It can be written as the p.q.r + p'.q.r +q'+r'
=> (p+p').q.r + q' +r'
=> q.r +(q'+r')
=> q.r + q'+r' = 1 i.e U
It can be written as the p.q.r + p'.q.r +q'+r'
=> (p+p').q.r + q' +r'
=> q.r +(q'+r')
=> q.r + q'+r' = 1 i.e U
Question 3 
(i) and (iv) only  
(ii) and (iii) only  
(iii) only  
(i), (ii) and (iv) only 
Question 3 Explanation:
If a hasse diagram is a lattice then every pair of elements will have exactly one lub and gub.
(ii) and (iii), having more than one lub or glb for some pairs due to which they are not lattice.
(ii) and (iii), having more than one lub or glb for some pairs due to which they are not lattice.
Question 4 
Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:
n and n  
n^{2} and n  
n^{2} and 0  
n and 1 
Question 4 Explanation:
A relation is said to be equivalent relation if it satisfies,
→ Reflexive
→ Symmetric
→ Transitive
Let a set S be,
S = {1, 2, 3}
Now, the smallest relation which is equivalence relation is,
S×S = {(1,1), (2,2), (3,3)}
= 3
= n (for set of n elements)
And, the largest relation which is equivalence relation is,
S×S = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}
= 9
= 3^{2}
= n^{2} (for set of n elements)
→ Reflexive
→ Symmetric
→ Transitive
Let a set S be,
S = {1, 2, 3}
Now, the smallest relation which is equivalence relation is,
S×S = {(1,1), (2,2), (3,3)}
= 3
= n (for set of n elements)
And, the largest relation which is equivalence relation is,
S×S = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}
= 9
= 3^{2}
= n^{2} (for set of n elements)
Question 5 
How many different nonisomorphic Abelian groups of order 4 are there?
2  
3  
4  
5 
Question 5 Explanation:
In this problem first of all we find the exponents of prime nos. that can be taken out from given number.
4 = 2^{2}
So, prime no. is 2 and power of 2 is 2. So exponent value 2 is considered now.
Now the no. of ways we can divide 2 into sets will be the answer.
So division can be done as,
{1,1}, {0,2}
in two ways. Hence, answer is 2.
4 = 2^{2}
So, prime no. is 2 and power of 2 is 2. So exponent value 2 is considered now.
Now the no. of ways we can divide 2 into sets will be the answer.
So division can be done as,
{1,1}, {0,2}
in two ways. Hence, answer is 2.
Question 6 
A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division.
i. (0, 0) ∊ P.
ii. (a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P.
Consider the following ordered pairs:
i. (101, 22)
ii. (22, 101)
iii. (145, 265)
iv. (0, 153)
Which of these ordered pairs of natural numbers are contained in P?
(i) and (iii)  
(ii) and (iv)  
(i) and (iv)  
(iii) and (iv) 
Question 6 Explanation:
For ordered pair (a, b) to be in P, each digit in starting from unit place must not be larger than the corresponding digit in b.
The given condition can be satisfied by
(iii) (145, 265) → 5 ≤ 5, 4 < 6 and 1< 2
(iv) (0, 153) → 0 < 3
The given condition can be satisfied by
(iii) (145, 265) → 5 ≤ 5, 4 < 6 and 1< 2
(iv) (0, 153) → 0 < 3
Question 7 
A logical binary relation □ ,is defined as follows:
Let ~ be the unary negation (NOT) operator, with higher precedence than □. Which one of the following is equivalent to A∧B ?
(~A B)  
~(A ~B)  
~(~A ~B)  
~(~ A B) 
Question 7 Explanation:
Question 8 
Let E, F and G be finite sets. Let X = (E ∩ F)  (F ∩ G) and Y = (E  (E ∩ G))  (E  F). Which one of the following is true?
X ⊂ Y  
X ⊃ Y
 
X = Y  
X  Y ≠ ∅ and Y  X ≠ ∅

Question 8 Explanation:
Let us consider
E = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}
F = {(1,1), (2,2), (3,3)}
G = {(1,3), (2,1), (2,3), (3,1)}
X = (E∩F)  (F∩G)
= {(1,1), (2,2), (3,3)  ∅}
= {(1,1), (2,2), (3,3)} (✔️)
Y = (E  (E∩G)  (E  F))
= (E  {(1,3), (2,3), (3,1)}  {(1,2), (1,3), (2,3), (3,1)})
= {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}  {(1,3), (2,2), (2,1)}  (1,2), (1,3), (2,3), (3,1)}
= {(1,1), (1,2), (2,2), (3,3)}  {(1,2), (1,3), (2,3), (3,1)}
= {(1,1), (2,2), (3,3)} (✔️)
X = Y
X = (E∩F)  (F∩G) = {2,5}  {5} = {2}
Y = (E  (E∩G)  (E  F))
= {(1,2,4,5)  (4,5)  (1,4)}
= {(1,2)  (1,4)}
= {2}
X = Y
E = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}
F = {(1,1), (2,2), (3,3)}
G = {(1,3), (2,1), (2,3), (3,1)}
X = (E∩F)  (F∩G)
= {(1,1), (2,2), (3,3)  ∅}
= {(1,1), (2,2), (3,3)} (✔️)
Y = (E  (E∩G)  (E  F))
= (E  {(1,3), (2,3), (3,1)}  {(1,2), (1,3), (2,3), (3,1)})
= {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}  {(1,3), (2,2), (2,1)}  (1,2), (1,3), (2,3), (3,1)}
= {(1,1), (1,2), (2,2), (3,3)}  {(1,2), (1,3), (2,3), (3,1)}
= {(1,1), (2,2), (3,3)} (✔️)
X = Y
X = (E∩F)  (F∩G) = {2,5}  {5} = {2}
Y = (E  (E∩G)  (E  F))
= {(1,2,4,5)  (4,5)  (1,4)}
= {(1,2)  (1,4)}
= {2}
X = Y
Question 9 
Given a boolean function f (x_{1}, x_{2}, …, x_{n}), which of the following equations is NOT true.
f (x_{1}, x_{2}, …, x_{n}) = x_{1}’f(x_{1}, x_{2}, …, x_{n}) + x_{1}f(x_{1}, x_{2}, …, x_{n})  
f (x_{1}, x_{2}, …, x_{n}) = x_{2}f(x_{1}, x_{2}, …, x_{n}) + x_{2}’f(x_{1}, x_{2}, …, x_{n})  
f (x_{1}, x_{2}, …, x_{n}) = x_{n}’f(x_{1}, x_{2}, …, 0) + x_{n}f(x_{1}, x_{2}, …,1)  
f (x_{1}, x_{2}, …, x_{n}) = f(0, x_{2}, …, x_{n}) + f(1, x_{2}, .., x_{n}) 
Question 9 Explanation:
Proceed by taking f(x_{1}) = x,
LHS: f(x_{1}) = 0 where x_{1} = 0
LHS: f(x_{1}) = 1 when x1 = 1
RHS: f(0) + f(1) = 0 + 1 = always 1
LHS: f(x_{1}) = 0 where x_{1} = 0
LHS: f(x_{1}) = 1 when x1 = 1
RHS: f(0) + f(1) = 0 + 1 = always 1
Question 10 
Let P, Q and R be sets let Δ denote the symmetric difference operator defined as PΔQ = (P U Q)  (P ∩ Q). Using Venn diagrams, determine which of the following is/are TRUE? PΔ (Q ∩ R) = (P Δ Q) ∩ (P Δ R) P ∩ (Q ∩ R) = (P ∩ Q) Δ (P Δ R)
1 only  
2 only  
Neither 1 nor 2  
Both 1 and 2 
Question 10 Explanation:
P = {1, 2, 4, 5}
Q = {2, 3, 5, 6}
R = {4, 5, 6, 7}
(1) P Δ (Q ∩ R) = (P Δ Q) ∩ (P Δ R)
P Δ ({2,3,5,6} ∩ {4,5,6,7}) = ({1,2,4,5} Δ {2,3,5,6} ∩ {1,2,4,5} Δ {4,5,6,7})
P Δ {5,6} = ({1,2,3,4,5,6}  {2,5}) ∩ ({1,2,4,5,6,7}  {4,5})
({1,2,4,5} Δ {5,6}) = {1,3,4,6} ∩ {1,2,6,7}
{1,2,4,5,6}  {5} = {1,6}
{1,2,4,6} ≠ {1,6}
Statement1 is False.
(2) P ∩ (Q ∩ R) = (P ∩ Q) Δ (P Δ R)
LHS:
{1,2,4,5} ∩ {5,6} = {5}
RHS:
({1,2,4,5} ∩ {2,3,5,6}) Δ ({1,2,4,5} Δ {4,5,6,7})
{2,5} Δ ({1,2,4,5,6,7}  {4,5})
{2,5} Δ {1,2,6,7}
{1,2,5,6,7}  {2}
{1,5,6,7}
LHS ≠ RHS
Statement  2 is also wrong.
Question 11 
not a lattice
 
a lattice but not a distributive lattice
 
a distributive lattice but not a Boolean algebra  
a Boolean algebra

Question 11 Explanation:
It is lattice because both LUB and GLB exist for each pair of the vertex in above Hasse diagram.
But it is not distributed because for some element there are more than one complement. Moreover if it is not distributive then it can't be boolean.
But it is not distributed because for some element there are more than one complement. Moreover if it is not distributive then it can't be boolean.
Question 12 
Consider the set H of all 3 × 3 matrices of the type
where a, b, c, d, e and f are real numbers and abc ≠ 0. Under the matrix multiplication operation, the set H is
a group
 
a monoid but not a group
 
a semi group but not a monoid
 
neither a group nor a semi group

Question 12 Explanation:
abc != 0 & Identity matrix is identity then it is nonsingular and inverse is also defined.
The algebraic structure is a group because the given matrix can have inverse and the inverse is nonsingular.
The algebraic structure is a group because the given matrix can have inverse and the inverse is nonsingular.
Question 13 
What is the minimum number of ordered pairs of nonnegative numbers that should be chosen to ensure that there are two pairs (a, b) and (c, d) in the chosen set such that "a ≡ c mod 3" and "b ≡ d mod 5"
4  
6  
16  
24 
Question 13 Explanation:
a = cmod3
That means a=0,1,2 ⇒ 3
b = dmod5
That means b=0,1,2,3,4 ⇒ 4
→ Total no. of order pairs = 3 * 5 = 15
→ Ordered pair (c,d) has 1 combination.
Then total no. of combinations = 15+1 = 16
That means a=0,1,2 ⇒ 3
b = dmod5
That means b=0,1,2,3,4 ⇒ 4
→ Total no. of order pairs = 3 * 5 = 15
→ Ordered pair (c,d) has 1 combination.
Then total no. of combinations = 15+1 = 16
Question 14 
Let R and S be any two equivalence relations on a nonempty set A. Which one of the following statements is TRUE?
R∪S, R∩S are both equivalence relations.  
R∪S is an equivalence relation.
 
R∩S is an equivalence relation.
 
Neither R∪S nor R∩S is an equivalence relation.

Question 14 Explanation:
R∪S might not be transitive.
Let (a,b) present in R and (b,c) present in S and (a,c) is not present in either of them. Then R∪S will contain (a,b) and (b,c) but not (a,c) and hence not transitive.
And equivalence relation must satisfy 3 property:
(i) Reflexive
(ii) Symmetric
(iii) Transitive
But as we have seen that for R∪S, Transitivity is not satisfied.
Let (a,b) present in R and (b,c) present in S and (a,c) is not present in either of them. Then R∪S will contain (a,b) and (b,c) but not (a,c) and hence not transitive.
And equivalence relation must satisfy 3 property:
(i) Reflexive
(ii) Symmetric
(iii) Transitive
But as we have seen that for R∪S, Transitivity is not satisfied.
Question 15 
{(x, y)y > x and x, y ∈ {0, 1, 2, ... }}  
{(x, y)y ≥ x and x, y ∈ {0, 1, 2, ... }}
 
{(x, y)y < x and x, y ∈ {0, 1, 2, ... }}
 
{(x, y)y ≤ x and x, y ∈ {0, 1, 2, ... }}

Question 15 Explanation:
Transitive means that x is related to greater value y and reflexive means x related to y.
Answer is option B.
{(x, y)y ≥ x and x, y ∈ {0, 1, 2, ... }}
Answer is option B.
{(x, y)y ≥ x and x, y ∈ {0, 1, 2, ... }}
Question 16 
c a e b
 
c b a e
 
c b e a
 
c e a b

Question 16 Explanation:
The last row is c e a b.
Question 17 
{1}  
{1}, {2, 3}
 
{1}, {1, 3}
 
{1}, {1, 3}, (1, 2, 3, 4}, {1, 2, 3, 5}

Question 17 Explanation:
A lattice is complete if every subset of partialordered set is to be a supremum and infimum element.
For the set {1, 2, 3, 4, 5} there is no supremum element i.e., {1}.
Then clearly we need to add {1}, then it is to be a lattice.
For the set {1, 2, 3, 4, 5} there is no supremum element i.e., {1}.
Then clearly we need to add {1}, then it is to be a lattice.
Question 18 
Consider the set Σ* of all strings over the alphabet Σ = {0, 1}. Σ* with the concatenation operator for strings
does not form a group
 
forms a noncommutative group
 
does not have a right identity element
 
forms a group if the empty string is removed from Σ*

Question 18 Explanation:
In the concatenation '∊' is the identity element. And given one is not a group because no element has inverse element.
→ To perform concatenation with the given set can result a Monoid and it follows the property of closure, associativity and consists of identity element.
→ To perform concatenation with the given set can result a Monoid and it follows the property of closure, associativity and consists of identity element.
Question 19 
Consider the set {a, b, c} with binary operators + and × defined as follows :
For example, a + c = c, c + a = a, c × b = c and b × c = a. Given the following set of equations :
+  a  b  c  ×  a  b  c  
a  b  a  c  a  a  b  c  
b  a  b  c  b  b  c  a  
c  a  c  b  c  c  c  b 
(a × x) + (a × y) = c (b × x) + (c × y) = cThe number of solution(s) (i.e., pair(s) (x, y)) that satisfy the equations is :
0  
1  
2  
3 
Question 19 Explanation:
Total possible values = 3^{2} = 9 i.e., (a,a), (b,b), (c,c), (a,b), (a,c), (b,a), (b,c), (c,a), (c,b)
In those (x, y) = (b,c) & (c,b) are the possible solution for the corresponding equations.
(x, y) = (b,c) ⇒ (a*b)+(a*c) ⇒ (b*b)+(c*c)
⇒ (b) + (c) ⇒ c + b
⇒ c (✔️) ⇒ c (✔️)
(x,y) = (c,b) ⇒ (a*c)+(a*b) ⇒ (b*c)+(c*b)
⇒ c+b ⇒ a+c
⇒ c (✔️) ⇒ c (✔️)
In those (x, y) = (b,c) & (c,b) are the possible solution for the corresponding equations.
(x, y) = (b,c) ⇒ (a*b)+(a*c) ⇒ (b*b)+(c*c)
⇒ (b) + (c) ⇒ c + b
⇒ c (✔️) ⇒ c (✔️)
(x,y) = (c,b) ⇒ (a*c)+(a*b) ⇒ (b*c)+(c*b)
⇒ c+b ⇒ a+c
⇒ c (✔️) ⇒ c (✔️)
Question 20 
Let ∑ = (a, b, c, d, e) be an alphabet. We define an encoding scheme as follows : g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11.
2^{7}3^{7}5^{7}
 
2^{8}3^{8}5^{8}
 
2^{9}3^{9}5^{9}  
2^{10}5^{10}7^{10}

Question 20 Explanation:
The answers can have only three possibilities of sequences i.e., "a", "a", "a", and there is no multiplies of 7 and 9. So eliminates option A & C.
And f(S) = 2^{3} = 8
So answer is 2^{8}3^{8}5^{8}.
And f(S) = 2^{3} = 8
So answer is 2^{8}3^{8}5^{8}.
Question 21 
Which of the following is true?
The set of all rational negative numbers forms a group under multiplication.  
The set of all nonsingular matrices forms a group under multiplication.  
The set of all matrices forms a group under multiplication.  
Both B and C are true. 
Question 21 Explanation:
A group G should follow 4 properties:
a. Closure: result of a * b must be in group G.
b. There must be an identity element i.e. e * a = a * e = a
c. There must be an inverse element b for every element a such that a * b = b * a = e
d. Associativity i.e. (a * b) * c = a * (b * c)
Rational negative numbers don't form a group under multiplication, as multiplying two negative numbers results into a positive number, so closure property is not satisfied.
Set of nonsingular matrices forms a group under multiplication.
The set of all matrices doesn't form a group under multiplication, since there may not be an inverse for a matrix (in particular, for singular matrices).
a. Closure: result of a * b must be in group G.
b. There must be an identity element i.e. e * a = a * e = a
c. There must be an inverse element b for every element a such that a * b = b * a = e
d. Associativity i.e. (a * b) * c = a * (b * c)
Rational negative numbers don't form a group under multiplication, as multiplying two negative numbers results into a positive number, so closure property is not satisfied.
Set of nonsingular matrices forms a group under multiplication.
The set of all matrices doesn't form a group under multiplication, since there may not be an inverse for a matrix (in particular, for singular matrices).
Question 22 
The binary relation S = ɸ (empty set) on set A = {1,2,3} is
Neither reflexive nor symmetric  
Symmetric and reflexive  
Transitive and reflexive  
Transitive and symmetric 
Question 22 Explanation:
S = ɸ; A = {1,2,3}
A×S = {(ɸ,1), (ɸ,2), (ɸ,3), (1,ɸ), (2,ɸ), (3,ɸ)}
Not reflexive = (1,1), (2,2), (3,3) not there
Symmetric: if (a,b) is present then (b,a) is also present
Transitive: True; if (x,y), (y,z) then (z,x) is also present
A×S = {(ɸ,1), (ɸ,2), (ɸ,3), (1,ɸ), (2,ɸ), (3,ɸ)}
Not reflexive = (1,1), (2,2), (3,3) not there
Symmetric: if (a,b) is present then (b,a) is also present
Transitive: True; if (x,y), (y,z) then (z,x) is also present
Question 23 
(a) S = {〈1,2〉,〈2,1〉} is binary relation on set A = {1,2,3}. Is it irreflexive? Add the minimum number of ordered pairs to S to make it an equivalence relation. Give the modified S.
(b) Let S = {a,b} and let (S) be the powerset of S. Consider the binary relation ‘⊆ (set inclusion)’ on (S). Draw the Hasse diagram corresponding to the lattice ((S),⊆).
Theory explanation is given below. 
Question 23 Explanation:
(a) S = {(1,2), (2,1)}; A = {1,2,3}
The given relation S is irreflexive because no diagonal elements are present in the relation i.e., (x,x)∉R, ∀x∈A
If a relation is equivalence then it is
Reflexive
Symmetric
Transitive
Given relation S is not Reflexive & Transitive.
Reflexive closure on S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
Transitive closure on S is does not change after performing reflexive closure on S.
S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
(b) Given S = {a,b}
Powerset of S i.e., P(S) = {(ɸ), (a), (b), (a,b)}
Hasse diagram:
The given relation S is irreflexive because no diagonal elements are present in the relation i.e., (x,x)∉R, ∀x∈A
If a relation is equivalence then it is
Reflexive
Symmetric
Transitive
Given relation S is not Reflexive & Transitive.
Reflexive closure on S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
Transitive closure on S is does not change after performing reflexive closure on S.
S = {(1,1), (2,2), (3,3), (1,2), (2,1)}
(b) Given S = {a,b}
Powerset of S i.e., P(S) = {(ɸ), (a), (b), (a,b)}
Hasse diagram:
Question 24 
A relation R is defined on the set of integers as xRy iff (x+y) is even. Which of the following statements is true?
R is not an equivalence relation  
R is an equivalence relation having 1 equivalence class  
R is an equivalence relation having 2 equivalence classes  
R is an equivalence relation having 3 equivalence classes 
Question 24 Explanation:
It is reflexive R(x+y) is even ⇒ R(x+x) is even.
It is symmetric R(x+y) is even ⇒ R(x+y) is even then R(y+x) is also v.
It is transitive R(x+y) is even ⇒ R((x+y)+z)) is even then R(x+(y+z)) is also even.
This given relation is equivalence.
Sum of two even numbers are even. Same sum of two odd numbers are even but one even, one odd is odd. It can have two equivalent classes.
It is symmetric R(x+y) is even ⇒ R(x+y) is even then R(y+x) is also v.
It is transitive R(x+y) is even ⇒ R((x+y)+z)) is even then R(x+(y+z)) is also even.
This given relation is equivalence.
Sum of two even numbers are even. Same sum of two odd numbers are even but one even, one odd is odd. It can have two equivalent classes.
Question 25 
Let P(S) denotes the powerset of set S. Which of the following is always true?
P(P(S)) = P(S)  
P(S) ∩ P(P(S)) = {ɸ}  
P(S) ∩ S = P(S)  
S ∉ P(S) 
Question 25 Explanation:
Let us consider
S={1}
P(S)=[{ }, {1}]
P(P(S)) = [{ }, {1}, {{ }, 1}, {1, { }}]
Option A: P(P(S)) ≠ P(S) (wrong)
Option B: P(S) ∩ P(P(S)) ≠ ɸ (wrong)
Option C: P(S) ∩ S ≠ P(S) (wrong)
Option D: S ∈ P(S) (wrong)
None of the given is correct.
S={1}
P(S)=[{ }, {1}]
P(P(S)) = [{ }, {1}, {{ }, 1}, {1, { }}]
Option A: P(P(S)) ≠ P(S) (wrong)
Option B: P(S) ∩ P(P(S)) ≠ ɸ (wrong)
Option C: P(S) ∩ S ≠ P(S) (wrong)
Option D: S ∈ P(S) (wrong)
None of the given is correct.
Question 27 
Theory Explanation is given below. 
Question 27 Explanation:
A1 is the identity element here. Inverse is does not exist for zero then it is not a group.
Question 28 
Theory Explanation is given below. 
Question 28 Explanation:
(a) No. of multiset of size 4 that can be constructed from n distinct elements so that atleast one element occurs exactly twice:
= multiset of size 4 with exactly one element occurs exactly twice + multiset of size 4 with exactly two element occurs exactly twice.
(b) Infinite, because size of multiset is not given.
= multiset of size 4 with exactly one element occurs exactly twice + multiset of size 4 with exactly two element occurs exactly twice.
(b) Infinite, because size of multiset is not given.
Question 29 
The number of binary relations on a set with n elements is:
n^{2}  
2^{n}  
2^{n (2) }  
None of the above 
Question 29 Explanation:
In binary relation two elements are selected from a set. So total no. of pairs possible are
n×n = n^{2}
Now, no. of binary relations possible is
2^{n}^{2}
Because each pair have two possibilities either chosen or not chosen.
n×n = n^{2}
Now, no. of binary relations possible is
2^{n}^{2}
Because each pair have two possibilities either chosen or not chosen.
Question 30 
Let L be a set with a relation R which is transitive, antisymmetric and reflexive and for any two elements a, b ∈ L let the least upper bound lub (a,b) and the greatest lower bound glb (a,b) exist. Which of the following is/are true?
L is a poset  
L is a Boolean algebra  
L1 is context free  
L2 is regular
 
Both A and C 
Question 30 Explanation:
Note: Options given are wrong.
Question 31 
Suppose A is a finite set with n elements. The number of elements in the largest equivalence relation of A is
n  
n^{2}  
1  
n +1 
Question 31 Explanation:
In a largest equivalence relation the every element is related to other element
⇒ n×n
⇒ n^{2}
⇒ n×n
⇒ n^{2}
Question 32 
Both assertions are true  
Assertion (i) is true but assertion (ii) is not true  
Assertion (ii) is true but assertion (i) is not true  
Neither (i) nor (ii) is true 
Question 32 Explanation:
If R_{1} and R_{2} be two equivalence relations on a set 'S' then the transitive property tells
(i) R_{1} ∩ R_{2} is also transitive.
(ii) R_{1} ∪ R_{2} is need not to be transitive.
(i) R_{1} ∩ R_{2} is also transitive.
(ii) R_{1} ∪ R_{2} is need not to be transitive.
Question 33 
The binary relation R = {(1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4) on the set A = {1,2,3,4} is
reflexive, symmetric and transitive  
neither reflexive, nor irreflexive but transitive  
irreflexive, symmetric and transitive  
irreflexive and antisymmetric 
Question 33 Explanation:
→ Not reflexive because (4, 4) not present.
→ Not irreflexive becuaes (1, 1) is present.
→ Not symmetric because (2, 1) is present but not (1, 2).
→ Not antisymmetric  (2, 3) and (3, 2) are present.
It is transitive so correct option is (B).
→ Not irreflexive becuaes (1, 1) is present.
→ Not symmetric because (2, 1) is present but not (1, 2).
→ Not antisymmetric  (2, 3) and (3, 2) are present.
It is transitive so correct option is (B).
Question 34 
Let (Z,*) be an algebraic structure, where Z is the set of integers and the operation * is defined by n*m = maximum (n,m). which of the following statements is true for (Z,*)?
(Z,*) is a monoid  
(Z,*) is an Abelian group  
(Z,*) is a group  
None of the above 
Question 34 Explanation:
Semigroup  Closed and associative
Monoid  Closed, Associative and has an identity
Group  Monoid with inverse
Abelian group  Group with commutative property
Go through with given:
Closure: Yes.
(m*n = max(m,n)) output is either m or n whichever is maximum since m,n belongs z. The result of the binary operation also belongs to z. So given is satisfying closure property.
Associative: Yes.
The output is max among the elements and it is associative.
Identity: No.
We don't have single unique element for all the elements which is less than all the elements.
Given one is semigroup only.
Monoid  Closed, Associative and has an identity
Group  Monoid with inverse
Abelian group  Group with commutative property
Go through with given:
Closure: Yes.
(m*n = max(m,n)) output is either m or n whichever is maximum since m,n belongs z. The result of the binary operation also belongs to z. So given is satisfying closure property.
Associative: Yes.
The output is max among the elements and it is associative.
Identity: No.
We don't have single unique element for all the elements which is less than all the elements.
Given one is semigroup only.
Question 35 
2  
3  
0  
1 
Question 35 Explanation:
g, c, d are the complements of e.
No. of complements = 3
e∨g = a and e∧g = f
e∨c = a and e∧c = f
e∨d = a and e∧d = f
No. of complements = 3
e∨g = a and e∧g = f
e∨c = a and e∧c = f
e∨d = a and e∧d = f
Question 36 
n!  
n+2  
n  
1 
Question 36 Explanation:
To make this partial order a total order, we need the relation to hold for every two element of the partial order. Currently between any a_{i} and a_{j}, there is no relation.
So for every a_{i}, a_{j} we have to add either (a_{i}, a_{j}) or (a_{j}, a_{i} in total order. So, this translates to giving an ordering for n elements between x and y, which can be done in n! ways. So answer is (A).
So for every a_{i}, a_{j} we have to add either (a_{i}, a_{j}) or (a_{j}, a_{i} in total order. So, this translates to giving an ordering for n elements between x and y, which can be done in n! ways. So answer is (A).
Question 37 
The number of equivalence relations of the set {1,2,3,4} is
15  
16  
24  
4 
Question 37 Explanation:
The no. of equivalence relation with 4 elements is 15.
Question 38 
Let A and B be sets and let A^{c} and B^{c} denote the complements of the sets A and
B. The set (A – B) ∪ (B  A) ∪ (A∩B) is equal to
A ∪ B  
A^{c} ∪ B^{c}  
A ∩ B  
A^{c} ∩ B^{c} 
Question 38 Explanation:
(A – B) ∪ (B  A) ∪ (A∩B)
(A  B) = 1
(B  A) = 2
(A∩B) = 3
A∪B = (1∪2∪3)
(A – B) ∪ (B  A) ∪ (A∩B) = 1∪2∪3 = (A∪B)
(A  B) = 1
(B  A) = 2
(A∩B) = 3
A∪B = (1∪2∪3)
(A – B) ∪ (B  A) ∪ (A∩B) = 1∪2∪3 = (A∪B)
Question 39 
Let X = {2,3,6,12,24}, Let ≤ be the partial order defined by X ≤ Y if x divides y.
Number of edge as in the Hasse diagram of (X,≤) is
3  
4  
9  
None of the above 
Question 39 Explanation:
No. of edges = 4
Question 40 
Which of the following statements is false?
The set of rational numbers is an abelian group under addition.  
The set of integers in an abelian group under addition.  
The set of rational numbers form an abelian group under multiplication.  
The set of real numbers excluding zero in an abelian group under multiplication.

Question 40 Explanation:
Rational number consists of number '0'. If 0 is present in a set inverse is not possible under multiplication.
Question 41 
Let R be a nonempty relation on a collection of sets defined by A R B if and only if A ∩ B = ф. Then, (pick the true statement)
R is reflexive and transitive  
R is symmetric and not transitive  
R is an equivalence relation  
R is not reflexive and not symmetric 
Question 41 Explanation:
Let A = {1, 2, 3} and B = {4, 5} and C = {1, 6, 7}
Now,
A ∩ B = ф
& B ∩ C = ф
But A ∩ B ≠ ф
So, R is not transitive.
A ∩ B = A, so R is not reflexive.
If A ∩ B = ф
then definitely B ∩ A = ф.
Hence, R is symmetric.
So, option (B) is true.
Now,
A ∩ B = ф
& B ∩ C = ф
But A ∩ B ≠ ф
So, R is not transitive.
A ∩ B = A, so R is not reflexive.
If A ∩ B = ф
then definitely B ∩ A = ф.
Hence, R is symmetric.
So, option (B) is true.
Question 42 
Which one of the following is false?
The set of all bijective functions on a finite set forms a group under function composition.
 
The set {1, 2, ……., p–1} forms a group under multiplication mod p where p is a prime number.  
The set of all strings over a finite alphabet forms a group under concatenation.  
A subset s ≠ ф of G is a subgroup of the group 
Question 42 Explanation:
Option (C) is False because string concatatieon operation is monoid(doesn't have inverse to become a group).
Question 43 
R1 and R2 are equivalence relations, R3 and R4 are not  
R1 and R3 are equivalence relations, R2 and R4 are not  
R1 and R4 are equivalence relations, R2 and R3 are not  
R1, R2, R3 and R4 are all equivalence relations 
Question 43 Explanation:
R1:
a+a=2a
The set (a,a) is reflexive.
The set representation (a,a), (b,b) is also Symmetric.
The set representation is Transitive.
So, this is Equivalence.
R2:
a+a≠2a
The (a,a) is nonreflexive.
R3:
a⋅a>0 → Reflexive
a⋅b>0 and b⋅a>0 → Symmetric
a⋅b>0, b⋅c>0 then c⋅a>0 → Transitive
The relation R3 is equivalence relation.
R4:
a  a ≤ 2, which is not possible, not Reflexive.
R1 & R3 are equivalence, R2 & R4 are not.
a+a=2a
The set (a,a) is reflexive.
The set representation (a,a), (b,b) is also Symmetric.
The set representation is Transitive.
So, this is Equivalence.
R2:
a+a≠2a
The (a,a) is nonreflexive.
R3:
a⋅a>0 → Reflexive
a⋅b>0 and b⋅a>0 → Symmetric
a⋅b>0, b⋅c>0 then c⋅a>0 → Transitive
The relation R3 is equivalence relation.
R4:
a  a ≤ 2, which is not possible, not Reflexive.
R1 & R3 are equivalence, R2 & R4 are not.
Question 44 
Only S1 is correct  
Only S2 is correct  
Both S1 and S2 are correct  
None of S1 and S2 is correct 
Question 44 Explanation:
S1: Consider A = {2,4,6,8,10,...} set of all even numbers
B = {2,3,5,7,11,13,...} set of prime numbers
C = {1,3,5,7,...} set of odd numbers
(B∪C) = {1,2,3,5,7,...}
A∩(B∪C) = {2}
Which is finite, S1 is true.
S2: Consider A=5+√3 Irrational
B=5√3 Irrational
A+B=10 Rational
A+B, which is rational number, S2 is true.
B = {2,3,5,7,11,13,...} set of prime numbers
C = {1,3,5,7,...} set of odd numbers
(B∪C) = {1,2,3,5,7,...}
A∩(B∪C) = {2}
Which is finite, S1 is true.
S2: Consider A=5+√3 Irrational
B=5√3 Irrational
A+B=10 Rational
A+B, which is rational number, S2 is true.
Question 45 
Only S1 is correct  
Only S2 is correct  
Both S1 and S2 are correct  
None of S1 and S2 is correct 
Question 45 Explanation:
S1: f(E∪F) = f(E)∪f(F)
The both LHS and RHS contains the same element in E and F.
So, S1 is true.
S2: f(E∩F) = f(E)∩f(F)
E and F are partitions of A.
f(E)∩f(F) = ϕ
f(ϕ) is not defined, but f(E)∩f(F)=1.
So, S2 is false.
The both LHS and RHS contains the same element in E and F.
So, S1 is true.
S2: f(E∩F) = f(E)∩f(F)
E and F are partitions of A.
f(E)∩f(F) = ϕ
f(ϕ) is not defined, but f(E)∩f(F)=1.
So, S2 is false.
Question 46 
The transitive closure of the relation {(1, 2), (2, 3), (3, 4), (5, 4)} on the set {1, 2, 3, 4, 5} is ___________.
{(1,2), (2,3), (1,3), (3,4), (2,4), (1,4), (5,4)} 
Question 46 Explanation:
Transitive closure of the relation {(1,2), (2,3), (3,4), (5,4)} ={(1,2), (2,3), (1,3), (3,4), (2,4), (1,4), (5,4)}
Transitive closure of R:
(a) It is transitive.
(b) It contains R.
(c) It is minimal, satisfies a & b.
Transitive closure of R:
(a) It is transitive.
(b) It contains R.
(c) It is minimal, satisfies a & b.
Question 47 
The union of two equivalence relations is also an equivalence relation.
True  
False 
Question 47 Explanation:
Equivalence relation should satisfy Reflexive, Symmetric and Transitive property.
Reflexive ∪ Reflexive = Reflexive
Symmetric ∪ Symmetric = Symmetric
Transitive ∪ Transitive ≠ Transitive
Since Transitivity does not satisfy union, so union of two equivalence relation is not an equivalence relation.
Reflexive ∪ Reflexive = Reflexive
Symmetric ∪ Symmetric = Symmetric
Transitive ∪ Transitive ≠ Transitive
Since Transitivity does not satisfy union, so union of two equivalence relation is not an equivalence relation.
Question 48 
Every infinite cyclic group is isomorphic to the infinite cyclic group of intergers under addition.
True  
False 
Question 48 Explanation:
True, every infinite cyclic group is isomorphic to the infinite cyclic group of integers under addition.
There are 48 questions to complete.