La lógica lineal, Conectivas, la dualidad y la polaridad, Presentación cálculo secuencial, Fórmulas notables, Codificación de la lógica clásica/intuicionista en la lógica lineal, La interpretación de los recursos, Otros sistemas de demostración, Semántica, Decidibilidad/complejidad de vinculación, Variantes de la lógica lineal

La lógica lineal es una lógica sub-estructural propuesto por Jean-Yves Girard como un refinamiento de la lógica clásica y intuicionista, uniéndose a la dualidad de la antigua con muchas de las propiedades constructivas de este último. Aunque la lógica también se ha estudiado por su propio bien, en términos más generales, las ideas de la lógica lineal han sido influyentes en campos tales como los lenguajes de programación, la semántica del juego y la física cuántica, así como la lingüística, en particular debido a su énfasis en los recursos acotación , la dualidad, y la interacción.

La lógica lineal se presta a muchas presentaciones diferentes, explicaciones e intuiciones. Prueba-teóricamente, que se deriva de un análisis de cálculo secuencial clásica en la que utiliza de la contracción y debilitamiento se controla cuidadosamente. Operativamente, esto significa que la deducción lógica ya no se trata únicamente de una colección cada vez mayor de persistentes "verdades", sino también una forma de manipular los recursos que no siempre pueden ser duplicadas o se desechan a voluntad. En términos de modelos denotacional simples, la lógica lineal puede ser visto como el perfeccionamiento de la interpretación de la lógica intuicionista sustituyendo categorías cerradas cartesianas por categorías monoidales simétricas, o la interpretación de la lógica clásica mediante la sustitución de las álgebras booleanas de C *-álgebras.

Conectivas, la dualidad y la polaridad

Sintaxis

El lenguaje de la lógica lineal clásica se define inductivamente por la notación BNF

Aquí p yp? gama más átomos lógicos. Por razones que se explican a continuación, las conectivas?,?, 1, y? son llamados multiplicatives, los conectivos y,?,?, y 0 se denominan aditivos y las conectivas! y? se llaman exponenciales. Podemos emplear más la siguiente terminología:

  • ? se denomina "conjunto multiplicativo" o "tiempos"
  • ? se llama "aditivo disyunción" o "plus"
  • Y se llama "conjunción aditiva" o "por"
  • ? se llama "multiplicativo disyunción" o "par"
  • ! se pronuncia "por supuesto"
  • ? se pronuncia "por qué no"

Toda proposición A en la LLC tiene una doble A, que se define de la siguiente?:

Observe eso? es una involución, es decir, A = A para todas las proposiciones. Un? También se llama la negación lineal de A.

Las columnas de la tabla sugieren otra forma de clasificar las conectivas de la lógica lineal, denominado polaridad: los conectores negados en la columna de la izquierda se llama positivo, mientras que sus duales de la derecha se llama negativo.

Implicación lineal no está incluido en la gramática de conectivas, pero es definible en la CLL usando negación lineal y disyunción multiplicativo, por A? B: = A? ? B. La conectivo? a veces se pronuncia "lollipop", debido a su forma.

Presentación cálculo secuencial

Una manera de definir la lógica lineal es como un cálculo secuencial. Utilizamos las letras G y? para ir más lista de proposiciones A1, ..., An, también llamados contextos. A los lugares posteriores de un contexto a la izquierda ya la derecha del torniquete, escrito G?. Intuitivamente, la subsiguiente afirma que la conjunción de T implica la disyunción de?. Girard describe la lógica lineal clásica utilizando sólo secuentes de un solo lado, y nosotros seguimos aquí, que la presentación más económica.

Ahora nos damos reglas de inferencia que describen cómo construir pruebas de secuentes.

En primer lugar, para formalizar el hecho de que no importa el orden de las proposiciones dentro de un contexto, se añade la regla estructural de cambio:

 Tenga en cuenta que no añadimos las reglas estructurales de debilitamiento y la contracción, ya que nos preocupamos por la ausencia de propuestas en una subsiguiente, y el número de ejemplares presentes.

A continuación añadimos secuentes iniciales y los recortes:

La regla de corte puede ser visto como una forma de pruebas que componen, y secuentes iniciales sirven como las unidades para la composición. En cierto sentido, estas reglas son redundantes: a medida que introducimos reglas adicionales para la construcción de las pruebas siguientes, vamos a mantener la propiedad de que secuentes iniciales arbitrarias se pueden derivar de secuentes iniciales atómicas, y que cada vez que un subsiguiente es demostrable que se puede dar un punto de corte prueba libre. En última instancia, esta propiedad forma canónica se encuentra detrás de las aplicaciones de la lógica lineal en ciencias de la computación, ya que permite que la lógica que se utilizará en la prueba de búsqueda y como recurso-aware lambda-cálculo.

