<p>Your solution is correct. It suffices to see that the formulae <span class="math-container">$\exists{y} P(y)$</span> and <span class="math-container">$\forall{x} \exists{y} P(y)$</span> are equi-satisfiable, which allows you to put your formulae in the desired form.</p>

CC BY-SA 4.0
2020-12-14T19:14:25.060Z
2020-12-14T19:14:25.060Z
Bartosz Bednarczyk
<p>In this <a href="https://www.jstor.org/stable/421196?seq=1#metadata_info_tab_contents" rel="nofollow noreferrer">paper</a>  Scott's reduction is discussed, which reduces any FO2 formula to Scott's Normal form. As far as I understand the reduction process explained in the paper can get you to formulas with only <span class="math-container">$\forall \forall$</span> and <span class="math-container">$\forall \exists$</span> quantification prefixes. Which has three possibilities of prefixes  <span class="math-container">$\forall x \forall y $</span>, <span class="math-container">$\forall x \exists y$</span> and <span class="math-container">$\exists y \forall x$</span>. Now scott's normal form only admits <span class="math-container">$\forall x \forall y $</span> and <span class="math-container">$\forall x \exists y$</span> quantification. Then how is the explained process sound for a formula like <span class="math-container">$\exists x \forall y R(x,y) $</span> ?</p>
<p>In other words, what is the scott's reduction for <span class="math-container">$\Phi(x,y) = \exists x \forall y R(x,y)$</span>.</p>
<p>My attempt on reduction according to the paper:</p>
<p><span class="math-container">$ Sc( \Phi(x,y) )= \exists x P(x)  \land \forall x \forall y (P(x) \leftrightarrow R(x,y)) $</span></p>

<first-order-logic>
Scott's normal form for $\exists y \forall x R(x,y) $
SagarM
# Scott's normal form for $\exists y \forall x R(x,y) $

(Asked by: username_0 on 2020-12-14)

In this [paper](https://www.jstor.org/stable/421196?seq=1#metadata_info_tab_contents) Scott's reduction is discussed, which reduces any FO2 formula to Scott's Normal form. As far as I understand the reduction process explained in the paper can get you to formulas with only $\forall \forall$ and $\forall \exists$ quantification prefixes. Which has three possibilities of prefixes $\forall x \forall y $, $\forall x \exists y$ and $\exists y \forall x$. Now scott's normal form only admits $\forall x \forall y $ and $\forall x \exists y$ quantification. Then how is the explained process sound for a formula like $\exists x \forall y R(x,y) $ ?

In other words, what is the scott's reduction for $\Phi(x,y) = \exists x \forall y R(x,y)$.

My attempt on reduction according to the paper:

$ Sc( \Phi(x,y) )= \exists x P(x) \land \forall x \forall y (P(x) \leftrightarrow R(x,y)) $

**Tags:** first-order-logic

---

## 1 answers

### Answer by username_1 on 2020-12-14. Score: 3 | Accepted answer

Your solution is correct. It suffices to see that the formulae $\exists{y} P(y)$ and $\forall{x} \exists{y} P(y)$ are equi-satisfiable, which allows you to put your formulae in the desired form.


---

