1
GATE CSE 2020
+2
-0.67
Which one of the following predicate formulae is NOT logically valid?

Note that W is a predicate formula without any free occurrence of x.
A
$$\forall x$$(p(x) $$\vee$$ W) $$\equiv$$ $$\forall x$$ p(x) $$\vee$$ W
B
$$\exists x$$(p(x) $$\wedge$$ W) $$\equiv$$ $$\exists x$$ p(x) $$\wedge$$ W
C
$$\forall x$$(p(x) $$\to$$ W) $$\equiv$$ $$\forall x$$ p(x) $$\to$$ W
D
$$\exists x$$(p(x) $$\to$$ W) $$\equiv$$ $$\exists x$$ p(x) $$\to$$ W
2
GATE CSE 2018
+2
-0.6
Consider the first-order logic sentence
$$\varphi \equiv \,\,\,\,\,\,\,\exists s\exists t\exists u\forall v\forall w$$ $$\forall x\forall y\psi \left( {s,t,u,v,w,x,y} \right)$$
where $$\psi$$ $$(𝑠,𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦)$$ is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose $$\varphi$$ has a model with a universe containing $$7$$ elements.

Which one of the following statements is necessarily true?

A
There exists at least one model of $$\varphi$$ with universe of size less than or equal to $$3.$$
B
There exists no model of $$\varphi$$ with universe of size less than or equal to $$3.$$
C
There exists no model of $$\varphi$$ with universe of size greater than $$7.$$
D
Every model of $$\varphi$$ has a universe of size equal to $$7.$$
3
GATE CSE 2016 Set 2
+2
-0.6
Which one of the following well-formed formulae in predicate calculus is NOT valid?
A
$$\left( {\forall xp\left( x \right) \vee \forall xq\left( x \right)} \right) \Rightarrow \left( {\exists x\neg p\left( x \right) \vee \forall xq\left( x \right)} \right)$$
B
$$\left( {\exists xp\left( x \right) \vee \exists xq\left( x \right)} \right) \Rightarrow \exists x\left( {p\left( x \right) \vee q\left( x \right)} \right)$$
C
$$\exists x\left( {p\left( x \right) \wedge q\left( x \right)} \right) \Rightarrow \left( {\exists xp\left( x \right) \wedge \exists xq\left( x \right)} \right)$$
D
$$\forall x\left( {p\left( x \right) \vee q\left( x \right)} \right) \Rightarrow \left( {\forall xp\left( x \right) \vee \forall xq\left( x \right)} \right)$$
4
GATE CSE 2015 Set 2
+2
-0.6
Which one of the following well formed formulae is a tautology?
A
$$\forall x\,\exists y\,R\left( {x,y} \right) \leftrightarrow \exists y\forall x\,R\left( {x,y} \right)$$
B
$$\left( {\forall x\left[ {\exists y\,R\left( {x,y} \right) \to S\left( {x,y} \right)} \right]} \right) \to \forall x\exists y\,S\left( {x,y} \right)$$
C
$$\left[ {\forall x\,\exists y\,\left( {P\left( {x,y} \right)} \right. \to R\left( {x,y} \right)} \right] \leftrightarrow \left[ {\forall x\,\exists y\,\left( {\neg P\left( {x,y} \right)V\,R\left( {x,y} \right)} \right.} \right]$$
D
$$\forall x\,\forall y\,P\left( {x,y} \right) \to \forall x\forall y\,P\left( {y,x} \right)$$
GATE CSE Subjects
EXAM MAP
Medical
NEET