Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Filter
Recent
Hot!
Most votes
Most answers
Most views
Previous GATE
Featured
Highest voted questions in Discrete Mathematics
76
votes
9
answers
21
GATE CSE 2006 | Question: 25
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$
Rucha Shelke
asked
in
Set Theory & Algebra
Sep 18, 2014
by
Rucha Shelke
11.0k
views
gatecse-2006
set-theory&algebra
normal
functions
73
votes
6
answers
22
GATE IT 2007 | Question: 25
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$
Ishrat Jahan
asked
in
Graph Theory
Oct 29, 2014
by
Ishrat Jahan
21.4k
views
gateit-2007
graph-theory
graph-connectivity
normal
72
votes
7
answers
23
GATE CSE 2017 Set 1 | Question: 02
Consider the first-order logic sentence $F:\forall x(\exists yR(x,y))$. Assuming non-empty 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
khushtak
asked
in
Mathematical Logic
Feb 14, 2017
by
khushtak
17.2k
views
gatecse-2017-set1
mathematical-logic
first-order-logic
71
votes
7
answers
24
GATE CSE 2016 Set 1 | Question: 1
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 ____________.
Sandeep Singh
asked
in
Mathematical Logic
Feb 12, 2016
by
Sandeep Singh
12.9k
views
gatecse-2016-set1
mathematical-logic
normal
numerical-answers
propositional-logic
70
votes
5
answers
25
GATE CSE 2008 | Question: 30
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}$ ...
Kathleen
asked
in
Mathematical Logic
Sep 12, 2014
by
Kathleen
14.0k
views
gatecse-2008
easy
mathematical-logic
first-order-logic
69
votes
6
answers
26
GATE CSE 2016 Set 2 | Question: 27
Which one of the following well-formed formulae in predicate calculus is NOT valid ? $(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\exists _{x} \neg p(x) \vee \forall _{x} q(x))$ ... $\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$
Akash Kanase
asked
in
Mathematical Logic
Feb 12, 2016
by
Akash Kanase
16.8k
views
gatecse-2016-set2
mathematical-logic
first-order-logic
normal
69
votes
5
answers
27
GATE CSE 2010 | Question: 30
Suppose the predicate $F(x, y, t)$ is used to represent the statement that person $x$ can fool person $y$ at time $t$. Which one of the statements below expresses best the meaning of the formula, $\qquad∀x∃y∃t(¬F(x,y,t))$ Everyone can ... time No one can fool everyone all the time Everyone cannot fool some person all the time No one can fool some person at some time
gatecse
asked
in
Mathematical Logic
Sep 21, 2014
by
gatecse
70.0k
views
gatecse-2010
mathematical-logic
easy
first-order-logic
68
votes
9
answers
28
GATE IT 2008 | Question: 21
Which of the following first order formulae is logically valid? Here $\alpha(x)$ is a first order formula with $x$ as a free variable, and $\beta$ ... $[(\forall x, \alpha(x)) \rightarrow \beta] \rightarrow [\forall x, \alpha(x) \rightarrow \beta]$
Ishrat Jahan
asked
in
Mathematical Logic
Oct 27, 2014
by
Ishrat Jahan
15.1k
views
gateit-2008
first-order-logic
normal
66
votes
10
answers
29
GATE CSE 2019 | Question: 35
Consider the first order predicate formula $\varphi$: $\forall x [ ( \forall z \: z | x \Rightarrow (( z=x) \vee (z=1))) \rightarrow \exists w ( w > x) \wedge (\forall z \: z | w \Rightarrow ((w=z) \vee (z=1)))]$ Here $a \mid b$ denotes ... of all integers Which of the above sets satisfy $\varphi$? $S_1$ and $S_2$ $S_1$ and $S_3$ $S_2$ and $S_3$ $S_1, S_2$ and $S_3$
Arjun
asked
in
Mathematical Logic
Feb 7, 2019
by
Arjun
19.9k
views
gatecse-2019
engineering-mathematics
discrete-mathematics
mathematical-logic
first-order-logic
2-marks
66
votes
10
answers
30
GATE CSE 2016 Set 1 | Question: 27
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n-1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
Sandeep Singh
asked
in
Combinatory
Feb 12, 2016
by
Sandeep Singh
28.1k
views
gatecse-2016-set1
combinatory
recurrence-relation
normal
numerical-answers
65
votes
16
answers
31
GATE CSE 2015 Set 3 | Question: 5
The number of $4$ digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set $\{1, 2, 3\}$ is ________.
go_editor
asked
in
Combinatory
Feb 14, 2015
by
go_editor
15.6k
views
gatecse-2015-set3
combinatory
normal
numerical-answers
65
votes
4
answers
32
GATE CSE 2006 | Question: 71
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$
Rucha Shelke
asked
in
Graph Theory
Sep 26, 2014
by
Rucha Shelke
17.1k
views
gatecse-2006
graph-theory
normal
degree-of-graph
65
votes
9
answers
33
GATE CSE 2004 | Question: 75
Mala has the colouring book in which each English letter is drawn two times. She wants to paint each of these $52$ prints with one of $k$ colours, such that the colour pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of $k$ that satisfies this requirement? $9$ $8$ $7$ $6$
Kathleen
asked
in
Combinatory
Sep 18, 2014
by
Kathleen
16.6k
views
gatecse-2004
combinatory
65
votes
9
answers
34
GATE CSE 2003 | Question: 40
A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-degree of $G$ cannot be $3$ $4$ $5$ $6$
Kathleen
asked
in
Graph Theory
Sep 17, 2014
by
Kathleen
15.6k
views
gatecse-2003
graph-theory
normal
degree-of-graph
65
votes
5
answers
35
GATE CSE 2003 | Question: 8, ISRO2009-53
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must necessarily lie down between $k$ and $n$ $k-1$ and $k+1$ $k-1$ and $n-1$ $k+1$ and $n-k$
Kathleen
asked
in
Graph Theory
Sep 16, 2014
by
Kathleen
15.3k
views
gatecse-2003
graph-theory
graph-connectivity
normal
isro2009
64
votes
6
answers
36
GATE CSE 2015 Set 1 | Question: 16
For a set $A$, the power set of $A$ is denoted by $2^{A}$. If $A = \left\{5,\left\{6\right\}, \left\{7\right\}\right\}$, which of the following options are TRUE? $\varnothing \in 2^{A}$ $\varnothing \subseteq 2^{A}$ ... I and III only II and III only I, II and III only I, II and IV only
makhdoom ghaya
asked
in
Set Theory & Algebra
Feb 13, 2015
by
makhdoom ghaya
15.5k
views
gatecse-2015-set1
set-theory&algebra
set-theory
normal
64
votes
9
answers
37
GATE IT 2006 | Question: 25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
Ishrat Jahan
asked
in
Graph Theory
Oct 31, 2014
by
Ishrat Jahan
13.1k
views
gateit-2006
graph-theory
graph-coloring
normal
63
votes
5
answers
38
GATE CSE 2014 Set 3 | Question: 2
Let $X$ and $Y$ be finite sets and $f:X \to Y$ be a function. Which one of the following statements is TRUE? For any subsets $A$ and $B$ of $X, |f(A \cup B)| = |f(A)| + |f(B)|$ For any subsets $A$ and $B$ of $X, f(A \cap B) = f(A) \cap f(B)$ For any subsets $A$ ... $S$ and $T$ of $Y, f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$
go_editor
asked
in
Set Theory & Algebra
Sep 28, 2014
by
go_editor
14.0k
views
gatecse-2014-set3
set-theory&algebra
functions
normal
63
votes
14
answers
39
GATE CSE 2014 Set 1 | Question: 49
A pennant is a sequence of numbers, each number being $1$ or $2$. An $n-$pennant is a sequence of numbers with sum equal to $n$. For example, $(1,1,2)$ is a $4-$pennant. The set of all possible $1-$pennants is ${(1)}$, the set of all possible ... $(1,2)$ is not the same as the pennant $(2,1)$. The number of $10-$pennants is________
go_editor
asked
in
Combinatory
Sep 28, 2014
by
go_editor
11.4k
views
gatecse-2014-set1
combinatory
numerical-answers
normal
62
votes
6
answers
40
GATE IT 2006 | Question: 21
Consider the following first order logic formula in which $R$ is a binary relation symbol. $∀x∀y (R(x, y) \implies R(y, x))$ The formula is satisfiable and valid satisfiable and so is its negation unsatisfiable but its negation is valid satisfiable but its negation is unsatisfiable
Ishrat Jahan
asked
in
Mathematical Logic
Oct 31, 2014
by
Ishrat Jahan
13.3k
views
gateit-2006
mathematical-logic
normal
first-order-logic
Page:
« prev
1
2
3
4
5
6
7
...
355
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Discrete Mathematics
(7.1k)
Mathematical Logic
(2.5k)
Set Theory & Algebra
(1.9k)
Combinatory
(1.6k)
Graph Theory
(1.1k)
Probability
(1.4k)
Linear Algebra
(1.1k)
Calculus
(792)
Optimization
(0)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Aptitude Overflow