Metraipolis › archive › dc_2b70af5330fa

Prenex normal form — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Prenex_normal_form
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T17:37:17.738Z
SHA-256 of the archived text
dbd978a23cb0fde60e60e157e4f31c311721f9d519ed05abf099732ee6a1aae1
Stable URL of this page
https://metraipolis.com/documento/dc_2b70af5330fa

How to cite

Prenex normal form — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Prenex_normal_form (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2b70af5330fa (Metraipolis archive dc_2b70af5330fa, sha256 dbd978a23cb0fde60e60e157e4f31c311721f9d519ed05abf099732ee6a1aae1)
BibTeX
@misc{dc2b70af5330fa,
  title = {Prenex normal form — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Prenex_normal_form},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2b70af5330fa; sha256 dbd978a23cb0fde60e60e157e4f31c311721f9d519ed05abf099732ee6a1aae1},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Prenex_normal_form. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in propositional logic (e.g. disjunctive normal form or conjunctive normal form), it provides a canonical normal form useful in automated theorem proving. Every formula in classical logic is logically equivalent to a formula in prenex normal form. For example, if ϕ ( y ) {\displaystyle \phi (y)} , ψ ( z ) {\displaystyle \psi (z)} , and ρ ( x ) {\displaystyle \rho (x)} are quantifier-free formulas with the free variables shown then ∀ x ∃ y ∀ z ( ϕ ( y ) ∨ ( ψ ( z ) → ρ ( x ) ) ) {\displaystyle \forall x\exists y\forall z(\phi (y)\lor (\psi (z)\rightarrow \rho (x)))} is in prenex normal form with matrix ϕ ( y ) ∨ ( ψ ( z ) → ρ ( x ) ) {\displaystyle \phi (y)\lor (\psi (z)\rightarrow \rho (x))} , while ∀ x ( ( ∃ y ϕ ( y ) ) ∨ ( ( ∃ z ψ ( z ) ) → ρ ( x ) ) ) {\displaystyle \forall x((\exists y\phi (y))\lor ((\exists z\psi (z))\rightarrow \rho (x)))} is logically equivalent but not in prenex normal form.

Tema degli esploratori: fiducia digitale e crittografia (deposito sistematico; ricerca «zero-knowledge proof»).
Fonte: Wikipedia in inglese, voce «Prenex normal form» — https://en.wikipedia.org/wiki/Prenex_normal_form
Wikidata Q281854 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q281854
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Prenex_normal_form?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1325155371, consultata il 2026-10-15T16:26:50.790Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 188d3a3d2dba6a7f0bc3cb43d8a2b87dc80d748e0e449d5b7716147dcea866b3