Forma de preness

În logica matematică , o formulă se spune în formă prenessă dacă este compusă dintr-o parte din stânga care conține numai cuantificatori și variabile și o parte din dreapta care nu conține cuantificatori.

În contextul logicii clasice , fiecare formulă este echivalentă cu o formulă în formă preness. De exemplu, dacă $\phi$ ${\ displaystyle \ phi}$ $\ phi$ , $\psi$ ${\ displaystyle \ psi}$ $\ psi$ Și $\rho$ ${\ displaystyle \ rho}$ $\ rho$ sunt formule în care nu apare nici un cuantificator, apoi la formula:

\forall x((\exists y\phi )\lor ((\forall z\psi )\rightarrow \rho ))

{\ displaystyle \ forall x ((\ există y \ phi) \ lor ((\ forall z \ psi) \ rightarrow \ rho))}

{\ displaystyle \ forall x ((\ există y \ phi) \ lor ((\ forall z \ psi) \ rightarrow \ rho))}

puteți asocia următoarea formulă în formă de preness:

\forall x\exists y\exists z(\phi \lor (\psi \rightarrow \rho ))

{\ displaystyle \ forall x \ există y \ există z (\ phi \ lor (\ psi \ rightarrow \ rho))}

{\ displaystyle \ forall x \ există y \ există z (\ phi \ lor (\ psi \ rightarrow \ rho))}

Conversia în formă de preness

Fiecare formulă de ordinul întâi este echivalentă din punct de vedere logic (în cadrul logicii clasice) cu o anumită formulă în formă preness. Există câteva reguli de conversie care pot fi aplicate recursiv pentru a converti o formulă. Regula care trebuie aplicată unui anumit pas de conversie depinde de conectivitatea logică care apare în cea mai exterioară formulă.

Conjuncție și disjuncție

Regulile pentru conjuncție și disjuncție afirmă că

(\forall x\phi )\land \psi

{\ displaystyle (\ forall x \ phi) \ land \ psi}

{\ displaystyle (\ forall x \ phi) \ land \ psi}

este echivalent cu

\forall x(\phi \land \psi )

{\ displaystyle \ forall x (\ phi \ land \ psi)}

{\ displaystyle \ forall x (\ phi \ land \ psi)}

,

(\forall x\phi )\lor \psi

{\ displaystyle (\ forall x \ phi) \ lor \ psi}

{\ displaystyle (\ forall x \ phi) \ lor \ psi}

este echivalent cu

\forall x(\phi \lor \psi )

{\ displaystyle \ forall x (\ phi \ lor \ psi)}

{\ displaystyle \ forall x (\ phi \ lor \ psi)}

;

Și

(\exists x\phi )\land \psi

{\ displaystyle (\ există x \ phi) \ land \ psi}

{\ displaystyle (\ există x \ phi) \ land \ psi}

este echivalent cu

\exists x(\phi \land \psi )

{\ displaystyle \ există x (\ phi \ land \ psi)}

{\ displaystyle \ există x (\ phi \ land \ psi)}

,

(\exists x\phi )\lor \psi

{\ displaystyle (\ există x \ phi) \ lor \ psi}

{\ displaystyle (\ există x \ phi) \ lor \ psi}

este echivalent cu

\exists x(\phi \lor \psi )

{\ displaystyle \ există x (\ phi \ lor \ psi)}

{\ displaystyle \ există x (\ phi \ lor \ psi)}

.

Echivalențele sunt valabile atunci când $X$ ${\ displaystyle x}$ $X$ nu apare ca o variabilă liberă în $\psi$ ${\ displaystyle \ psi}$ $\ psi$ ; dacă apare, trebuie înlocuit cu o altă variabilă liberă (care nu apare cuantificată și nici în $\psi$ ${\ displaystyle \ psi}$ $\ psi$ nici în $\phi$ ${\ displaystyle \ phi}$ $\ phi$ ).

De exemplu, în limba inelelor ,

(\exists x(x^{2}=1))\land (0=y)

{\ displaystyle (\ există x (x ^ {2} = 1)) \ land (0 = y)}

{\ displaystyle (\ există x (x ^ {2} = 1)) \ land (0 = y)}

este echivalent cu

\exists x(x^{2}=1\land 0=y)

