Secvență

O secvență este o entitate logică care permite exprimarea legăturilor între enunțuri complexe folosind legăturile metalingvistice și pe care le implică . Primele formalizări ale secvențelor și calculul secvențelor se datorează muncii logicianului Gerhard Gentzen , în special descoperirilor sale de la începutul anilor 1930.

Se spune că lista afirmațiilor C _i follow urmează dintr-o listă de afirmații D _i Γ (sau echivalent care Γ implică Δ) și este scrisă

$\Gamma \vdash \Delta$ ${\ displaystyle \ Gamma \ vdash \ Delta}$ ${\ displaystyle \ Gamma \ vdash \ Delta}$

cand

$(C_{1}ass.\ e\ C_{2}ass.\ e\ \dots \ e\ C_{n}ass.)\ comporta\ (D_{1}ass.\ o\ \dots \ o\ D_{m}ass.)$ ${\ displaystyle (C_ {1} abs. \ e \ C_ {2} abs. \ e \ \ dots \ e \ C_ {n} abs.) \ implică \ (D_ {1} abs. \ o \ \ dots \ sau \ D_ {m} abs.)}$ ${\ displaystyle (C_ {1} abs. \ e \ C_ {2} abs. \ e \ \ dots \ e \ C_ {n} abs.) \ implică \ (D_ {1} abs. \ o \ \ dots \ sau \ D_ {m} abs.)}$

În viziunea logicii clasice ( LK ) Δ este o listă de m afirmații (sau propoziții ), în timp ce în logica intuiționistă ( LJ ) există o singură propoziție în Δ. Acesta este un fapt foarte important, deoarece afectează întreaga structură a regulilor de inferență pentru cele două sisteme.

Calculul secvențelor în LJ

Tot ceea ce privește regulile de derivare în LJ poate fi urmărit înapoi la așa-numitele ecuații definitorii ale conectivelor , care sunt construite prin deducție naturală. Calculul secvențelor constă în aplicarea, pornind de la o secvență formată din afirmații complexe, regulile sistemului pentru a ajunge la secvențe recunoscute ca valide. Dacă aplicarea regulilor de derivare duce întotdeauna la scrieri ambigue sau neadevărate (de exemplu dintr-o propoziție B rezultă că A nu este considerat cu siguranță o secvență validă) atunci se poate concluziona că acea secvență nu este derivabilă sau, mai bine, că propoziția pe care o exprimă nu este demonstrabilă .

Definirea ecuațiilor

Acestea sunt definite:

⊥ sau propoziția falsă din orice interpretare, atunci susține că $\Gamma ,\perp \vdash \Delta$ ${\ displaystyle \ Gamma, \ perp \ vdash \ Delta}$ ${\ displaystyle \ Gamma, \ perp \ vdash \ Delta}$ (din fals totul urmează)
T sau propunerea întotdeauna adevărată $\vdash \top$ ${\ displaystyle \ vdash \ top}$ ${\ displaystyle \ vdash \ top}$
Identitate: secvența este întotdeauna adevărată $A\vdash A$ ${\ displaystyle A \ vdash A}$ ${\ displaystyle A \ vdash A}$ pentru orice propunere A.

În plus, ecuațiile definitorii ale celor patru conectivități și ale celor două cuantificatoare sunt formalizate după cum urmează:

