Hispanopedia Wiki
Articulo de referencia

Hipersecuencia

En lógica matemática , el marco hipersecuente es una extensión del marco teórico de la demostración de los cálculos de secuencias utilizados en la teoría de la demostración estr...

Hispanopedia WikiContenido en espanolLectura gratuita

En lógica matemática , el marco hipersecuente es una extensión del marco teórico de la demostración de los cálculos de secuencias utilizados en la teoría de la demostración estructural para proporcionar cálculos analíticos para lógicas que no están capturadas en el marco de secuencias. Un hipersecuente se suele tomar como un multiconjunto finito de secuencias ordinarias , escrito

Γ1⇒Δ1∣⋯∣Γnorte⇒Δnorte{\displaystyle \Gamma _{1}\Rightarrow \Delta _{1}\mid \cdots \mid \Gamma _{n}\Rightarrow \Delta _{n}}

Las secuencias que componen una hipersecuencia se denominan componentes. La expresividad adicional del marco de la hipersecuencia la proporcionan las reglas que manipulan diferentes componentes, como la regla de comunicación para la lógica intermedia LC ( lógica de Gödel-Dummett ).

Γ1⇒Δ1∣⋯∣Γnorte⇒Δnorte∣Σ⇒AΩ1⇒Θ1∣⋯∣Ωmetro⇒Θmetro∣Π⇒BΓ1⇒Δ1∣⋯∣Γnorte⇒Δnorte∣Ω1⇒Θ1∣⋯∣Ωmetro⇒Θmetro∣Σ⇒B∣Π⇒A{\displaystyle {\frac {\Gamma _{1}\Rightarrow \Delta _{1}\mid \dots \mid \Gamma _{n}\Rightarrow \Delta _{n}\mid \Sigma \Rightarrow A\qquad \Omega _{1}\Rightarrow \Theta _{1}\mid \dots \mid \Omega _{m}\Rightarrow \Theta _{m}\mid \Pi \Rightarrow B}{\Gamma _{1}\Rightarrow \Delta _{1}\mid \dots \mid \Gamma _{n}\Rightarrow \Delta _{n}\mid \Omega _{1}\Rightarrow \Theta _{1}\mid \dots \mid \Omega _{m}\Rightarrow \Theta _{m}\mid \Sigma \Rightarrow B\mid \Pi \Rightarrow A}}}

o la regla de división modal para la lógica modal S5 : [ 1 ]

Γ1⇒Δ1∣⋯∣Γnorte⇒Δnorte∣◻Σ,Θ⇒◻Π,ΩΓ1⇒Δ1∣⋯∣Γnorte⇒Δnorte∣◻Σ⇒◻Π∣Θ⇒Ω{\displaystyle {\frac {\Gamma _{1}\Rightarrow \Delta _{1}\mid \dots \mid \Gamma _{n}\Rightarrow \Delta _{n}\mid \Box \Sigma ,\Theta \Rightarrow \Box \Pi ,\Omega }{\Gamma _{1}\Rightarrow \Delta _{1}\mid \dots \mid \Gamma _{n}\Rightarrow \Delta _{n}\mid \Box \Sigma \Rightarrow \Box \Pi \mid \Theta \Rightarrow \Omega }}}

Los cálculos de hipersecuencias se han utilizado para tratar lógicas modales , lógicas intermedias y lógicas subestructurales . Las hipersecuencias suelen tener una interpretación mediante fórmulas, es decir, se interpretan mediante una fórmula en el lenguaje objeto, casi siempre como algún tipo de disyunción. La interpretación precisa de la fórmula depende de la lógica considerada.

Definiciones formales y reglas proposicionales

Formalmente, un hipersecuente se suele tomar como un multiconjunto finito de secuencias ordinarias , escrito

Γ1⇒Δ1∣⋯∣Γnorte⇒Δnorte{\displaystyle \Gamma _{1}\Rightarrow \Delta _{1}\mid \dots \mid \Gamma _{n}\Rightarrow \Delta _{n}}

