Set Theory & Algebra · Discrete Mathematics · GATE CSE

Start Practice

Marks 1

GATE CSE 2020
Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ______.
GATE CSE 2020
Let R be the set of all binary relations on the set {1,2,3}. Suppose a relation is chosen from R at random. The probability that the chosen relation i...
GATE CSE 2019
Let G be an arbitrary group. Consider the following relations on G : R1: ∀a,b ∈ G, aR1b if and only if ∃g ∈ G such that a = g-1bg R2: ∀a,b ∈ G, aR2b...
GATE CSE 2019
Let U = {1, 2 ,..., n}. Let A = {(x, X) | x ∈ X, X ⊆ U}. Consider the following two statements on |A|. I. |A| = n2n–1 II. |A| = $$\sum\limits_{k = 1}^...
GATE CSE 2015 Set 3
Suppose $$𝑈$$ is the power set of the set $$S = \left\{ {1,2,3,4,5,6,} \right\}$$. For any $$T \in U,$$ let $$\left| T \right|$$ denote the number of...
GATE CSE 2015 Set 2
The cardinally of the power set of $$\left\{ {0,1,2,\,\,....,\,\,10} \right.\left. \, \right\}$$ is _____________.
GATE CSE 2015 Set 2
Let $$𝑅$$ be the relation on the set of positive integers such that $$aRb$$ if and only if $$𝑎 $$ and $$𝑏$$ are distinct and have a common divisor ...
GATE CSE 2015 Set 1
For a set A, the power set of A is denoted by 2A. If A = {5, {6}, {7}}, which of the following options are TRUE? I. $$\phi \in {2^A}$$ II. $$\phi \s...
GATE CSE 2014 Set 3
Let $$X$$ and $$Y$$ be finite sets and $$f:X \to Y$$ be a function. Which one of the following statements is TRUE?
GATE CSE 2013
A Binary operation $$ \oplus $$ on a set of integers is defined as $$x$$ $$ \oplus $$ $$y$$ $$ = {x^2} + {y^2}$$. Which one of the following statem...
GATE CSE 2013
Which one of the following functions is continuous at $$x = 3$$?
GATE CSE 2010
What is the possible number of reflexive relations on a set $$5$$ elements?
GATE CSE 2010
Consider the set $$S = \left\{ {1,\,\omega ,\,{\omega ^2}} \right\},$$ where $$\omega $$ and $${{\omega ^2}}$$, are cube roots of unity. If $$ * $$ de...
GATE CSE 2009
Which one of the following in NOT necessarily a property of Group?
GATE CSE 2009
consider the binary relation $$R = \left\{ {\left( {x,y} \right),\,\left( {x,z} \right),\,\left( {z,x} \right),\,\left( {z,y} \right)} \right\}$$ on t...
GATE CSE 2008
If $$P, Q, R$$ are subsets 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} \...
GATE CSE 2007
What is the maximum number of different Boolean functions involving $$n$$ Boolean variables?
GATE CSE 2007
Let $$S$$ be a set6 of $$n$$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $$S$$ are
GATE CSE 2006
A relation $$R$$ is defined on ordered pairs of integers as follows: $$\left( {x,y} \right)R\left( {u,v} \right)\,if\,x < u$$ and $$y > v$$. Th...
GATE CSE 2006
Let $$X,. Y, Z$$ be sets of sizes $$x, y$$ and $$z$$ respectively. Let $$W = X x Y$$ and $$E$$ be the set of all subjects of $$W$$. The number ...
GATE CSE 2006
The set $$\left\{ {1,\,\,2,\,\,3,\,\,5,\,\,7,\,\,8,\,\,9} \right\}$$ under multiplication modulo 10 is not a group. Given below are four plausible rea...
GATE CSE 2006
For the set $$N$$ of natural numbers and a binary operation $$f:N \times N \to N$$, an element $$z \in N$$ is called an identity for $$f$$ if $$f\left...
GATE CSE 2005
Let $$A$$, $$B$$ and $$C$$ be non-empty sets and let $$X = (A - B) - C$$ and $$Y = (A - C) - (B - C)$$ Which one of the following is TRUE?
GATE CSE 2005
The set $$\left\{ {1,\,\,2,\,\,4,\,\,7,\,\,8,\,\,11,\,\,13,\,\,14} \right\}$$ is a group under multiplication modulo $$15$$. The inverse of $$4$$ and ...
GATE CSE 2005
Let $$f$$ be a function from a set $$A$$ to a set $$B$$, $$g$$ a function from $$B$$ to $$C$$, and $$h$$ a function from $$A$$ to $$C$$, such that $$h...
GATE CSE 2005
The following is the Hasse diagram of the poset $$\left[ {\left\{ {a,b,c,d,e} \right\}, \prec } \right]$$ The poset is: ...
GATE CSE 2004
The number of different $$n$$ $$x$$ $$n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is (Note: power ($$2,$$ $$x$$) is s...
GATE CSE 2004
Consider the binary relation: $$S = \left\{ {\left( {x,y} \right)|y = x + 1\,\,and\,\,x,y \in \left\{ {0,1,2,...} \right\}} \right\}$$ The reflexive ...
GATE CSE 2004
Let $${R_1}$$ be a relation from $$A = \left\{ {1,3,5,7} \right\}$$ to $$B = \left\{ {2,4,6,8} \right\}$$ and $${R_2}$$ be another relation from $$B$$...
GATE CSE 2001
Consider the following relations: $${R_1}\,\,\left( {a,\,\,b} \right)\,\,\,iff\,\,\left( {a + b} \right)$$ is even over the set of integers $${R_2}\,\...
GATE CSE 1999
The number of binary relations on a set with $$n$$ elements is:
GATE CSE 1998
Let $${R_1}$$ and $${R_2}$$ be two equivalence relations on a set. Consider the following assertions: (i)$$\,\,\,\,{R_1} \cup {R_2}$$ is an euivalence...
GATE CSE 1998
Suppose $$A$$ is a finite set with $$n$$ elements. The number of elements in the Largest equivalence relation of $$A$$ is
GATE CSE 1998
The number of functions from an $$m$$ element set to an $$n$$ element set is
GATE CSE 1997
The number of equivalence relations on the set $$\left\{ {1,2,3,4} \right\}$$ is
GATE CSE 1996
Let $$X$$ $$X = \left\{ {2,3,6,12,24} \right\}$$. Let $$ \le $$ the partial order defined by $$x \le y$$ if $$x$$ divides $$y$$. The number of edges...
GATE CSE 1996
Suppose $$X$$ and $$Y$$ are sets and $$\left| X \right|$$ and $$\left| Y \right|$$ are their respective cardinalities. It is given that there are exac...
GATE CSE 1996
Let $$A$$ and $$B$$ be sets and let $${A^c}$$ and $${B^c}$$ denote the complements of the sets $$A$$ and $$B$$. The set $$\left( {A - B} \right) \cup ...
GATE CSE 1996
Which of the following statements is false?
GATE CSE 1995
The number of elements in the power set $$P(S)$$ of the set $$S = \left\{ {\left\{ \phi \right\},1,\left\{ {2,3} \right\}} \right\}$$ is
GATE CSE 1995
Let $$R$$ be a symmetric and transitive relation on a set $$A$$. Then
GATE CSE 1993
Let $$S$$ be an infinite set and $${S_1},\,\,{S_2},....\,\,{S_n}$$ be sets such that $${S_1} \cup {S_2} \cup ....... \cup {S_n} = S$$. Then
GATE CSE 1993
Let $${\rm A}$$ be a finite set of size $$n$$. The number of elements in the power set of $${\rm A} \times {\rm A}$$ is
GATE CSE 1987
(a) How many binary relations are there on a set A with n elements? (b) How many one - to - one functions are there from a set A with n elements onto ...
GATE CSE 1987
State whether the following statement are TRUE or FALSE: (a) The union of two equivalence relations is also an equivalence relation.

Marks 2

GATE CSE 2023
Let X be a set and 2$$^X$$ denote the powerset of X. Define a binary operation $$\Delta$$ on 2$$^X$$ as follows: $$A\Delta B=(A-B)\cup(B-A)$$. Let $$H...
GATE CSE 2021 Set 1
A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?...
GATE CSE 2019
Consider the first order predicate formula φ: ∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (z = 1)))] Here 'a|b' denotes t...
GATE CSE 2018
Let N be the set of natural numbers. Consider the following sets. $$\,\,\,\,\,\,\,\,$$ $$P:$$ Set of Rational numbers (positive and negative) $$\,\,\...
GATE CSE 2016 Set 2
A binary relation $$R$$ on $$N \times N$$ is defined as follows: $$(a,b)R(c,d)$$ if $$a \le c$$ or $$b \le d.$$ Consider the following propositions: ...
GATE CSE 2016 Set 2
Consider a set $$U$$ of $$23$$ different compounds in a Chemistry lab. There is a subset $$S$$ of $$U$$ of $$9$$ compounds, each of which reacts with ...
GATE CSE 2016 Set 1
A function $$f:\,\,{N^ + } \to {N^ + },$$ defined on the set of positive integers $${N^ + },$$ satisfies the following properties: $$$\eqalign{ &am...
GATE CSE 2015 Set 3
Let $$R$$ be a relation on the set of ordered pairs of positive integers such that $$\left( {\left( {p,q} \right),\left( {r,s} \right)} \right) \in R$...
GATE CSE 2015 Set 2
Let $$X$$ and $$Y$$ denote the sets containing $$2$$ and $$20$$ distinct objects respectively and $$𝐹$$ denote the set of all possible functions defi...
GATE CSE 2015 Set 2
The number of onto functions (subjective functions) from set $$X = \left\{ {1,2,3,4} \right\}$$ to set $$Y = \left\{ {a,b,c} \right\}$$ is __________...
GATE CSE 2014 Set 2
Consider the following relation on subsets of the set S integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the mini...
GATE CSE 2014 Set 3
Consider the set of all functions $$f:\left\{ {0,\,1,.....,2014} \right\} \to \left\{ {0,\,1,.....,2014} \right\}$$ such that $$f\left( {f\left( i \ri...
GATE CSE 2014 Set 3
There are two elements $$x, y$$ in a group $$\left( {G,\, * } \right)$$ such that every elements in the group can be written as a product of some numb...
GATE CSE 2014 Set 1
Let S denote the set of all functions $$f:\,{\{ 0,\,1\} ^4}\, \to \,\{ 0,\,1\} $$. Denote by N the number of functions from S to the set {0, 1}. The v...
GATE CSE 2012
How many onto (or subjective) functions are there form an n-element $$(n\, \ge \,2)$$ set to a 2-element set ?
GATE CSE 2009
For the compositive table of a cyclic group shown below Which one of the following choices is correct?...
GATE CSE 2007
How many different non-isomorphic Abelian groups of order 4 are there?
GATE CSE 2007
Consider the following Hasse diagrams. Which all of the above represent a lattice? ...
GATE CSE 2007
A partial order P is defined on the set of natural numbers as following. Herw x/y denotes integer division. i) (0, 0) $$ \in \,P$$. ii) (a, b) $$ \i...
GATE CSE 2007
Consider the set of (column) vectors defined by $$X = \,\{ \,x\, \in \,{R^3}\,\left| {{x_1}\, + \,{x_2}\, + \,{x_3} = 0} \right.$$, where $${x^T} = \...
GATE CSE 2006
Let E, F and G be finite sets. Let $$X = \,\left( {E\, \cap \,F\,} \right)\, - \,\left( {F\, \cap \,G\,} \right)$$ and $$Y = \,\left( {E\, - \left( ...
GATE CSE 2006
Given a set of elements N = {1, 2, ....., n} and two arbitrary subsets $$A\, \subseteq \,N\,$$ and $$B\, \subseteq \,N\,$$, how many of the n! permuta...
GATE CSE 2006
Let S = {1, 2, 3,....., m} , m > 3. Let $${X_1},\,....,\,{X_n}$$ be subsets of S each of size 3. Define a function f from S to the set of natural n...
GATE CSE 2006
Consider the set S = {a, b, c, d}. Consider the following 4 partitions $$\,{\pi _1},\,{\pi _2},\,{\pi _3},\,{\pi _4}$$ on $$S:\,{\pi _1} = \left\{ {\o...
GATE CSE 2005
Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets $${S_1}$$ and $${S_2}$$ in C, either $${S...
GATE CSE 2005
Let f: $$\,B \to \,C$$ and g: $$\,A \to \,B$$ be two functions and let h = fog. Given that h is an onto function which one of the following is TRUE?
GATE CSE 2005
Let R and S be any two equivalence relations on a non-emply set A. Which one of the following statements is TRUE?
GATE CSE 2004
The following is the incomplete operation table of a 4-element group. The last row of the table is ...
GATE CSE 2004
The inclusion of which of the following sets into S = { {1, 2}, 1, 2, 3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5} } Is necessary and sufficient to m...
GATE CSE 2002
The binary relation $$S = \phi $$ (emply set) on set A = {1, 2, 3} is
GATE CSE 2001
Consider the following statements: S1: There exist infinite sets A, B, C such that $$A\, \cap \left( {B\, \cup \,C} \right)$$ is finite. S2: Ther...
GATE CSE 2001
Let $$f:\,A\, \to B$$ be a function, and let E and F be subsets of A. Consider the following statements about images. $$S1:\,f\,\left( {E\, \cup \,F}...
GATE CSE 2000
Let P(S) denote the power set of a set S. Which of the following is always true?
GATE CSE 2000
A relation R is defined on the set of integers as zRy if f (x + y) is even. Which of the following statements is true?
GATE CSE 1999
(a) Mr. X claims the following: If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof. ...
GATE CSE 1998
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
GATE CSE 1998
Let (A, *) be a semigroup. Furthermore, for every a and b in A, if $$a\, \ne \,b$$, then $$a\,*\,b \ne \,\,b\,*\,a$$. (a) Show that for every a in A ...
GATE CSE 1998
Suppose A = {a, b, c, d} and $${\Pi _1}$$ is the following partition of A $${\Pi _1}\, = \,\{ \{ a,\,\,b,\,\,c\,\} \,,\,\{ d\} \,\} $$ (a) List the ...
GATE CSE 1996
Let R be a non-emply relation on a collection of sets defined by $${A^R}\,B $$ if and only if $$A\, \cap \,B\, = \,\phi $$. Then, (pick the true state...
GATE CSE 1996
Which one of the following is false?
GATE CSE 1996
Let R denote the set of real numbers. Let f: $$R\,x\,R \to \,R\,x\,R\,$$ be a bijective function defined by f (x, y ) = (x + y, x - y). The inverse fu...
GATE CSE 1995
Let A be the set of all nonsingular matrices over real numbers and let * be the matrix multiplication operator. Then
GATE CSE 1994
Some group (G, o) is known to be abelian. Then, which one of the following is true for G?
GATE CSE 1989
The transitive closure of the relation $$\left\{ {\left( {1,2} \right)\left( {2,3} \right)\left( {3,4} \right)\left( {5,4} \right)} \right\}$$ on th...
GATE CSE 1988
The complement(s) of the element 'a' in the lattice shown in Fig. is (are) ........... . ...

Marks 5

GATE CSE 2002
(a) $$S = \left\{ { < 1,2 > ,\, < 2,1 > } \right\}$$ is binary relation on set $$A = \left\{ {1,2,3} \right\}$$. Is it irreflexive? Add th...
GATE CSE 2002
Let $$A$$ be a set of $$n\left( { > 0} \right)$$ elements. Let $${N_r}$$ be the number of binary relations on $$A$$ and Let $${N_r}$$ be the number...
GATE CSE 2000
A multiset is an unordered collection of elements where elements may repeat ay number of times. The size of a multiset is the number of elements in it...
GATE CSE 2000
Let $$S = \left\{ {0,1,2,3,4,5,6,7} \right\}$$ and $$ \otimes $$ denote multiplication modulo $$8$$, that is, $$x \otimes y = \left( {xy} \right)$$ mo...
GATE CSE 1995
Let $${G_1}$$ and $${G_2}$$ be subgroups of a group $$G$$. (a) Show that $${G_1}\, \cap \,{G_2}$$ is also a subgroup of $$G$$. (b) $${\rm I}$$s $${G_...
GATE CSE 1992
(a) If G is a group of even order, then show that there exists an element $$a \ne e$$, the identifier $$g$$, such that $${a^2} = e$$ (b) Consider t...
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12