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$$nxn$$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$$XX = \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... LetR$$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