Las secuencias que componen una hipersecuencia consisten en pares de multiconjuntos de fórmulas y se denominan componentes de la hipersecuencia. También se consideran variantes que definen hipersecuencias y secuencias en términos de conjuntos o listas en lugar de multiconjuntos, y dependiendo de la lógica considerada, las secuencias pueden ser clásicas o intuicionistas . Las reglas para los conectores proposicionales suelen ser adaptaciones de las reglas estándar de secuencias correspondientes con una hipersecuencia adicional, también llamada contexto hipersecuencia. Por ejemplo, un conjunto común de reglas para el conjunto funcionalmente completo de conectores.{⊥,→}{\displaystyle \{\bot,\to \}}La lógica proposicional clásica viene dada por las siguientes cuatro reglas:

GRAMO∣Γ,pag⇒pag,Δ{\displaystyle {\frac {}{{\mathcal {G}}\mid \Gamma ,p\Rightarrow p,\Delta }}}
GRAMO∣Γ,⊥⇒Δ{\displaystyle {\frac {}{{\mathcal {G}}\mid \Gamma ,\bot \Rightarrow \Delta }}}
GRAMO∣Γ,B⇒ΔGRAMO∣Γ⇒A,ΔGRAMO∣Γ,A→B⇒Δ{\displaystyle {\frac {{\mathcal {G}}\mid \Gamma ,B\Rightarrow \Delta \qquad {\mathcal {G}}\mid \Gamma \Rightarrow A,\Delta }{{\mathcal {G}}\mid \Gamma ,A\to B\Rightarrow \Delta }}}

GRAMO∣Γ,A⇒B,ΔGRAMO∣Γ⇒A→B,Δ{\displaystyle {\frac {{\mathcal {G}}\mid \Gamma ,A\Rightarrow B,\Delta }{{\mathcal {G}}\mid \Gamma \Rightarrow A\to B,\Delta }}}

Debido a la estructura adicional en el contexto hipersecuencial, las reglas estructurales se consideran en sus variantes internas y externas. Las reglas de debilitamiento interno y contracción interna son adaptaciones de las reglas de secuencia correspondientes con un contexto hipersecuencial añadido:

GRAMO∣Γ⇒ΔGRAMO∣Γ,Σ⇒Δ,Π{\displaystyle {\frac {{\mathcal {G}}\mid \Gamma \Rightarrow \Delta }{{\mathcal {G}}\mid \Gamma,\Sigma \Rightarrow \Delta,\Pi }}}

GRAMO∣Γ,A,A⇒ΔGRAMO∣Γ,A⇒Δ{\displaystyle {\frac {{\mathcal {G}}\mid \Gamma ,A,A\Rightarrow \Delta }{{\mathcal {G}}\mid \Gamma ,A\Rightarrow \Delta }}}

GRAMO∣Γ⇒A,A,ΔGRAMO∣Γ⇒A,Δ{\displaystyle {\frac {{\mathcal {G}}\mid \Gamma \Rightarrow A,A,\Delta }{{\mathcal {G}}\mid \Gamma \Rightarrow A,\Delta }}}

Las reglas de debilitamiento externo y contracción externa son las reglas correspondientes a nivel de componentes hipersecuenciales en lugar de fórmulas:

GRAMOGRAMO∣Γ⇒Δ{\displaystyle {\frac {\mathcal {G}}{{\mathcal {G}}\mid \Gamma \Rightarrow \Delta }}}

GRAMO∣Γ⇒Δ∣Γ⇒ΔGRAMO∣Γ⇒Δ{\displaystyle {\frac {{\mathcal {G}}\mid \Gamma \Rightarrow \Delta \mid \Gamma \Rightarrow \Delta }{{\mathcal {G}}\mid \Gamma \Rightarrow \Delta }}}

La validez de estas reglas está estrechamente ligada a la interpretación de la fórmula de la estructura hipersecuencial, casi siempre como alguna forma de disyunción . La interpretación precisa de la fórmula depende de la lógica considerada; véanse algunos ejemplos a continuación.

Ejemplos principales

Las hipersecuentes se han utilizado para obtener cálculos analíticos para lógicas modales , para las cuales los cálculos de secuencias analíticas resultaron esquivos. En el contexto de las lógicas modales, la interpretación de fórmula estándar de una hipersecuente