{\ displaystyle \ există x (x ^ {2} = 1 \ land 0 = y)}

{\ displaystyle \ există x (x ^ {2} = 1 \ land 0 = y)}

,

dar

(\exists x(x^{2}=1))\land (0=x)

{\ displaystyle (\ există x (x ^ {2} = 1)) \ land (0 = x)}

{\ displaystyle (\ există x (x ^ {2} = 1)) \ land (0 = x)}

nu este echivalent cu

\exists x(x^{2}=1\land 0=x)

{\ displaystyle \ există x (x ^ {2} = 1 \ land 0 = x)}

{\ displaystyle \ există x (x ^ {2} = 1 \ land 0 = x)}

deoarece formula din stânga este adevărată în fiecare inel când variabila este liberă $X$ ${\ displaystyle x}$ $X$ este egal cu 0, în timp ce formula din dreapta nu are variabile libere și este falsă în orice inel.

Negare

Regulile de refuz prevăd că:

\lnot \exists x\phi

{\ displaystyle \ lnot \ există x \ phi}

{\ displaystyle \ lnot \ există x \ phi}

este echivalent cu

\forall x\lnot \phi

{\ displaystyle \ forall x \ lnot \ phi}

{\ displaystyle \ forall x \ lnot \ phi}

\lnot \forall x\phi

{\ displaystyle \ lnot \ forall x \ phi}

{\ displaystyle \ lnot \ forall x \ phi}

este echivalent cu

\exists x\lnot \phi

{\ displaystyle \ există x \ lnot \ phi}

{\ displaystyle \ există x \ lnot \ phi}

.

Implicare

Există patru reguli de implicare: două care elimină cuantificatorii din ipoteză și două care îi elimină din concluzie. Aceste reguli pot fi derivate din cele anterioare prin simpla rescriere a implicației $\phi \rightarrow \psi$ ${\ displaystyle \ phi \ rightarrow \ psi}$ ${\ displaystyle \ phi \ rightarrow \ psi}$ ca $\lnot \phi \lor \psi$ ${\ displaystyle \ lnot \ phi \ lor \ psi}$ ${\ displaystyle \ lnot \ phi \ lor \ psi}$ . Ca și în cazul disjuncțiilor, pentru aplicarea acestor reguli se presupune că o variabilă cuantificată într-o subformulă nu este prezentă ca o formulă liberă în cealaltă subformulă; în caz contrar, toate aparițiile trebuie înlocuite cu o altă variabilă aleasă în mod corespunzător.

Regulile pentru eliminarea cuantificatorului din ipoteză sunt

(\forall x\phi )\rightarrow \psi

{\ displaystyle (\ forall x \ phi) \ rightarrow \ psi}

{\ displaystyle (\ forall x \ phi) \ rightarrow \ psi}

este echivalent cu

\exists x(\phi \rightarrow \psi )

{\ displaystyle \ există x (\ phi \ rightarrow \ psi)}

{\ displaystyle \ există x (\ phi \ rightarrow \ psi)}

,

(\exists x\phi )\rightarrow \psi

{\ displaystyle (\ exists x \ phi) \ rightarrow \ psi}

{\ displaystyle (\ exists x \ phi) \ rightarrow \ psi}

este echivalent cu

\forall x(\phi \rightarrow \psi )

{\ displaystyle \ forall x (\ phi \ rightarrow \ psi)}

{\ displaystyle \ forall x (\ phi \ rightarrow \ psi)}

.

Regulile pentru eliminarea cuantificatorului din teză sunt

\phi \rightarrow (\exists x\psi )

{\ displaystyle \ phi \ rightarrow (\ există x \ psi)}

{\ displaystyle \ phi \ rightarrow (\ există x \ psi)}

este echivalent cu

\exists x(\phi \rightarrow \psi )

{\ displaystyle \ există x (\ phi \ rightarrow \ psi)}

{\ displaystyle \ există x (\ phi \ rightarrow \ psi)}

,

\phi \rightarrow (\forall x\psi )

{\ displaystyle \ phi \ rightarrow (\ forall x \ psi)}

{\ displaystyle \ phi \ rightarrow (\ forall x \ psi)}

este echivalent cu

\forall x(\phi \rightarrow \psi )

{\ displaystyle \ forall x (\ phi \ rightarrow \ psi)}

