Sintaxis y Semántica en Lógica Formal

Sintaxis

Un lenguaje formal en lógica puede definirse sin referencia a ninguna interpretación, es decir, de modo puramente sintáctico. Esto implica especificar un alfabeto del lenguaje (el conjunto de símbolos permitidos) y un conjunto de reglas de formación para construir secuencias de símbolos llamadas fórmulas bien formadas (FBFs). La sintaxis se completa al añadir un mecanismo deductivo (un conjunto de axiomas y/o reglas de inferencia) que permita transformar o derivar unas FBFs a partir de otras. De este modo, podemos establecer, por ejemplo, un sistema formal basado en un alfabeto, reglas de formación y reglas de inferencia.

Semántica

Podemos dar una interpretación semántica al lenguaje formal descrito anteriormente. La semántica asigna significado a los símbolos y establece las condiciones bajo las cuales las FBFs son verdaderas o falsas. Así, el lenguaje de la lógica proposicional es un lenguaje formal cuyos elementos (letras proposicionales, conectivas) son, sintácticamente, meros símbolos sin significado intrínseco hasta que se les asigna una semántica (mediante asignaciones de verdad y tablas de verdad para las conectivas).

Fórmulas Bien Formadas (FBFs) y Conceptos Relacionados

Definición y Reglas de Formación

Las Fórmulas Bien Formadas (FBFs) son las combinaciones de símbolos admisibles según las reglas de formación de un lenguaje formal. Las reglas de formación definen recursivamente cómo construir FBFs. Por ejemplo, en lógica proposicional:

• Una letra proposicional (p, q, r…) es una FBF.
• Si A es una FBF, entonces ¬A (negación de A) es una FBF.
• Si A y B son FBFs, entonces (A ∧ B), (A ∨ B), (A → B), (A ↔ B) son FBFs (conjunción, disyunción, condicional, bicondicional).

Estas reglas permiten comprobar si una secuencia de símbolos constituye una FBF válida.

Alcance de una Conectiva

El alcance de una ocurrencia de una conectiva en una FBF es la subfórmula (o subfórmulas) más pequeña(s) sobre la(s) que actúa directamente esa conectiva.

Subordinación y Conectiva Principal

Una conectiva está subordinada a otra en una FBF si el alcance de la primera está contenido propiamente en el alcance de la segunda. La conectiva principal de una FBF compuesta es aquella que no está subordinada a ninguna otra; es la última conectiva que se aplicaría al evaluar la fórmula.

Subfórmula

Son subfórmulas de una FBF A todas aquellas FBFs que son parte de A (incluida la propia A). Formalmente, A es subfórmula de A; si ¬B es subfórmula, B también lo es; si (B ∘ C) es subfórmula (donde ∘ es una conectiva binaria), B y C también lo son.

Condicional, Implicación y Equivalencia

Es importante distinguir entre conectivas (objetos del lenguaje) y relaciones metalógicas:

• Condicional (→): Es una conectiva lógica que forma una nueva FBF (A → B) a partir de dos FBFs (A y B). Su verdad se define mediante una tabla de verdad (es falsa solo si A es verdadera y B es falsa).
• Implicación Semántica (Consecuencia Lógica, ╞): Es una relación metalógica entre un conjunto de premisas (Γ) y una conclusión (A). Γ ╞ A significa que no hay ninguna interpretación que haga verdaderas a todas las fórmulas en Γ y falsa a A. Una conclusión es consecuencia lógica de (o es implicada por) las premisas cuando, en todas las interpretaciones en que estas son verdaderas, también lo es la conclusión.
• Bicondicional (↔): Es una conectiva lógica (A ↔ B).
• Equivalencia Lógica (╞═ o ≡): Es una relación metalógica. A y B son lógicamente equivalentes si tienen la misma tabla de verdad, o equivalentemente, si A ╞ B y B ╞ A.

