Recent activity in Discrete Mathematics / GATE Overflow for GATE CSE

35 votes

5 answers

1

GATE IT 2006 | Question: 6
Given a boolean function $f (x_1, x_2, \ldots, x_n),$ which of the following equations is NOT true? $f (x_1, x_2, \ldots, x_n) = x_1'f(x_1, x_2, \ldots, x_n) + x_1f(x_1, x_2, \ldots, x_n)$ ... $f (x_1, x_2, \ldots , x_n) = f(0, x_2, , x_n) + f(1, x_2, \ldots, x_n)$

Given a boolean function $f (x_1, x_2, \ldots, x_n),$ which of the following equations is NOT true?$f (x_1, x_2, \ldots, x_n) = x_1'f(x_1, x_2, \ldots, x_n) + x_1f(x_1, x...

Rakmo

6.3k views

Rakmo commented 1 hour ago

0 votes

1 answer

2

Kenneth H. Rosen, Chapter 1
When three professors are seated in a restaurant, the hostess asks them: Does everyone want coffee? The first professor says: I do not know. The second professor then says: I do not know. Finally, the third professor says: No, not ... wants coffee. The hostess comes back and gives coffee to the professors who want it. How did she figure out who wanted coffee?

When three professors are seated in a restaurant, the hostess asks them: “Does everyone want coffee?” The first professor says: “I do not know.” The second profe...

Shubham Sharma 2

68 views

Shubham Sharma 2 retagged 8 hours ago

35 votes

8 answers

3

GATE CSE 2009 | Question: 24
The binary operation $\Box$ ... following is equivalent to $P \vee Q$? $\neg Q \Box \neg P$ $P\Box \neg Q$ $\neg P\Box Q$ $\neg P\Box \neg Q$

The binary operation $\Box$ is defined as follows$$\begin{array}{|c|c|c|} \hline \textbf{P} & \textbf{Q} & \textbf{P} \Box \textbf{Q}\\\hline \text{T} & \text{T}& \text{T...

꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂

8.7k views

꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ commented 23 hours ago

15 votes

2 answers

4

GO Classes CS Test Series 2025 | Discrete Mathematics | Topic Wise Test 1 | Question: 2
Consider the following proposition : $\text{A}_{n} = \underbrace{(p \rightarrow (q \rightarrow (p \rightarrow (q \rightarrow (\dots)))))}_{\text{number of p's + number of q's = n}}.$ Which of the following is false for ... $n > 2, \text{A}_{n}$ is Not contingency.

Consider the following proposition :$\text{A}_{n} = \underbrace{(p \rightarrow (q \rightarrow (p \rightarrow (q \rightarrow (\dots)))))}_{\text{number of p’s + number o...

KG

865 views

KG answered 1 day ago

2 votes

1 answer

5

GO 2023 Topic Wise Free Test 1 | Question: 3
Which of the following expressions is always true? $\neg p \vee p$ $\neg p \wedge p$ $\neg p \wedge \neg p$ none of the above

Which of the following expressions is always true?$\neg p \vee p$$\neg p \wedge p$$\neg p \wedge \neg p$none of the above

mo7ammedfarooq

122 views

mo7ammedfarooq answered 2 days ago

42 votes

9 answers

6

GATE CSE 2020 | Question: 39
Which one of the following predicate formulae is NOT logically valid? Note that $W$ is a predicate formula without any free occurrence of $x$. $\forall x (p(x) \vee W) \equiv \forall x \: ( px) \vee W$ ... $\exists x(p(x) \rightarrow W) \equiv \forall x \: p(x) \rightarrow W$

Which one of the following predicate formulae is NOT logically valid?Note that $W$ is a predicate formula without any free occurrence of $x$.$\forall x (p(x) \vee W) \equ...

Deepak Poonia

17.5k views

Deepak Poonia comment edited 2 days ago

1 votes

2 answers

7

# FREE VARIABLE ( NULL QUANTIFICATION ) Related problem
Given that LHS : [(∃x,α(x))→β] RHS : [∃x,α(x)→β] than which one is valid ? a) LHS → RHS b) RHS → LHS

Given that LHS : [(∃x,α(x))→β]RHS : [∃x,α(x)→β]than which one is valid ?a) LHS → RHSb) RHS → LHS

