The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Highest voted questions in Discrete Mathematics
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
+60
votes
6
answers
1
GATE201238
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
asked
Sep 12, 2014
in
Graph Theory
by
gatecse
Boss
(
18.5k
points)

9.3k
views
gate2012
graphtheory
normal
markstoall
counting
+52
votes
7
answers
2
GATE2014151
Consider an undirected graph $G$ where selfloops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $ac \leq 1$ and $bd \leq 1$. The number of edges in this graph is______.
asked
Sep 28, 2014
in
Graph Theory
by
jothee
Veteran
(
116k
points)

6.9k
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
+51
votes
6
answers
3
GATE2016128
A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{N^+}$,satisfies the following properties: $f(n)=f(n/2)$ if $n$ is even $f(n)=f(n+5)$ if $n$ is odd Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ___________.
asked
Feb 12, 2016
in
Set Theory & Algebra
by
Sandeep Singh
Loyal
(
7.8k
points)

5.6k
views
gate20161
settheory&algebra
functions
normal
numericalanswers
+50
votes
3
answers
4
GATE200333
Consider the following formula and its two interpretations \(I_1\) and \(I_2\). \(\alpha: (\forall x)\left[P_x \Leftrightarrow (\forall y)\left[Q_{xy} \Leftrightarrow \neg Q_{yy} \right]\right] \Rightarrow (\forall x)\left[\neg P_x\right]\) \(I_1\) : Domain: the set of ... , \(I_1\) does not Neither \(I_1\) nor \(I_2\) satisfies \(\alpha\) Both \(I_1\) and \(I_2\) satisfies \(\alpha\)
asked
Sep 16, 2014
in
Mathematical Logic
by
Kathleen
Veteran
(
59.8k
points)

3.8k
views
gate2003
mathematicallogic
difficult
firstorderlogic
+48
votes
5
answers
5
GATE2016201
Consider the following expressions: $false$ $Q$ $true$ $P\vee Q$ $\neg Q\vee P$ The number of expressions given above that are logically implied by $P \wedge (P \Rightarrow Q)$ is ___________.
asked
Feb 12, 2016
in
Mathematical Logic
by
Akash Kanase
Boss
(
43.6k
points)

6.4k
views
gate20162
mathematicallogic
normal
numericalanswers
propositionallogic
+46
votes
7
answers
6
GATE2015139
Consider the operations $\textit{f (X, Y, Z) = X'YZ + XY' + Y'Z'}$ and $\textit{g (X, Y, Z) = X'YZ + X'YZ' + XY}$ Which one of the following is correct? Both $\left\{\textit{f} \right\}$ and $\left\{ \textit{g}\right\}$ are ... Only $\left\{ \textit{g}\right\}$ is functionally complete Neither $\left\{ \textit{f}\right\}$ nor $\left\{\textit{g}\right\}$ is functionally complete
asked
Feb 13, 2015
in
Set Theory & Algebra
by
makhdoom ghaya
Boss
(
41.2k
points)

6.9k
views
gate20151
settheory&algebra
functions
difficult
+46
votes
4
answers
7
GATE200423, ISRO200732
Identify the correct translation into logical notation of the following assertion. Some boys in the class are taller than all the girls Note: $\text{taller} (x, y)$ is true if $x$ is taller than $y$ ... $(\exists x) (\text{boy}(x) \land (\forall y) (\text{girl}(y) \rightarrow \text{taller}(x, y)))$
asked
Sep 19, 2014
in
Mathematical Logic
by
Kathleen
Veteran
(
59.8k
points)

4.1k
views
gate2004
mathematicallogic
easy
isro2007
firstorderlogic
+45
votes
6
answers
8
GATE2016228
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 exactly $3$ compounds of $U$. Consider the following statements: Each compound in U \ S reacts with an odd number ... in U \ S reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE? Only I Only II Only III None.
asked
Feb 12, 2016
in
Set Theory & Algebra
by
Akash Kanase
Boss
(
43.6k
points)

4.5k
views
gate20162
settheory&algebra
difficult
sets
+45
votes
4
answers
9
GATE2007IT25
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$
asked
Oct 30, 2014
in
Graph Theory
by
Ishrat Jahan
Boss
(
19.1k
points)

4.5k
views
gate2007it
graphtheory
spanningtree
normal
+43
votes
2
answers
10
GATE2015255
Which one of the following wellformed formulae is a tautology? $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$ ... $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$
asked
Feb 13, 2015
in
Mathematical Logic
by
jothee
Veteran
(
116k
points)

5.4k
views
gate20152
mathematicallogic
normal
firstorderlogic
+42
votes
5
answers
11
GATE2014250
Consider the following relation on subsets of the set $S$ of integers between 1 and 2014. For two distinct subsets $U$ and $V$ of $S$ we say $U\:<\:V$ if the minimum element in the symmetric difference of the two sets is in $U$. Consider the following two statements: $S1$ ... $S2$ are true $S1$ is true and $S2$ is false $S2$ is true and $S1$ is false Neither $S1$ nor $S2$ is true
asked
Sep 28, 2014
in
Set Theory & Algebra
by
jothee
Veteran
(
116k
points)

3.9k
views
gate20142
settheory&algebra
normal
sets
+41
votes
5
answers
12
GATE2014349
Consider the set of all functions $f:\{0,1, \dots,2014\} \to \{0,1,\dots, 2014\}$ such that $ f\left(f\left(i\right)\right)=i$, for all $0 \leq i \leq 2014$. Consider the following statements: $P$ ... the following is CORRECT? $P, Q$ and $R$ are true Only $Q$ and $R$ are true Only $P$ and $Q$ are true Only $R$ is true
asked
Sep 28, 2014
in
Set Theory & Algebra
by
jothee
Veteran
(
116k
points)

4k
views
gate20143
settheory&algebra
functions
normal
+41
votes
3
answers
13
GATE200625
Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is the number of sets $X_j$ that contain the element $i.$ That is $f(i)=\left  \left\{j \mid i\in X_j \right\} \right$ then $ \sum_{i=1}^{m} f(i)$ is: $3m$ $3n$ $2m+1$ $2n+1$
asked
Sep 18, 2014
in
Set Theory & Algebra
by
Rucha Shelke
Active
(
3.7k
points)

2.2k
views
gate2006
settheory&algebra
normal
functions
+39
votes
4
answers
14
GATE200672
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in $G$ is: $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$ $2^{n2}$ $2^{n3}\times 3$ $2^{n1}$
asked
Apr 24, 2016
in
Graph Theory
by
jothee
Veteran
(
116k
points)

3.7k
views
gate2006
graphtheory
normal
degreeofgraph
+39
votes
5
answers
15
GATE2015134
Suppose $L = \left\{ p, q, r, s, t\right\}$ is a lattice represented by the following Hasse diagram: For any $x, y \in L$, not necessarily distinct , $x \vee y$ and $x \wedge y$ are join and meet of $x, y$ ... $p_r = 0$ $p_r = 1$ $0 < p_r ≤ \frac{1}{5}$ $\frac{1}{5} < p_r < 1$
asked
Feb 13, 2015
in
Set Theory & Algebra
by
makhdoom ghaya
Boss
(
41.2k
points)

4.7k
views
gate20151
settheory&algebra
normal
lattice
+38
votes
7
answers
16
GATE2015324
In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the ... The result is tail If the person is of Type 2, then the result is tail If the person is of Type 1, then the result is tail
asked
Feb 14, 2015
in
Mathematical Logic
by
jothee
Veteran
(
116k
points)

4.5k
views
gate20153
mathematicallogic
difficult
logicalreasoning
+38
votes
3
answers
17
GATE200830
Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown automaton. Let $\text{equivalent}$ be another predicate such that $\text{equivalent} (a,b)$ ...
asked
Sep 12, 2014
in
Mathematical Logic
by
Kathleen
Veteran
(
59.8k
points)

3.3k
views
gate2008
easy
mathematicallogic
firstorderlogic
+37
votes
5
answers
18
GATE200723
Which of the following graphs has an Eulerian circuit? Any $k$regular graph where $k$ is an even number. A complete graph on $90$ vertices. The complement of a cycle on $25$ vertices. None of the above
asked
Sep 22, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.8k
points)

4.9k
views
gate2007
graphtheory
normal
graphconnectivity
eulergraph
+37
votes
2
answers
19
GATE200479
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2  3n)}{ 2}$ edges ? $^{\left(\frac{n^2n}{2}\right)}C_{\left(\frac{n^23n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^23n}{2} \right )}}.\left(n^2n\right)}C_k\\$ $^{\left(\frac{n^2n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2n}{2}\right)}C_k$
asked
Sep 19, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.8k
points)

3.8k
views
gate2004
graphtheory
permutationsandcombinations
normal
counting
+36
votes
5
answers
20
GATE201611
Let $p, q, r, s$ represents the following propositions. $p:x\in\left\{8, 9, 10, 11, 12\right\}$ $q:$ $x$ is a composite number. $r:$ $x$ is a perfect square. $s:$ $x$ is a prime number. The integer $x\geq2$ which satisfies $\neg\left(\left(p\Rightarrow q\right) \wedge \left(\neg r \vee \neg s\right)\right)$ is ____________.
asked
Feb 12, 2016
in
Mathematical Logic
by
Sandeep Singh
Loyal
(
7.8k
points)

