GATE Questions & Answers of First Order Logic

What is the Weightage of First Order Logic in GATE Exam?

Total 3 Questions have been asked from First Order Logic topic of Discrete Mathematics subject in previous GATE papers. Average marks 2.00.

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

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.

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