Escritura de predicados: ¿es necesario el cuantificador?

Question

Estoy tomando un curso de lógica matemática, que recientemente ha cubierto cuantificadores y ahora me encuentro un poco confundido de si o no el cuantificador existencial es necesario - considere este ejemplo:

Descargo de responsabilidad: Asumir que nuestro universo es el conjunto de números naturales

$x$ es un número par

Ahora, realmente no puedo decir la diferencia entre estas dos notaciones:
$$(\exists m)(x=2m)$$ Y esto: $$x=2m$$ Son básicamente lo mismo? Si es así, ¿significa que siempre podemos omitir el cuantificador existencial?
Ahora, veamos otro ejemplo:

$x$ es el prime

El mismo problema, yo tengo dos notaciones y no puede decidir cual de ellos es el correcto.
$$(\forall a)(a |x \Rightarrow ((a=1 \lor a=x) \land x\ne1))$$ Y $$a|x \Rightarrow ((a =1 \lor a=x) \land x\ne 1) \\ [1]$$ Y finalmente, el último predicado:

$x$ es compuesto

Es suficiente escribir $$\neg [1]$$ or it is necessary to write $$(\exists a)(\neg [1])$$ Hacer estos predicados que realmente significan la misma cosa?

Answer 1

No, no podemos omitir el cuantificador existencial.

Cómo se lee la fórmula:

$x=2m$ ?

Como: "todos los $x$ es incluso" ? O como: "algunos $x$ es incluso" ? O como: "todos los $x$ es el doble de todos los $m$" ? O como: "algunos $x$ es el doble de todos los $m$" ?

La "costumbre" convención es que podemos omitir el universal cuantificador.

Si la aplicamos, podemos leer:

$\exists m \ (x = 2m)$

como: $\forall x \exists m \ (x=2m)$, es decir, como: "todo número es par".

---

Respecto a la segunda parte de la pregunta, si escribimos, por $x \ne 1$: $\text{Prime}(x)$ como $\forall a (a|x \to \ldots)$, claramente:

$\text{Comp}(x) \text { iff } \lnot \text {Prime}(x) \text { iff } \lnot \forall a (a|x \to \ldots) \text { iff } \exists x \lnot (a|x \to \ldots)$.

Answer 2

Observe cómo '$x$ es incluso " se hace referencia explícita a $x$, pero no a $m$. Que debe ser una indicación ya que en su fórmula que desee $x$ como libre de la variable i.e no cuantificar el$x$), pero no $m$, por lo que el uso de:

$$\exists m \ x = 2m$$

También tenga en cuenta que dependiendo de cómo cuantificar el $x$, se obtiene un diferente declaración:

$$\forall x \exists m \ x =2m$$

significa que todos los números son aún, mientras que

$\exists x \exists m \ x=2m$

significa que un número es par. (tenga en cuenta que ambas interpretaciones, ya no hay una referencia a $x$, de nuevo la señalización que la $x$ ha sido cuantificada)

Del mismo modo, el significado de

$$x =2m$$

(que, de por sí, se lee como '$x$ es el doble de $m$' ... así que ahora te hacen tener una referencia explícita a $m$, reflejando el hecho de que $m$ es una variable libre)

depende de cómo $m$ es ser cuantificados:

$$\exists m \ x=2m$$

claramente significa que $x$ es par, mientras que

$$\forall m \ x =2m$$

claramente significa algo diferente!

Así que, sí, usted realmente desea existencialmente cuantificar ese $m$.

La misma historia de '$x$ es compuesto": se hace referencia a ninguna $a$, y lo que no es necesario cuantificar ese $a$, y sólo tienen $x$ como una variable libre. Y también tenga en cuenta que si se va a cuantificar el $a$ existencialmente, usted no consigue lo que desea.

Finalmente, para '$x$ está compuesto' tiene sentido sólo niega lo que usted tiene para '$x$ es una de las principales' (y, por tanto, cualquier quantificational asuntos serán atendidos de forma automática) ... si no fuera por el hecho de que $1$ es ni el primer ni el compuesto! Así que lo que realmente quieres, no hay '$x$ no $1$ $x$ no es primo'

Answer 3

Si es así, ¿significa que siempre podemos omitir el cuantificador existencial?

No exactamente, pero hay una manera rigurosa de la eliminación de cuantificadores existenciales. Se llama skolemization, y sigue un proceso de 3 pasos:

1. Mover todos los cuantificadores hacia el exterior, dando forma normal prenex. Esto normalmente es bastante sencillo, pero puede requerir un menor de reestructuración de la fórmula.
2. Mover cuantificadores existencial fuera de cuantificadores universal. Si su expresión es de la forma $\forall x \exists y \phi(x, y)$, es afirmar que para cada x, hay una y. Se puede decir que como no hay una única función que se asigna x a la y, que escribimos como $\exists f \forall x \phi(x, f(x))$. En este contexto, llamamos a $f$ una función de skolem.
3. Eliminar todos los cuantificadores existenciales. Las variables que fueron atados a los cuantificadores de ser libre. Estas variables pueden entonces ser unificada con cualquier términos adecuados que cumplan el predicado.

Porque hemos de separar las variables en el paso 3, esto cambia el significado de la declaración (en lugar de simplemente afirmar que hay un $f$ o $y$ satisface el requisito, se está afirmando que $f$ o $y$ tiene algún significado independiente que se cumple la fórmula). Como resultado, este no es un propósito general técnica, y debe ser utilizado con cuidado. Sin embargo, la alteración de la declaración es equisatisfiable con el original, que lo hace adecuado para automatizada de teoremas y otros contextos donde satisfiability es el objeto de nuestra investigación.

Desafortunadamente, no podemos detenernos en el paso 2, si queremos permanecer dentro de la lógica de primer orden. Cuantificadores existenciales de las funciones sólo están permitidos en segundo orden de la lógica; la fórmula que se muestra en el paso 2 está mal formado en la lógica de primer orden. Es bastante posible llevar a cabo esta transformación, sin tomar ese desvío a través de la segunda orden de la lógica (al caer el cuantificador existencial al mismo tiempo que se introduce la función de skolem), pero que es un poco más difícil de seguir.

En la práctica, skolemization es a menudo combinado con una conversión conjuntivo forma normal, debido a que es un requisito previo a la aplicación de la resolución.