Deepak Poonia

507 views

Deepak Poonia answer edited 2 days ago

4 votes

2 answers

8

FREE VARIABLE and VALIDITY related problem
Given that LHS : [(∃x,α(x))→β] RHS : [∃x,α(x)→β] Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable. than which one is valid ? a) LHS → RHS b) RHS → LHS

Given that LHS : [(∃x,α(x))→β]RHS : [∃x,α(x)→β]Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free v...

Deepak Poonia

643 views

Deepak Poonia answer edited 2 days ago

3 votes

1 answer

9

Null Quantification Rule
What is the meaning of NULL Quantification Rule in Predicate Calculus ?

What is the meaning of NULL Quantification Rule in Predicate Calculus ?

Deepak Poonia

3.6k views

Deepak Poonia answer edited 2 days ago

13 votes

2 answers

10

GO Classes CS Test Series 2025 | Discrete Mathematics | Topic Wise Test 1 | Question: 11
Translate the following sentences into First-order logic (FOL): If someone is noisy, everybody is annoyed. Use the following predicates : $\text{N}(x)\;:$ $x$ is noisy $\text{A}(x)\;:$ $x$ is annoyed Which of the ... $\forall x(\text{N}(x) \rightarrow \forall y(\text{A}(y)))$

Translate the following sentences into First-order logic (FOL): “ If someone is noisy, everybody is annoyed.”Use the following predicates :$\text{N}(x)\;:$ “$x$ is ...

Deepak Poonia

773 views

Deepak Poonia answer edited 2 days ago

9 votes

2 answers

11

GO Classes CS Test Series 2025 | Discrete Mathematics | Topic Wise Test 1 | Question: 15
Let's make a trip to a new world called "Never Never Land". Regular, ordinary first-order logic has two quantifiers: $\forall$ and $\exists$. Now, let's imagine we lived in a world in which these quantifiers ... $\mathrm{Nx}(\neg A(x) \wedge B(x))$

Let's make a trip to a new world called "Never Never Land".Regular, ordinary first-order logic has two quantifiers: $\forall$ and $\exists$.Now, let's imagine we lived in...

Amlan Kumar Majumdar

460 views

Amlan Kumar Majumdar commented 2 days ago

89 votes

7 answers

12

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

Knight_Hawk

132k views

Knight_Hawk commented 2 days ago

7 votes

2 answers

13

GO Classes CS Test Series 2025 | Discrete Mathematics | Topic Wise Test 3 | Question: 12
Let $\mathbf{Z}$ be set of integers, and $+$ be an integer addition operation. Let $p, q$ be distinct primes. If $\text{J}$ is a proper subgroup of $(\mathbf{Z}, +)$ containing exactly three of $\{p, p + q, pq, p^q, q^p\},$ ... $\{pq, p^{q}, q^{p}\}$ $\{p, pq, p^{q}\}$ $\{p, pq, q^{p}\}$

Let $\mathbf{Z}$ be set of integers, and “$+$” be an integer addition operation.Let $p, q$ be distinct primes. If $\text{J}$ is a proper subgroup of $(\mathbf{Z}, +)$...

Cxdr

578 views

Cxdr answered 2 days ago

30 votes

6 answers

14

GATE CSE 2002 | Question: 2.17
The binary relation $S= \phi \text{(empty set)}$ on a set $A = \left \{ 1,2,3 \right \}$ is Neither reflexive nor symmetric Symmetric and reflexive Transitive and reflexive Transitive and symmetric

The binary relation $S= \phi \text{(empty set)}$ on a set $A = \left \{ 1,2,3 \right \}$ is Neither reflexive nor symmetricSymmetric and reflexiveTransitive and reflexive...

Deepak Poonia

13.1k views

Deepak Poonia commented 2 days ago

1 votes

2 answers

15

Discrete Mathematics | Propositional Logic | Test 2 | Question: 11
Consider the following argument: If either wages or prices are raised, there will be inflation. If there is inflation, then either Congress must regulate it or the people will suffer. If the people suffer, Congressmen ... $P \rightarrow Q$ is a tautology. Validity of the given argument can't be determined.

Consider the following argument: If either wages or prices are raised, there will be inflation. If there is inflation, then either Congress must regulate it or ...

MrBananaMan

997 views

MrBananaMan commented 2 days ago

0 votes

0 answers

16

Counting
Suppose that there are nine students in a discrete mathematics class at a small college. a) Show that the class must have at least five male students or at least five female students. b) Show that the class must have at least three male students or at least seven female students.

Suppose that there are nine students in a discrete mathematics class at a smallcollege.a) Show that the class must have at least five male students or at least five femal...

Shubham Sharma 2

30 views

Shubham Sharma 2 retagged 3 days ago

0 votes

1 answer

17

GATE DS&AI 2024 | Question: 19
Let $x$ and $y$ be two propositions. Which of the following statements is a tautology /are tautologies? $(\neg x \wedge y) \Rightarrow(y \Rightarrow x)$ $(x \wedge \neg y) \Rightarrow(\neg x \Rightarrow y)$ $(\neg x \wedge y) \Rightarrow(\neg x \Rightarrow y)$ $(x \wedge \neg y) \Rightarrow(y \Rightarrow x)$

Let $x$ and $y$ be two propositions. Which of the following statements is a tautology /are tautologies?$(\neg x \wedge y) \Rightarrow(y \Rightarrow x)$$...

Arjun

823 views

Arjun recategorized 3 days ago

13 votes

2 answers

18

GO Classes CS 2025 | Weekly Quiz 4 | Set Theory | Question: 7
Power set of empty set has exactly _______ subsets. One Two Zero Three

Power set of empty set has exactly _______ subsets.OneTwoZeroThree

Himashis Biswas

361 views

Himashis Biswas answered 3 days ago

9 votes

2 answers

19

Discrete Mathematics question

Bharadwaja1557

3.7k views

Bharadwaja1557 answered 4 days ago

2 votes

1 answer

20

composition of function
Let f : A → B and g : B → C denote two functions. Consider the following two statements: S1 : If both f and g are injections then the composition function gof: A → C is an injection. S2 : If the function gof: A → C is surjection and g is an ... a)) and h(a) is onto then g must be onto, where ∀a, a ∈ A. Which of the above statements are valid? please give explanation

Let f : A → B and g : B → C denote two functions. Consider the following two statements:S1 : If both f and g are injections then the composition function gof: A → C...

Deepak Poonia

949 views

Deepak Poonia commented 4 days ago

0 votes

1 answer

21

Function Composition Question Oscar Levin Qn. 20
Let $f : X \rightarrow Y$ and $g : Y \rightarrow Z$ be functions. We can define the composition of $f$ and $g$ to be the function $g \circ f : X \rightarrow Z$ for which the image of each $x \in X$ is $g( f (x))$. That is, plug ... $f$ and $g$? Explain. (d) Suppose $g \circ f$ is surjective. What, if anything, can you say about $f$ and $g$? Explain.

Let $f : X \rightarrow Y$ and $g : Y \rightarrow Z$ be functions. We can define the composition of $f$ and $g$ to be the function $g \circ f : X \rightarrow Z$ for which ...

Deepak Poonia

44 views

Deepak Poonia answered 4 days ago

1 votes

3 answers

22

UGC NET CSE | January 2017 | Part 2 | Question: 3
The functions mapping $R$ into $R$ are defined as : $f\left(x \right)=x^{3} - 4x, g\left(x \right)=\frac{1}{x^{2}+1}$ and $h\left(x \right)=x^{4}.$ Then find the value of the following composite functions : $h_{o}g\left(x \right)$ ... $\left ( x^{2}+1 \right )^{-4}$ and $\left [ \left ( x^{3}-4x \right )^{2}+1 \right ]^{-4}$

The functions mapping $R$ into $R$ are defined as :$f\left(x \right)=x^{3} - 4x, g\left(x \right)=\frac{1}{x^{2}+1}$ and $h\left(x \right)=x^{4}.$Then find the value of t...

Deepak Poonia

942 views

Deepak Poonia commented 4 days ago

12 votes

1 answer

23

