GATE CSE 2008 | Mathematical Logic Question 31 | Discrete Mathematics

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

If $$P$$, $$Q$$, $$R$$ are Boolean variables, then $$(P + \bar{Q}) (P.\bar{Q} + P.R) (\bar{P}.\bar{R} + \bar{Q})$$ simplifies to

$$P.\overline Q $$

$$P.\overline R $$

$$P.\overline Q + R$$

$$P.\overline R + Q$$