Previous GATE Questions in Discrete Mathematics / GATE Overflow for GATE CSE

34 votes

6 answers

271

GATE CSE 2004 | Question: 24
Consider the binary relation: $S= \left\{\left(x, y\right) \mid y=x+1 \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$ The reflexive transitive closure is $S$ ... $\left\{\left(x, y\right) \mid y \leq x \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$

Consider the binary relation:$S= \left\{\left(x, y\right) \mid y=x+1 \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$The reflexive transitive closure is $S$ is$\lef...

Kathleen

9.9k views

Kathleen asked Sep 18, 2014

88 votes

7 answers

272

GATE CSE 2004 | Question: 23, ISRO2007-32
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)))$

Identify the correct translation into logical notation of the following assertion.Some boys in the class are taller than all the girlsNote: $\text{taller} (x, y)$ is true...

Kathleen

131k views

Kathleen asked Sep 18, 2014

37 votes

8 answers

273

GATE CSE 2006 | Question: 28
A logical binary relation $\odot$ ... $(\sim A\odot B)$ $\sim(A \odot \sim B)$ $\sim(\sim A\odot\sim B)$ $\sim(\sim A\odot B)$

A logical binary relation $\odot$, is defined as follows: $$\begin{array}{|l|l|l|} \hline \textbf{A} & \textbf{B}& \textbf{A} \odot \textbf{B}\\\hline \text{True} & \text...

Rucha Shelke

5.9k views

Rucha Shelke asked Sep 18, 2014

45 votes

3 answers

274

GATE CSE 2006 | Question: 27
Consider the following propositional statements: $P_1: ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))$ $P_2: ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))$ Which one of the following is true? $P_1$ is a tautology, but not $P_2$ $P_2$ is a tautology, but not $P_1$ $P_1$ and $P_2$ are both tautologies Both $P_1$ and $P_2$ are not tautologies

Consider the following propositional statements:$P_1: ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))$$P_2: ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))$Which one of...

Rucha Shelke

8.6k views

Rucha Shelke asked Sep 18, 2014

54 votes

6 answers

275

GATE CSE 2006 | Question: 26
Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or threatened. ...

Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or ...

Rucha Shelke

9.3k views

Rucha Shelke asked Sep 18, 2014

77 votes

9 answers

276

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$

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...

Rucha Shelke

11.1k views

Rucha Shelke asked Sep 18, 2014

58 votes

7 answers

277

GATE CSE 2006 | Question: 24
Given a set of elements $N = {1, 2, ..., n}$ and two arbitrary subsets $A⊆N$ and $B⊆N$, how many of the n! permutations $\pi$ from $N$ to $N$ satisfy $\min(\pi(A)) = \min(\pi(B))$, where $\min(S)$ is the smallest integer in the set of integers $S$, and $\pi$(S) is the set of ... $n! \frac{|A ∩ B|}{|A ∪ B|}$ $\dfrac{|A ∩ B|^2}{^n \mathrm{C}_{|A ∪ B|}}$

Given a set of elements $N = {1, 2, ..., n}$ and two arbitrary subsets $A⊆N$ and $B⊆N$, how many of the n! permutations $\pi$ from $N$ to $N$ satisfy $\min(\pi(A)) = ...

Rucha Shelke

11.3k views

Rucha Shelke asked Sep 18, 2014

25 votes

8 answers

278

GATE CSE 2006 | Question: 22
Let $E, F$ and $G$ be finite sets. Let $X = (E ∩ F) - (F ∩ G)$ and $Y = (E - (E ∩ G)) - (E - F)$. Which one of the following is true? $X ⊂ Y$ $X ⊃ Y$ $X = Y$ $X - Y ≠ \emptyset$ and $Y - X ≠ \emptyset$

Let $E, F$ and $G$ be finite sets. Let$X = (E ∩ F) - (F ∩ G)$ and$Y = (E - (E ∩ G)) - (E - F)$.Which one of the following is true?$X ⊂ Y$$X ⊃ Y$$X = Y$$X - Y �...

Rucha Shelke

6.7k views

Rucha Shelke asked Sep 17, 2014

58 votes

6 answers

279

GATE CSE 2003 | Question: 72
The following resolution rule is used in logic programming. Derive clause $(P \vee Q)$ from clauses $(P\vee R),(Q \vee ¬R)$ Which of the following statements related to this rule is FALSE? $((P ∨ R)∧(Q ∨ ¬R))⇒(P ∨ Q)$ ... if $(P ∨ R)∧(Q ∨ ¬R)$ is satisfiable $(P ∨ Q)⇒ \text{FALSE}$ if and only if both $P$ and $Q$ are unsatisfiable

The following resolution rule is used in logic programming.Derive clause $(P \vee Q)$ from clauses $(P\vee R),(Q \vee ¬R)$Which of the following statements related to th...

Kathleen

14.3k views

Kathleen asked Sep 17, 2014

65 votes

9 answers

280

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$

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-d...

Kathleen

15.7k views

Kathleen asked Sep 17, 2014

46 votes

6 answers

281

GATE CSE 2003 | Question: 39
Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows: $g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$. Let $p_i$ denote the i-th prime number $\left(p_1 = 2\right)$ ... numbers is the encoding, $h$, of a non-empty sequence of strings? $2^73^75^7$ $2^83^85^8$ $2^93^95^9$ $2^{10}3^{10}5^{10}$

Let $\Sigma = \left\{a, b, c, d, e\right\}$ be an alphabet. We define an encoding scheme as follows:$g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11$.Let $p_i$ denote t...

Kathleen

7.6k views

Kathleen asked Sep 17, 2014

41 votes

10 answers

282

GATE CSE 2003 | Question: 38
Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows: ... $(x, y)$ that satisfy the equations) is $0$ $1$ $2$ $3$

Consider the set $\{a, b, c\}$ with binary operators $+$ and $*$ defined as follows:$$\begin{array}{|c|c|c|c|} \hline \textbf{+} & \textbf{a}& \textbf{b} &\textbf{c...

Kathleen

7.1k views

Kathleen asked Sep 17, 2014

61 votes

6 answers

283

GATE CSE 2003 | Question: 37
Let $f : A \to B$ be an injective (one-to-one) function. Define $g : 2^A \to 2^B$ as: $g(C) = \left \{f(x) \mid x \in C\right\} $, for all subsets $C$ of $A$. Define $h : 2^B \to 2^A$ as: $h(D) = \{x \mid x \in A, f(x) \in D\}$, for all ... always true? $g(h(D)) \subseteq D$ $g(h(D)) \supseteq D$ $g(h(D)) \cap D = \phi$ $g(h(D)) \cap (B - D) \ne \phi$

Let $f : A \to B$ be an injective (one-to-one) function. Define $g : 2^A \to 2^B$ as:$g(C) = \left \{f(x) \mid x \in C\right\} $, for all subsets $C$ of $A$.Define ...

Kathleen

8.2k views

Kathleen asked Sep 16, 2014

60 votes

10 answers

284

GATE CSE 2003 | Question: 36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$

How many perfect matching are there in a complete graph of $6$ vertices?$15$$24$$30$$60$

Kathleen

50.4k views

Kathleen asked Sep 16, 2014

23 votes

9 answers

285

GATE CSE 2003 | Question: 34
$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be placed in the bags if each bag must contain at least $k$ ... $\left( \begin{array}{c} m - kn + n + k - 2 \\ n - k \end{array} \right)$

$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be place...

Kathleen

11.2k views

Kathleen asked Sep 16, 2014

114 votes

6 answers

286

GATE CSE 2003 | Question: 33
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: ... I_1\) does not Neither $I_1$ nor $I_2$ satisfies $\alpha$ Both $I_1$ and $I_2$ satisfies $\alpha$

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...

Kathleen

15.9k views

Kathleen asked Sep 16, 2014

59 votes

7 answers

287

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.9k views

Kathleen asked Sep 16, 2014

58 votes

6 answers

288

GATE CSE 2003 | Question: 31
Let $(S, \leq)$ be a partial order with two minimal elements a and b, and a maximum element c. Let P: S $\to$ {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) $\implies$ P(y) for all $x, y \in S$ satisfying $x \leq y$ ... for all x $\in$ S such that b ≤ x and x ≠ c P(x) = False for all x $\in$ S such that a ≤ x and b ≤ x

Let $(S, \leq)$ be a partial order with two minimal elements a and b, and a maximum element c. Let P: S $\to$ {True, False} be a predicate defined on S. Suppose that P(...

Kathleen

11.8k views

Kathleen asked Sep 16, 2014

65 votes

5 answers

289

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$

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 neces...

Kathleen

15.4k views

Kathleen asked Sep 16, 2014

33 votes

2 answers

290

GATE CSE 2003 | Question: 7
Consider the set $\Sigma^*$ of all strings over the alphabet $\Sigma = \{0, 1\}$. $\Sigma^*$ with the concatenation operator for strings does not form a group forms a non-commutative group does not have a right identity element forms a group if the empty string is removed from $\Sigma^*$

Consider the set $\Sigma^*$ of all strings over the alphabet $\Sigma = \{0, 1\}$. $\Sigma^*$ with the concatenation operator for stringsdoes not form a groupforms a non-c...

Kathleen

9.0k views

Kathleen asked Sep 16, 2014

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