True Quantified Boolean Formula - Prenex Normal Form

Prenex Normal Form

A fully quantified Boolean formula can be assumed to have a very specific form, called prenex normal form. It has two basic parts: a portion containing only quantifiers and a portion containing an unquantified Boolean formula usually denoted as . If there are Boolean variables, the entire formula can be written as

where every variable falls within the scope of some quantifier. By introducing dummy variables, any formula in prenex normal form can be converted into a sentence where existential and universal quantifiers alternate. Using the dummy variable ,

$\displaystyle \exists x_1 \exists x_2 \phi(x_1, x_2) \quad \mapsto \quad \exists x_1 \forall y_1 \exists x_2 \phi(x_1, x_2)$

The second sentence has the same truth value but follows the restricted syntax. Assuming fully quantified Boolean formulas to be in prenex normal form is a frequent feature of proofs.

Read more about this topic: True Quantified Boolean Formula

Famous quotes containing the words normal and/or form:

“We have been weakened in our resistance to the professional anti-Communists because we know in our hearts that our so-called democracy has excluded millions of citizens from a normal life and the normal American privileges of health, housing and education.”
—Agnes E. Meyer (1887–1970)

“Here form is content, content is form.”
—Samuel Beckett (1906–1989)