1
GATE CSE 2009
MCQ (Single Correct Answer)
+2
-0.6
Consider the following well-formed formulae:

$${\rm I}.$$ $$\,\,\neg \forall x\left( {P\left( x \right)} \right)$$
$${\rm I}{\rm I}.\,\,\,\,\,\,\neg \exists x\left( {P\left( x \right)} \right)$$
$${\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\neg \exists x\left( {\neg P\left( x \right)} \right)$$
$${\rm I}V.\,\,\,\,\,\,\exists x\left( {\neg P\left( x \right)} \right)$$

Which of the above are equivalent?

A
$${\rm I}$$ and $${\rm I}$$$${\rm I}$$
B
$${\rm I}$$ and $${\rm I}$$$$V$$
C
$${\rm I}$$$${\rm I}$$ and $${\rm I}$$$${\rm I}$$$${\rm I}$$
D
$${\rm I}$$$${\rm I}$$ and $${\rm I}$$$$V$$
2
GATE CSE 2009
MCQ (Single Correct Answer)
+2
-0.6
The binary operation ◻ is defined as follows:

Which one of the following is equivalence to $$P \vee Q$$?

A
$$\neg \,Q$$ ◻ $$\neg \,P$$
B
$$P$$ ◻ $$\neg \,Q$$
C
$$\neg \,P$$ ◻ $$Q$$
D
$$\neg \,P$$ ◻ $$\neg \,Q$$
3
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-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
A
$$P.\overline Q$$
B
$$P.\overline R$$
C
$$P.\overline Q + R$$
D
$$P.\overline R + Q$$
4
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Let fsa and $$pda$$ be two predicates such that fsa$$(x)$$ means $$x$$ is a finite state automation, and pda$$(y)$$ means that $$y$$ is a pushdown automation. Let $$equivalent$$ be another predicate such that $$equivalent$$$$(a,b)$$ means $$a$$ and $$b$$ are equivalent. Which of the following first order logic statements represents the following:

Each finite state automation has an equivalent pushdown automation.

A
$$\left( {\forall x\,\,fsa\left( x \right)} \right) \Rightarrow \left( {\exists y\,\,pda\left( y \right) \wedge \,equivalent\,\,\left( {x,\,y} \right)} \right)$$
B
$$\sim \forall y\left( {\exists x\,\,fsa\left( x \right) \Rightarrow pda\left( y \right) \wedge \,equivalent\left( {x,\,y} \right)} \right)$$
C
$$\forall x\,\exists y\left( {fsa\left( x \right) \wedge pda\left( y \right) \wedge \,equivalent\left( {x,\,y} \right)} \right)$$
D
$$\forall x\,\exists y\left( {fsa\left( y \right) \wedge pda\left( x \right) \wedge \,equivalent\left( {x,\,y} \right)} \right)$$
GATE CSE Subjects
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12