SAT preserving conversion of statement to existential one

42 Views Asked by At

For me, a formula $\psi$ is existential if and only if it is of the form $\psi=\exists x_1\cdots\exists x_n \varphi$ such that $\varphi$ has no quantifiers.

Prove or Disprove: There exists an algorithm that given a statement $\alpha$ outputs an existential statement $\beta$ such that $\alpha$ is satisfiable if and only if $\beta$ is satisfiable.

I have heard about Herbrandization but it only preserves validity as far as I know...