¿Por qué son universales introducción y existencial eliminación válidas las reglas de inferencia?

Question

Estoy estudiando la inferencia de reglas de deducción natural para la lógica de primer orden. No puedo entender por qué universal introducción y existencial de la eliminación son las normas válidas. La primera dice que si $\Sigma\models\theta[k/x]$$\Sigma\models\forall x\theta[x]$; la segunda dice que si $\Sigma\models\exists x\theta[x]$$\Sigma\models\theta[k/x]$.

Universal introducción permitiría a la siguiente deducción: si $1$ es impar, entonces cada número es impar. Existencial eliminación permitiría a la siguiente deducción: si existe un número impar, entonces $2$ es impar.

He leído acerca de algunas de las restricciones que usted debe comprobar antes de la aplicación de tales reglas, pero son también no tan claro para mí.

Algunas notas acerca de la notación que se utiliza: $\Sigma$ es un conjunto de sentencias; $\theta$ es una fórmula tal que la única variable libre es $x$ que $x$ no está en el conjunto de la delimitadas las variables; $\theta[k/x]$ es la fórmula que obtenga de $\theta[x]$ mediante la sustitución de cada instancia gratuita de $x$$k$, $x$ es una variable e $k$ es una constante.

Gracias.

Answer 1

Usted está consiguiendo disparado por algunos muy tradicionales, pero muy mal, la notación.

El $k$ en estas fórmulas no son ciertas constantes de la dominio de los individuos, sino que son más bien constante de Skolem. La idea es que si tenemos, digamos, el conocimiento de que una fórmula existencial $\exists x. \theta(x)$ es true, se puede tratar como si fuera la fórmula de la $\theta(k)$ donde $k$ es alguna constante arbitraria acerca de la cual nada sabemos. Por el contrario, si sabemos que $\theta(k)$ mantiene para cualquier constante $k$, entonces podemos concluir $\forall x.\; \theta(x)$. Estos hechos-up constantes se denominan constantes de Skolem.

Si nos explícitamente gestionar las variables libres con un contexto de libre variables $\Gamma$, luego de la introducción y elimiantion reglas de la forma esperada, y de acuerdo con Andrej Bauer reglas.

$$\frac{\Gamma; \Sigma \vdash \forall x.\theta(x) \qquad FV(t) \subseteq \Gamma} {\Gamma; \Sigma \vdash \theta(t)}$$

$$\frac{\Gamma, x; \Sigma \vdash \theta \qquad \qquad x \no\en FV(\Sigma)} {\Gamma; \Sigma \vdash \forall x.\; \theta}$$

Answer 2

En FOL no hay tal existencial de la eliminación de la regla de que iba a ser una validez general. Aunque hay algunos casos en que dicha la regla sí es válida, por ejemplo, algunos lógica de los programas, para arbitrario las teorías de la regla de inferencia no se sostiene.

Un simple contador de ejemplo es la siguiente teoría:

p(a) \/ p(b)

Aunque se tiene la siguiente consecuencia:

p(a) \/ p(b) |= exists x p(x)

No tenemos uno de los siguientes consecuencias:

p(a) \/ p(b) |\= p(a)

p(a) \/ p(b) |\= p(b)

Ambos tienen consecuencias a un contramodelo. Por ejemplo, la primera consecuencia no se mantiene por un modelo donde p(a) es falsa y p(b) es verdadera. En este modelo la disyunción es verdadera, pero la primera consecuencia es falsa. De la misma manera un contramodelo para la segunda consecuencia se puede encontrar.

Bye