Recent questions and answers in Mathematical Logic / GATE Overflow for GATE CSE

5 votes

3 answers

1

GO Classes CS Test Series 2025 | Discrete Mathematics | Topic Wise Test 1 | Question: 1
For a given predicate $\mathrm{P}(\mathrm{x}),$ you might believe that the statements $\forall \mathrm{xP}(\mathrm{x})$ or $\exists \mathrm{xP}(\mathrm{x})$ ... the domain, that $P(n)$ is true. Show for every element $n$ in the domain, that $P(n)$ is false.

For a given predicate $\mathrm{P}(\mathrm{x}),$ you might believe that the statements $\forall \mathrm{xP}(\mathrm{x})$ or $\exists \mathrm{xP}(\mathrm{x})$ are either tr...

Cxdr

414 views

Cxdr answered 22 hours ago

1 votes

1 answer

2

Kenneth Rosen Edition 7 Exercise 1.4 Question 39 (Page No. 55)
Translate these specifications into English where $F(p)$ is Printer $p$ is out of service, $B(p)$ is Printer $p$ is busy, $L(j )$ is Print job $j$ is lost, and $Q(j )$is Print job $j$ ... $(\forall p B(p) \wedge \forall j Q(j)) \rightarrow \exists j L(j)$

Translate these specifications into English where $F(p)$ is“Printer $p$ is out of service,”$B(p)$ is “Printer $p$ is busy,”$L(j )$ is “Print job $j$ is lost,”...

Bhaskar_Saini

537 views

Bhaskar_Saini answered 1 day ago

0 votes

1 answer

3

Memory Based GATE DA 2024 | Question: 57
First-order logic question: All balls are round except rugby balls.

First-order logic question: All balls are round except rugby balls.

Prakash_017

152 views

Prakash_017 answered 3 days ago

0 votes

1 answer

4

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

natelikesnoise

84 views

natelikesnoise answered 5 days ago

15 votes

2 answers

5

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

902 views

KG answered 6 days ago

2 votes

1 answer

6

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

128 views

mo7ammedfarooq answered May 8

1 votes

2 answers

7

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

145 views

hypnotized answered May 1

0 votes

1 answer

8

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

150 views

Kaustubh Parmar answered Apr 30

6 votes

3 answers

9

GO Classes CS Test Series 2025 | Discrete Mathematics | Topic Wise Test 1 | Question: 5
Consider the statement $\text{S} :$ "For all natural numbers $n,$ if $n$ is prime, then $n$ is antisocial." You do not need to know what antisocial means for this problem, just that it is a property ... $10$ is antisocial. $10$ is not antisocial. $7$ is antisocial. $7$ is not antisocial.

Consider the statement $\text{S} :$ "For all natural numbers $n,$ if $n$ is prime, then $n$ is antisocial."You do not need to know what antisocial means for this problem,...

pinaksh10

440 views

pinaksh10 answered Apr 26

9 votes

2 answers

10

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

pinaksh10

480 views

pinaksh10 answered Apr 25

14 votes

2 answers

11

GO Classes CS Test Series 2025 | Discrete Mathematics | Topic Wise Test 1 | Question: 9
Many programming languages support a ternary conditional operator. For example, in $\text{C, C++},$ and $\text{Java}$, the expression $x ? y : z$ means evaluate the boolean expression $x.$ If it's true, the entire expression ... $p ? p : (\neg p)$ is tautology. $(\neg p) ? p : (\neg p)$ is tautology.

Many programming languages support a ternary conditional operator. For example, in $\text{C, C++},$ and $\text{Java}$, the expression $x ? y : z$ means “evaluate the bo...

https_guru

532 views

https_guru answered Apr 25

35 votes

4 answers

12

GO Classes CS 2025 | Weekly Quiz 2 | Propositional Logic | Question: 12
Two compound propositions are logically equivalent if they have the same truth table. For example, the following two compound propositions are logically equivalent: $\mathrm{p} \rightarrow \mathrm{q}$ ... propositional variables, how many compound propositions are there that are Not logically equivalent to each other?