Afirmar que las premisas implican la conclusión (Γ ╞ A) es afirmar la validez semántica del argumento correspondiente. Identificar directamente el bicondicional (↔) con la noción de equivalencia lógica (╞═) o el condicional (→) con la implicación semántica (╞) puede llevar a confusiones (paradojas de la implicación material) si no se matiza la diferencia entre lenguaje objeto y metalenguaje.

Sin embargo, estas nociones están estrechamente relacionadas en la lógica clásica: A implica semánticamente a B (A ╞ B) si y solo si el condicional A → B es una tautología (es decir, es lógicamente válido: ╞ A → B). Por tanto, puede decirse que la implicación semántica se corresponde con la validez del condicional material. Similarmente, A ╞═ B si y solo si ╞ A ↔ B.

Lógica Clásica y Lógicas No Clásicas

La lógica clásica (proposicional y de primer orden) se basa en principios fundamentales como:

• Principio de Bivalencia: Toda proposición es o verdadera o falsa, sin valores intermedios.
• Principio de No Contradicción: Una proposición no puede ser verdadera y falsa a la vez.
• Principio del Tercero Excluido: Toda proposición es o verdadera o falsa (A ∨ ¬A es una ley lógica).

Las lógicas no-clásicas surgen al modificar o rechazar alguno de estos principios u otros aspectos de la lógica clásica. Se pueden clasificar en:

• Lógicas extendidas: Conservan todas las leyes y teoremas de la lógica clásica pero añaden nuevos operadores lógicos (y sus axiomas/reglas) para tratar conceptos como la modalidad (necesidad, posibilidad – lógica modal), el tiempo (lógica temporal), la obligación (lógica deóntica), el conocimiento (lógica epistémica), etc.
• Lógicas alternativas (o divergentes): Modifican o rechazan algunas leyes o principios de la lógica clásica. Usan a menudo la misma simbología básica pero con una semántica o un sistema deductivo diferente. Ejemplos incluyen:
  • Lógica multivalente: Admite más de dos valores de verdad (ej., verdadero, falso, indeterminado).
  • Lógica intuicionista: Rechaza el principio del tercero excluido y la eliminación de la doble negación (¬¬A → A) basándose en una filosofía constructivista de la matemática.
  • Lógica de la relevancia: Exige que exista una conexión de significado relevante entre las premisas y la conclusión de una implicación válida.

Sistemas Formales Axiomáticos

Los primeros sistemas formales de lógica desarrollados rigurosamente fueron axiomáticos. El sistema de Gottlob Frege en su *Begriffsschrift* (1879) fue pionero, aunque fueron Bertrand Russell y Alfred North Whitehead, con sus *Principia Mathematica* (1910-1913), quienes lograron una amplia difusión e influencia de la lógica formal moderna.

Los sistemas axiomáticos dominaron el desarrollo de la lógica formal hasta la aparición de métodos alternativos como el cálculo de deducción natural (Gerhard Gentzen, 1934) y el cálculo de secuentes (Gentzen, 1934), que ofrecían procedimientos deductivos a menudo considerados más intuitivos o cercanos al razonamiento matemático ordinario.

No obstante, el enfoque axiomático sigue siendo fundamental, especialmente para el desarrollo teórico, el estudio de nuevos sistemas lógicos y la búsqueda de fundamentos elegantes y simplificados.

Un sistema axiomático para una lógica consta típicamente de:

• Un lenguaje formal (alfabeto y reglas de formación de FBFs).
• Un conjunto de FBFs seleccionadas como axiomas (o esquemas de axiomas), que se aceptan como verdaderos o derivables sin prueba dentro del sistema.
• Un conjunto reducido de reglas de inferencia (como el Modus Ponens: de A y A → B, inferir B), que permiten derivar nuevas FBFs (llamadas teoremas) a partir de los axiomas y/o teoremas previamente derivados.

