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
Featured 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
+13
votes
2
answers
1
TIFR2016B4
In the following, $A$ stands for a set of apples, and $S(x, y)$ stands for "$x$ is sweeter than $y$. Let $\Psi \equiv \exists x : x \in A$ $\Phi \equiv \forall x \in A : \exists y \in A : S(x, y).$ Which of the following statements implies that there are infinitely many apples ( ...
asked
Dec 28, 2016
in
Mathematical Logic
by
jothee
Veteran
(
116k
points)

759
views
tifr2016
mathematicallogic
firstorderlogic
+17
votes
3
answers
2
TIFR2017B11
Given that $B(x)$ means "$x$ is a bat", $F(x)$ means "$x$ is a fly", and $E(x, y)$ means "x eats $y$", what is the best English translation of $ \forall x(F(x) \rightarrow \forall y (E(y, x) \rightarrow B(y)))?$ all flies eat bats every fly is eaten by some bat bats eat only flies every bat eats flies only bats eat flies
asked
Dec 23, 2016
in
Mathematical Logic
by
jothee
Veteran
(
116k
points)

783
views
tifr2017
firstorderlogic
+7
votes
0
answers
3
GATE19879e
How many true inclusion relations are there of the from $A \subseteq B$, where $A$ and $B$ are subsets of a set $S$ with $n$ elements?
asked
Nov 15, 2016
in
Set Theory & Algebra
by
makhdoom ghaya
Boss
(
41.2k
points)

413
views
gate1987
settheory&algebra
relations
+39
votes
4
answers
4
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
+5
votes
1
answer
5
MadeEasy Test Series: Mathematical Logic  First Order Logic
Match the following Lists ListI A. There are atmost two apples. B. There are exactly two apples. C. There is atmost one apple. D. There is exactly one apple. ListII 1. ... D (a) 1 2 3 4 (b) 3 2 1 4 (c) 1 3 2 4 (d) 3 1 2 4 $a$ $b$ $c$ $d$
asked
Jan 26, 2016
in
Mathematical Logic
by
vikas khuswaha
(
69
points)

452
views
madeeasytestseries
engineeringmathematics
discretemathematics
mathematicallogic
firstorderlogic
+3
votes
2
answers
6
number of function
How many functions are there from the set {1, 2, . . . , n}, where n is a positive integer, to the set {0, 1} a) that assign 1 to exactly one of the positive integers less than n?
asked
Jul 13, 2015
in
Combinatory
by
Anu
Loyal
(
5.9k
points)

867
views
counting
functions
+8
votes
7
answers
7
Kenneth Rosen Edition 6 Question 45 (Page No. 346)
How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?
asked
Jul 13, 2015
in
Combinatory
by
Anu
Loyal
(
5.9k
points)

2k
views
permutationsandcombinations
counting
+32
votes
2
answers
8
GATE2005IT56
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is $4$ $7$ $23$ $99$
asked
Nov 4, 2014
in
Graph Theory
by
Ishrat Jahan
Boss
(
19.1k
points)

2.5k
views
gate2005it
graphtheory
graphconnectivity
normal
+19
votes
2
answers
9
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?
asked
Oct 24, 2014
in
Set Theory & Algebra
by
shree
Active
(
3.5k
points)

13.6k
views
settheory&algebra
+52
votes
7
answers
10
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
+33
votes
3
answers
11
GATE201326
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ and $e'$ ... graph of a planar graph is planar. (S) The line graph of a tree is a tree. $P$ only $P$ and $R$ only $R$ only $P, Q$ and $S$ only
asked
Sep 24, 2014
in
Graph Theory
by
Arjun
Veteran
(
400k
points)

3.8k
views
gate2013
graphtheory
normal
linegraph
+25
votes
3
answers
12
GATE200332
Which of the following is a valid first order formula? (Here \(\alpha\) and \(\beta\) are first order formulae with $x$ as their only free variable) $((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α ⇒ β]$ $(∀x)[α] ⇒ (∃x)[α ∧ β]$ $((∀x)[α ∨ β] ⇒ (∃x)[α]) ⇒ (∀x)[α]$ $(∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])$
asked
Sep 16, 2014
in
Mathematical Logic
by
Kathleen
Veteran
(
59.8k
points)

4.8k
views
gate2003
mathematicallogic
firstorderlogic
normal
+36
votes
2
answers
13
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
To see more, click for the
full list of questions
or
popular tags
.
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,721
questions
53,593
answers
185,825
comments
70,878
users