Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
Recent
Hot!
Most votes
Most answers
Most views
Previous GATE
Featured
Featured Questions in Discrete Mathematics
22
votes
1
answer
1
Recurrence Relation - Self Doubt
What is the recurrence relation for the ternary strings of length $n$ which can be constructed using 0,1 or 2 only such that the number of 0’s and number of 1's is odd ?
What is the recurrence relation for the ternary strings of length $n$ which can be constructed using 0,1 or 2 only such that the number of 0’s and number of 1's is od...
P C
1.5k
views
P C
asked
Dec 31, 2022
Combinatory
recurrence-relation
discrete-mathematics
+
–
0
votes
1
answer
2
Provided by teacher, topic -arguments
Show that: (r → ~ q, r ∪ S, S → ~ q, p → q) ↔ ~ p are inconsistent.
Show that: (r → ~ q, r ∪ S, S → ~ q, p → q) ↔ ~ pare inconsistent.
raj-123
274
views
raj-123
asked
Nov 26, 2022
Mathematical Logic
mathematical-logic
propositional-logic
descriptive
+
–
23
votes
4
answers
3
TIFR CSE 2016 | Part B | Question: 4
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 ...
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 :...
go_editor
3.1k
views
go_editor
asked
Dec 28, 2016
Mathematical Logic
tifr2016
mathematical-logic
first-order-logic
+
–
32
votes
3
answers
4
TIFR CSE 2017 | Part B | Question: 11
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
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...
go_editor
3.5k
views
go_editor
asked
Dec 23, 2016
Mathematical Logic
tifr2017
first-order-logic
+
–
24
votes
2
answers
5
GATE CSE 1987 | Question: 9e
How many true inclusion relations are there of the form $A \subseteq B$, where $A$ and $B$ are subsets of a set $S$ with $n$ elements?
How many true inclusion relations are there of the form $A \subseteq B$, where $A$ and $B$ are subsets of a set $S$ with $n$ elements?
makhdoom ghaya
3.1k
views
makhdoom ghaya
asked
Nov 14, 2016
Set Theory & Algebra
gate1987
set-theory&algebra
relations
descriptive
+
–
89
votes
6
answers
6
GATE CSE 2006 | Question: 72
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^{n-2}$ $2^{n-3}\times 3$ $2^{n-1}$
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...
go_editor
17.6k
views
go_editor
asked
Apr 24, 2016
Graph Theory
gatecse-2006
graph-theory
normal
degree-of-graph
+
–
8
votes
2
answers
7
MadeEasy Test Series: Mathematical Logic - First Order Logic
Match the following Lists List-I A. There are atmost two apples. B. There are exactly two apples. C. There is atmost one apple. D. There is exactly one apple. List-II 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$
Match the following ListsList-IA. There are atmost two apples.B. There are exactly two apples.C. There is atmost one apple.D. There is exactly one apple.List-II1. $\foral...
vikas khuswaha
1.5k
views
vikas khuswaha
asked
Jan 26, 2016
Mathematical Logic
made-easy-test-series
engineering-mathematics
discrete-mathematics
mathematical-logic
first-order-logic
+
–
4
votes
2
answers
8
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?
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 les...
Anu
3.8k
views
Anu
asked
Jul 13, 2015
Combinatory
counting
functions
+
–
9
votes
9
answers
9
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?
How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?
Anu
8.9k
views
Anu
asked
Jul 13, 2015
Combinatory
combinatory
counting
+
–
57
votes
3
answers
10
GATE IT 2005 | Question: 56
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$
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...
Ishrat Jahan
10.5k
views
Ishrat Jahan
asked
Nov 3, 2014
Graph Theory
gateit-2005
graph-theory
graph-connectivity
normal
+
–
19
votes
2
answers
11
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric? Please explain how to calculate .
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?Please explain how to calculate .
shree
25.9k
views
shree
asked
Oct 24, 2014
Set Theory & Algebra
set-theory&algebra
relations
+
–
100
votes
10
answers
12
GATE CSE 2014 Set 1 | Question: 51
Consider an undirected graph $G$ where self-loops 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 $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
Consider an undirected graph $G$ where self-loops 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 $...
go_editor
26.6k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set1
graph-theory
numerical-answers
normal
graph-connectivity
+
–
59
votes
8
answers
13
GATE CSE 2013 | Question: 26
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 ... 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
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 ...
Arjun
18.8k
views
Arjun
asked
Sep 24, 2014
Graph Theory
gatecse-2013
graph-theory
normal
graph-connectivity
+
–
59
votes
7
answers
14
GATE CSE 2003 | Question: 32
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)[β])$
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...
Kathleen
16.6k
views
Kathleen
asked
Sep 16, 2014
Mathematical Logic
gatecse-2003
mathematical-logic
first-order-logic
normal
+
–
78
votes
6
answers
15
GATE CSE 1992 | Question: 92,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)$
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) \w...
Arjun
16.3k
views
Arjun
asked
Sep 2, 2014
Mathematical Logic
gate1992
mathematical-logic
normal
first-order-logic
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register