Editing Prenex normal form (section)

=== Conjunction and disjunction ===

The rules for [[logical conjunction|conjunction]] and [[logical disjunction|disjunction]] say that
:<math>(\forall x \phi) \land \psi</math> is equivalent to <math>\forall x ( \phi \land \psi)</math> under (mild) additional condition <math>\exists x \top</math>, or, equivalently, <math>\lnot\forall x \bot</math> (meaning that at least one individual exists),
:<math>(\forall x \phi) \lor \psi</math> is equivalent to <math>\forall x ( \phi \lor \psi)</math>;
and 
:<math>(\exists x \phi) \land \psi</math> is equivalent to <math>\exists x (\phi \land \psi)</math>,
:<math>(\exists x \phi) \lor \psi</math> is equivalent to <math>\exists x (\phi \lor \psi)</math> under additional condition <math>\exists x \top</math>.
The equivalences are valid when <math>x</math> does not appear as a [[free variable]] of <math>\psi</math>; if <math>x</math> does appear free in <math>\psi</math>, one can rename the bound <math>x</math> in <math>(\exists x \phi)</math> and obtain the equivalent <math>(\exists x' \phi[x/x'])</math>.

For example, in the language of [[ring (mathematics)|rings]],
:<math>(\exists x (x^2 = 1)) \land (0 = y)</math> is equivalent to  <math>\exists x ( x^2 = 1 \land 0 = y)</math>,
but
:<math>(\exists x (x^2 = 1)) \land (0 = x)</math> is not equivalent to <math>\exists x ( x^2 = 1 \land 0 = x)</math>
because the formula on the left is true in any ring when the free variable ''x'' is equal to 0, while the formula on the right has no free variables and is false in any nontrivial ring. So <math>(\exists x (x^2 = 1)) \land (0 = x)</math> will be first rewritten as <math>(\exists x' (x'^2 = 1)) \land (0 = x)</math> and then put in prenex normal form <math>\exists x' ( x'^2 = 1 \land 0 = x)</math>.