Set Theory and Algebra
Exam Duration: 45 Mins Total Questions : 25
What is the possible number of reflexive relations on a set of 5 elements?
- (a)
210
- (b)
215
- (c)
220
- (d)
225
Let the set
S={a,b,c,d,e}
Relation is subset of SxS
There are totally 52=25 ordered pairs in SxS including five ordered pairs (a,a), (b,b), (c,c), (d,d) and (e,e) that must be included to find reflecive relations.
Total number of reflexive relation on S
S=225-5 =220
Consider the set \(S=\left\{ 1,\omega ,{ \omega }^{ 2 } \right\} \) where \(\omega \) and \({ \omega }^{ 2 }\) are cube root of unity. If * denotes the multiplication operations, the structure {S*} forms
- (a)
a group
- (b)
a ring
- (c)
an integral domain
- (d)
a field
Here, we have only one operation given. Therefore, given options, viz.; ring, integral domain and field are ruled out.
As it requires two binary operations
Alternative
(i) For all \(a,b\epsilon S\)
\(a\times b\epsilon S\\ a*b\epsilon S\)
i.e,
Closure property holds on sets.
(ii) x is an associative operation.
(iii) \(1\epsilon S\) is the identity element.
(iv) 1-1=1, \({ \omega }^{ -1 }={ \omega }^{ 2 },\left( { \omega }^{ 2 } \right) ^{ -1 }=\omega \)
Inverse axiom is satisfied on given set.
(S,*) is a group
Which one of the following is true for any simple connected undirected graph with more than two vertices?
- (a)
Commutativity
- (b)
Associativity
- (c)
Existence of inverse for every element
- (d)
Existence of identity
Group properties are closure, associativity, existence of identity and existence of inverse for every element. Commutativity is not required for a mathematical structure to become a group.
Which one of the following is true for any simple connected undirected graph with more than two vertices?
- (a)
No two vertices have the same degree
- (b)
Atleast two vertices have the same degree
- (c)
Atleast three vertices have the same degree
- (d)
All vertices have the same degree
In a simple connected undirected graph (with more than two vertices) atleast 2 vertices must have same degree, since if this is not true, then all vertices would have different degrees. A graph with all vertices having different degrees is not possible to construct. Notice that it is possible to construct graphs satisfying choices (a), (c) and (d).
Consider the binary relation R={(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z} which one of the following is true?
- (a)
R is symmetric but not anti-symmetric
- (b)
R is not symmetric but anti-symmetric
- (c)
R is both symmetric and anti-symmetric
- (d)
R is neither symmetric nor anti-symmetric
Given, R={(x,y), (x,z), (z,x), (z,y)} on set {x,y,z} Now, since \(\left( x,y \right) \epsilon R\) and \(\left( y,x \right) \notin R\), R is not symmetric.
Also since \(\left( x,y \right) \epsilon R\) and \(\left( z,x \right) \epsilon R\), R is not anti-symmetric either.
R is neither symmetric nor anti-symmetric.
If P,Q,R are subset of the universal set U, then \(\left( P\cap Q\cap R \right) \cup \left( { P }^{ c }\cap Q\cap R \right) \cup { Q }^{ c }\cup { R }^{ c }\) is
- (a)
\({ Q }^{ c }\cup { R }^{ c }\)
- (b)
\(P\cup { Q }^{ c }\cup { R }^{ c }\)
- (c)
\({ P }^{ c }\cup { Q }^{ c }\cup { R }^{ c }\)
- (d)
\(\cup \)
\(\therefore { Q }^{ c }\cup { R }^{ c }=\left( Q\cap R \right) ^{ c }\quad and\quad \left( P\cap Q\cap R \right) \cup \left( { P }^{ c }\cap Q\cap R \right) \cup { Q }^{ c }\cup { R }^{ c }\\ Therefore,\quad \quad \left( P\cap Q\cap R \right) \cup \left( { P }^{ c }\cap Q\cap R \right) \cup { Q }^{ c }\cup { R }^{ c }\\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad =\left( Q\cap R \right) \cup \left( Q\cap { R }^{ c } \right) \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad =U(Universal\quad set)\)
Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are
- (a)
n and n
- (b)
n2 and n
- (c)
n and 0
- (d)
n and 1
Let S={1,2,3,......n} be a set of n elements number of ordered pairs in the smallest equivalent relation on S is n art it must contain all the reflexive elements viz.,
{(1,1), (2,2), (3,3),.......n(n,n)}
and the largest equivalence relation on S has nxn = n2 ordered pairs.
Let X,Y,Z be sets of sizes X,Y and Z respectively. Let W=XxY and E be the set of all subsets of W. The number of functions from Z to E is
- (a)
Z
- (b)
Zx2xy
- (c)
Z2
- (d)
2xyz
Let n(X) denotes the number of elements of set X.
Given, n(X) = x
n(Y) = y
n(Z) = z
n(E) = Number of all subsets of W
= Number of all subsets of XxY
= 2n(X).n(Y) = 2xy
Therefore, the number of functions from Z to E
=[n(E)]n(Z)
=(2xy)z = 2xyz
The set {1,2,3,5,7,8,9} under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?
- (a)
It is not closed
- (b)
2 does not have an inverse
- (c)
3 does not have an inverse
- (d)
8 does not have an inverse
Let A={1,2,3,5,7,8,9}
Construct the table for any \(x,y\epsilon A\) such that
x*y = (x.y) mod 10
\(\bullet \) | 1 | 2 | 3 | 5 | 7 | 8 | 9 |
1 | 1 | 2 | 3 | 5 | 7 | 8 | 9 |
2 | 2 | 4 | 6 | 0 | 4 | 6 | 8 |
3 | 3 | 6 | 9 | 5 | 1 | 4 | 7 |
5 | 5 | 0 | 5 | 5 | 5 | 0 | 5 |
7 | 7 | 4 | 1 | 5 | 9 | 6 | 3 |
8 | 8 | 6 | 4 | 0 | 6 | 4 | 2 |
9 | 9 | 8 | 7 | 5 | 3 | 2 | 1 |
We know that \(o\notin A.\) So, it is not closed. Therefore, option (a) is true.
The identity element=1
(2.2-1)mod 10=1
From the table we see that 2-1 does not exist
Since, (3.7) mod 10=1
7 is the inverse of 3 and 7\(\epsilon \)A.
Which one of the following option is CORRECT given three positive integers x,y and z and a predicate
- (a)
P(x) being true means that x is a prime number
- (b)
P(x) being true means that x is a number other than 1
- (c)
P(x) is always true irrespective of the value of x
- (d)
P(x) is being true means that x has exactly two factors other than 1 and x
\(P\left( x \right) =\rightharpoondown \left( x=1 \right) \cap v\quad y\left( \ni z\left( x=y*z \right) \right) \\ \Rightarrow \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \left( y=x \right) \cup \left( y=1 \right) \)
The statement says that P(x) is true, if x!=1 and if x=y*z, then either x=y or y=1
for x=y, z=1
x=y*1=x
and for x=y*z=1*z=z
In both base either y=1 or z=1 means x is prime.
Let Xn denotes the number of binary strings of length n that contains no consecutive 0's.
Which of the following recurrences does Xn satisfy?
- (a)
Xn =2Xn-1
- (b)
Xn =Xn/2 + 1
- (c)
Xn = Xn/2 + n
- (d)
Xn =Xn-1 + Xn-2
In xn denotes number of binary strings of length n. There are 2n possible sequencies of outcomes. We want to know the binary strings that contain no consecutive 0's. In each string of (n-1) 0's and 1's in which there are no consecutive 0's. We can append a 1 to obtain a string of length m. For each string of n-2 0's and 1's in which there are no consecutive 0's we can append a 1. So, the recurrence equation is
x1 = 2
x2 = 3
xn = xn-1 + xn-2
Let Xn denotes the number of binary strings of length n that contains no consecutive 0's.
The value of X5 is
- (a)
5
- (b)
7
- (c)
8
- (d)
None of these
x1 = 2, x2 = 3
x3 = 2+3 =5
x4 = 3+5 =8
x5 = x3+x4 =5+8 =13
Since, 13 is not one of the answers.
Consider the set of the (column) vectors defined by X={x\(\epsilon \)R3|x1+x2+x3=0, where xT=[x1,x2,x2]T}Which of the following is true ?
- (a)
{1,-1,0]T, [1,0,-1]T is a basis for the surface X
- (b)
{[1,-1,0]T,[1,0,-1]T} is a linearly independent set
- (c)
X is not a sub place for R3
- (d)
None of these
{1,-1,0]T is a linearly independent set because one cannot be obtained from another by scalar multiplication.
Also, since all such combinations [x1,x2,x3] such that x1+x2+x3=0 cannot be expressed a linear combination of [1,-1,0]. Therefore, [1,-1,0] and [1,0,-1] do not span X and hence, is not a basis of X.
What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a,b) and (c, d) in the chosen set such that a \(\equiv \) c mod 3 and b\(\equiv \)d mod 5?
- (a)
4
- (b)
6
- (c)
16
- (d)
24
The number of combination od pairs (a mode 3, b mod 5) is
3\(\times\)5=15
(Since, a mode 3 can be 0, 1 or 2 and b mod 5 can be 0, 1, 2, 3 or 4)
\(\therefore\)If 16 different ordered pairs are chosen atleast 2 of then must have (a mod 3, b mod 5) as same (basic pigeon hole principle).
Let such two pairs be (a, b) and (c, d), then
a mod 3\(\equiv \)C mod 3 \(\Rightarrow\)a=c mod 3
and b m od 5 =d mod 5\(\Rightarrow\) b=d mod 5
Let S={1,2,3,...,m}, m>3. Let X1,....,Xn be subsets of S each of size 3.Define a function f from S to the set of natural number as, f(i) is the number of sets Xj that contain the element i. i.e.,\(f(i)=\left| \{ j \right| i\epsilon { X }_{ i }\} |,\) then \(\sum _{ i=1 }^{ m }{ f(i) } \)is
- (a)
3m
- (b)
3n
- (c)
2m+1
- (d)
2n+1
\(Here,n=^{ m }{ C }_{ 3 }\\ and\quad f(1)=f(2)...=f(m)=^{ m-1 }{ C }_{ 2 }\\ \Rightarrow \sum _{ i=1 }^{ m }{ f(i)={ m. }^{ m-1 }{ C }_{ 2 } } \\ \quad \quad \quad \quad \quad \quad \quad \quad =3\times ^{ m }{ C }_{ 3 }\\ \quad \quad \quad \quad \quad \quad \quad \quad =3\times n\\ \quad \quad \quad \quad \quad \quad \quad \quad =3n\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \)
What is the first order predicate calculus statement equivalent to the following every teacher is liked by some students?
- (a)
\(\forall (x)\{ teacher(x)->\exists (y)[student(y)->likes(y,x)]]\)
- (b)
\(\forall (x)\{ teacher(x)->\exists (y)[student(y)\wedge likes(y,x)]]\)
- (c)
\(\exists (y),\forall (x)\quad [teacher(x)->[student(y)\wedge likes(y,x)]]\)
- (d)
\(\forall (x),[teacher(x)\wedge \exists (y)[student(y)\wedge likes(y,x)]]\)
"Every teacher is liked by some student, then the logical expression is \(\forall (x)\)[teacher(x)->\(\exists (y)\)[student (y) \(\wedge \) likes(y,x)]]
where, likes (y,x) means y likes x, such that y represents the student and xrepresnts the teacher.
Consider the set H of all 3\(\times\)3 matrices of the type
\(\left[ \begin{matrix} a & f & e \\ 0 & b & d \\ 0 & 0 & c \end{matrix} \right] \)
where, a,b,c,d,e, and f are real number and abc\(\neq \)0.Under the matrix multiplication operation the set S is
- (a)
a group
- (b)
a monoid but not group
- (c)
a semi-group but not a monoid
- (d)
neither a group nor a semi-group
(i) The set H is closed since multiplication of upper triangular matrices will result only in upper triangular matrix.
(ii) Matrix multiplication is associative, i.e, ..
A*(B*C)=(A*B)*C
(iiI) The identity element is
I=\(\left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} \right] \)
and this belongs to H is an upper triangular as well as a lower triangular matrix.
(Iv) If A\(\epsilon \)H, then |A| =abc. Since, it is given that abc\(\neq \)0, this means that |A|\(\neq \)0, i.e., every matrix belonging to H is non -singular and has a unique inverse.
\(\therefore\)The set H under matrix multiplication operation is a group.
Let G(x)=\(\frac { 1 }{ { (1-x) }^{ 2 } } =\sum _{ i=0 }^{ \infty }{ g(i){ x }^{ i } } ,\quad where\quad |x|<1,\quad what\quad is\quad g(i)?\)
- (a)
i
- (b)
i+1
- (c)
2i
- (d)
-2i
\(\frac { 1 }{ { (1-x) }^{ 2 } } ={ \left( x-2 \right) }^{ -2 }\\ \quad \quad \quad =1+^{ 2 }{ { C }_{ 1 }x }+^{ 3 }{ { C }_{ 2 }x }+...|X|<1\\ \quad \quad \quad =g(0)+g(1)+g(2){ x }^{ 2 }+....\\ g(0)=1\\ g(1)=^{ 2 }{ { C }_{ 1 } }=2\\ g(2)=^{ 3 }{ { C }_{ 1 } }=^{ 3 }{ { C }_{ 1 } }=2\\ g(i)=^{ x+1 }{ { C }_{ 1 } }=^{ i+1 }{ { C }_{ 1 } }=i+1\)
The following is the incomplete operation table of a 4-element group.
* | e | a | b | c |
e | e | a | b | c |
a | a | b | c | d |
b | ||||
c |
The last row of the table is
- (a)
caeb
- (b)
cbae
- (c)
cbea
- (d)
ceab
From given table
e*a=a,e*b=b,e*c=c
\(\Rightarrow\)e is the identity element
\(\therefore\) a*e=a, b*e=b,c*e=c
Again from the given column, we have
a*c=e
c*a=e
(if a is the inverse of c, then c is the inverse of a)
\(\therefore\)First two elements of the last row will be ce,
Let (S,\(\le \)) be a partial order with two minimal elements and a and b and a, c maximum element. Let P : S \(\Rightarrow\){True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) \(\Rightarrow\) P(y), \(\forall \)x, y\(\epsilon \)S satisfying x \(\le \)y, where \(\Rightarrow\) stands for logical implication .Which of the following statement cannot be true?
- (a)
P(x) = True for all x\(\epsilon \)S such that x\(\epsilon \)0 such that x\(\neq\) b
- (b)
P(x) = False for all x\(\epsilon \)S Such that x\(\neq\)a and x\(\neq\)c
- (c)
P(x) = False for all x\(\epsilon \)S Such that b\(\le \)x such tht x\(\neq\)c
- (d)
P(x) = False for all x\(\epsilon \)S Such that a\(\le \)x and b\(\le \)x
If a\(\le \)x , since P(x) = P(y) whenver x\(\le \)y
\(\therefore\)P(a) \(\Rightarrow\) P(x)
Now since, P(a) = True , P(x) = cannot be false
\(\therefore\)(d) cannot be true
Consider the set {a,b,c} with binary operators + and x defined as follows
+ | a | b | c | x | 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 |
e.g., a+c = c, c+a=a,c\(\times\)b = c and b\(\times\)c = a.
Given , the following set of equation :
(a\(\times\) x) + (a\(\times\)y) = c
(b\(\times\)x)+(c\(\times\)y) = c
The number of solutions (i.e., pairs (x,y) that satisfies the equation ) is
- (a)
0
- (b)
1
- (c)
2
- (d)
3
The possible solution are(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b) and (c,c).
Substitute then ono-by-one in both questions and see which of them satisfies both the equations .
The given equations are
(a\(\times\) x) + (a\(\times\)y) = c ..........(i)
(b\(\times\)x)+(c\(\times\)y) = c ...........(ii)
Substitute irst (x,y) = (a,a)
LHS of Eq.(i) becomes
(a\(\times\)a)+(a\(\times\)a) = a + a = b
Now, RHS of Eq.(i) = c
Therefore , LHS \(\neq \) RHS . This means that (a,a) is not a solution pair .Similarly , try each of the remaining seven possible solution pairs.It will be found that only two pairs(b,c) and (c,b) will satisfy both Eqs.(i) and (ii) simultaneously.
The set of {1,2,4,7,8,11,13,14} is a group under multiplication modulo 15. The inverse of 4 and 7 are respectively
- (a)
3 and 13
- (b)
2 and 11
- (c)
4 and 13
- (d)
8 and 14
The set of S = {1,2,4,7,8,11,13,14} is a group under multiplication modulo 15.
The identify element for the group is e =1
Since, \(\forall \)x\(\epsilon \)S,1 .x and 15 = x
Now, let the inverse of 4 be 4-1.
Now, (4. 4-1) mod 15 = e =1
Now, (4. 4) mod 15 = 1
Since , (4. 4) mod 15 = 1
\(\therefore\)4-1 = 4 (This invere is unique)
Similarly , let the inverse of 7 by 7-1
(7.7-1) mod 15 = 1
Putting each element of set as 7-1 by trial and error , we get
(7.13) mod 15 = 91 mod 15 =1
7-1 = 13
So, 4-1 and 7-1 are respectively 4 and 13
Let E,F andG be finite sets . Let X = (E \(\cap \) F)-(F \(\cap \) G) and Y = (E-(E\(\cap \) G)-E-F).Which one of the following is true?
- (a)
XY
- (b)
XY
- (c)
X = Y
- (d)
X -Y\(\neq \)\(\phi \) and Y-X \(\neq \) \(\phi \)
X = ( E\(\cap \) F ) - ( F \(\cap \) G )
= ( E\(\cap \) F ) \(\cap \) ( F \(\cap \) G )'
= ( E \(\cap \) F ) \(\cap \) ( F' \(\cap \) G' )
= ( E \(\cap \) F \(\cap \) F' ) \(\cap \) ( E \(\cap \) F \(\cap \) G' )
= ( E \(\cap \) F \(\cap \) G'
Y = (E-( E \(\cap \) G ) )-(E-F)
= (E \(\cap \)( E \(\cap \) G' ) )-(E \(\cap \)F')
= (E \(\cap \)( E' \(\cup \) G' ) ) \(\cap \)(E' \(\cap \)F')'
= ( E' \(\cup \) G' ) \(\cap \) (E' \(\cap \) F)
= ( E \(\cup \) G' \(\cap \) E' ) \(\cap \) ( E \(\cap \) G' \(\cap \) E' )
= E \(\cap \) F \(\cap \) G'
\(\Rightarrow\) X = Y
The number of vertices of degree zero in G is
- (a)
1
- (b)
n
- (c)
n+1
- (d)
2n
Let S contain n elements, then S have 2n subsets graph contain 2n vertices.
Let S = {V1,V2,.....Vn}
To vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements .
S0 = | {V1} \(\cap \) Vj | = 2
For this to happen , then subset must have atleast 2 elements .There are n stes which contains a sigle elements for V1 to Vn who does not intersect another set such that it contains two elements. Therefore, the degree of all these n vertices is zero. G is also contains a vertex \(\phi \)whose degree is zero.So, the number of vertices whose degree ios zero is n+1
Let P,Q,R be three atomic propositional assertions.Let X denotes (P\(\vee \)Q) \(\rightarrow\) R and Y denotes (P\(\rightarrow\)R)\(\vee \)(Q\(\rightarrow\)R).Which one of the following is tautology?
- (a)
X \(\equiv \) Y
- (b)
X\(\rightarrow\)Y
- (c)
Y\(\rightarrow\)X
- (d)
\(\neg \)Y\(\rightarrow\)X
X : (P\(\vee \)Q) \(\rightarrow\) R
Y : (P\(\rightarrow\) R) \(\vee \) (Q\(\rightarrow\) R)
X : P + Q \(\rightarrow\) R \(\equiv \) ( P+ Q )' + R = P'Q' + R
Y : (P + R) +( Q'+ R ) \(\equiv \) P' + Q' +R
Clearly , X \(\neq\) Y
Consider X \(\rightarrow\) Y
\(\equiv \) (P'Q'+R) \(\rightarrow\) (P'+Q'+R')
\(\equiv \) (P'Q'+R)' + P'+Q'+R
\(\equiv \) (P'Q')+R' + P'+Q'+R
\(\equiv \) (P+Q)'R' + P'+Q'+R
\(\equiv \) P'R'+Q'R' + P'+Q'+R
\(\equiv \) (PR'+R) +(QR'+Q')+P'
\(\equiv \) (P+R)(R'+R)+(Q+Q')\(\times\)(R'+Q')+P'
\(\equiv \) P+P'+R+R'+Q'
\(\equiv \) 1+1+Q'
\(\equiv \) 1
\(\therefore\) X \(\rightarrow\)Y is a tautology