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:

“Our normal waking consciousness, rational consciousness as we call it, is but one special type of consciousness, whilst all about it, parted from it by the filmiest of screens, there lie potential forms of consciousness entirely different.”
—William James (1842–1910)

“At any rate, let us love for a while, for a year or so, you and me. That’s a form of divine drunkenness that we can all try.”
—F. Scott Fitzgerald (1896–1940)