Existen muchos sistemas axiomáticos alternativos (pero equivalentes en poder deductivo) para la lógica proposicional clásica. Un ejemplo es el sistema propuesto por Alonzo Church, que utiliza solo la regla de inferencia Modus Ponens (MP) y axiomas que involucran únicamente las conectivas de negación (¬) y condicional (→).

Propiedades de los Sistemas Formales: Corrección, Adecuación, Completitud y Decidibilidad

Estas son propiedades metalógicas cruciales que relacionan la sintaxis (derivabilidad, ├) y la semántica (consecuencia lógica, ╞) de un sistema formal.

Corrección (Solidez)

La Corrección (o Solidez) de un sistema deductivo establece que todo lo derivable sintácticamente es también una consecuencia semántica: si Γ ├ A, entonces Γ ╞ A. Es decir, el sistema deductivo no permite derivar conclusiones falsas a partir de premisas verdaderas; solo deriva verdades semánticas.

Para el método de los árboles semánticos (tableaux), la corrección se formula así: si el árbol para el conjunto {Γ, ¬A} (premisas y negación de la conclusión) se cierra completamente, entonces Γ implica semánticamente A (Γ ╞ A). Esto equivale a decir: si {Γ, ¬A} es semánticamente insatisfacible, entonces su árbol se cierra.

Por contraposición, la corrección también implica: si un árbol para {Γ, ¬A} termina y queda abierto, entonces el conjunto {Γ, ¬A} es semánticamente satisfacible. La prueba de corrección demuestra que si la lista inicial de fórmulas es satisfacible, no puede generar un árbol cerrado.

Prueba de Corrección para Árboles (Esbozo)

Se basa en el Lema de Adecuación de las Reglas: Si la fórmula a la que se aplica una regla de árbol es verdadera bajo una interpretación I, entonces, en al menos una de las ramas generadas por la regla, todas las fórmulas resultantes también son verdaderas bajo I.

Hipótesis: Supongamos que la lista inicial de fórmulas {Γ, ¬A} es simultáneamente satisfacible bajo una interpretación I.

Estrategia (Inducción): Demostrar que, en cada paso de la construcción del árbol, existe al menos una rama tal que todas sus fórmulas son verdaderas bajo I.

• Base: La lista inicial forma la rama inicial, y es verdadera bajo I por hipótesis.
• Paso Inductivo: Si existe una rama R verdadera bajo I antes de aplicar una regla, se usa el Lema de Adecuación para mostrar que después de aplicar la regla (ya sea a una fórmula en R o en otra rama), sigue existiendo al menos una rama (posiblemente una extensión de R, o la propia R si la regla se aplicó fuera de ella) que es verdadera bajo I.

Conclusión: Si la lista inicial es satisfacible bajo I, entonces el árbol terminado debe contener al menos una rama donde todas las fórmulas son verdaderas bajo I. Tal rama no puede estar cerrada (no puede contener B y ¬B, pues ambas no pueden ser verdaderas bajo I). Por lo tanto, el árbol tendrá al menos una rama abierta. Esto demuestra la Corrección: si el árbol se cierra, la lista inicial debe ser insatisfacible.

Completitud

La Completitud establece la conversa de la corrección: si algo es una consecuencia semántica, entonces es derivable sintácticamente: si Γ ╞ A, entonces Γ ├ A. Es decir, el sistema deductivo es lo suficientemente potente como para derivar todas las verdades semánticas.

Para los árboles semánticos, la completitud significa: si Γ implica semánticamente A (Γ ╞ A), entonces el árbol para {Γ, ¬A} se cierra. Esto equivale a: si {Γ, ¬A} es semánticamente insatisfacible, entonces su árbol asociado se cierra.

Por contraposición, la completitud también implica: si el árbol para {Γ, ¬A} termina y queda abierto, entonces el conjunto {Γ, ¬A} es semánticamente satisfacible. La prueba de completitud (Metateorema de Completitud para Árboles) se centra en demostrar esto último.