{\ displaystyle \ forall x (\ phi \ rightarrow \ psi)}

.

Exemplu

Lasa-i sa fie $\phi$ ${\ displaystyle \ phi}$ $\ phi$ , $\psi$ ${\ displaystyle \ psi}$ $\ psi$ Și $\rho$ ${\ displaystyle \ rho}$ $\ rho$ formule fără niciun cuantificator în interiorul lor și să presupunem că luate două câte două nu împărtășesc nicio variabilă liberă. Să luăm în considerare formula

(\phi \lor \exists x\psi )\rightarrow \forall z\rho

{\ displaystyle (\ phi \ lor \ există x \ psi) \ rightarrow \ forall z \ rho}

{\ displaystyle (\ phi \ lor \ există x \ psi) \ rightarrow \ forall z \ rho}

.

Aplicând regulile recursiv, pornind de la cele mai interioare formule, obținem următoarea succesiune de formule echivalente din punct de vedere logic:

(\exists x(\phi \lor \psi ))\rightarrow \forall z\rho

{\ displaystyle (\ există x (\ phi \ lor \ psi)) \ rightarrow \ forall z \ rho}

{\ displaystyle (\ există x (\ phi \ lor \ psi)) \ rightarrow \ forall z \ rho}

,

\forall x((\phi \lor \psi )\rightarrow \forall z\rho )

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

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

,

\forall z\forall 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)}

.

Cu toate acestea, aceasta nu este singura formă de preness echivalentă cu formula originală. De exemplu, tratând teza înainte de ipoteza din exemplul anterior, am fi obținut forma preness:

\forall x\forall z((\phi \lor \psi )\rightarrow \rho )

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

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

Logica intuiționistă

Regulile pentru convertirea unei formule într-o formă de prenessă utilizează în mare măsură logica clasică. În logica intuiționistă , nu este adevărat că fiecare formulă este echivalentă cu o formulă în formă de preness. Un obstacol este dat de simbolul negației. Dar, de asemenea, operatorul de „implicație” este tratat diferit în logica intuiționistă decât în logica clasică; de fapt, în logica intuiționistă nu poate fi redefinită pur și simplu prin utilizarea operatorilor de disjuncție și negație.

Interpretarea BHK ilustrează de ce unele formule nu au o formă prenessă echivalentă în sens intuiționist. În această interpretare, o demonstrație a

(\exists x\phi )\rightarrow \exists y\psi \qquad (1)

{\ displaystyle (\ există x \ phi) \ dreapta \ există y \ psi \ qquad (1)}

{\ displaystyle (\ există x \ phi) \ dreapta \ există y \ psi \ qquad (1)}

este o funcție care, dată fiind un $X$ ${\ displaystyle x}$ $X$ specific și o dovadă a lui φ ( x ), dă un y specific și o dovadă a lui ψ ( y ). În acest caz, valoarea lui y poate fi derivată din valoarea dată pentru x . O demonstrație de

\exists y(\exists x\phi \rightarrow \psi ),\qquad (2)

{\ displaystyle \ există y (\ există x \ phi \ rightarrow \ psi), \ qquad (2)}

{\ displaystyle \ există y (\ există x \ phi \ rightarrow \ psi), \ qquad (2)}

produce o singură valoare specifică a lui y și o funcție care convertește orice dovadă a $\exists x\phi$ ${\ displaystyle \ există x \ phi}$ ${\ displaystyle \ există x \ phi}$ într-o dovadă a lui ψ ( y ). Dacă fiecare x satisfăcător φ poate fi folosit pentru a obține un y satisfăcător ψ, dar nu se poate obține un astfel de y fără a cunoaște mai întâi un astfel de x , atunci formula (1) nu este echivalentă cu formula (2).

Regulile pentru conversia unei formule în formă de preness care nu sunt valabile în logica intuiționistă sunt următoarele:

(1)

\forall x(\phi \lor \psi )

{\ displaystyle \ forall x (\ phi \ lor \ psi)}

{\ displaystyle \ forall x (\ phi \ lor \ psi)}

implica

(\forall x\phi )\lor \psi

{\ displaystyle (\ forall x \ phi) \ lor \ psi}

{\ displaystyle (\ forall x \ phi) \ lor \ psi}

,

(2)

\forall x(\phi \lor \psi )

