# 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 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 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 2

The cardinally of the power set of $$\left\{ {0,1,2,\,\,....,\,\,10} \right.\left. \, \right\}$$ is _____________.

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 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

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 2007

What is the maximum number of different Boolean functions involving $$n$$ Boolean variables?

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

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

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

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

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 following is the Hasse diagram of the poset $$\left[ {\left\{ {a,b,c,d,e} \right\}, \prec } \right]$$
The poset is:
...

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

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

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

The number of functions from an $$m$$ element set to an $$n$$ element set 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 1997

The number of equivalence relations on the set $$\left\{ {1,2,3,4} \right\}$$ is

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

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

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

State whether the following statement are TRUE or FALSE:
(a) The union of two equivalence relations is also an equivalence relation.

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 ...

## 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 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 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 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 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 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 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 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 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 one of the following 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

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 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 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 2000

Let P(S) denote the power set of a set S. Which of the following is always 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

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 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 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...