Γ1⇒Δ1∣⋯∣Γnorte⇒Δnorte{\displaystyle \Gamma _{1}\Rightarrow \Delta _{1}\mid \dots \mid \Gamma _{n}\Rightarrow \Delta _{n}}

es la fórmula

◻(⋀Γ1→⋁Δ1)∨⋯∨◻(⋀Γnorte→⋁Δnorte){\displaystyle \Box (\bigwedge \Gamma _{1}\to \bigvee \Delta _{1})\lor \dots \lor \Box (\bigwedge \Gamma _{n}\to \bigvee \Delta _{n})}

Aquí siΓ{\displaystyle \Gamma }es el multiconjuntoA1,…,Anorte{\displaystyle A_{1},\dots ,A_{n}}escribimos◻Γ{\displaystyle \Box \Gamma }para el resultado de anteponer cada fórmula enΓ{\displaystyle \Gamma }con◻{\displaystyle \Box }, es decir, el multiconjunto◻A1,…,◻Anorte{\displaystyle \Box A_{1},\dots ,\Box A_{n}}. Tenga en cuenta que los componentes individuales se interpretan utilizando la interpretación de fórmula estándar para secuencias, y la barra hipersecuencial∣{\displaystyle \mid }se interpreta como una disyunción de cajas. El ejemplo principal de una lógica modal para la cual las hipersecuencias proporcionan un cálculo analítico es la lógica S5 . En un cálculo de hipersecuencias estándar para esta lógica [ 1 ] , la interpretación de la fórmula es la anterior, y las reglas proposicionales y estructurales son las de la sección anterior. Además, el cálculo contiene las reglas modales.

GRAMO∣◻Γ⇒AGRAMO∣◻Γ⇒◻A{\displaystyle {\frac {{\mathcal {G}}\mid \Box \Gamma \Rightarrow A}{{\mathcal {G}}\mid \Box \Gamma \Rightarrow \Box A}}}

GRAMO∣Γ,A⇒ΔGRAMO∣Γ,◻A⇒Δ{\displaystyle {\frac {{\mathcal {G}}\mid \Gamma ,A\Rightarrow \Delta }{{\mathcal {G}}\mid \Gamma ,\Box A\Rightarrow \Delta }}}

GRAMO∣◻Γ,Σ⇒◻Δ,ΠGRAMO∣◻Γ⇒◻Δ∣Σ⇒Π{\displaystyle {\frac {{\mathcal {G}}\mid \Box \Gamma ,\Sigma \Rightarrow \Box \Delta ,\Pi }{{\mathcal {G}}\mid \Box \Gamma \Rightarrow \Box \Delta \mid \Sigma \Rightarrow \Pi }}}

La admisibilidad de una versión adecuadamente formulada de la regla de corte puede demostrarse mediante un argumento sintáctico sobre la estructura de las derivaciones o demostrando la completitud del cálculo sin la regla de corte directamente utilizando la semántica de S5. En consonancia con la importancia de la lógica modal S5, se han formulado varios cálculos alternativos. [ 2 ] [ 3 ] [ 1 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] También se han propuesto cálculos hipersecuenciales para muchas otras lógicas modales. [ 6 ] [ 7 ] [ 8 ] [ 9 ]

Lógicas intermedias

Los cálculos hipersecuenciales basados ​​en secuencias intuicionistas o de un solo sucesor se han utilizado con éxito para capturar una gran clase de lógicas intermedias , es decir, extensiones de la lógica proposicional intuicionista . Dado que los hipersecuenciales en este contexto se basan en secuencias de un solo sucesor, tienen la siguiente forma:

Γ1⇒A1∣⋯∣Γnorte⇒Anorte{\displaystyle \Gamma _{1}\Rightarrow A_{1}\mid \dots \mid \Gamma _{n}\Rightarrow A_{n}}

La interpretación de fórmula estándar para tal hipersecuencia es

