Prenex normální forma - Prenex normal form

A vzorec z predikátový počet je v prenex^[1] normální forma (PNF), pokud je zapsán jako řetězec kvantifikátory a vázané proměnné, nazvaný předpona, následovaná částí bez kvantifikátoru nazvanou matice.^[2]

Každý vzorec v klasická logika je ekvivalentní vzorci v prenexové normální formě. Například pokud ${ displaystyle phi (y)}$, ${ displaystyle psi (z)}$, a ${ displaystyle rho (x)}$ jsou vzorce bez kvantifikátoru a poté jsou zobrazeny volné proměnné

${ displaystyle forall x existuje y forall z ( phi (y) lor ( psi (z) rightarrow rho (x)))}$

je v prenex normální formě s maticí ${ Displaystyle phi (y) lor ( psi (z) rightarrow rho (x))}$, zatímco

${ displaystyle forall x (( existuje y phi (y)) lor (( existuje z psi (z)) rightarrow rho (x)))}$

je logicky ekvivalentní, ale ne v prenexové normální formě.

Konverze do prenexové formy

Tato sekce potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. (Srpna 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Každý první objednávka vzorec je logicky ekvivalentní (v klasické logice) k nějakému vzorci v prenex normální formě.^[3] Existuje několik pravidel převodu, která lze rekurzivně použít k převodu vzorce do prenex normální formy. Pravidla závisí na kterém logické spojky se objeví ve vzorci.

Spojení a disjunkce

Pravidla pro spojení a disjunkce říkají, že

${ displaystyle ( forall x phi) land psi}$ je ekvivalentní k ${ displaystyle forall x ( phi land psi)}$ pod (mírnou) další podmínkou ${ displaystyle existuje x nahoru}$, nebo ekvivalentně ${ Displaystyle lnot forall x bot}$ (což znamená, že existuje alespoň jeden jedinec),

${ displaystyle ( forall x phi) lor psi}$ je ekvivalentní k ${ displaystyle forall x ( phi lor psi)}$;

a

${ displaystyle ( existuje x phi) země psi}$ je ekvivalentní k ${ displaystyle existuje x ( phi land psi)}$,

${ displaystyle ( existuje x phi) lor psi}$ je ekvivalentní k ${ displaystyle existuje x ( phi lor psi)}$ za dalších podmínek ${ displaystyle existuje x nahoru}$.

Ekvivalence jsou platné, když ${ displaystyle x}$ nevypadá jako volná proměnná z ${ displaystyle psi}$; -li ${ displaystyle x}$ se objeví zdarma v ${ displaystyle psi}$, lze vázaný přejmenovat ${ displaystyle x}$ v ${ displaystyle ( existuje x phi)}$ a získat ekvivalent ${ displaystyle ( existuje x ' phi [x / x'])}$.

Například v jazyce prsteny,

${ displaystyle ( existuje x (x ^ {2} = 1)) země (0 = y)}$ je ekvivalentní k ${ displaystyle existuje x (x ^ {2} = 1 land 0 = y)}$,

ale

${ displaystyle ( existuje x (x ^ {2} = 1)) země (0 = x)}$ není ekvivalentní s ${ displaystyle existuje x (x ^ {2} = 1 land 0 = x)}$

protože vzorec vlevo je pravdivý v jakémkoli kruhu, když je volná proměnná X je rovno 0, zatímco vzorec vpravo nemá žádné volné proměnné a je nepravdivý v jakémkoli netriviálním kruhu. Tak ${ displaystyle ( existuje x (x ^ {2} = 1)) země (0 = x)}$ bude nejprve přepsán jako ${ displaystyle ( existuje x '(x' ^ {2} = 1)) země (0 = x)}$ a poté vložte do prenex normální formy ${ displaystyle existuje x '(x' ^ {2} = 1 land 0 = x)}$.

Negace

Pravidla pro negaci to říkají

${ displaystyle lnot existuje x phi}$ je ekvivalentní k ${ displaystyle forall x lnot phi}$