Ahora, explicamos las conectivas dando reglas lógicas. Normalmente, en cálculo secuencial se da tanto "derecho-reglas" y "izquierda-reglas" para cada conectivo, describiendo esencialmente dos modos de razonar acerca de las proposiciones que implican que conectivo. En una presentación de un solo lado, una vez hace uso de la negación: el derecho-reglas para un conectivo desempeñar eficazmente la función de la izquierda-reglas de su doble. Por lo tanto, debemos esperar una cierta "armonía" entre la norma para un conectivo y el Estado por su dual.

Multiplicatives

Las reglas para la combinación multiplicativa y la disyunción:

y para sus unidades:

Observe que las reglas para el conjunto multiplicativo y la disyunción son admisibles para la conjunción y la disyunción normal bajo una interpretación clásica.

Aditivos

Las reglas de combinación aditiva y la disyunción:

y para sus unidades:

Observe que las reglas de combinación aditiva y disyunción son más admisible en virtud de una interpretación clásica. Pero ahora podemos explicar la base para la multiplicación/aditivo distinción en las normas para las dos versiones diferentes de la relación: el conectivo multiplicativo, el contexto de la conclusión se divide entre los locales, mientras que para el caso de aditivos conectivo el contexto de la celebración se lleva todo en ambas premisas.

Exponenciales

Los exponentes se utilizan para dar acceso controlado a debilitamiento y la contracción. En concreto, le añadimos las reglas estructurales de debilitamiento y la contracción de 'd proposiciones?:

y utilizar las siguientes reglas lógicas:

Uno puede observar que las normas para las exponenciales siguen un patrón diferente de las reglas para los demás conectores, y que ya no hay una simetría tan clara entre los duales! y?. Esta situación se solucionó en presentaciones alternativas de CLL.

Fórmulas notables

Además de los Morgan dualidades De descritos anteriormente, algunas equivalencias importantes en la lógica lineal incluyen:

 Distributivity isomorfismo exponencial

Lo siguiente no es, en general, una equivalencia, sólo una implicación:

 Semi-distributiva

Codificación de la lógica clásica/intuicionista en la lógica lineal

Implicación Tanto intuicionista y clásica se puede recuperar de implicación lineal exponenciales inserción: implicación intuicionista se codifica como una? B, y la implicación clásica como! A? ¿B. La idea es que los exponenciales nos permiten utilizar una fórmula tantas veces como necesitemos, que siempre es posible en la lógica clásica y la intuicionista.

Formalmente, existe una traducción de las fórmulas de la lógica intuicionista a las fórmulas de la lógica lineal de una manera que garantiza que la fórmula original es demostrable en la lógica intuicionista si y sólo si la fórmula traducido es demostrable en la lógica lineal. Usando la traducción Gödel-Gentzen negativo, por lo tanto podemos integrar la lógica de primer orden clásico en la lógica lineal de primer orden.

La interpretación de los recursos

Lafont primero mostró cómo la lógica lineal intuicionista puede explicarse como una lógica de los recursos, por lo que siempre que el lenguaje lógico con acceso a formalismos que se pueden utilizar para razonar acerca de los recursos dentro de la propia lógica, en lugar de, como en la lógica clásica, por medio de la no predicados y las relaciones lógicas. Ejemplo clásico Antony Hoare 's de la máquina expendedora se puede utilizar para ilustrar esta idea.

Supongamos que representamos a una barra de chocolate de los caramelos proposición atómica, y un dólar en $ 1. Para indicar el hecho de que un dólar va a comprar una barra de chocolate, podríamos escribir la implicación de $ 1? caramelos. Pero en la lógica ordinaria, de A y A? B se puede concluir A? B. Por lo tanto, la lógica común nos lleva a pensar que podemos comprar la barra de chocolate y mantener nuestro dólar! Por supuesto, podemos evitar este problema mediante el uso de codificación más sofisticados, aunque normalmente estas codificaciones sufren el problema del marco. Sin embargo, el rechazo de debilitamiento y la contracción permite la lógica lineal de evitar este tipo de razonamiento falso, incluso con la regla de "ingenua". En lugar de $ 1? dulces, expresamos la propiedad de la máquina expendedora como una implicación lineal $ 1? caramelos. A partir de $ 1 y este hecho, podemos concluir dulces, pero no $ 1? caramelos. En general, podemos usar la lógica lineal propuesta de A? B para expresar la validez de la transformación de recursos Un recurso en B.

