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:

“The word career is a divisive word. It’s a word that divides the normal life from business or professional life.”
—Grace Paley (b. 1922)

“Who among us has not, in moments of ambition, dreamt of the miracle of a form of poetic prose, musical but without rhythm and rhyme, both supple and staccato enough to adapt itself to the lyrical movements of our souls, the undulating movements of our reveries, and the convulsive movements of our consciences? This obsessive ideal springs above all from frequent contact with enormous cities, from the junction of their innumerable connections.”
—Charles Baudelaire (1821–1867)