Conceptos Fundamentales de Lógica Proposicional y de Predicados

Introducción a la Lógica

La lógica investiga la relación de consecuencia que se da entre una serie de premisas y la conclusión de un argumento correcto. Se dice que un argumento es correcto si su conclusión se sigue o es consecuencia de sus premisas.

Enunciados Declarativos

Son aquellos enunciados que podemos afirmar su verdad o falsedad. Se clasifican en:

• Enunciados de acción: Sujeto no determinado.
• Enunciados de atribución de propiedades a sujetos determinados.
• Enunciados de relación entre sujetos.

Consecuencia Lógica

Un enunciado es consecuencia lógica de un conjunto de premisas si y solo si (ssi), sean cuales sean las circunstancias concebibles, el enunciado es verdadero (V) siempre que las premisas sean verdaderas (V).

Partes de la Lógica

• Sintaxis: Estudia los sistemas formales, es decir, los lenguajes formales, los cálculos deductivos y las propiedades asociadas a ellas.
• Semántica: Estudia la asignación de significados a los formalismos.

Conectiva Principal

Se determina mediante la construcción del árbol de la fórmula.

Atribución Veritativa

Dada una forma enunciativa A, llamamos atribución veritativa a una asignación α de valores de verdad al conjunto {p1, p2, ..., pn} de variables enunciativas de A. Es decir, una atribución veritativa es una aplicación α: {p1, p2, ..., pn} → {V, F}.

Valoración

Dada una atribución veritativa α, una valoración es una función υ_α cuyo dominio es el conjunto de las formas enunciativas y cuyo rango es el conjunto {V, F}, tal que para cualesquiera formas enunciativas A y B:

1. υ_α(A) = α(A) si A es una variable enunciativa.
2. υ_α(¬A) = f¬(υ_α(A))...

Equivalencia Lógica

Dadas dos formas enunciativas, A y B, se dice que A y B son lógicamente equivalentes, denotado A ⇔ B, ssi para toda valoración υ, υ(A) = υ(B). Dadas dos formas enunciativas A y B, con funciones veritativas f_A y f_B asociadas, se dice que A y B son lógicamente equivalentes ssi f_A y f_B son la misma función de verdad.

Consecuencia Lógica

1. Dado el conjunto de formas enunciativas Γ = {A1, A2, ..., An} y la forma enunciativa A, A es consecuencia lógica del conjunto Γ ssi, para toda valoración υ, tal que υ(Ai) = V, para cada Ai ∈ Γ, entonces υ(A) = V.
2. Dado un conjunto de premisas y una conclusión Δ, se dice que Δ es consecuencia lógica ssi la tabla de verdad es una tautología.

Sistemas Formales

Sistema Formal S

• Vocabulario: Conjunto de símbolos y letras (infinito numerable).
• Reglas que establezcan qué cadenas de símbolos son fórmulas bien formadas (fbfs) en S.
• Conjunto de las definiciones utilizadas.
• Conjunto de fbfs de S que se usan como axiomas.
• Un conjunto finito de reglas de inferencia y reglas de construcción de una deducción en S.
• Las condiciones necesarias y suficientes que debe reunir una deducción para dar como resultado un teorema de S.
• Para usar axiomas adicionales de S, específicos.

Sistema Formal Axiomático L

1. Vocabulario: Conjunto de símbolos infinito numerable {¬, →, p1, ...}.
2. Conjunto de fbfs:
   • a) p1, p2, ... son fbfs.
   • b) Si A y B son fbfs, entonces (¬A) y (A→B) son fbfs.
   • c) El conjunto de todas las fbfs es el generado con a) y b).
3. Definiciones: (A^B) es abreviatura de (¬(A→(¬B))), ...
4. Axiomas: Las siguientes fbfs son axiomas de L:
   • (L1) (A→(B→A)).
   • (L2) ((A→(B→C))→((A→B)→(A→C))).
   • (L3) (((¬A)→(¬B))→(B→A)).
5. Reglas de inferencia: Solo hay Modus Ponens.

Deducción

Sea Γ un conjunto de fbfs de L. Una sucesión finita A1, A2, ..., An de fbfs de L, es una deducción a partir de Γ si para todo i ∈ {1, 2, ..., n} se cumple alguna de las siguientes condiciones:

1. Ai es un axioma de L.
2. Ai ∈ Γ.
3. Ai se infiere inmediatamente de dos miembros anteriores de la sucesión, digamos Aj y Ak (con j < k), mediante la regla de Modus Ponens.

Demostración: En L es una deducción en L sin premisas. Si la fbf A es el último miembro de una demostración, decimos que A es un teorema de L y escribimos |-_L A.

Teorema de la Deducción

Sean A y B fbfs de L y Γ un conjunto de fórmulas de L (puede ser vacío). Si Γ ∪ {A} |-_L B entonces Γ |-_L (A→B).

Lógica de Predicados

Designadores

Una o varias palabras que hacen referencia a objetos o individuos. Forman el sujeto de una oración. Los más usuales son los nombres.

Functores

Expresiones que, seguidas de un número determinado de designadores, forman a su vez un designador. Se relacionan con funciones: f, g, h, ...