Correr con el ejemplo de la máquina expendedora, consideremos las "interpretaciones" de los recursos de la otra multiplicativo y aditivo conectivas.

Conjunción multiplicativa denota ocurrencia simultánea de los recursos, para ser utilizado como dirige el consumidor. Por ejemplo, si usted compra un chicle y una botella de refresco, entonces usted está solicitando chicle? beber. La constante de 1 denota la ausencia de cualquier recurso, y así funciona como la unidad de?.

Junto Aditivo representa ocurrencia alternativa de los recursos, la elección de los cuales controla el consumidor. Si en la máquina expendedora que hay un paquete de papas fritas, una barra de chocolate, y una lata de refresco, cada uno cuesta un dólar, luego de que el precio que usted puede comprar exactamente uno de estos productos. Así que escribimos $ 1?. No escribimos $ 1?, Lo que implicaría que uno es suficiente en dólares para la compra de los tres productos juntos. ¿Sin embargo, a partir de $ 1, podemos deducir correctamente 3 $, donde $ 3:? = $ 1? $ 1? $ 1. La unidad? de conjunción aditiva puede ser visto como una papelera de alternativas irrelevantes. Por ejemplo, podemos escribir $ 3? para expresar que tres dólares va a comprar una barra de chocolate y algo más.

Disyunción Aditivo representa ocurrencia alternativa de los recursos, la elección de los cuales controla la máquina. Por ejemplo, supongamos que la máquina expendedora de permisos de juego: insertar un dólar y la máquina puede prescindir de una barra de chocolate, un paquete de papas fritas, o un refresco. Podemos expresar esta situación sólo $ 1?. La constante de 0 representa un producto que no se puede hacer, y por lo tanto sirve como la unidad de? .

Disyunción multiplicativo es más difícil de pasar por alto en cuanto a la interpretación de los recursos, aunque podemos codificar de nuevo en la implicación lineal, ya sea como A? ? B o B? ? A.

Otros sistemas de demostración

Redes de prueba

Presentado por Jean-Yves Girard, neto prueba se han creado para evitar la burocracia, es decir todas las cosas que hacen que dos derivación diferente en el punto de vista lógico, pero no en un punto "moral" de vista.

Por ejemplo, estas dos pruebas son "moralmente" idéntico:

El objetivo de la red es la prueba para que sean idénticos mediante la creación de una representación gráfica de ellos.

Semántica

Semántica algebraica

Decidibilidad/complejidad de vinculación

La relación de vinculación en su totalidad CLL es indecidible. Fragmentos de CLL a menudo se consideran, por lo que el problema de decisión es más sutil:

  • Lógica lineal multiplicativo: sólo los conectivos multiplicativos. MLL vinculación es NP-completo.
  • Multiplicativo, aditivo lógica lineal: sólo multiplicatives y aditivos. Vinculación MALL es PSPACE-completo.
  • Lógica lineal-exponencial multiplicativo: solamente multiplicatives y exponenciales. La decidibilidad de MELL vinculación está actualmente abierto.

Variantes de la lógica lineal

Muchas variaciones de la lógica lineal surgen por más retoques con las reglas estructurales:

  • Lógica afín, que prohíbe la contracción, pero permite debilitamiento global.
  • Estricta lógica o de la lógica relevante, que prohíbe debilitamiento, sino que permite la contracción global.
  • La lógica no conmutativa o la lógica ordenada, lo que elimina la regla de intercambio, además de bloqueo de debilitamiento y la contracción. En la lógica ordenada, implicación lineal divide más a fondo en la izquierda implicación y derecha implicación.

Se han considerado diferentes variantes intuicionistas de la lógica lineal. Cuando en base a una sola conclusión-terior presentación cálculo, como en ILL, las conectivas?, ¿Y? están ausentes, y la implicación lineal es tratado como un conectivo primitiva. En FILL las conectivas?, ¿Y? están presentes, la implicación lineal es un conjuntivo primitivo y, de manera similar a lo que ocurre en la lógica intuicionista, todos los conectores son independientes. También hay de primera y de orden superior extensiones de la lógica lineal, cuyo desarrollo formal es algo estándar.