GATE CSE 2008 | Mathematical Logic Question 28 | Discrete Mathematics

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Which of the following first order formulae is logically valid? Here $$\alpha \left( x \right)$$ is a first order formulae with $$x$$ as a free variable, and $$\beta $$ is a first order formula with no free variable.

$$\left[ {\beta \to \left( {\exists x,\alpha \left( x \right)} \right)} \right] \to \left[ {\forall x,\beta \to \alpha \left( x \right)} \right]$$

$$\left[ {\exists x,\beta \to \alpha \left( x \right)} \right] \to \left[ {\beta \to \left( {\forall x,\alpha \left( x \right)} \right)} \right]$$

$$\left[ {\left( {\exists x,\alpha \left( x \right)} \right) \to \beta } \right] \to \left[ {\forall x,\alpha \left( x \right) \to \beta } \right]$$

$$\left[ {\left( {\forall x,\alpha \left( x \right)} \right) \to \beta } \right] \to \left[ {\forall x,\alpha \left( x \right) \to \beta } \right]$$

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

$$P$$ and $$Q$$ are two propositions. Which of the following logical expressions are equivalent?

$${\rm I}.$$ $${\rm P}\, \vee \sim Q$$
$${\rm I}{\rm I}.$$ $$ \sim \left( { \sim {\rm P} \wedge Q} \right)$$
$${\rm I}{\rm I}{\rm I}.$$ $$\left( {{\rm P} \wedge Q} \right) \vee \left( {{\rm P} \wedge \sim Q} \right) \vee \left( { \sim {\rm P} \wedge \sim Q} \right)$$
$${\rm I}V.$$ $$\left( {{\rm P} \wedge Q} \right) \vee \left( {{\rm P} \wedge \sim Q} \right) \vee \left( { \sim {\rm P} \wedge Q} \right)$$

Only $${\rm I}$$ and $${\rm I}$$$${\rm I}$$

Only $${\rm I}$$, $${\rm I}$$$${\rm I}$$ and $${\rm I}$$$${\rm I}$$$${\rm I}$$

Only $${\rm I}$$, $${\rm I}$$$${\rm I}$$ and $${\rm I}$$$$V$$

All of $${\rm I}$$, $${\rm I}$$$${\rm I}$$, $${\rm I}$$$${\rm I}$$$${\rm I}$$ and $${\rm I}$$$$V$$

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Which of the following is the negation of $$$\left[ {\forall x,\alpha \to \left( {\exists y,\beta \to \left( {\forall u,\exists v,\gamma } \right)} \right)} \right]?$$$

$$\left[ {\exists x,\alpha \to \left( {\forall y,\beta \to \left( {\exists u,\forall v,\gamma } \right)} \right)} \right]$$

$$\left[ {\exists x,\alpha \to \left( {\forall y,\beta \to \left( {\exists u,\forall v,\neg \gamma } \right)} \right)} \right]$$

$$\left[ {\forall x,\neg \alpha \to \left( {\exists y,\neg \beta \to \left( {\forall u,\exists v,\neg \gamma } \right)} \right)} \right]$$

$$\left[ {\exists x,\alpha \wedge \left( {\forall y,\beta \wedge \left( {\exists u,\forall v,\neg \gamma } \right)} \right)} \right]$$

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Which one of these first-order logic formulae is valid?

$$\forall x\left( {P\left( x \right) \Rightarrow Q\left( x \right)} \right) \Rightarrow \left( {\left( {\forall xP\left( x \right)} \right) \Rightarrow \left( {\forall xQ\left( x \right)} \right)} \right)$$

$$\exists x\left( {P\left( x \right) \vee Q\left( x \right)} \right) \Rightarrow \left( {\left( {\exists xP\left( x \right)} \right) \Rightarrow \left( {\exists xQ\left( x \right)} \right)} \right)$$

$$\exists x\left( {P\left( x \right) \wedge Q\left( x \right)} \right) \Leftrightarrow \left( {\left( {\exists xP\left( x \right)} \right) \wedge \left( {\exists xQ\left( x \right)} \right)} \right)$$

$$\forall x\exists yP\left( {x,y} \right) \Rightarrow \exists y\forall xP\left( {x,y} \right)$$

PREVIOUS NEXT