GATE Questions & Answers of First Order Logic

Consider the first order predicate formula $\varphi$:

$ \forall x\lbrack(\forall z\;z\vert x\Rightarrow((z=x)\vee(z=1)))\Rightarrow\exists w\;(w>x)\wedge(\forall z\;z\vert w\Rightarrow((w=z)\vee(z=1)))\rbrack $ Here $'a\vert b'$ denotes that ‘$a$ divides $b$’, where $a$ and $b$ are integers. Consider the following sets:

S1.   {1,2,3, … , 100}

S2.   Set of all positive integers

S3.   Set of all integers

Which of the above sets satisfy $\varphi$?

•  (A)  S1 and S2
•  (B)  S1 and S3
•  (C)  S2 and S3
•  (D)  S1, S2 and S3

Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. 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 automaton has an equivalent pushdown automaton.

•  (A) $\left(\forall x fsa\left(x\right)\right)\Rightarrow \left(\exists y pda\left(y\right) \Lambda \mathrm{equivalent} \left(x,y\right)\right)$
•  (B) $~\forall y\left(\exists x fsa\left(x\right)\Rightarrow pda\left(y\right) \Lambda \mathrm{equivalent} \left(x,y\right)\right)$
•  (C) $\forall x\exists y\left(fsa\left(x\right) \Lambda pda\left(y\right) \Lambda equivalent \left(x,y\right)\right)$
•  (D) $\forall x\exists y\left(fsa\left(y\right) \Lambda pda\left(x\right) \Lambda equivalent \left(x,y\right)\right)$

Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: “Not every graph is connected”?

•  (A) $\neg \forall x\left(Graph\left(x\right)\Rightarrow Connected\left(x\right)\right)$
•  (B) $\exists x\left(Graph\left(x\right)\wedge \neg Connected\left(x\right)\right)$
•  (C) $\neg \forall x\left(\neg Graph\left(x\right)\vee Connected\left(x\right)\right)$
•  (D) $\forall x\left(Graph\left(x\right)\Rightarrow \neg Connected\left(x\right)\right)$