(⋀Γ1→A1)∨⋯∨(⋀Γnorte→Anorte){\displaystyle (\bigwedge \Gamma _{1}\to A_{1})\lor \dots \lor (\bigwedge \Gamma _{n}\to A_{n})}

La mayoría de los cálculos hipersecuenciales para lógicas intermedias incluyen las versiones de un solo sucesor de las reglas proposicionales dadas anteriormente y una selección de las reglas estructurales. Las características de una lógica intermedia particular se capturan principalmente mediante una serie de reglas estructurales adicionales . Por ejemplo, el cálculo estándar para lógica intermedia LC , a veces también llamado lógica de Gödel-Dummett, contiene además la llamada regla de comunicación: [ 1 ]

Γ1⇒Δ1∣⋯∣Γnorte⇒Δnorte∣Σ⇒AΩ1⇒Θ1∣⋯∣Ωmetro⇒Θmetro∣Π⇒BΓ1⇒Δ1∣⋯∣Γnorte⇒Δnorte∣Ω1⇒Θ1∣⋯∣Ωmetro⇒Θmetro∣Σ⇒B∣Π⇒A{\displaystyle {\frac {\Gamma _{1}\Rightarrow \Delta _{1}\mid \dots \mid \Gamma _{n}\Rightarrow \Delta _{n}\mid \Sigma \Rightarrow A\qquad \Omega _{1}\Rightarrow \Theta _{1}\mid \dots \mid \Omega _{m}\Rightarrow \Theta _{m}\mid \Pi \Rightarrow B}{\Gamma _{1}\Rightarrow \Delta _{1}\mid \dots \mid \Gamma _{n}\Rightarrow \Delta _{n}\mid \Omega _{1}\Rightarrow \Theta _{1}\mid \dots \mid \Omega _{m}\Rightarrow \Theta _{m}\mid \Sigma \Rightarrow B\mid \Pi \Rightarrow A}}}

Se han introducido cálculos hipersecuenciales para muchas otras lógicas intermedias, [ 1 ] [ 10 ] [ 11 ] [ 12 ] y existen resultados muy generales sobre la eliminación de cortes en dichos cálculos. [ 13 ]

Lógicas subestructurales

En cuanto a las lógicas intermedias, se han utilizado hipersecuentes para obtener cálculos analíticos para muchas lógicas subestructurales y lógicas difusas . [ 1 ] [ 13 ] [ 14 ]

Historia

La estructura hipersecuencial parece haber aparecido por primera vez en [ 2 ] bajo el nombre de cortege , para obtener un cálculo para la lógica modal S5 . Parece haber sido desarrollada independientemente en [ 3 ] también para tratar lógicas modales, y en el influyente [ 1 ] donde se consideran cálculos para lógicas modales, intermedias y subestructurales, y se introduce el término hipersecuencial.

Referencias

  1. 1 2 3 4 5 6 7 Avron, Arnon (1996). «El método de las hipersecuencias en la teoría de la demostración de lógicas no clásicas proposicionales». Lógica: De los fundamentos a las aplicaciones . págs. 1–32 . ISBN  978-0-19-853862-2.
  2. 1 2 Mints, Grigori (1971). "Sobre algunos cálculos de lógica modal". Proc. Steklov Inst. Of Mathematics . 98 : 97– 122.
  3. 1 2 Pottinger, Garrell (1983). "Formulaciones uniformes y sin cortes de T, S4 y S5 (resumen)". J. Symb. Log. 48 (3): 900.
  4. ↑ Poggiolesi, Francesca (2008). "Un cálculo de secuencias simples sin cortes para la lógica modal S5" (PDF) . Rev. Symb. Log. 1 : 3–15 . doi : 10.1017/S1755020308080040 . S2CID 37437016 . 
  5. ↑ Restall, Greg (2007). Dimitracopoulos, Costas; Newelski, Ludomir; Normann, Dag; Steel, John R (eds.). "Proofnets for S5: Sequents and circuits for modal logic". Logic Colloquium 2005. Lecture Notes in Logic. 28 : 151–172 . doi : 10.1017/CBO9780511546464.012 . hdl : 11343/31712 . ISBN 9780511546464.
  6. 1 2 Kurokawa, Hidenori (2014). "Cálculos hipersecuentes para lógicas modales que extienden S4". Nuevas fronteras en inteligencia artificial . Notas de clase en ciencias de la computación. Vol. 8417. pp. 51– 68. doi : 10.1007/978-3-319-10061-6_4 . ISBN   978-3-319-10060-9.
  7. 1 2 Lahav, Ori (2013). "De las propiedades de los marcos a las reglas hipersecuenciales en lógicas modales". 28.º Simposio Anual ACM-IEEE de Lógica en Ciencias de la Computación de 2013. pp. 408-417 . doi : 10.1109/LICS.2013.47 . ISBN  978-1-4799-0413-6. S2CID 221813 . 
  8. ↑ Indrzejczak, Andrzej (2015). "Eliminación del corte en cálculos hipersecuenciales para algunas lógicas modales de marcos lineales". Information Processing Letters . 115 (2): 75– 81. doi : 10.1016/j.ipl.2014.07.002 .
  9. ↑ Lellmann, Björn (2016). "Reglas hipersecuentes con contextos restringidos para lógicas modales proposicionales" . Theor. Comput. Sci. 656 : 76–105 . doi : 10.1016/j.tcs.2016.10.004 .
  10. ↑ Ciabattoni, Agata ; Ferrari, Mauro (2001). "Cálculos hipersecuentes para algunas lógicas intermedias con modelos de Kripke acotados". J. Log. Comput. 11 (2): 283– 294. doi : 10.1093/logcom/11.2.283 .
  11. ↑ Ciabattoni, Ágata ; Maffezioli, Paolo; Spendier, Lara (2013). Galmiche, Didier; Larchey-Wendling, Dominique (eds.). "Cálculos hipersecuentes y etiquetados para lógica intermedia". Cuadros 2013 : 81– 96.
  12. ↑ Baaz, Matthias; Ciabattoni, Agata ; Fermüller, Christian G. (2003). "Cálculos hipersecuentes para lógicas de Gödel: una revisión". J. Log. Comput . 13 (6): 835– 861. CiteSeerX 10.1.1.8.5319 . doi : 10.1093/logcom/13.6.835 . 
  13. 1 2 Ciabattoni, Agata ; Galatos, Nicolás; Terui, Kazushige (2008). "De los axiomas a las reglas analíticas en lógica no clásica". 2008 23º Simposio anual del IEEE sobre lógica en informática . págs. 229–240 . CiteSeerX 10.1.1.405.8176 . doi : 10.1109/LICS.2008.39 . ISBN   978-0-7695-3183-0. S2CID 7456109 . 
  14. ↑ Metcalfe, George; Olivetti, Nicola; Gabbay, Dov (2008). Teoría de la demostración para lógicas difusas . Springer, Berlín.
Lecturas relacionadas
6 articulos
Lógica matemáticaLógica matemáticaLa lógica matemática es el estudio de la lógica formal dentro de las matemáticas . Las subáreas principales incluyen la teoría de modelos , la teor...Estilo de visualización: Pi _{1}^{0}}Teoría de la pruebaLa teoría de pruebas es una rama importante [1] de la lógica matemática y la informática teórica dentro de la cual las pruebas se tratan como objet...{\estilo de visualización B}Cálculo secuencialEn lógica matemática , el cálculo consecuente es un estilo de argumentación lógica formal en el que cada línea de una prueba es una tautología cond...{\displaystyle A_{1},\dots ,A_{m}\vdash B_{1},\dots ,B_{n}}Teoría de la demostración estructuralEn lógica matemática , la teoría de la demostración estructural es la subdisciplina de la teoría de la demostración que estudia los cálculos de dem...Prueba analíticaPrueba analíticaEn matemáticas , una prueba analítica es una prueba de un teorema en análisis que solo hace uso de métodos de análisis, y que no hace uso predomina...{\displaystyle 120=2^{3}3^{1}5^{1},}Conjunto múltipleEn matemáticas , un multiconjunto (o bag , o mset ) es una modificación del concepto de conjunto que, a diferencia de un conjunto, [1] permite múlt...