NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
VISIT NOW

GATE CSE

Set Theory & Algebra

Discrete Mathematics

Previous Years Questions

Marks 1

More
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 probabil...
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 U = {1, 2 ,..., n}. Let A = {(x, X) | x ∈ X, X ⊆ U}. Consider the following two statements on |A|. I. |A| = n2n–1 II...
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...
GATE CSE 2019
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 ...
GATE CSE 2015 Set 3
Let $$𝑅$$ be the relation on the set of positive integers such that $$aRb$$ if and only if $$𝑎 $$ and $$𝑏$$ are disti...
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
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. $$\p...
GATE CSE 2015 Set 1
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 2014 Set 3
Which one of the following functions is continuous at $$x = 3$$?
GATE CSE 2013
A Binary operation $$ \oplus $$ on a set of integers is defined as $$x$$ $$ \oplus $$ $$y$$ $$ = {x^2} + {y^2}$$. Whi...
GATE CSE 2013
Consider the set $$S = \left\{ {1,\,\omega ,\,{\omega ^2}} \right\},$$ where $$\omega $$ and $${{\omega ^2}}$$, are cube...
GATE CSE 2010
What is the possible number of reflexive relations on a set $$5$$ elements?
GATE CSE 2010
consider the binary relation $$R = \left\{ {\left( {x,y} \right),\,\left( {x,z} \right),\,\left( {z,x} \right),\,\left( ...
GATE CSE 2009
Which one of the following in NOT necessarily a property of Group?
GATE CSE 2009
If $$P, Q, R$$ are subsets of the universal set $$U$$, then $$\left( {P \cap Q \cap R} \right) \cup \left( {{P^c} \cap ...
GATE CSE 2008
Let $$S$$ be a set6 of $$n$$ elements. The number of ordered pairs in the largest and the smallest equivalence relations...
GATE CSE 2007
What is the maximum number of different Boolean functions involving $$n$$ Boolean variables?
GATE CSE 2007
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 ...
GATE CSE 2006
The set $$\left\{ {1,\,\,2,\,\,3,\,\,5,\,\,7,\,\,8,\,\,9} \right\}$$ under multiplication modulo 10 is not a group. Give...
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 ...
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...
GATE CSE 2006
The following is the Hasse diagram of the poset $$\left[ {\left\{ {a,b,c,d,e} \right\}, \prec } \right]$$ The poset is:...
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...
GATE CSE 2005
The set $$\left\{ {1,\,\,2,\,\,4,\,\,7,\,\,8,\,\,11,\,\,13,\,\,14} \right\}$$ is a group under multiplication modulo $$1...
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 ...
GATE CSE 2005
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}$$ ...
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...
GATE CSE 2004
The number of different $$n$$ $$x$$ $$n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is (No...
GATE CSE 2004
Consider the following relations: $${R_1}\,\,\left( {a,\,\,b} \right)\,\,\,iff\,\,\left( {a + b} \right)$$ is even over ...
GATE CSE 2001
The number of binary relations on a set with $$n$$ elements is:
GATE CSE 1999
The number of functions from an $$m$$ element set to an $$n$$ element set is
GATE CSE 1998
Suppose $$A$$ is a finite set with $$n$$ elements. The number of elements in the Largest equivalence relation of $$A$$ i...
GATE CSE 1998
Let $${R_1}$$ and $${R_2}$$ be two equivalence relations on a set. Consider the following assertions: (i)$$\,\,\,\,{R_1}...
GATE CSE 1998
The number of equivalence relations on the set $$\left\{ {1,2,3,4} \right\}$$ is
GATE CSE 1997
Which of the following statements is false?
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 ...
GATE CSE 1996
Suppose $$X$$ and $$Y$$ are sets and $$\left| X \right|$$ and $$\left| Y \right|$$ are their respective cardinalities. I...
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$$ divi...
GATE CSE 1996
Let $$R$$ be a symmetric and transitive relation on a set $$A$$. Then
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...
GATE CSE 1995
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 1993
Let $$S$$ be an infinite set and $${S_1},\,\,{S_2},....\,\,{S_n}$$ be sets such that $${S_1} \cup {S_2} \cup ....... \cu...
GATE CSE 1993
State whether the following statement are TRUE or FALSE: (a) The union of two equivalence relations is also an equivale...
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...
GATE CSE 1987

Marks 2

More
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 2021 Set 1
Consider the first order predicate formula φ: ∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (...
GATE CSE 2019
Let N be the set of natural numbers. Consider the following sets. $$\,\,\,\,\,\,\,\,$$ $$P:$$ Set of Rational numbers (p...
GATE CSE 2018
Consider a set $$U$$ of $$23$$ different compounds in a Chemistry lab. There is a subset $$S$$ of $$U$$ of $$9$$ compoun...
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...
GATE CSE 2016 Set 2
A function $$f:\,\,{N^ + } \to {N^ + },$$ defined on the set of positive integers $${N^ + },$$ satisfies the following p...
GATE CSE 2016 Set 1
Let $$R$$ be a relation on the set of ordered pairs of positive integers such that $$\left( {\left( {p,q} \right),\left(...
GATE CSE 2015 Set 3
The number of onto functions (subjective functions) from set $$X = \left\{ {1,2,3,4} \right\}$$ to set $$Y = \left\{ {a...
GATE CSE 2015 Set 2
Let $$X$$ and $$Y$$ denote the sets containing $$2$$ and $$20$$ distinct objects respectively and $$𝐹$$ denote the set ...
GATE CSE 2015 Set 2
There are two elements $$x, y$$ in a group $$\left( {G,\, * } \right)$$ such that every elements in the group can be wri...
GATE CSE 2014 Set 3
Consider the set of all functions $$f:\left\{ {0,\,1,.....,2014} \right\} \to \left\{ {0,\,1,.....,2014} \right\}$$ such...
GATE CSE 2014 Set 3
Let S denote the set of all functions $$f:\,{\{ 0,\,1\} ^4}\, \to \,\{ 0,\,1\} $$. Denote by N the number of functions f...
GATE CSE 2014 Set 1
Consider the following relation on subsets of the set S integers between 1 and 2014. For two distinct subsets U and V of...
GATE CSE 2014 Set 2
How many onto (or subjective) functions are there form an n-element $$(n\, \ge \,2)$$ set to a 2-element set ?
GATE CSE 2012
For the compositive table of a cyclic group shown below Which one of the following choices is correct?...
GATE CSE 2009
Consider the set of (column) vectors defined by $$X = \,\{ \,x\, \in \,{R^3}\,\left| {{x_1}\, + \,{x_2}\, + \,{x_3} = 0}...
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) $...
GATE CSE 2007
Consider the following Hasse diagrams. Which all of the above represent a lattice? ...
GATE CSE 2007
How many different non-isomorphic Abelian groups of order 4 are there?
GATE CSE 2007
Consider the set S = {a, b, c, d}. Consider the following 4 partitions $$\,{\pi _1},\,{\pi _2},\,{\pi _3},\,{\pi _4}$$ o...
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 ...
GATE CSE 2006
Given a set of elements N = {1, 2, ....., n} and two arbitrary subsets $$A\, \subseteq \,N\,$$ and $$B\, \subseteq \,N\,...
GATE CSE 2006
Let E, F and G be finite sets. Let $$X = \,\left( {E\, \cap \,F\,} \right)\, - \,\left( {F\, \cap \,G\,} \right)$$ and...
GATE CSE 2006
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 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 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}$$ a...
GATE CSE 2005
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...
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 binary relation $$S = \phi $$ (emply set) on set A = {1, 2, 3} is
GATE CSE 2002
Let $$f:\,A\, \to B$$ be a function, and let E and F be subsets of A. Consider the following statements about images. $...
GATE CSE 2001
Consider the following statements: S1: There exist infinite sets A, B, C such that $$A\, \cap \left( {B\, \cup \,C} ...
GATE CSE 2001
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 2000
Let P(S) denote the power set of a set S. Which of the following is always true?
GATE CSE 2000
(a) Mr. X claims the following: If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. ...
GATE CSE 1999
Suppose A = {a, b, c, d} and $${\Pi _1}$$ is the following partition of A $${\Pi _1}\, = \,\{ \{ a,\,\,b,\,\,c\,\} \,,\...
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$$. (...
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...
GATE CSE 1998
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 ) = ...
GATE CSE 1996
Which one of the following is false?
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 ...
GATE CSE 1996
Let A be the set of all nonsingular matrices over real numbers and let * be the matrix multiplication operator. Then
GATE CSE 1995
Some group (G, o) is known to be abelian. Then, which one of the following is true for G?
GATE CSE 1994
The transitive closure of the relation $$\left\{ {\left( {1,2} \right)\left( {2,3} \right)\left( {3,4} \right)\left( {5...
GATE CSE 1989
The complement(s) of the element 'a' in the lattice shown in Fig. is (are) ........... . ...
GATE CSE 1988

Marks 5

More
Let $$A$$ be a set of $$n\left( { > 0} \right)$$ elements. Let $${N_r}$$ be the number of binary relations on $$A$$ a...
GATE CSE 2002
(a) $$S = \left\{ { < 1,2 > ,\, < 2,1 > } \right\}$$ is binary relation on set $$A = \left\{ {1,2,3} \right\...
GATE CSE 2002
Let $$S = \left\{ {0,1,2,3,4,5,6,7} \right\}$$ and $$ \otimes $$ denote multiplication modulo $$8$$, that is, $$x \otime...
GATE CSE 2000
A multiset is an unordered collection of elements where elements may repeat ay number of times. The size of a multiset i...
GATE CSE 2000
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...
GATE CSE 1995
(a) If G is a group of even order, then show that there exists an element $$a \ne e$$, the identifier $$g$$, such that...
GATE CSE 1992

Joint Entrance Examination

JEE Main JEE Advanced WB JEE

Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

Medical

NEET

CBSE

Class 12