GATE CSE 2021 Set 1 | Mathematical Logic Question 1 | Discrete Mathematics

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.67

Let p and q be two propositions. Consider the following two formulae in propositional logic.

S₁ : (¬p ∧ (p ∨ q)) → q

S₂ : q → (¬p ∧ (p ∨ q))

Which one of the following choices is correct?

Neither S₁ nor S₂ is a tautology.

S₁ is not a tautology but S₂ is a tautology.

Both S₁ and S₂ are tautologies.

S₁ is a tautology but S₂ is not a tautology.

GATE CSE 2020

MCQ (Single Correct Answer)

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

$$\forall x$$(p(x) $$ \vee $$ W) $$ \equiv $$ $$\forall x$$ p(x) $$ \vee $$ W

$$\exists x$$(p(x) $$ \wedge $$ W) $$ \equiv $$ $$\exists x$$ p(x) $$ \wedge $$ W

$$\forall x$$(p(x) $$ \to $$ W) $$ \equiv $$ $$\forall x$$ p(x) $$ \to $$ W

$$\exists x$$(p(x) $$ \to $$ W) $$ \equiv $$ $$\exists x$$ p(x) $$ \to $$ W

GATE CSE 2018

MCQ (Single Correct Answer)

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

There exists at least one model of $$\varphi $$ with universe of size less than or equal to $$3.$$

There exists no model of $$\varphi $$ with universe of size less than or equal to $$3.$$

There exists no model of $$\varphi $$ with universe of size greater than $$7.$$

Every model of $$\varphi $$ has a universe of size equal to $$7.$$

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.6

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

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

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

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

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