Ecuația ∧: $\Gamma \vdash A\land B\iff \Gamma \vdash A\land \Gamma \vdash B$ ${\ displaystyle \ Gamma \ vdash A \ land B \ iff \ Gamma \ vdash A \ land \ Gamma \ vdash B}$ ${\ displaystyle \ Gamma \ vdash A \ land B \ iff \ Gamma \ vdash A \ land \ Gamma \ vdash B}$
Ecuația ∨: $A\lor B\vdash \Delta \iff A\vdash \Delta \land B\vdash \Delta$ ${\ displaystyle A \ lor B \ vdash \ Delta \ if A \ vdash \ Delta \ land B \ vdash \ Delta}$ ${\ displaystyle A \ lor B \ vdash \ Delta \ if A \ vdash \ Delta \ land B \ vdash \ Delta}$
→ -ecuație: $\Gamma \vdash A\rightarrow B\iff \Gamma ,A\vdash B$ ${\ displaystyle \ Gamma \ vdash A \ rightarrow B \ iff \ Gamma, A \ vdash B}$ ${\ displaystyle \ Gamma \ vdash A \ rightarrow B \ iff \ Gamma, A \ vdash B}$
¬-ecuație: $\vdash \neg A\iff A\vdash \perp$ ${\ displaystyle \ vdash \ neg A \ if A \ vdash \ perp}$ ${\ displaystyle \ vdash \ neg A \ if A \ vdash \ perp}$
Ecuația ∀: $\Gamma \vdash (\forall x\in D)A(x)\iff \Gamma ,z\in D\vdash A(z)$ ${\ displaystyle \ Gamma \ vdash (\ forall x \ in D) A (x) \ if \ Gamma, z \ in D \ vdash A (z)}$ ${\ displaystyle \ Gamma \ vdash (\ forall x \ in D) A (x) \ if \ Gamma, z \ in D \ vdash A (z)}$
Ecuația ∃: $\Gamma ,(\exists x\in D)A(x)\vdash \Delta \iff per\ un\ generico\ z\in D\ si\ ha\ \Gamma ,z\in D,A(z)\vdash \Delta$ ${\ displaystyle \ Gamma, (\ exist x \ in D) A (x) \ vdash \ Delta \ iff pentru \ a \ generic \ z \ in D \ si \ ha \ \ Gamma, z \ in D, A (z ) \ vdash \ Delta}$ ${\ displaystyle \ Gamma, (\ exist x \ in D) A (x) \ vdash \ Delta \ iff pentru \ a \ generic \ z \ in D \ si \ ha \ \ Gamma, z \ in D, A (z ) \ vdash \ Delta}$

Unde D este domeniul variabilei x și A (x) este un predicat

Calcul propozițional în LJ

Ținând cont de regula de identitate $A\vdash A$ ${\ displaystyle A \ vdash A}$ ${\ displaystyle A \ vdash A}$ este întotdeauna adevărat, ecuațiile definitorii sunt rezolvate prin obținerea următoarelor reguli inferențiale de derivare pentru secvențe.

∧-instruire ${\frac {\Gamma \vdash A\ \ \ \Gamma \vdash B}{\Gamma \vdash A\land B}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A \ \ \ \ Gamma \ vdash B} {\ Gamma \ vdash A \ land B}}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A \ \ \ \ Gamma \ vdash B} {\ Gamma \ vdash A \ land B}}}$

∧-reflecție ${\frac {\Gamma ,A\vdash \Delta }{\Gamma ,A\land B\vdash \Delta }},{\frac {\Gamma ,B\vdash \Delta }{\Gamma ,A\land B\vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma, A \ vdash \ Delta} {\ Gamma, A \ land B \ vdash \ Delta}}, {\ frac {\ Gamma, B \ vdash \ Delta} {\ Gamma, A \ teren B \ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma, A \ vdash \ Delta} {\ Gamma, A \ land B \ vdash \ Delta}}, {\ frac {\ Gamma, B \ vdash \ Delta} {\ Gamma, A \ teren B \ vdash \ Delta}}}$

∨-instruire ${\frac {\Gamma ,A\vdash \Delta \ \ \ \Gamma ,B\vdash \Delta }{\Gamma ,A\lor B\vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma, A \ vdash \ Delta \ \ \ \ Gamma, B \ vdash \ Delta} {\ Gamma, A \ lor B \ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma, A \ vdash \ Delta \ \ \ \ Gamma, B \ vdash \ Delta} {\ Gamma, A \ lor B \ vdash \ Delta}}}$

∨-reflecție ${\frac {\Gamma \vdash A}{\Gamma \vdash A\lor B}},{\frac {\Gamma \vdash B}{\Gamma \vdash A\lor B}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A} {\ Gamma \ vdash A \ lor B}}, {\ frac {\ Gamma \ vdash B} {\ Gamma \ vdash A \ lor B}}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A} {\ Gamma \ vdash A \ lor B}}, {\ frac {\ Gamma \ vdash B} {\ Gamma \ vdash A \ lor B}}}$