Relatores

Unidos a un número determinado de designadores forman un enunciado. Serán los enunciados atómicos.

Término de £

Es una expresión, en la que intervienen variables, constantes y símbolos de función, que se define de acuerdo a las siguientes reglas:

1. Si t ∈ V ∪ C entonces t es un término. Esto es, toda variable o constante de £ es un término de £.
2. Si t1, t2, ..., tn son términos de £ y fⁿ es un símbolo de función n-ádico de £ entonces fⁿ(t1, t2, ..., tn) es un término de £.

Denotamos el conjunto de todos los términos con τ.

Fórmula Atómica

Si t1, t2, ..., tn son términos de £ y Rⁿ es un símbolo de relación n-ádico de £ entonces Rⁿ(t1, t2, ..., tn) es una fórmula atómica de £.

Fórmula Bien Formada

Una fórmula bien formada de £ es una expresión, en la que intervienen fórmulas atómicas, conectivas y/o cuantificadores, que puede formarse utilizando las siguientes reglas:

1. Toda fórmula atómica de £ es una fbf.
2. Si A y B son fbfs de £, también lo son: (¬A), (A^B), ...
3. Si A es una fbf de £ y x ∈ V entonces (Λx)A y (Vx)A son fbfs.

Interpretación

Una interpretación I de £ es un par (D_I, J) que consiste en:

1. Un conjunto no vacío D_I, el dominio de I.
2. Una aplicación J que asigna:
   • a) A cada símbolo de constante, ai, de £ un elemento distinguido de D_I; J(a_i) = ã_i.
   • b) A cada símbolo de función fⁿ_i n-ario de £ una función J(fⁿ_i) = fⁿ_i, tal que fⁿ_i : Dⁿ_I → D_I.
   • c) A cada símbolo de relación R_iⁿ n-ario de £ una relación J(R_iⁿ) = R_iⁿ, tal que R_iⁿ ⊆ Dⁿ_I; esto es, R_iⁿ = {(d1, ..., dn) | di ∈ D_I} es un conjunto de n-tuplas de Dⁿ_I.

Valoración en I

Una valoración υ en I es una aplicación que asigna a cada variable de £ un elemento x del dominio de la interpretación D_I.

υ : V → D_I

x → υ(x) = x

Una valoración también recibe el nombre de asignación.

Valoración x-equivalente

Sea x ∈ D_I, donde D_I es el dominio de una interpretación I y sea υ una valoración en I. La valoración υ^x_x tal que:

se dice que es una valoración x-equivalente de υ.

Valoración Extendida al Conjunto de Términos

Una valoración υ en I es una aplicación que asigna a cada término de I un elemento del dominio D_I, υ: τ → D_I

que definimos mediante las siguientes reglas:

donde υ es una valoración de V en D_I.

Satisfacibilidad

Sea una interpretación I = (D_I, J). Sea A una fbf de £. La valoración υ en I satisface la fbf A (denotado υ sat A) ssi se cumple que Eval_I,υ(A) = V.

Esto es, decimos que una valoración υ en I satisface la fbf A como resultado de su valoración en una interpretación, A toma el valor de verdad V. En caso contrario, cuando A toma el valor de verdad F, decimos que υ no satisface A.

Equivalencia Lógica

Dos fbfs A y B de £ son lógicamente equivalentes, denotado A ⇔ B, ssi para toda interpretación I y para toda valoración υ en I, υ sat A ssi υ sat B. Es decir, A y B fbfs de £ son lógicamente equivalentes ssi Eval_I,υ(A) = Eval_I,υ(B), cualesquiera que sean la interpretación I y la valoración υ en I utilizadas.

Verdad en I

1. Una fbf A es verdadera en I ssi toda valoración υ en I satisface A.
2. Una fbf es falsa en I ssi no existe valoración υ en I que satisfaga A.

Fórmula Lógicamente Válida

Sea A una fbf de £.

1. A es lógicamente válida ssi para toda interpretación I, A es verdadera en I.
2. A es insatisfacible ssi para toda interpretación I, A es falsa en I.
3. A es satisfacible ssi existe una interpretación I y una valoración en I tal que υ satisface A en I.

Modelo

Dada una fbf cerrada A de £, decimos que una interpretación I es modelo de A ssi la fbf A es verdadera en la interpretación I. Sea Γ un conjunto de fbfs cerradas de £, sea I una interpretación de £. I es modelo de Γ ssi I es modelo para cada una de las fórmulas de Γ.

Consecuencia Lógica

Sea Γ un conjunto de fbfs cerradas de £ y A una fbf cerrada de £. A es consecuencia lógica de Γ ssi, para toda interpretación I de £, si I es modelo de Γ entonces I es modelo de A. NOTACIÓN: Γ |= A.

Teorema de la Deducción Semántica

Sea un conjunto Γ = {A1, A2, ..., An} de fbfs cerradas de £ y B una fbf cerrada de £.

1. Γ |= B ssi |= (A1 Λ ... Λ An) → B.
2. Γ |= B ssi |= (A1 Λ ... Λ An Λ ¬B) esto es, la fbf es insatisfacible.
3. Γ |= B ssi Γ ∪ {¬B} es insatisfacible.

