Sequente

Un sequente è un'entità della logica che permette di esprimere legami tra asserzioni complesse facendo uso dei legami metalinguistici e che comporta. Le prime formalizzazioni di sequenti e di calcolo dei sequenti sono dovute al lavoro del logico Gerhard Gentzen, in particolare alle sue scoperte dei primi anni Trenta.

Si dice che lista di asserzioni C_i Δ segue da una lista di asserzioni D_i Γ (o equivalentemente che Γ comporta Δ) e si scrive

Γ ⊢ Δ {\displaystyle \Gamma \vdash \Delta }

quando

( C 1 a s s .   e   C 2 a s s .   e   …   e   C n a s s . )   c o m p o r t a   ( D 1 a s s .   o   …   o   D m a s s . ) {\displaystyle (C_{1}ass.\ e\ C_{2}ass.\ e\ \dots \ e\ C_{n}ass.)\ comporta\ (D_{1}ass.\ o\ \dots \ o\ D_{m}ass.)}

Nella visione della logica classica (LK) Δ è una lista di m asserzioni (o proposizioni), mentre in logica intuizionista (LJ) in Δ trova posto una sola proposizione. Questo è un fatto di notevole importanza perché condiziona tutta la struttura di regole inferenziali sui due sistemi.

Tutto quel che riguarda le regole di derivazione in LJ si riconduce alle cosiddette equazioni definitorie dei connettivi, che si costruiscono per deduzione naturale. Il calcolo dei sequenti consiste nell'applicare, partendo da un sequente formato da asserzioni complesse, le regole del sistema per giungere a sequenti riconosciuti validi. Se l'applicazione delle regole di derivazione porta sempre a scritture ambigue o non vere (ad esempio da una proposizione B segue che A non viene di certo considerato un sequente valido) allora si può concludere che quel sequente non è derivabile, o, meglio, che la frase che esprime non è dimostrabile.

Vengono definiti:

• ⊥ ovvero la proposizione falsa in qualsiasi interpretazione, allora vale che Γ , ⊥⊢ Δ {\displaystyle \Gamma ,\perp \vdash \Delta } (da falso segue qualsiasi cosa)
• T ovvero la proposizione sempre vera ⊢ ⊤ {\displaystyle \vdash \top }
• Identità: è sempre vero il sequente A ⊢ A {\displaystyle A\vdash A} per qualsiasi proposizione A.

Si formalizzano inoltre le equazioni definitorie dei quattro connettivi e dei due quantificatori come segue:

• ∧-equazione: Γ ⊢ A ∧ B ⟺ Γ ⊢ A ∧ Γ ⊢ B {\displaystyle \Gamma \vdash A\land B\iff \Gamma \vdash A\land \Gamma \vdash B}
• ∨-equazione: A ∨ B ⊢ Δ ⟺ A ⊢ Δ ∧ B ⊢ Δ {\displaystyle A\lor B\vdash \Delta \iff A\vdash \Delta \land B\vdash \Delta }
• →-equazione: Γ ⊢ A → B ⟺ Γ , A ⊢ B {\displaystyle \Gamma \vdash A\rightarrow B\iff \Gamma ,A\vdash B}
• ¬-equazione: ⊢ ¬ A ⟺ A ⊢⊥ {\displaystyle \vdash \neg A\iff A\vdash \perp }
• ∀-equazione: Γ ⊢ ( ∀ x ∈ D ) A ( x ) ⟺ Γ , z ∈ D ⊢ A ( z ) {\displaystyle \Gamma \vdash (\forall x\in D)A(x)\iff \Gamma ,z\in D\vdash A(z)}
• ∃-equazione: Γ , ( ∃ x ∈ D ) A ( x ) ⊢ Δ ⟺ p e r   u n   g e n e r i c o   z ∈ D   s i   h a   Γ , z ∈ D , A ( z ) ⊢ Δ {\displaystyle \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 }

Dove D è il dominio della variabile x e A(x) è un predicato

Tenendo presente che regola di identità A ⊢ A {\displaystyle A\vdash A} è vera sempre, si risolvono le equazioni definitorie ottenendo le seguenti regole inferenziali di derivazione per i sequenti.

• ∧-formazione Γ ⊢ A       Γ ⊢ B Γ ⊢ A ∧ B {\displaystyle {\frac {\Gamma \vdash A\ \ \ \Gamma \vdash B}{\Gamma \vdash A\land B}}}

• ∧-riflessione Γ , A ⊢ Δ Γ , A ∧ B ⊢ Δ , Γ , B ⊢ Δ Γ , A ∧ B ⊢ Δ {\displaystyle {\frac {\Gamma ,A\vdash \Delta }{\Gamma ,A\land B\vdash \Delta }},{\frac {\Gamma ,B\vdash \Delta }{\Gamma ,A\land B\vdash \Delta }}}

• ∨-formazione Γ , A ⊢ Δ       Γ , B ⊢ Δ Γ , A ∨ B ⊢ Δ {\displaystyle {\frac {\Gamma ,A\vdash \Delta \ \ \ \Gamma ,B\vdash \Delta }{\Gamma ,A\lor B\vdash \Delta }}}

• ∨-riflessione Γ ⊢ A Γ ⊢ A ∨ B , Γ ⊢ B Γ ⊢ A ∨ B {\displaystyle {\frac {\Gamma \vdash A}{\Gamma \vdash A\lor B}},{\frac {\Gamma \vdash B}{\Gamma \vdash A\lor B}}}

• →-formazione Γ , A ⊢ B Γ ⊢ A → B {\displaystyle {\frac {\Gamma ,A\vdash B}{\Gamma \vdash A\rightarrow B}}}

