sábado, 15 de septiembre de 2012

Un método para el cálculo restringido de predicados

El método de la cuarta edición de Hilbert-Ackerman (Grundzüge der theoretischen Logic) para demostrar las fórmulas válidas proposicionales fue presentado en este post.

Sobre dicha base se formula en el mismo libro un sistema axiomático para la expresiones universalmente válidas del cálculo restringido de predicados (la lógica de primer orden).

Se reformula el concepto de fórmula elemental¹. Serán elementales las fórmulas que consistan en una disyunción «α1 ∨ ... ∨ α2» donde:

1) αi será una fórmula primaria, una fórmula primaria negada o será de la forma: «∃x β» o «∃y β» o «∃z β», etc.
2) han de existir una αi y uan αj tales que αi sea una fórmula primaria y αj sea «¬αi».

Las reglas de deducción son:

(a)


   θ ∨ α ∨ γ 
θ ∨ ¬¬α ∨ γ

No es necesario que θ y γ estén presentes en la deducción. Si lo hace γ, ninguno de sus miembros disyuntivos tendrá la forma «¬¬β», «¬(β ∨ δ)» o «¬∃x β» (ni tener una forma así).

(b)

θ ∨ ¬α ∨ γ             θ ∨ ¬β ∨ γ
        θ ∨ ¬(α ∨ β) ∨ γ

Aquí se cumplen para θ y γ las mismas reglas que en (a). En cuanto a β, ésta no puede ser una disyunción.

la siguiente regla no tenía lugar en el cálculo proposicional:

(c)

  θ ∨ ¬α(y) ∨ γ 
θ ∨ ¬∃x α(x) ∨ γ

La expresión «α(y)» contiene una variable libre y. θ y γ (que están sujetas a idénticas condiciones que en (a)) pueden no estar presentes y si lo están en ellas no aparecerá dicha variable, ni tampoco la variable x (pueden tener otras variables).

La última regla es la siguiente:

(d)

θ ∨ ∃x α(x) ∨ α(y) ∨ γ
   θ ∨   ∃x α(x)   ∨   γ

θ y γ deben cumplir con las mismas condiciones que en (a) se exigen para θ. «α(y)» no debe aparecer como miembro disyuntivo una segunda en la fórmula superior.

La equivalencia entre las fórmulas de cada uno de los pisos de (c) se vé así: «¬α(y)» significa que esta fórmula si es verdadero, lo es de cualquier y, pues es una variable libre. Esto equivale a decir que lo es de todo «y», es decir «∀y ¬α(y)». Es cierto además que decir que para todo «x» se cumple que no es α es lo mismo que decir que no existe «x» alguno para el que se cumpla α. O sea: «¬∃y α(y)».

La equivalencia entre los pisos de (d) se sigue de la equivalencia siguiente:

∃x α(x) ∨ α(x)   ≡eq   ∃x α(x)

Esto es así porque:

Primero: ∃x α(x) ∨ α(x)  →   ∃x α(x)

1) ∃x α(x) implica   ∃x α(x) por motivos obvios.
2) Si α(x), esto significa que α es verdadero de cualquier x, asi dado que el dominio de la función no es vacío, existe en él al menos un x que es α

Segundo: ∃x α(x)   →    ∃x α(x) ∨ α(x)

Basta con que el antecedente implique cualquiera de los miembros disyuntivos del consecuente, que es el caso de 1).

___________
1. Se agregan las fórmulas con letras de predicados y cuantificadores a las variables proposicionales.

No hay comentarios: