miniaturadeimagen|295x295px|Intersección de dos conjuntos representada mediante un diagrama de Venn. La lógica algebraica es un área de la lógica matemática que estudia los sistemas lógicos mediante métodos y estructuras algebraicas. En un sentido clásico, la lógica algebraica analiza la lógica mediante ecuaciones, operaciones, relaciones, retículos y álgebras asociadas a sistemas deductivos. En un sentido contemporáneo más amplio, incluye tanto el estudio de clases particulares de álgebras vinculadas a lógicas específicas —como las álgebras booleanas, las álgebras de Heyting, las álgebras de relaciones, las álgebras cilíndricas, las álgebras poliadicas, las álgebras modales y las álgebras-MV— como la investigación general de los procesos mediante los cuales una lógica puede ser algebraizada.
En la lógica algebraica clásica, el interés se concentra en identificar y describir algebráicamente los modelos adecuados para estudiar distintas lógicas. En la lógica algebraica abstracta, en cambio, el objeto principal es el proceso mismo de algebraización, i.e. qué significa que una lógica tenga una semántica algebraica natural, qué clase de álgebras constituye su contraparte algebraica y cómo se relacionan las propiedades metalógicas del sistema con propiedades algebraicas de dicha clase.
Históricamente, la lógica algebraica nació en el siglo con los trabajos de George Boole, Augustus De Morgan, Charles Sanders Peirce y Ernst Schröder. Estos autores tomaron la equivalencia lógica, la inclusión de clases y las relaciones como objetos susceptibles de tratamiento algebraico. En contraste, la tradición de Gottlob Frege, Bertrand Russell y Alfred North Whitehead centró la lógica en la aserción, la inferencia, la verdad lógica y la cuantificación. La conexión precisa entre ambas perspectivas fue formulada posteriormente mediante el método de Lindenbaum-Tarski, que asocia a un sistema lógico una estructura algebraica obtenida al identificar entre sí las fórmulas lógicamente equivalentes.
Caracterización general La lógica algebraica puede describirse como el estudio de la lógica mediante estructuras algebraicas y ecuaciones. En vez de tratar una lógica únicamente como un cálculo de fórmulas, reglas y demostraciones, la lógica algebraica asocia a sus fórmulas una estructura en la que los conectivos se interpretan como operaciones y las relaciones de equivalencia, consecuencia o deducibilidad se traducen en congruencias, filtros, ideales, matrices o clases de álgebras.
En una presentación algebraica típica:
las variables se consideran tácitamente cuantificadas universalmente sobre un universo de discurso; los términos se construyen a partir de variables mediante operaciones primitivas o definidas; las fórmulas pueden identificarse si son equivalentes respecto del sistema lógico; las tautologías o teoremas pueden representarse algebraicamente como elementos distinguidos (e.g. el elemento superior de un álgebra booleana); las reglas de inferencia pueden estudiarse como propiedades de filtros, congruencias, homomorfismos o clases de modelos.
Una idea central es que las fórmulas de un lenguaje pueden verse como términos de un álgebra absolutamente libre. Los conectivos lógicos son entonces símbolos de operación, y las sustituciones corresponden a endomorfismos del álgebra de fórmulas. Si una relación de equivalencia lógica es una congruencia, se puede tomar el cociente del álgebra de fórmulas por dicha congruencia y obtener una estructura algebraica característica del sistema.
Cálculo de relaciones Una de las formas clásicas de lógica algebraica es el cálculo de relaciones. Una relación binaria homogénea sobre un conjunto es un subconjunto de . Una relación binaria heterogénea entre dos conjuntos e es un subconjunto de . Dado que una relación puede ser verdadera o falsa para cada par ordenado, las relaciones pueden estudiarse mediante operaciones booleanas.
Las operaciones básicas del cálculo de relaciones son: OperaciónNotación habitualInterpretaciónUniónpares que pertenecen a o a Intersecciónpares que pertenecen simultáneamente a y a Complementopares del universo que no pertenecen a Conversión o relación conversarelación que invierte el orden de los pares: si y solo si Composición relativa o si existe tal que y Relación identidadpares del universo Estas operaciones permiten estudiar relaciones mediante una aritmética booleana de matrices. Si una relación se representa por una matriz lógica, su relación conversa corresponde a la matriz transpuesta, y la composición de relaciones corresponde a una multiplicación matricial en la que la suma y el producto se interpretan de manera booleana.
A modo de ejemplo, considérese la erotética (o teoría lógica de las preguntas). En un universo de enunciados, puede distinguirse entre afirmaciones y preguntas . Se pueden definir dos relaciones de a :
, cuando es una respuesta directa a la pregunta ; , cuando es una presuposición de la pregunta .
La relación conversa va de a . La composición produce entonces una relación homogénea sobre . En términos filosóficos, este tipo de formalismo permite expresar la relación entre presuposiciones, preguntas y respuestas dentro de una estructura relacional.
Funciones como relaciones En el cálculo de relaciones, las funciones pueden caracterizarse como relaciones que satisfacen propiedades algebraicas. Sea una relación binaria y la relación identidad. La propiedad de univalencia puede expresarse mediante:
La propiedad de inyectividad corresponde a la univalencia de la relación conversa:
Una relación univalente es una función parcial. Para que sea una función total, debe satisfacer además la condición de totalidad:
Así, una aplicación o función total univalente puede caracterizarse mediante ecuaciones y desigualdades relacionales. Usando complementos, De Morgan y Schröder formularon propiedades equivalentes para relaciones univalentes y totales. Para una aplicación , una formulación característica es:
Gunther Schmidt llama a este principio "deslizarse bajo la negación desde la izquierda" (slipping below negation from the left); para una aplicación , puede escribirse:
Abstracción y álgebras de relaciones El cálculo de relaciones fue axiomatizado abstractamente por Alfred Tarski, quien introdujo las álgebras de relaciones como estructuras algebraicas que capturan operaciones fundamentales sobre relaciones binarias. El problema de representación consiste en determinar si toda álgebra que satisface los axiomas abstractos de las álgebras de relaciones puede representarse como un álgebra concreta de relaciones sobre un conjunto. Roger Lyndon mostró que la respuesta general es negativa, abriendo una línea de investigación sobre representabilidad y clases no representables.
Las álgebras de relaciones son consideradas una de las formas paradigmáticas de lógica algebraica. En ellas, las operaciones lógicas y relacionales se tratan como operaciones algebraicas sobre elementos abstractos, y los problemas lógicos se transforman en problemas de representación, axiomatización, completitud, dualidad y estructura algebraica.
Álgebras como modelos de lógicas La lógica algebraica trata estructuras algebraicas, con frecuencia retículos acotados o álgebras con operadores, como modelos o interpretaciones de sistemas lógicos. En este contexto, una lógica puede asociarse a una clase de álgebras, y las propiedades de la lógica pueden estudiarse mediante propiedades de esa clase.
La siguiente tabla recoge algunas correspondencias clásicas: Sistema lógico o matemáticoEstructura algebraica asociadaLógica proposicional clásicaÁlgebra de BooleLógica intuicionista proposicionalÁlgebra de HeytingLógica de ŁukasiewiczÁlgebra-MVLógica modal normalÁlgebra modalLógica modal S4 de LewisÁlgebra interior o álgebra de clausuraLógica modal S5 de Lewis; lógica monádica de primer ordenÁlgebra booleana monádicaLógica de primer ordenÁlgebra booleana completa, álgebra poliádica, lógica de functores predicativosLógica de primer orden con igualdadÁlgebra cilíndricaTeoría de conjuntosLógica combinatoria, álgebra de relaciones La idea general consiste en que, cuando dos fórmulas son equivalentes de acuerdo con una lógica, pueden identificarse algebraicamente. Si la equivalencia lógica es una congruencia respecto de los conectivos, el cociente del álgebra de fórmulas produce una estructura algebraica que refleja el comportamiento deductivo del sistema.
Método de Lindenbaum-Tarski El método de Lindenbaum-Tarski es una de las herramientas centrales de la lógica algebraica. Sea el álgebra de fórmulas de un lenguaje proposicional. En la lógica proposicional clásica, se define una relación de equivalencia entre fórmulas mediante:
Esta relación es una congruencia del álgebra de fórmulas. El cociente es el álgebra de Lindenbaum-Tarski de la lógica. En el caso de la lógica proposicional clásica, dicho cociente es un álgebra booleana libre. En el caso de la lógica intuicionista, el cociente produce un álgebra de Heyting.
De manera más general, si es una teoría, se puede definir:
El cociente se llama álgebra de Lindenbaum-Tarski determinada por . Para lógicas con implicación adecuada, la equivalencia puede definirse también por:
Jon Michael Dunn y Gary M. Hardegree describen este procedimiento como una manera de hacer visible una estructura algebraica más profunda que el simple álgebra sintáctica de las fórmulas. En una presentación logística, las fórmulas y son expresiones distintas; sin embargo, en el álgebra de Lindenbaum-Tarski de la lógica clásica pertenecen a la misma clase de equivalencia, porque expresan la misma proposición lógica en el sistema.
Matrices lógicas Otra herramienta fundamental de la lógica algebraica es la matriz lógica. Para un lenguaje lógico , una matriz lógica es un par ordenado:
donde es un álgebra del tipo de y es un conjunto de valores designados. Una fórmula es válida en la matriz si, para toda asignación , se tiene .
Una matriz es modelo de una lógica si para todo homomorfismo y para todo conjunto de premisas y fórmula :
En este caso, se llama filtro deductivo o -filtro de . Esta noción fue central en la tradición polaca de lógica y en el desarrollo posterior de la lógica algebraica abstracta.
Lógica algebraica abstracta La lógica algebraica abstracta (también llamada AAL, por abstract algebraic logic) es la teoría general de la algebraización de sistemas lógicos. En vez de estudiar solo las álgebras asociadas a una lógica concreta, busca criterios generales para determinar cuándo una clase de álgebras, matrices o modelos generalizados es la contraparte algebraica de una lógica.
Uno de sus objetivos centrales es clasificar los sistemas lógicos de acuerdo con propiedades algebraicas de sus modelos. Entre las nociones principales se encuentran:
las lógicas protoalgebraicas; las lógicas equivalenciales; las lógicas algebraizables; las lógicas débilmente algebraizables; la jerarquía de Leibniz; los operadores de Leibniz, Suszko y Tarski sobre filtros o teorías.
Una lógica se considera algebraizable cuando existe una traducción adecuada entre consecuencias lógicas y consecuencias ecuacionales que permite representar el sistema deductivo mediante una clase de álgebras. En estos casos, las propiedades metalógicas de la lógica pueden estudiarse a través de propiedades algebraicas de su semántica equivalente.
La lógica algebraica abstracta también permite formular teoremas puente, que conectan rasgos metalógicos con propiedades algebraicas. Por ejemplo, ciertos teoremas de interpolación se corresponden con propiedades de amalgamación; formas del teorema de la deducción se relacionan con congruencias principales definibles ecuacionalmente; y propiedades de definibilidad de Beth pueden corresponderse con la sobreyectividad de epimorfismos en clases algebraicas.
Álgebras cilíndricas