Conversion of formula to Prenex Normal Form

63 Views Asked by At

A question about formula conversion to prenex normal form:

Does this formula convert to 1 or 2 or both of them are incorrect ?

∃x∃y∀z S(x,y,z) ∨ ∀x∃z∃y S(x,y,z) ~

  1. ∃x∃y∀z∀g∃h (S(x,y,z) ∨ S(g,y,h))
  2. ∃x∃y∀z∀g∃h∃j (S(x,y,z) ∨ S(g,j,h))

And is this conversion correct ?

∃x∃y∀z S(x,y,z) ∨ ∀x∃y∃z S(x,y,z) ~ ∃x∃y∀z∀g∃h (S(x,y,z) ∨ S(g,y,h))

1

There are 1 best solutions below

1
On BEST ANSWER

Some of the conversion you listed are not correct,
For $(2)$, it rewrited $x$ as $g$, $z$ as $h$ and $y$ as $j$ and didn't change the order of the quantifier, correct!
$$∃x∃y∀z S(x,y,z) ∨ \color{orange}{∀x}\color{blue}{∃z}\color{red}{∃y} S(x,y,z)\equiv∃x∃y∀z\color{orange}{∀g}\color{blue}{∃h}\color{red}{∃j} (S(x,y,z) ∨ S(g,j,h))\tag*{$\require{enclose} \enclose{box}[mathcolor="green"]{\unicode{x2714}}$}$$ But for $(1)$ the order changed, the equivalence which will not hold.
we can put $g,h$ anywhere before $y$, but not after.
The idea is do not change the order of the quantifier, to fix $(1)$ we can write:

\begin{align} ∃x∃y∀z S(x,y,z) ∨ \color{orange}{∀x}\color{blue}{∃z}\color{red}{∃y} S(x,y,z) &\equiv ∃x\color{orange}{∀g}\color{blue}{∃h}\color{red}{∃y}∀z(S(x,y,z) ∨ S(g,y,h))\\ \end{align}

Similar problem for the last expression, order changed,
Since we want $x$ before $y$, and $z$ after $y$, to fix it we can write:

\begin{align} ∃x∃y∀z S(x,y,z) ∨ ∃x\color{orange}{∀x}\color{red}{∃y}\color{blue}{∃z} S(x,y,z) &\equiv∃x\color{orange}{∀g}\color{red}{∃y}\color{blue}{∃h}∀z (S(x,y,z) ∨ S(g,y,h)) \end{align}

In conclusion, $(2)$ is the only correct conversion listed above.