Wikipedia

Diferencia entre revisiones de «Forma normal prenexa»

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Acratta (discusión · contribs.)
11 766 ediciones
Acratta (discusión · contribs.)
11 766 ediciones
Sin resumen de edición
Línea 1:
Una [[Fórmula bien formada|formulafórmula]] de la [[lógica de predicados]] tiene '''forma prenexa<ref>The term 'prenex' comes from the [[Latin]] ''praenexus'' "tied or bound up in front", past participle of ''praenectere'' [http://cs.nyu.edu/pipermail/fom/2007-November/012328.html].</ref>''' si está escrita como una cadena de [[cuantificador]]es seguidos por una parte sin cuantifcar (designada como '''matriz''').
 
Toda fórmula es equivalente en [[lógica clásica]] a una fórmula en forma prenexa. Por ejemplo, si
<math>\phi(y)</math>, <math>\psi(z)</math>, y <math>\rho(x)</math> son fórmulas sin cuantificar con las variables libres mostradas, luego
:<math>\forall x \exists y \exists z (\phi(y) \lor (\psi(z) \rightarrow \rho(x)))</math>
Es en forma normal prenexa con la mtrizmatriz <math>\phi(y) \lor (\psi(z) \rightarrow \rho(x))</math>, mientras que
:<math>\forall x ((\exists y \phi(y)) \lor ((\exists z \psi(z) ) \rightarrow \rho(x)))</math>
Es lógicamente equivalente pero no en forma prenexa.
Línea 10:
== Conversión a forma prenexa ==
 
Toda fórmula de primer orden es lógicalógicamente equivalente (en[[equivalencia lógica clasíca)|equivalente]] a alguna fórmula en forma prenexa. Hay algunas reglas de conversión que pueden ser aplicadas recursivamente para convertir una fórmula a forma prenexa. Las reglas dependen de qué [[conectiva lógica]] (o conectivas) y [[cuantificador]] (o cuantificadores) aparezcan en la fórmula.
 
=== Conjunción y disyunción ===
Línea 75:
== Uso de la forma prenexa ==
 
Algunos [[cálculossistema delógico|sistemas derivaciónlógicos]] sólo pueden tratar con una [[teoría (lógica)|teoría]] cuyas fórmulas estén escritas en forma normal prenexa.
El concepto es esencial para desarrollar la [[jerarquía aritmética]] y la [[jerarquía analítica]].
La prueba de [[Gödel]] de su [[Teorema de completitud de Gödel|teorema de completitud]] para la [[lógica de primer orden]] presupone que todas las fórmulas han sido reescritas en formal normal prenexa.
Línea 82:
* [[Herbrandization]]
* [[Skolemization]]
* [[ArithmeticalJerarquía hierarchyanalítica]]
 
== Referencias ==
Obtenido de «https://es.wikipedia.org/wiki/Forma_normal_prenexa»