4.4k
views
gate20161
mathematicallogic
normal
numericalanswers
propositionallogic
+36
votes
10
answers
21
GATE201535
The number of $4$ digit numbers having their digits in nondecreasing order (from left to right) constructed by using the digits belonging to the set $\{1, 2, 3\}$ is ________.
asked
Feb 14, 2015
in
Combinatory
by
jothee
Veteran
(
116k
points)

3.7k
views
gate20153
permutationsandcombinations
normal
numericalanswers
+36
votes
2
answers
22
GATE199292,xv
Which of the following predicate calculus statements is/are valid? $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$ $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$ ... $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$
asked
Sep 2, 2014
in
Mathematical Logic
by
Arjun
Veteran
(
400k
points)

4.5k
views
gate1992
mathematicallogic
normal
firstorderlogic
+35
votes
8
answers
23
GATE2016127
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

6.9k
views
gate20161
permutationsandcombinations
recurrence
normal
numericalanswers
+35
votes
4
answers
24
GATE2014350
There are two elements $x,\:y$ in a group $(G,*)$ such that every element in the group can be written as a product of some number of $x$'s and $y$'s in some order. It is known that $x*x=y*y=x*y*x*y=y*x*y*x=e$ where $e$ is the identity element. The maximum number of elements in such a group is ____.
asked
Sep 28, 2014
in
Set Theory & Algebra
by
jothee
Veteran
(
116k
points)

4.1k
views
gate20143
settheory&algebra
groups
numericalanswers
normal
+35
votes
5
answers
25
GATE2014150
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 value of $ \log_2 \log_2N $ is _______.
asked
Sep 28, 2014
in
Set Theory & Algebra
by
jothee
Veteran
(
116k
points)

3.6k
views
gate20141
settheory&algebra
functions
permutationsandcombinations
numericalanswers
+35
votes
6
answers
26
GATE200340
A graph $G=(V,E)$ satisfies $E \leq 3 V  6$. The mindegree of $G$ is defined as $\min_{v\in V}\left\{degree (v)\right \}$. Therefore, mindegree of $G$ cannot be $3$ $4$ $5$ $6$
asked
Sep 17, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.8k
points)

3.3k
views
gate2003
graphtheory
normal
degreeofgraph
+35
votes
5
answers
27
GATE20002.6
Let $P(S)$ denotes the power set of set $S.$ Which of the following is always true? $P(P(S)) = P(S)$ $P(S) ∩ P(P(S)) = \{ Ø \}$ $P(S) ∩ S = P(S)$ $S ∉ P(S)$
asked
Sep 14, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.8k
points)

3.5k
views
gate2000
settheory&algebra
easy
sets
+34
votes
10
answers
28
GATE2016126
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

8.4k
views
gate20161
permutationsandcombinations
generatingfunctions
normal
numericalanswers
+34
votes
4
answers
29
GATE200671
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$
asked
Sep 26, 2014
in
Graph Theory
by
Rucha Shelke
Active
(
3.7k
points)

4.4k
views
gate2006
graphtheory
normal
degreeofgraph
+33
votes
6
answers
30
GATE2017102
Consider the firstorder logic sentence $F:\forall x(\exists yR(x,y))$. Assuming nonempty logical domains, which of the sentences below are implied by $F$? $\exists y(\exists xR(x,y))$ $\exists y(\forall xR(x,y))$ $\forall y(\exists xR(x,y))$ $¬\exists x(\forall y¬R(x,y))$ IV only I and IV only II only II and III only
asked
Feb 14, 2017
in
Mathematical Logic
by
khushtak
Loyal
(
7.7k
points)

5.1k
views
gate20171
mathematicallogic
firstorderlogic
Page:
1
2
3
4
5
6
...
174
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has started
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
All categories
General Aptitude
1.7k
Engineering Mathematics
7.4k
Discrete Mathematics
5.2k
Mathematical Logic
2.1k
Set Theory & Algebra
1.4k
Combinatory
898
Graph Theory
801
Probability
989
Linear Algebra
686
Calculus
497
Digital Logic
2.9k
Programming & DS
4.9k
Algorithms
4.3k
Theory of Computation
6k
Compiler Design
2k
Operating System
4.2k
Databases
4.1k
CO & Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.4k
Others
1.6k
Admissions
591
Exam Queries
643
Tier 1 Placement Questions
23
Job Queries
72
Projects
23
Follow @csegate
Recent Blog Comments
It was free when I gave them, maybe they made it...
The tests are there but it ain't free. Cost is...
They removed their tests recently, I think it'll...
how did you get Success gateway test series for...
49,781
questions
53,593
answers
185,825
comments
70,880
users