→ -formare ${\frac {\Gamma ,A\vdash B}{\Gamma \vdash A\rightarrow B}}$ ${\ displaystyle {\ frac {\ Gamma, A \ vdash B} {\ Gamma \ vdash A \ rightarrow B}}}$ ${\ displaystyle {\ frac {\ Gamma, A \ vdash B} {\ Gamma \ vdash A \ rightarrow B}}}$

→ -reflecție ${\frac {\Gamma \vdash A\ \ \ \Gamma ',B\vdash \Delta }{\Gamma ,\Gamma ',A\rightarrow B\vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A \ \ \ \ Gamma ', B \ vdash \ Delta} {\ Gamma, \ Gamma', A \ rightarrow B \ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A \ \ \ \ Gamma ', B \ vdash \ Delta} {\ Gamma, \ Gamma', A \ rightarrow B \ vdash \ Delta}}}$

¬-instruire ${\frac {\Gamma ,A\vdash \perp }{\Gamma \vdash \neg A}}$ ${\ displaystyle {\ frac {\ Gamma, A \ vdash \ perp} {\ Gamma \ vdash \ neg A}}}$ ${\ displaystyle {\ frac {\ Gamma, A \ vdash \ perp} {\ Gamma \ vdash \ neg A}}}$

¬-reflecție ${\frac {\Gamma \vdash A}{\Gamma ,\neg A\vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A} {\ Gamma, \ neg A \ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A} {\ Gamma, \ neg A \ vdash \ Delta}}}$

Este clar că regulile privind ¬ derivă direct din cele de pe →: de fapt scrierile $\neg A$ ${\ displaystyle \ neg A}$ $\ neg A$ Și $A\rightarrow \perp$ ${\ displaystyle A \ rightarrow \ perp}$ ${\ displaystyle A \ rightarrow \ perp}$ sunt echivalente.

Reguli structurale în LJ

În LJ se aplică următoarele două reguli:

Slăbire ${\frac {\Gamma \vdash \Delta }{\Gamma ,\Sigma \vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma \ vdash \ Delta} {\ Gamma, \ Sigma \ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash \ Delta} {\ Gamma, \ Sigma \ vdash \ Delta}}}$

Contracție ${\frac {\Gamma ,A,A\vdash \Delta }{\Gamma ,A\vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma, A, A \ vdash \ Delta} {\ Gamma, A \ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma, A, A \ vdash \ Delta} {\ Gamma, A \ vdash \ Delta}}}$

Cuantificatoare

Regulile de derivare a cuantificatorilor în LJ sunt:

∀-instruire ${\frac {\Gamma ,z\in D\vdash A(z)}{\Gamma \vdash (\forall x\in D)A(x)}}$ ${\ displaystyle {\ frac {\ Gamma, z \ in D \ vdash A (z)} {\ Gamma \ vdash (\ forall x \ in D) A (x)}}}$ ${\ displaystyle {\ frac {\ Gamma, z \ in D \ vdash A (z)} {\ Gamma \ vdash (\ forall x \ in D) A (x)}}}$ sau echivalent ${\frac {\Gamma \vdash A(z)}{\Gamma \vdash \forall xA(x)}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A (z)} {\ Gamma \ vdash \ forall xA (x)}}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A (z)} {\ Gamma \ vdash \ forall xA (x)}}}$

cu $z$ ${\ displaystyle z}$ $z$ nu eliberează în D. Aceasta înseamnă că z nu trebuie să apară deja în unele propoziții ale secvenței, altfel am avea un sistem inconsistent: să afirmăm că, dat fiind A pentru o anumită variabilă, A este valabil pentru toate elementele domeniului este absolut nebun.

∀-reflecție ${\frac {\Gamma \vdash z\in D\ \ \ \Gamma ',A(x)\vdash \Delta }{\Gamma ,(\forall x\in D)A(x),\Gamma '\vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma \ vdash z \ in D \ \ \ \ Gamma ', A (x) \ vdash \ Delta} {\ Gamma, (\ forall x \ in D) A (x), \ Gamma '\ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash z \ in D \ \ \ \ Gamma ', A (x) \ vdash \ Delta} {\ Gamma, (\ forall x \ in D) A (x), \ Gamma '\ vdash \ Delta}}}$ sau echivalent ${\frac {\Gamma ,A(z)\vdash \Delta }{\Gamma ,\forall xA(x)\vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma, A (z) \ vdash \ Delta} {\ Gamma, \ forall xA (x) \ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma, A (z) \ vdash \ Delta} {\ Gamma, \ forall xA (x) \ vdash \ Delta}}}$

∃-instruire ${\frac {\Gamma ,z\in D,A(z)\vdash \Delta }{\Gamma ,(\exists x\in D)A(x)\vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma, z \ in D, A (z) \ vdash \ Delta} {\ Gamma, (\ exist x \ in D) A (x) \ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma, z \ in D, A (z) \ vdash \ Delta} {\ Gamma, (\ exist x \ in D) A (x) \ vdash \ Delta}}}$ sau echivalent ${\frac {\Gamma ,A(z)\vdash \Delta }{\Gamma ,\exists xA(x)\vdash \Delta }}$ ${\ displaystyle {\ frac {\ Gamma, A (z) \ vdash \ Delta} {\ Gamma, \ există xA (x) \ vdash \ Delta}}}$ ${\ displaystyle {\ frac {\ Gamma, A (z) \ vdash \ Delta} {\ Gamma, \ există xA (x) \ vdash \ Delta}}}$

cu $z$ ${\ displaystyle z}$ $z$ nu liber în D.

∃-reflecție ${\frac {\Gamma \vdash z\in D\ \ \ \Gamma '\vdash A(z)}{\Gamma ,\Gamma '\vdash (\exists x\in D)A(x)}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash z \ in D \ \ \ \ Gamma '\ vdash A (z)} {\ Gamma, \ Gamma' \ vdash (\ exist x \ in D) A (x)} }}$ ${\ displaystyle {\ frac {\ Gamma \ vdash z \ in D \ \ \ \ Gamma '\ vdash A (z)} {\ Gamma, \ Gamma' \ vdash (\ exist x \ in D) A (x)} }}$ sau echivalent ${\frac {\Gamma \vdash A(z)}{\Gamma \vdash \exists xA(x)}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A (z)} {\ Gamma \ vdash \ există xA (x)}}}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A (z)} {\ Gamma \ vdash \ există xA (x)}}}$

Calculul secvențelor în LK

Calculul secvențelor în logica clasică diferă de calculul secvențelor în logica intuiționistă prin faptul că contextele (listele de propoziții ) sunt prezente și în dreapta. Acest lucru se aplică tuturor regulilor, inclusiv regulilor de slăbire structurală și de reducere.

Din acest motiv, în logica clasică, principiul terțului exclus și al secvenței sunt considerate adevărate $\neg \neg A\vdash A$ ${\ displaystyle \ neg \ neg A \ vdash A}$ ${\ displaystyle \ neg \ neg A \ vdash A}$ : având reguli disponibile cu contextele din dreapta, este posibil să oferiți cu ușurință o demonstrație , contrar a ceea ce se întâmplă în sistemul LJ , pentru care acestea nu sunt adevărate.

Regulile de calcul aplicabile în logica propozițională prin utilizarea secvențelor sunt: regula presupunerii, modus ponendo ponens , modus tollendo tollens , dubla negație , introducerea conjuncției, eliminarea conjuncției, introducerea disjuncției, eliminarea disjuncției, condițională dovadă și reducere ad absurdum . Formalismul succesiv ne permite să definim care subgrup al ipotezelor de care depind premisele constituie și subgrupul ipotezelor de care depinde concluzia derivată din acestea. În cazul ultimilor trei operatori logici (eliminarea disjuncției, dovezilor condiționate și reductio ad absurdum ), setul de ipoteze de care depinde concluzia nu coincide cu unirea (sau suma) seturilor de ipoteze ale respectivului premise. ^[1]

Notă

^ prof. Giuseppe Spolaore, Limbaje formale și calcule - Regulile calculului propozițional ( PDF ), Universitatea din Verona, pp. 13-20. Adus la 18 noiembrie 2020 ( arhivat la 18 noiembrie 2020) .

Elemente conexe

[1] rof. Giuseppe Spolaore, Limbaje formale și calcule - Regulile calculului propozițional ( PDF ), Universitatea din Verona, pp. 13-20. Adus la 18 noiembrie 2020 ( arhivat la 18 noiembrie 2020) .

[1]