GATE CS Propositional and First Order Logic questions

For two different persons $x$ and $y$, the predicate $M(x, y)$ denotes that $x$ knows $y$. Consider the following statement. There is a person who does not know anyone else, but that person is known by everyone else. Which one of the following expressions represents the above statement?

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"? The meanings of the predicates used are: mother $(y, x): y$ is the mother of $x$ noteq $(x, y): x$ and $y$ are not equal

​​​Let $P(x)$ be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?

​​​​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." Which one of the following is the CORRECT representation of the above statement in propositional logic?

Geetha has a conjecture about integers, which is of the form $$\forall x(P(x) \Longrightarrow \exists y Q(x, y)),$$ where $P$ is a statement about integers, and $Q$ is a statement about pairs of integers. Which of the following (one or more) option(s) would imply Geetha's conjecture?

Let $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic. $S_1: (\neg p\wedge(p\vee q))\rightarrow q$ $S_2: q\rightarrow(\neg p\wedge(p\vee q))$ Which one of the following choices is correct?

Choose the correct choice(s) regarding the following proportional logic assertion $S$: $$S: (( P \wedge Q) \rightarrow R) \rightarrow (( P \wedge Q) \rightarrow (Q \rightarrow R))$$

Which one of the following predicate formulae is NOT logically valid? Note that $W$ is a predicate formula without any free occurrence of $x$.

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 that $’a \text{ divides } b’$ , where $a$ and $b$ are integers. Consider the following sets: …

Consider the first-order logic sentence $$\varphi \equiv \exists \: s \: \exists \: t \: \exists \: u \: \forall \: v \: \forall \: w \forall \: x \: \forall \: y \: \psi(s, t, u, v, w, x, y)$$ where $\psi(s, t, u, v, w, x, y, )$ is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. …

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))$

The statement $\left ( ¬p \right ) \Rightarrow \left ( ¬q \right )$ is logically equivalent to which of the statements below? $p \Rightarrow q$ $q \Rightarrow p$ $\left ( ¬q \right ) \vee p$ $\left ( ¬p \right ) \vee q$

Let $p, q, r$ denote the statements ”It is raining”, “It is cold”, and “It is pleasant”, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by

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

Which one of the following well-formed formulae in predicate calculus is NOT valid ?

Consider the following expressions: $false$ $Q$ $true$ $P\vee Q$ $\neg Q\vee P$ The number of expressions given above that are logically implied by $P \wedge (P \Rightarrow Q)$ is ___________.

Which one of the following is NOT equivalent to $p ↔ q$?

Which one of the following well-formed formulae is a tautology?

Consider the following two statements. $S_1$: If a candidate is known to be corrupt, then he will not be elected $S_2$: If a candidate is kind, he will be elected Which one of the following statements follows from $S_1$ and $S_2$ as per sound inference rules of logic?

In a room there are only two types of people, namely $\text{Type 1}$ and $\text{Type 2}$. $\text{Type 1}$ people always tell the truth and $\text{Type 2}$ people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking the …