Two compound propositions are logically equivalent if they have the same truth table.For example, the following two compound propositions are logically equivalent: $\math...

AjithAddala

1.4k views

AjithAddala answered Apr 21

0 votes

1 answer

13

Linear Algebra AX=B
Consider a matrix A (n×m) ,X(m×n) and B(n×n) such that AX=B . If A has k linearly independent columns then what conclusions can we nake about the number of linearly independent columns of B.

Consider a matrix A (n×m) ,X(m×n) and B(n×n) such that AX=B . If A has k linearly independent columns then what conclusions can we nake about the number of linearly in...

Sahil5635

107 views

Sahil5635 answered Apr 20

3 votes

2 answers

14

Poset
Consider the poset ({3,5,9,15,24,45},|). Which of the following is correct for the given poset? A. There exists a least element but not a greatest element B. There exists a greatest element but not a least element C. There exists a greatest element and a least element D. There does not exist a greatest element and a least element

Consider the poset ({3,5,9,15,24,45},|). Which of the following is correct for the given poset? A. There exists a least element but not a greatest elementB. There exists ...

Sahil5635

289 views

Sahil5635 answered Apr 20

0 votes

1 answer

15

self doubt
how to check the validity of an a argument using laws of logics

how to check the validity of an a argument using laws of logics

Sahil5635

61 views

Sahil5635 answered Apr 15

3 votes

2 answers

16

self doubt
Twin primes are pairs of numbers p and p+2 such that both are primes-for instance, 5 and 7, 11 and 13, 41 and 43. The Twin Prime Conjecture says that there are infinitely many twin primes. Let TwinPrime(n) be a predicate that is true if n and n+2 are twin primes. Which of the ... (n)) ∃m. ∀n. n ≤ m implies TwinPrime(n) ∃m. ∀n. TwinPrime(n) implies n ≤ m ∀m. ∃n. n ≤ m and TwinPrime(n)

Twin primes are pairs of numbers p and p+2 such that both are primes—for instance, 5 and 7, 11 and 13, 41 and 43. The Twin Prime Conjecture says that there are infinite...

Deepak Poonia

602 views

Deepak Poonia answered Apr 14

26 votes

6 answers

17

GO Classes CS 2025 | Weekly Quiz 1 | Propositional Logic | Question: 15
Consider the following popular puzzle. A boy and a girl are talking. One of them has black hair, another has white hair. I am a boy said the child with black hair. I am a girl said the child with white hair ... Which of them is lying? The boy only The girl only Both of them Information is not sufficient to find out the liar

Consider the following popular puzzle.A boy and a girl are talking. One of them has black hair, another has white hair.“I am a boy” said the child with black hair.“...

KG

1.7k views

KG answered Apr 14

58 votes

8 answers

18

GO Classes CS 2025 | Weekly Quiz 1 | Propositional Logic | Question: 14
Consider the following popular puzzle. When asked for the ages of her three children, Mrs. Baker says that Alice is her youngest child if Bill is not her youngest child, and that Alice is not her youngest child ... is her youngest child. Carl is her youngest child. Information is not sufficient to find out the youngest child.

Consider the following popular puzzle.When asked for the ages of her three children, Mrs. Baker says that “Alice is her youngest child if Bill is not her youngest child...

KG

3.9k views

KG answered Apr 14

31 votes

5 answers

19

GATE CSE 1989 | Question: 14a
Symbolize the expression "Every mother loves her children" in predicate logic.

Symbolize the expression "Every mother loves her children" in predicate logic.

Ayon Sinha

6.1k views

Ayon Sinha answered Apr 12

1 votes

2 answers

20

Does Either...Or means Exclusive Or or Inclusive Or?
Let's take a compound propositions Either it is below freezing or it is snowing. Now if $p$: it is below freezing $q$: it is snowing Will it be $p \vee q$ or $p \oplus q$? There are some instances where semantics are ... both cases can't be true, because if you are ill you can't appear for example and you must be in one state.