{\ displaystyle \ forall x (\ phi \ lor \ psi)}

{\ displaystyle \ forall x (\ phi \ lor \ psi)}

implica

\phi \lor (\forall x\psi )

{\ displaystyle \ phi \ lor (\ forall x \ psi)}

{\ displaystyle \ phi \ lor (\ forall x \ psi)}

,

(3)

(\forall x\phi )\rightarrow \psi

{\ displaystyle (\ forall x \ phi) \ rightarrow \ psi}

{\ displaystyle (\ forall x \ phi) \ rightarrow \ psi}

implica

\exists x(\phi \rightarrow \psi )

{\ displaystyle \ există x (\ phi \ rightarrow \ psi)}

{\ displaystyle \ există x (\ phi \ rightarrow \ psi)}

,

(4)

\phi \rightarrow (\exists x\psi )

{\ displaystyle \ phi \ rightarrow (\ există x \ psi)}

{\ displaystyle \ phi \ rightarrow (\ există x \ psi)}

implica

\exists x(\phi \rightarrow \psi )

{\ displaystyle \ există x (\ phi \ rightarrow \ psi)}

{\ displaystyle \ există x (\ phi \ rightarrow \ psi)}

,

(5)

\lnot \forall x\phi

{\ displaystyle \ lnot \ forall x \ phi}

{\ displaystyle \ lnot \ forall x \ phi}

implica

\exists x\lnot \phi

{\ displaystyle \ există x \ lnot \ phi}

{\ displaystyle \ există x \ lnot \ phi}

,

( x nu apare ca o variabilă liberă a $\,\psi$ ${\ displaystyle \, \ psi}$ ${\ displaystyle \, \ psi}$ în (1) și (3); x nu apare ca o variabilă liberă a $\,\phi$ ${\ displaystyle \, \ phi}$ $\, \ phi$ în (2) și (4)).

Utilitatea formularului preness

Unele metode de calculare a predicatelor presupun că toate formulele teoriei sunt în formă prenessă. Conceptul este esențial pentru dezvoltarea ierarhiei aritmetice și a ierarhiei analitice .

Dovada lui Gödel a teoremei sale de completitudine pentru logica de ordinul întâi presupune că toate formulele sunt reconvertite în formă preness.

Definiția clasică a formei normale a lui Skolem este „o formulă a cărei formă de preneză conține doar cuantificatori universali” .

Formular normal de preness

Așa cum am văzut în regula de conversie pentru operatorul de implicație, în general, o formulă poate fi echivalentă cu mai multe formule în formă preness. Din acest motiv, vorbirea despre o formă normală prenezală ar fi nepotrivită. Cu toate acestea, acest termen este destul de răspândit și este parțial justificat de faptul că, în scopuri practice , formulele de preness echivalente pot fi considerate aceleași, deoarece diferă doar în ordinea în care unii cuantificatori universali sunt dispuși (sau existențiali) consecutive. Cu alte cuvinte, următoarele formule:

$\forall x\forall y\phi$ ${\ displaystyle \ forall x \ forall y \ phi}$ ${\ displaystyle \ forall x \ forall y \ phi}$
$\forall y\forall x\phi$ ${\ displaystyle \ forall y \ forall x \ phi}$ ${\ displaystyle \ forall y \ forall x \ phi}$

sunt considerate egale, la fel ca următoarele:

$\exists x\exists y\phi$ ${\ displaystyle \ există x \ există y \ phi}$ ${\ displaystyle \ există x \ există y \ phi}$
$\exists y\exists x\phi$ ${\ displaystyle \ există y \ există x \ phi}$ ${\ displaystyle \ există y \ există x \ phi}$

Nu este surprinzător că ortografiile sunt comune în matematică $\exists x,y(\phi )$ ${\ displaystyle \ există x, y (\ phi)}$ ${\ displaystyle \ există x, y (\ phi)}$ Și $\forall x,y(\phi )$ ${\ displaystyle \ forall x, y (\ phi)}$ ${\ displaystyle \ forall x, y (\ phi)}$ , în care mai multe variabile sunt cuantificate „simultan”.

Referințe

Hinman, P., Fundamentals of Mathematical Logic , AK Peters, 2005, ISBN 1-56881-262-0 .

linkuri externe

( EN ) Forma de Preness , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.