GO Classes CS Test Series 2025 | Discrete Mathematics | Topic Wise Test 1| Question: 12
We define a new quantifier, uniqueness quantifier, the symbol of which is $\exists!.$ For any predicate $\text{P}$ and universe $\text{U}, \exists! x \text{P}(x)$ ... I, II, IV I, III II, III, IV IV only

We define a new quantifier, uniqueness quantifier, the symbol of which is $\exists!.$For any predicate $\text{P}$ and universe $\text{U}, \exists! x \text{P}(x)$ means th...

Deepak Poonia

625 views

Deepak Poonia commented 4 days ago

6 votes

1 answer

24

GO Classes CS Test Series 2025 | Discrete Mathematics | Topic Wise Test 1 | Question: 8
Let $P(x), Q(x), R(x)$ and $S(x)$ denote the following predicates with domain $\mathbb{Z}$ ... $\forall x \in \mathbb{Z}, \quad S(x) \rightarrow(Q(x) \wedge S(x))$

Let $P(x), Q(x), R(x)$ and $S(x)$ denote the following predicates with domain $\mathbb{Z}$ :$$\begin{aligned}& P(x): x^2-x-12=0, \\& Q(x): x \text { is odd, } \\& R(x): x...

Deepak Poonia

322 views

Deepak Poonia commented 4 days ago

4 votes

1 answer

25

GO Classes CS 2025 | Weekly Quiz 5 | Set Theory | Question: 9
Which of the following statements is $\textbf{TRUE}$? For all sets $A, B$, and $C, A-(B-C)=(A-B)-C$. For all sets $A, B$, and $C,(A-B) \cap(C-B)=(A \cap C)-B$. For all sets $A, B$, and $C,(A-B) \cap(C-B)=A-(B \cup C)$. For all sets $A, B$, and $C$, if $A \cap C=B \cap C$ then $A=B$.

Which of the following statements is $\textbf{TRUE}$?For all sets $A, B$, and $C, A-(B-C)=(A-B)-C$.For all sets $A, B$, and $C,(A-B) \cap(C-B)=(A \cap C)-B$.For all sets ...

Srken

127 views

Srken answered May 3

1 votes

2 answers

26

Permutation and combination
Your mother-in-law buys 1000 small gifts to give to relatives for Christmas. Each of the 1000 things in different. There are 25 relatives to give gifts to. How many ways are there to distribute the gifts? The correct answer is $25^{1000}$. I ... ? I know some people may feel its silly question but please trust me many people like me are confused with this doubt.

Your mother-in-law buys 1000 small gifts to give to relatives for Christmas. Each of the 1000 things in different. There are 25 relatives to give gifts to. How many ways ...

hypnotized

139 views

hypnotized answered May 1

0 votes

1 answer

27

ISI PCB 2023 Q1
Suppose there are three types of people in the world. A person is honest if the person always speaks the truth. A person is a liar if the person always lies. A person is normal if the person sometimes speaks the truth and sometimes lies. In a city ... . C: B is not normal. Based on the above, deduce with appropriate justifications who among A, B and C has committed the crime.

Suppose there are three types of people in the world.A person is “honest” if the person always speaks the truth. A person is a “liar” if the person always lies. A...

Kaustubh Parmar

109 views

Kaustubh Parmar answered Apr 30

0 votes

0 answers

28

ISI PCB 2023 Q3

vbsurya

47 views

vbsurya asked Apr 30

1 votes

0 answers

29

ISI PCB 2023 Q2

vbsurya

32 views

vbsurya asked Apr 30

1 votes

2 answers

30

GO Classes 2023 | IIITH Mock Test 1 | Question: 1
Let $\text{R}$ be a relation from a set $\text{A}$ to a set $\text{B}.$ The inverse relation from $\text{B}$ to $\text{A},$ denoted by $\text{R}^{-1},$ is the set of ordered pairs $\{(b,a) \mid (a,b) \in R\}$ ... $\text{S1}$ Only $\text{S2}$ Both $\text{S1}$ and $\text{S2}$ None of the above

Let $\text{R}$ be a relation from a set $\text{A}$ to a set $\text{B}.$ The inverse relation from $\text{B}$ to $\text{A},$ denoted by $\text{R}^{-1},$ is the set of orde...

rachna-2000

1.1k views

rachna-2000 answered Apr 28

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