a

${ Displaystyle lnot forall x phi}$ je ekvivalentní k ${ displaystyle existuje x lnot phi}$.

Implikace

Existují čtyři pravidla implikace: dva, které odstraňují kvantifikátory z předchůdce a dva, které odstraňují kvantifikátory z následku. Tato pravidla lze odvodit přepsáním implikace${ displaystyle phi rightarrow psi}$ tak jako ${ displaystyle lnot phi lor psi}$ a použití výše uvedených pravidel pro disjunkce. Stejně jako u pravidel pro disjunkce, i tato pravidla vyžadují, aby se proměnná kvantifikovaná v jednom podformulu nezdála volná v ostatních podformulích.

Pravidla pro odstranění kvantifikátorů z předchůdce jsou (všimněte si změny kvantifikátorů):

${ displaystyle ( forall x phi) rightarrow psi}$ je ekvivalentní k ${ displaystyle existuje x ( phi rightarrow psi)}$ (za předpokladu, že ${ displaystyle existuje x nahoru}$),

${ displaystyle ( existuje x phi) pravá šipka psi}$ je ekvivalentní k ${ displaystyle forall x ( phi rightarrow psi)}$.

Pravidla pro odstranění kvantifikátorů z následku jsou:

${ displaystyle phi rightarrow ( existuje x psi)}$ je ekvivalentní k ${ displaystyle existuje x ( phi rightarrow psi)}$ (za předpokladu, že ${ displaystyle existuje x nahoru}$),

${ Displaystyle phi rightarrow ( forall x psi)}$ je ekvivalentní k ${ displaystyle forall x ( phi rightarrow psi)}$.

Příklad

Předpokládejme to ${ displaystyle phi}$, ${ displaystyle psi}$, a ${ displaystyle rho}$ jsou vzorce bez kvantifikátoru a žádné dva z těchto vzorců nesdílejí žádnou volnou proměnnou. Zvažte vzorec

${ displaystyle ( phi lor existuje x psi) rightarrow forall z rho}$.

Rekurzivní aplikací pravidel začínajících na nejvnitřnějších podformulách lze získat následující posloupnost logicky ekvivalentních vzorců:

${ displaystyle ( phi lor existuje x psi) rightarrow forall z rho}$.

${ Displaystyle ( existuje x ( phi lor psi)) rightarrow forall z rho}$,

${ Displaystyle neg ( existuje x ( phi lor psi)) lor forall z rho}$,

${ displaystyle ( forall x neg ( phi lor psi)) lor forall z rho}$,

${ displaystyle forall x ( neg ( phi lor psi) lor forall z rho)}$,

${ displaystyle forall x (( phi lor psi) rightarrow forall z rho)}$,

${ displaystyle forall x ( forall z (( phi lor psi) rightarrow rho))}$,

${ displaystyle forall x forall z (( phi lor psi) rightarrow rho)}$.

Toto není jediná forma prenexu ekvivalentní původnímu vzorci. Například jednáním s následníkem před předchůdcem ve výše uvedeném příkladu, forma prenex

${ displaystyle forall z forall x (( phi lor psi) rightarrow rho)}$

lze získat:

${ displaystyle forall z (( phi lor existuje x psi) rightarrow rho)}$

${ displaystyle forall z (( existuje x ( phi lor psi)) rightarrow rho)}$,

${ displaystyle forall z ( forall x (( phi lor psi) rightarrow rho))}$,

${ displaystyle forall z forall x (( phi lor psi) rightarrow rho)}$.

Intuicionistická logika

Pravidla pro převod vzorce do prenexové formy velmi využívají klasickou logiku. v intuicionistická logika, není pravda, že každý vzorec je logicky ekvivalentní s vzorcem prenex. Negace spojovací je jedna překážka, ale ne jediná. S implikačním operátorem se také zachází jinak než v klasické logice; v intuicionistické logice to není definovatelné pomocí disjunkce a negace.

