Diferencia entre revisiones de «Forma normal prenexa»

56 bytes eliminados ,  hace 9 años
m
Bot: Retirando plantilla "traducción". Fue insertada por Usuario:Ferdr?n el 19 de May de 2011 y su última edición en él fue el 19 de May de 2011.; cambios triviales
m (Bot: Retirando plantilla "traducción". Fue insertada por Usuario:Ferdr?n el 19 de May de 2011 y su última edición en él fue el 19 de May de 2011.; cambios triviales)
{{Traducción inconclusa|ci=en|Prenex_normal_form}}
 
Una [[Fórmula bien formada|formula]] 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''').
 
Las reglas para la conjunción y la disyunción dicen que
:<math>(\forall x \phi) \land \psi</math> es equivalente a <math>\forall x ( \phi \land \psi)</math>,
:<math>(\forall x \phi) \lor \psi</math> es equivalente a <math>\forall x ( \phi \lor \psi)</math>;
Y
:<math>(\exists x \phi) \land \psi</math> es equivalente a <math>\exists x (\phi \land \psi)</math>,
:<math>(\exists x \phi) \lor \psi</math> es equivalente a <math>\exists x (\phi \lor \psi)</math>.
Las equivalencias son válidas cuando ''x'' no aparece como variable libre de ψ; si ''x'' sí aparece libre en ψ, debe ser reemplazada por otra variable libre.
 
Por ejemplo, en el lenguaje de los [[Anillo (matemática)|anillos]],
:<math>(\exists x (x^2 = 1)) \land (0 = y)</math> es equivalente a <math>\exists x ( x^2 = 1 \land 0 = y)</math>,
pero
:<math>(\exists x (x^2 = 1)) \land (0 = x)</math> no es equivalente a <math>\exists x ( x^2 = 1 \land 0 = x)</math>
 
Las reglas para la negación dicen que
:<math>\lnot \exists x \phi</math> es equivalente a <math>\forall x \lnot \phi</math>
y
:<math>\lnot \forall x \phi</math> es equivalente a <math>\exists x \lnot \phi</math>.
 
=== Implicación ===
 
== Véase también ==
* [[Herbrandization]]
* [[Skolemization]]
* [[Arithmetical hierarchy]]
 
== Referencias ==
137 881

ediciones