GATE CSE
Discrete Mathematics
Set Theory & Algebra
Previous Years Questions

Marks 1

Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ______.
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...
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...
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}^...
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...
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 ...
The cardinally of the power set of $$\left\{ {0,1,2,\,\,....,\,\,10} \right.\left. \, \right\}$$ is _____________.
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...
Let $$X$$ and $$Y$$ be finite sets and $$f:X \to Y$$ be a function. Which one of the following statements is TRUE?
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...
Which one of the following functions is continuous at $$x = 3$$?
What is the possible number of reflexive relations on a set $$5$$ elements?
Consider the set $$S = \left\{ {1,\,\omega ,\,{\omega ^2}} \right\},$$ where $$\omega $$ and $${{\omega ^2}}$$, are cube roots of unity. If $$ * $$ de...
Which one of the following in NOT necessarily a property of Group?
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...
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} \...
Let $$S$$ be a set6 of $$n$$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $$S$$ are
What is the maximum number of different Boolean functions involving $$n$$ Boolean variables?
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 ...
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...
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...
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...
The set $$\left\{ {1,\,\,2,\,\,4,\,\,7,\,\,8,\,\,11,\,\,13,\,\,14} \right\}$$ is a group under multiplication modulo $$15$$. The inverse of $$4$$ and ...
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...
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?
The following is the Hasse diagram of the poset $$\left[ {\left\{ {a,b,c,d,e} \right\}, \prec } \right]$$ The poset is: ...
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 ...
The number of different $$n$$ $$x$$ $$n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is (Note: power ($$2,$$ $$x$$) is s...
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$$...
Consider the following relations: $${R_1}\,\,\left( {a,\,\,b} \right)\,\,\,iff\,\,\left( {a + b} \right)$$ is even over the set of integers $${R_2}\,\...
The number of binary relations on a set with $$n$$ elements is:
The number of functions from an $$m$$ element set to an $$n$$ element set is
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...
Suppose $$A$$ is a finite set with $$n$$ elements. The number of elements in the Largest equivalence relation of $$A$$ is
The number of equivalence relations on the set $$\left\{ {1,2,3,4} \right\}$$ is
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 ...
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...
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...
Which of the following statements is false?
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
Let $$R$$ be a symmetric and transitive relation on a set $$A$$. Then
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
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
State whether the following statement are TRUE or FALSE: (a) The union of two equivalence relations is also an equivalence relation.
(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 ...

Marks 2

A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?...
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...
Let N be the set of natural numbers. Consider the following sets. $$\,\,\,\,\,\,\,\,$$ $$P:$$ Set of Rational numbers (positive and negative) $$\,\,\...
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: ...
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 ...
A function $$f:\,\,{N^ + } \to {N^ + },$$ defined on the set of positive integers $${N^ + },$$ satisfies the following properties: $$$\eqalign{ &am...
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$...
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 __________...
Let $$X$$ and $$Y$$ denote the sets containing $$2$$ and $$20$$ distinct objects respectively and $$𝐹$$ denote the set of all possible functions defi...
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...
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...
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...
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...
How many onto (or subjective) functions are there form an n-element $$(n\, \ge \,2)$$ set to a 2-element set ?
For the compositive table of a cyclic group shown below Which one of the following choices is correct?...
How many different non-isomorphic Abelian groups of order 4 are there?
Consider the following Hasse diagrams. Which all of the above represent a lattice? ...
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...
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} = \...
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( ...
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...
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...
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...
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...
Let R and S be any two equivalence relations on a non-emply set A. Which one of the following statements is TRUE?
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?
The following is the incomplete operation table of a 4-element group. The last row of the table is ...
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...
The binary relation $$S = \phi $$ (emply set) on set A = {1, 2, 3} is
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}...
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...
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?
Let P(S) denote the power set of a set S. Which of the following is always true?
(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. ...
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
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 ...
Suppose A = {a, b, c, d} and $${\Pi _1}$$ is the following partition of A $${\Pi _1}\, = \,\{ \{ a,\,\,b,\,\,c\,\} \,,\,\{ d\} \,\} $$ (a) List the ...
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...
Which one of the following is false?
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...
Let A be the set of all nonsingular matrices over real numbers and let * be the matrix multiplication operator. Then
Some group (G, o) is known to be abelian. Then, which one of the following is true for G?
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...
The complement(s) of the element 'a' in the lattice shown in Fig. is (are) ........... . ...

Marks 5

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...
(a) $$S = \left\{ { < 1,2 > ,\, < 2,1 > } \right\}$$ is binary relation on set $$A = \left\{ {1,2,3} \right\}$$. Is it irreflexive? Add th...
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...
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...
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_...
(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
Joint Entrance Examination
JEE MainJEE AdvancedWB JEE
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Medical
NEET