• →-riflessione Γ ⊢ A       Γ ′ , B ⊢ Δ Γ , Γ ′ , A → B ⊢ Δ {\displaystyle {\frac {\Gamma \vdash A\ \ \ \Gamma ',B\vdash \Delta }{\Gamma ,\Gamma ',A\rightarrow B\vdash \Delta }}}

• ¬-formazione Γ , A ⊢⊥ Γ ⊢ ¬ A {\displaystyle {\frac {\Gamma ,A\vdash \perp }{\Gamma \vdash \neg A}}}

• ¬-riflessione Γ ⊢ A Γ , ¬ A ⊢ Δ {\displaystyle {\frac {\Gamma \vdash A}{\Gamma ,\neg A\vdash \Delta }}}

Appare chiaro che le regole sul ¬ derivano direttamente da quelle su →: infatti le scritture ¬ A {\displaystyle \neg A} e A →⊥ {\displaystyle A\rightarrow \perp } si equivalgono.

In LJ valgono le due seguenti regole:

• Indebolimento Γ ⊢ Δ Γ , Σ ⊢ Δ {\displaystyle {\frac {\Gamma \vdash \Delta }{\Gamma ,\Sigma \vdash \Delta }}}

• Contrazione Γ , A , A ⊢ Δ Γ , A ⊢ Δ {\displaystyle {\frac {\Gamma ,A,A\vdash \Delta }{\Gamma ,A\vdash \Delta }}}

Le regole di derivazione dei quantificatori in LJ sono:

• ∀-formazione Γ , z ∈ D ⊢ A ( z ) Γ ⊢ ( ∀ x ∈ D ) A ( x ) {\displaystyle {\frac {\Gamma ,z\in D\vdash A(z)}{\Gamma \vdash (\forall x\in D)A(x)}}} o equivalentemente Γ ⊢ A ( z ) Γ ⊢ ∀ x A ( x ) {\displaystyle {\frac {\Gamma \vdash A(z)}{\Gamma \vdash \forall xA(x)}}}

con z {\displaystyle z} non libera in D. Ciò significa che z non deve già comparire in qualche proposizione del sequente altrimenti si avrebbe un sistema inconsistente: asserire che, dato A per una certa variabile, valga A per tutti gli elementi del dominio è assolutamente folle.

• ∀-riflessione Γ ⊢ z ∈ D       Γ ′ , A ( x ) ⊢ Δ Γ , ( ∀ x ∈ D ) A ( x ) , Γ ′ ⊢ Δ {\displaystyle {\frac {\Gamma \vdash z\in D\ \ \ \Gamma ',A(x)\vdash \Delta }{\Gamma ,(\forall x\in D)A(x),\Gamma '\vdash \Delta }}} o equivalentemente Γ , A ( z ) ⊢ Δ Γ , ∀ x A ( x ) ⊢ Δ {\displaystyle {\frac {\Gamma ,A(z)\vdash \Delta }{\Gamma ,\forall xA(x)\vdash \Delta }}}

• ∃-formazione Γ , z ∈ D , A ( z ) ⊢ Δ Γ , ( ∃ x ∈ D ) A ( x ) ⊢ Δ {\displaystyle {\frac {\Gamma ,z\in D,A(z)\vdash \Delta }{\Gamma ,(\exists x\in D)A(x)\vdash \Delta }}} o equivalentemente Γ , A ( z ) ⊢ Δ Γ , ∃ x A ( x ) ⊢ Δ {\displaystyle {\frac {\Gamma ,A(z)\vdash \Delta }{\Gamma ,\exists xA(x)\vdash \Delta }}}

con z {\displaystyle z} non libera in D.

• ∃-riflessione Γ ⊢ z ∈ D       Γ ′ ⊢ A ( z ) Γ , Γ ′ ⊢ ( ∃ x ∈ D ) A ( x ) {\displaystyle {\frac {\Gamma \vdash z\in D\ \ \ \Gamma '\vdash A(z)}{\Gamma ,\Gamma '\vdash (\exists x\in D)A(x)}}} o equivalentemente Γ ⊢ A ( z ) Γ ⊢ ∃ x A ( x ) {\displaystyle {\frac {\Gamma \vdash A(z)}{\Gamma \vdash \exists xA(x)}}}

Il calcolo dei sequenti in logica classica si differenzia dal calcolo dei sequenti in logica intuizionista per il fatto che i contesti (le liste di proposizioni) sono presenti anche a destra. Ciò vale per tutte le regole, incluse quelle strutturali di indebolimento e contrazione.

Per questo motivo in logica classica sono considerati veri il principio del terzo escluso e il sequente ¬ ¬ A ⊢ A {\displaystyle \neg \neg A\vdash A} : avendo a disposizione regole con i contesti a destra è possibile fornirne agilmente una dimostrazione, contrariamente a quanto accade nel sistema LJ, per il quale non sono vere.

Le regole di calcolo applicabili nella logica proposizionale mediante l'uso dei sequenti, sono: regola di assunzione, modus ponendo ponens, modus tollendo tollens, doppia negazione, introduzione della congiunzione, eliminazione della congiunzione, introduzione della disgiunzione, eliminazione della disgiunzione, prova condizionale e reductio ad absurdum. Il formalismo dei sequenti permette di definire quale sottoinsieme delle assunzioni dalle quali dipendono le premesse costituisce anche il sottoinsieme delle assunzioni dalle quali dipende la conclusione da esse derivata. Nel caso degli ultimi tre operatori logici (eliminazione della disgiunzione, prova condizionale e reductio ad absurdum), l'insieme delle assunzioni da cui dipende la conclusione non coincide con l'unione (o somma) degli insiemi delle assunzioni delle rispettive premesse.^[1]

• Logica intuizionista
• Logica classica
• Gerhard Gentzen
• Teorema di eliminazione del taglio

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica