[Solved]: Can we move quantifiers to the left in predicate logic?

Problem Detail: 

Say I have part of a query in the form: ∃x_a(...)∧∃x_b(...)∧∃x_c(...), where a, b, and c are attributes and the ellipses can be anything (I'm looking for a general rule). Is this equivalent to saying ∃x_a,x_b,x_c(...∧...∧...) - i.e. compacting all the existential quantifiers into one and 'anding' their domains together?

For example, if I have the query:

would it be correct (albeit unwieldy) to write it as:

{ x_pid | ∃x_pname,x_color,x_sid,x_sname,x_address,x_cost,y_sid,y_sname,y_address,y_cost( PARTS(x_pid,x_pname,x_color) ∧ SUPPLIERS(x_sid,x_sname,x_address... (and then the rest of the query)

Asked By : false_azure

Answered By : Yuval Filmus

If all the quantified variables are distinct, then you can safely move all quantifiers to the left. This is the only obstruction to this procedure. You can always ensure that all quantified variables are distinct by renaming them. For example, starting with $$(\forall x P(x)) \lor (\forall x Q(x)),$$ we first rename the second variable to $y$, $$(\forall x P(x)) \lor (\forall y Q(y)),$$ and then move the quantifiers to the left, $$ \forall x \forall y (P(x) \lor Q(y)). $$ This is equivalent to the original formula.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23588