Let's take a compound propositionsEither it is below freezing or it is snowing.Now if$p$: it is below freezing $q$: it is snowingWill it be $p \vee q$ or $p \oplus q$? Th...

dhruvak23

234 views

dhruvak23 answered Apr 11

4 votes

2 answers

21

GO Classes CS 2025 | Weekly Quiz 3 | Propositional Logic | Question: 6
The implies connective $\rightarrow$ is one of the stranger connectives in propositional logic. Below are a series of statements regarding implications. Which of the following statements is/are TRUE? For any propositions $P$ ... $R,$ the following statement is always true: $(P \rightarrow Q) \vee (R \rightarrow Q)$.

The “implies” connective “$\rightarrow$” is one of the stranger connectives in propositional logic. Below are a series of statements regarding implications.Which ...

ayushgemini

413 views

ayushgemini answered Apr 9

1 votes

1 answer

22

GATE 2022 | Linear Algebra | Question 11
Let 𝑴 be a 2 × 2 real matrix such that $(𝑰 + 𝑴)^-1 = 𝑰 − 𝛼𝑴$, where 𝛼 is a non-zero real number and 𝑰 is the 2 × 2 identity matrix. If the trace of the matrix 𝑴 is 3, then the value of 𝛼 is (A) 3/4 (B) 1/3 (C) 1/2 (D) 1/4

Let 𝑴 be a 2 × 2 real matrix such that $(𝑰 + 𝑴)^-1 = 𝑰 − 𝛼𝑴$, where 𝛼 is a non-zero real number and 𝑰 is the 2 × 2 identity matrix. If the tra...

C1h2a3i4t5

142 views

C1h2a3i4t5 answered Apr 8

0 votes

1 answer

23

BME entrance exam
A hash function h maps 16-bit inputs to 8-bit hash values. What is the largest k such that in any set of 1000 inputs, there are at least k inputs that h maps to the same hash value?

A hash function h maps 16-bit inputs to 8-bit hash values. What is the largest k such that in any set of 1000 inputs, there are at least k inputs that h maps to the same ...

bhanu7486

84 views

bhanu7486 answered Apr 8

0 votes

1 answer

24

Made Easy Mock Test 2

Sherry_22

290 views

Sherry_22 answered Apr 8

0 votes

1 answer

25

Internet
A non empty set A is termed as an algebraic structure ________ a)with respect to binary operation * b)with respect to ternary operation ? c)with respect to binary operation + d)with respect to unary operation –

A non empty set A is termed as an algebraic structure ________a)with respect to binary operation *b)with respect to ternary operation ?c)with respect to binary operation ...

bhanu7486

121 views

bhanu7486 answered Apr 6

2 votes

2 answers

26

Memory Based GATE DA 2024 | Question: 33
Which of the following are tautologies? $x \land \neg y \Rightarrow y \rightarrow x$ $\neg x \land y \Rightarrow \neg x \rightarrow y$ $x \land \neg y \Rightarrow \neg x \rightarrow y$ $\neg x \land y \Rightarrow y \rightarrow x$

Which of the following are tautologies? $x \land \neg y \Rightarrow y \rightarrow x$$\neg x \land y \Rightarrow \neg x \rightarrow y$\(x \land \neg y \Rightarrow \ne...

i_m_sudip

290 views

i_m_sudip answered Apr 3

0 votes

0 answers

27

BME entrance exam
A data file of 1,000,000 records must be stored using bucket hashing. Record length is 350 bytes, the net capacity of a block is 2000 bytes. Keys occupy 32 bytes, while pointers need 8 bytes. Each bucket consists of 2 blocks. How many blocks are needed at least to store the whole structure (i.e. data file + hash table) on disc? Select one:

A data file of 1,000,000 records must be stored using bucket hashing. Record length is 350 bytes, the net capacity of a block is 2000 bytes. Keys occupy 32 bytes, while p...

Ilqar

94 views

Ilqar asked Apr 2

12 votes

3 answers

28

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 58
Let $\mathrm{F}$ and $\mathrm{G}$ be two propositional formulae. Which of the following is/are True? If $F \vee G$ is a tautology then at least one of $F, G$ is a tautology. If $F \wedge G$ is a contradiction then at ... $G$ is a tautology. If $F \rightarrow G$ is a contradiction then $F$ is a tautology and $G$ is a contradiction.

Let $\mathrm{F}$ and $\mathrm{G}$ be two propositional formulae.Which of the following is/are True?If $F \vee G$ is a tautology then at least one of $F, G$ is a tautology...

Lakshmi Narayana404

934 views

Lakshmi Narayana404 answered Apr 2

76 votes

8 answers

29

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

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

i_m_sudip

13.2k views

i_m_sudip answered Mar 30

12 votes

2 answers

30

GO Classes CS 2025 | Weekly Quiz 3 | Propositional Logic | Question: 8
The Logic Problem, taken from $\text{"WFF'N PROOF, The Game of Logic"}$ has these two assumptions: "Logic is difficult or not many students like logic." "If mathematics is easy, then logic ... is not easy or logic is difficult." "Logic is not difficult or mathematics is not easy."

The Logic Problem, taken from $\text{"WFF'N PROOF, The Game of Logic"}$ has these two assumptions:"Logic is difficult or not many students like logic.""If mathematics is ...

tejashmore25

551 views

tejashmore25 answered Mar 29

7 votes

2 answers

31

GO Classes CS 2025 | Weekly Quiz 3 | Propositional Logic | Question: 10
Let $F$ and $G$ be two propositional formula. Which of the following is/are True? $F \vee G$ is a tautology iff at least one of them is a tautology If $F \rightarrow G$ is a tautology and $F$ ... is a tautology. $(F \rightarrow G) \wedge (F \rightarrow \neg G)$ is a tautology iff $F$ is a contradiction.

Let $F$ and $G$ be two propositional formula.Which of the following is/are True?$F \vee G$ is a tautology iff at least one of them is a tautologyIf $F \rightarrow G$ is a...

samitmohan

910 views

samitmohan answered Mar 29

10 votes

6 answers

32

GO Classes CS 2025 | Weekly Quiz 3 | Propositional Logic | Question: 3
Consider the following atomic propositions: $\text{R}$: It is Raining $\text{S}$ ... , and vice versa It is raining is equivalent to sonu is sick It is raining or sonu is sick but not both

Consider the following atomic propositions:$\text{R}$: It is Raining$\text{S}$: Sonu is SickWhich of the following is/are correct English Translation of the following log...

samitmohan

835 views

samitmohan answered Mar 29

6 votes

2 answers

33

GO Classes CS 2025 | Weekly Quiz 3 | Propositional Logic | Question: 5
Which of the following compound propositions is/are a tautology? $[p \land (p \rightarrow q)] \rightarrow q$ $[q \land (p \rightarrow q)] \rightarrow p$ $[(p \lor q) \land (r \rightarrow p) \land (r \rightarrow q)] \rightarrow r$ $[(p \lor q) \land (p \rightarrow r) \land (q \rightarrow r)] \rightarrow r$

Which of the following compound propositions is/are a tautology?$[p \land (p \rightarrow q)] \rightarrow q$$[q \land (p \rightarrow q)] \rightarrow p$$[(p \lor q) \land (...

samitmohan

227 views

samitmohan answered Mar 29

7 votes

2 answers

34

GO Classes CS 2025 | Weekly Quiz 3 | Propositional Logic | Question: 4
Consider the following arguments. $\text{Argument 1:}$ ... ? Only Argument $1$ is valid. Only Argument $2$ is valid. Both Arguments are valid. No Argument is valid.

Consider the following arguments.$\text{Argument 1:}$ Kerry errs or Myrna fails to show. If Kerry errs, then he does not break the record. Myrna fails to show. Therefore,...

https_guru

541 views

https_guru answered Mar 29

22 votes

6 answers

35

GO Classes CS 2025 | Weekly Quiz 3 | Propositional Logic | Question: 9
Which of the following statements is/are true? The argument form with premises $p_1, p_2, \ldots, p_n$ and conclusion $q \rightarrow r$ is valid iff the argument form with premises $p_1, p_2, \ldots, p_n, r$ ... the argument form with premises $p_1, p_2, \ldots, p_n, \sim r$, and conclusion $\sim q$ is valid.

Which of the following statements is/are true?The argument form with premises $p_1, p_2, \ldots, p_n$ and conclusion $q \rightarrow r$ is valid iff the argument form with...

Lakshmi Narayana404

1.6k views

Lakshmi Narayana404 answered Mar 29

8 votes

4 answers

36

GATE CSE 2024 | Set 2 | Question: 2
Let $p$ and $q$ be the following propositions: $p$ : Fail grade can be given. $q$ : Student scores more than $50 \%$ marks. Consider the statement: "Fail grade cannot be given when student scores more than $50 \%$ marks." ... above statement in propositional logic? $q \rightarrow \neg p$ $q \rightarrow p$ $p \rightarrow q$ $\neg p \rightarrow q$

Let $p$ and $q$ be the following propositions:$p$ : Fail grade can be given.$q$ : Student scores more than $50 \%$ marks.Consider the statement: "Fail grade c...

Bhaskar_Saini

3.8k views

Bhaskar_Saini answered Mar 29

15 votes

3 answers

37

GO Classes CS 2025 | Weekly Quiz 1 | Propositional Logic | Question: 10
Given the truth table of a Binary Operation \$ as follows: $ ... }$ Identify the matching Boolean Expression. $X \$ \neg Y$ $\neg X \$ Y$ $\neg X \$ \neg Y$ none of the options

Given the truth table of a Binary Operation \$ as follows:$$\begin{array}{|l|l|l|l|} \hline {} \text{X} & \text{Y }& \text{X\$Y }\\ \hline \text{1} & \text{0 }& ...

Ayon Sinha

1.3k views

Ayon Sinha answered Mar 28

36 votes

3 answers

38

GO Classes CS 2025 | Weekly Quiz 2 | Propositional Logic | Question: 8
Let $\varphi$ be a propositional formula on a set of variables $A$ and $\psi$ be a propositional formula on a set of variables $B$ , such that $\varphi$ $\Rightarrow$ $\psi$ . A $\textit{Craig interpolant}$ of $\varphi$ and $\psi$ ... interpolant for $\varphi$ and $\psi?$ $\varphi$ itself $q \vee s$ $q \vee r$ $\neg q \wedge s$

Let $\varphi$ be a propositional formula on a set of variables $A$ and $\psi$ be a propositional formula on a set of variables $B$ , such that $\varphi$ $\Rightarrow$...

Sahil5635

866 views

Sahil5635 answered Mar 27

9 votes

5 answers

39

GO Classes CS 2025 | Weekly Quiz 1 | Propositional Logic | Question: 2
A sufficient condition for a triangle $T$ be a right triangle is that $a^2+b^2=c^2$. An equivalent statement is If $T$ is a right triangle then $a^2+b^2=c^2$. If $a^2+b^2=c^2$ then $T$ is a right triangle. If $a^2+b^2\neq c^2$ then $T$ is not a right triangle. $T$ is a right triangle only if $a^2+b^2=c^2$.

A sufficient condition for a triangle $T$ be a right triangle is that $a^2+b^2=c^2$. An equivalent statement isIf $T$ is a right triangle then $a^2+b^2=c^2$.If $a^2+b^2=c...

tejashmore25

1.7k views

tejashmore25 answered Mar 27

73 votes

8 answers

40

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

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(\ex...

TusharRana

17.5k views

TusharRana answered Mar 26

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