1
GATE CSE 2009
+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
+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
+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
+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
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
EXAM MAP
Joint Entrance Examination