Prueba de Completitud para Árboles (Esbozo)

Hipótesis: Supongamos que un árbol terminado para {Γ, ¬A} contiene una rama abierta R.

Estrategia: Construir una interpretación I a partir de la información contenida en la rama abierta R, y demostrar que I satisface todas las fórmulas de la lista inicial {Γ, ¬A}.

Construcción de la Interpretación I:

• Para cada letra proposicional p: si p aparece como fórmula (literal positivo) en la rama abierta R, asignamos I(p) = Verdadero.
• Si ¬p aparece como fórmula (literal negativo) en la rama abierta R, asignamos I(p) = Falso.
• (Se asume que para toda p relevante, o p o ¬p está en la rama terminada R, o se asigna un valor por defecto si no aparece). Como R es abierta, no contiene pares contradictorios p y ¬p.

Prueba (Inducción sobre la complejidad de las fórmulas en R): Se demuestra que, bajo esta interpretación I, todas las fórmulas presentes en la rama abierta R son verdaderas.

• Caso Base: Los literales en R son verdaderos por definición de I.
• Paso Inductivo: Se muestra que si una fórmula compleja L está en R, y las fórmulas resultantes de aplicar la regla a L (que también deben estar en R, ya que la rama está terminada y abierta) son verdaderas bajo I (por hipótesis inductiva), entonces L también debe ser verdadera bajo I. Esto se verifica para cada regla de árbol.

Conclusión: Dado que todas las fórmulas en la rama abierta R son verdaderas bajo la interpretación I construida, en particular, las fórmulas de la lista inicial {Γ, ¬A} que pertenecen a R también son verdaderas bajo I. Por lo tanto, la lista inicial es satisfacible. Esto prueba la Completitud (en su forma contrapositiva).

Decidibilidad

Un sistema formal (o un problema lógico, como la validez o la satisfacibilidad) es decidible si existe un algoritmo (un procedimiento efectivo y mecánico) que pueda determinar, en un número finito de pasos, para cualquier entrada válida (ej., una fórmula, un argumento), si la propiedad en cuestión se cumple o no (ej., si la fórmula es una tautología, si el argumento es válido).

El método de los árboles semánticos proporciona un procedimiento de decisión para la lógica proposicional clásica. Si la lista inicial de fórmulas es finita:

• El árbol comienza con un número finito de FBFs, cada una con longitud finita.
• Cada aplicación de una regla de árbol descompone una fórmula compleja en fórmulas estrictamente más simples (en términos de conectivas o estructura).
• Como las fórmulas se descomponen y no se introducen nuevas complejidades, el proceso debe terminar. Cada rama eventualmente contendrá solo literales o se habrá cerrado.
• Dado que el número de subfórmulas distintas de las fórmulas iniciales es finito, y cada regla se aplica a lo sumo un número limitado de veces a cada fórmula no literal en cada rama, el árbol completo tiene una profundidad y anchura finitas.

Por lo tanto, el procedimiento de construcción del árbol siempre termina en un número finito de pasos, proporcionando una respuesta definitiva (árbol cerrado = insatisfacible/válido; árbol abierto = satisfacible/inválido). Esto demuestra la decidibilidad de la lógica proposicional clásica mediante este método.

Completitud Funcional y Adecuación de Conectivas

Completitud Funcional

Un conjunto de conectivas lógicas es funcionalmente completo (o adecuado) si cualquier función de verdad posible (es decir, cualquier tabla de verdad concebible con un número finito de entradas) puede ser representada por una fórmula que utilice únicamente conectivas de ese conjunto.

Forma Normal Disyuntiva (FND)

El conjunto {¬, ∧, ∨} (negación, conjunción, disyunción) es funcionalmente completo. Una forma estándar de demostrarlo es mostrando que toda función de verdad puede expresarse mediante una fórmula en Forma Normal Disyuntiva (FND). Una FND es una disyunción de una o más conjunciones de literales (letras proposicionales o sus negaciones).

Dada una función de verdad con n argumentos (variables proposicionales), su tabla de verdad tendrá 2ⁿ filas. Consideramos las filas donde la función da como resultado Verdadero (V):

• Caso 1: No hay filas V (la función es una contradicción). Se puede representar por una contradicción simple, como p ∧ ¬p (que usa ¬ y ∧).
• Caso 2: Hay una o más filas V. Para cada fila i donde la función es V, se construye una conjunción C_i que contiene cada variable p_j si p_j es V en esa fila, o ¬p_j si p_j es F en esa fila. La FND equivalente a la función de verdad es la disyunción de todas estas conjunciones: C₁ ∨ C₂ ∨ … ∨ C_k.

Dado que cualquier función de verdad puede ser representada usando solo ¬, ∧, ∨ (a través de su FND), este conjunto es funcionalmente completo.

Otros Conjuntos Adecuados de Conectivas

Una vez establecido que {¬, ∧, ∨} es funcionalmente completo, podemos demostrar la completitud de otros conjuntos mostrando que podemos definir ¬, ∧, y ∨ (o un subconjunto ya conocido como adecuado, como {¬, ∧} o {¬, ∨}) usando solo las conectivas del nuevo conjunto. Esto se hace encontrando equivalencias lógicas:

• {¬, →} (Negación y Condicional): Es adecuado porque podemos definir ∧ y ∨:
  A ∧ B ╞═ ¬(A → ¬B)
  A ∨ B ╞═ (¬A → B)
• {¬, ∨} (Negación y Disyunción): Es adecuado porque podemos definir ∧:
  A ∧ B ╞═ ¬(¬A ∨ ¬B) (Ley de De Morgan)
• {¬, ∧} (Negación y Conjunción): Es adecuado porque podemos definir ∨:
  A ∨ B ╞═ ¬(¬A ∧ ¬B) (Ley de De Morgan)
• {↑} (NOR o Flecha de Peirce – “ni A ni B”): Es adecuado por sí solo porque podemos definir ¬ y ∨:
  ¬A ╞═ (A ↑ A)
  A ∨ B ╞═ (A ↑ B) ↑ (A ↑ B) (o también ((A ↑ A) ↑ (B ↑ B)))
• {↓} (NAND o Barra de Sheffer – “no ambos A y B”): Es adecuado por sí solo porque podemos definir ¬ y ∧:
  ¬A ╞═ (A ↓ A)
  A ∧ B ╞═ (A ↓ B) ↓ (A ↓ B) (o también ((A ↓ A) ↓ (B ↓ B)))

Conectivas Diádicas Adecuadas por Sí Solas

Se puede demostrar que las únicas conectivas binarias (diádicas) que son funcionalmente completas por sí solas son la Flecha de Peirce (NOR, ↑) y la Barra de Sheffer (NAND, ↓). Una parte clave de la prueba implica mostrar que cualquier conectiva ‘⊗’ adecuada por sí sola debe ser capaz de expresar la negación, típicamente a través de la fórmula A ⊗ A.

Si ¬A ╞═ A ⊗ A, entonces la tabla de verdad de A ⊗ A debe coincidir con la de ¬A:

A | ¬A | A ⊗ A
--|----|-------
V | F  |   F
F | V  |   V

Esto impone condiciones sobre la tabla de verdad de A ⊗ B:

A | B | A ⊗ B
--|---|-------
V | V |   F     (De V ⊗ V ╞═ F)
V | F |   ?
F | V |   ?
F | F |   V     (De F ⊗ F ╞═ V)

Además, la conectiva debe ser capaz de generar tanto salidas V como F en las filas intermedias para poder expresar todas las funciones de verdad. Un análisis más completo (usando, por ejemplo, el criterio de Post) confirma que solo ↑ y ↓ satisfacen todas las condiciones necesarias para la completitud funcional individual.