Independencia

Sea Γ un conjunto de fbfs de £. Una fbf A de £ es independiente de Γ ssi Γ no implica lógicamente A (Γ |= A). Sea Γ un conjunto de fbfs de £. Una fbf A de £ es independiente ssi para todo A ∈ Γ, A es independiente de Γ \ {A}.

Propiedades Formales de la Lógica de Enunciados

Teorema de Corrección

Sea A una fbf de L. Si A es un teorema de L (|-_LA) entonces A es una tautología.

Consistencia

Sea Γ un conjunto de fbfs.

1. Γ es inconsistente ssi cualquier fbf de L es deducible a partir de Γ.
2. Γ es consistente ssi no es inconsistente. Esto es, existe alguna fbf de L que no es deducible a partir de Γ.

Caracterización de la consistencia: Sea Γ un conjunto de fbfs. Γ es consistente ssi no existe una fbf A de L tal que Γ |-_LA y Γ |-_L¬A.

Teorema de Completitud

(Es el recíproco de la corrección): Sea A una fbf de L. Si A es una tautología entonces A es un teorema de L (|-_LA).

Indecidibilidad

Un sistema formal S es (recursivamente) indecidible ssi no existe ningún algoritmo que pueda responder a las preguntas de la clase: ¿Es A un teorema de S?, donde A es una fbf de S. En caso contrario, diremos que el sistema es decidible. (Un conjunto es decidible cuando existe un proceso mecánico para determinar cuáles son los elementos que le pertenecen y cuáles no).

Ley de Equivalencia

Sean A y B dos fbfs de L. A y B son demostrablemente equivalentes ssi A↔B es un teorema de L.

Propiedades de la lógica de enunciados: El sistema formal L es correcto, consistente, completo y decidible. (La corrección y completitud de L establecen la equivalencia entre sintaxis y semántica).

Propiedades Formales de la Lógica de Predicados

La verdad lógica de la lógica de predicados se corresponde con la tautología en la lógica proposicional.

Teorema de Corrección

Sea A una fbf de £. Si |-_KLA entonces |=A.

Esto es, para probar la corrección de un sistema KL, debemos comprobar que todo teorema de KL es una fórmula lógicamente válida.

Consistencia

Si se cumple el teorema de corrección, el sistema KL es consistente.

Teorema de Completitud

Sea A una fbf de £. Si |=A entonces |-_KLA.

Indecidibilidad

Un sistema de primer orden S es (recursivamente) indecidible... (igual que en enunciados).

Propiedades de la lógica de predicados: El sistema formal KL es correcto, consistente, completo y es indecidible por norma general, pero hay fragmentos que pueden probarse decidibles, entonces podemos decir que es semidecidible. (La indecidibilidad impide la completa automatización de la lógica de predicados).

Otros Conceptos

Evaluación de una Fórmula

Sean A una fbf de £, I = (DI, J) una interpretación y ν una valoración en I. Eval_I,v es una aplicación de fbfs a valores de verdad que se define inductivamente como:

1. Si A ≡ Rⁿ(t1, ..., tn) (esto es, A es una fórmula atómica) entonces: Eval_I,v ssi (ν(t1), ..., ν(tn)) ∈ Rⁿ, donde Rⁿ = J(Rⁿ) es una relación en Dⁿ_I.
2. Si A es de la forma:
   • a) ¬B entonces Eval_I,v(A) = f_¬(Eval_I,v(B)).
   • b) (B ^ C) entonces Eval_I,v(A) = f_Λ(Eval_I,v(B), Eval_I,v(C)).
3. Si A ≡ (Λx)B entonces Eval_I,v(A) = V ssi para TODA valoración x-equivalente de ν, Eval_I,v(B) = V.
4. Si A ≡ (∃x)B entonces Eval_I,v(A) = V ssi para ALGUNA valoración x-equivalente de ν, Eval_I,v(B) = V.

Enunciado Analítico

Es aquel que en cualquier situación concebible es verdadero. Esto es, ssi no puede ser falso. Forma A ∨ ¬A.

Enunciados Sintéticos

Son aquellos que solo son verdaderos para el mundo actual (o para uno de los mundos posibles).

Forma Enunciativa

Es una expresión, en la que intervienen variables de enunciado y símbolos de conectiva, que puede formarse utilizando las siguientes reglas:

1. Toda letra enunciativa p, q, r, ... es una forma enunciativa.
2. Si A y B son formas enunciativas bien construidas, también son formas enunciativas: (¬A), (¬B), (A→B), ...
3. Solo son formas enunciativas bien construidas las que cumplen 1 y 2.

Conjunto Adecuado de Conectivas

Es un conjunto tal que toda función veritativa puede representarse por medio de una forma enunciativa en la que solo intervienen conectivas de ese conjunto.

• Barra de Sheffer (A es incompatible con B): A | B ⇔ ¬(A^B).
• Barra de Pierce (negación de la disyunción): A ↓ B ⇔ ¬(A ∨ B).