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:

“Unlike the normal pattern, I know I have grown more liberal as I’ve grown older. I have become more convinced that there is room for improvement in the world.”
—Walter Wellesley (Red)

“Patience. A minor form of despair disguised as a virtue.”
—Ambrose Bierce (1842–1914)