The Interpretace BHK ilustruje, proč některé vzorce nemají intuitivně ekvivalentní formu prenexu. V této interpretaci důkaz o

${ displaystyle ( existuje x phi) pravá šipka existuje y psi qquad (1)}$

je funkce, která vzhledem k konkrétní X a doklad o ${ displaystyle phi (x)}$, vyrábí beton y a doklad o ${ displaystyle psi (y)}$. V tomto případě je to přípustné pro hodnotu y se počítá z dané hodnoty X. Důkaz

${ displaystyle existuje y ( existuje x phi rightarrow psi), qquad (2)}$

na druhé straně produkuje jedinou konkrétní hodnotu y a funkce, která převádí jakýkoli důkaz o ${ displaystyle existuje x phi}$ do dokladu o ${ displaystyle psi (y)}$. Pokud každý X uspokojující ${ displaystyle phi}$ lze použít ke konstrukci a y uspokojující ${ displaystyle psi}$ ale žádné takové y lze postavit bez znalosti takového X potom vzorec (1) nebude ekvivalentní vzorci (2).

Pravidla pro převod vzorce na formu prenex, která ano selhat v intuicionistické logice jsou:

(1) ${ displaystyle forall x ( phi lor psi)}$ naznačuje ${ displaystyle ( forall x phi) lor psi}$,

(2) ${ displaystyle forall x ( phi lor psi)}$ naznačuje ${ Displaystyle phi lor ( forall x psi)}$,

(3) ${ displaystyle ( forall x phi) rightarrow psi}$ naznačuje ${ displaystyle existuje x ( phi rightarrow psi)}$,

(4) ${ displaystyle phi rightarrow ( existuje x psi)}$ naznačuje ${ displaystyle existuje x ( phi rightarrow psi)}$,

(5) ${ Displaystyle lnot forall x phi}$ naznačuje ${ displaystyle existuje x lnot phi}$,

(X se neobjevuje jako volná proměnná ${ displaystyle , psi}$ v (1) a (3); X se neobjevuje jako volná proměnná ${ displaystyle , phi}$ v (2) a (4)).

Použití formy prenex

Nějaký důkazní kameny se bude zabývat pouze teorií, jejíž vzorce jsou psány prenex normální formou. Koncept je nezbytný pro rozvoj aritmetická hierarchie a analytická hierarchie.

Gödel jeho důkaz věta o úplnosti pro logika prvního řádu předpokládá, že všechny vzorce byly přepracovány v prenex normální formě.

Tarskiho axiomy pro geometrii je logický systém, jehož věty mohou Všechno být zapsán univerzálně-existenciální forma, speciální případ prenexové normální formy, který má všechny univerzální kvantifikátor předcházející existenční kvantifikátor, takže všechny věty lze přepsat do formuláře ${ displaystyle forall u}$ ${ displaystyle forall v}$ ${ displaystyle ldots}$ ${ displaystyle existuje a}$ ${ displaystyle existuje b}$ ${ displaystyle phi}$, kde ${ displaystyle phi}$ je věta, která neobsahuje žádný kvantifikátor. Tato skutečnost umožňovala Tarski dokázat, že euklidovská geometrie je rozhodnutelné.

Viz také

• Aritmetická hierarchie
• Herbrandizace
• Skolemizace

Poznámky

Reference

• Richard L. Epstein (18. prosince 2011). Klasická matematická logika: Sémantické základy logiky. Princeton University Press. 108–. ISBN  978-1-4008-4155-4.
• Peter B. Andrews (17. dubna 2013). Úvod do matematické logiky a teorie typů: K pravdě skrz důkaz. Springer Science & Business Media. str. 111–. ISBN  978-94-015-9934-4.
• Elliott Mendelson (1. června 1997). Úvod do matematické logiky, čtvrté vydání. CRC Press. str. 109–. ISBN  978-0-412-80830-2.
• Hinman, P. (2005), Základy matematické logiky, K Peters, ISBN  978-1-56881-262-5