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