Cuantificación vacía

Question

En esta fórmula se puede eliminar una cuantificación vacía:

$ \exists x \forall x (P(x) \rightarrow Q(x)) \equiv \forall x (P(x) \rightarrow Q(x)) $

¿Qué tal una fórmula como esta?

$ \forall x (P(x) \rightarrow \exists x Q(x)) $

¿Es también una cuantificación vacía o no es una fórmula bien formada?

¿Se puede reescribir de otra forma como para la primera fórmula?

Answer 1

La fórmula $\exists x \forall x (P(x) \to Q(x))$ es lógicamente equivalente a $\forall x (P(x) \to Q(x))$$ -$ y, por tanto, la primera puede reescribirse en la segunda sin cambiar su significado $-$ porque $\exists x$ no vincula ninguna ocurrencia de $x$ en $\forall x (P(x) \to Q(x))$ y por lo tanto esto $\exists x$ es superfluo (técnicamente, se suele decir dummy ).

Por el contrario, en la fórmula $\forall x (P(x) \to \exists x Q(x))$ el cuantificador $\forall x $ no es ficticio (o "vacuo" según su terminología), porque vincula la ocurrencia de $x$ en $P(x)$ . Por lo tanto, $\forall x$ no puede ser eliminado. Un discurso similar es válido para $\exists x$ (con respecto a la ocurrencia de $x$ en $Q(x)$ ).

Pero se puede reescribir la fórmula $\forall x (P(x) \to \exists x Q(x))$ como $\forall x (P(x) \to \exists y Q(y))$ : son exactamente los mismo fórmula, ya que las fórmulas se identifican hasta el cambio de nombre de las variables ligadas. La ventaja de la segunda versión de la fórmula es que ahora se puede mover el cuantificador existencial delante de la implicación, sin cambiar el significado de la fórmula. En efecto, la fórmula $\forall x (P(x) \to \exists y Q(y))$ es lógicamente equivalente a $$\forall x \exists y (P(x) \to Q(y))$$ Esta última es una fórmula en forma normal prenex lo que significa que todos los cuantificadores están al principio de la fórmula. Un conocido teorema de la lógica clásica dice que toda fórmula es lógicamente equivalente a una fórmula en forma normal prenex.

Answer 2

La cuantificación es vacía cuando no vincula ninguna variable, ya sea porque no hay ocurrencias de la variable vinculante o porque es completamente anulada por otro cuantificador. Este último es el caso de la primera fórmula, en la que $\exists x$ es inmediatamente seguido por $\forall x$ .

En la segunda fórmula, hower, $\forall x$ sí tiene un enlace activo, es decir, la aparición de $x$ en $P(x)$ . Es sólo la ocurrencia en $Q(x)$ que se sobrescribe con $\exists x$ . $\forall x$ por lo que no puede ser eliminado.

En la mayoría de las definiciones de la sintaxis FOL, la cuantificación vacía, la anulación de la ligadura y la ligadura con nombre idéntico en subfórmulas independientes (como $(\exists x P(x)) \land (\forall x Q(x))$ ) está permitido.

Si quieres que la fórmula sea más clara evitando nombres de variables idénticos para diferentes vinculaciones, puedes realizar el renombramiento de los vínculos y, por ejemplo, escribir $\forall x (P(x) \to \exists y P(y))$ . Esta fórmula será lógicamente equivalente a la original.