Fundamentos de la Lógica Proposicional

Fundamentos de la Lógica Proposicional

La lógica proposicional es una subdisciplina de la lógica matemática que estudia las proposiciones y su combinación a través de operadores lógicos. Se caracteriza por un alfabeto que incluye letras proposicionales (p, q, r, ...), símbolos para constantes lógicas (Verdadero, Falso), conectivas lógicas como la negación (¬), conjunción (∧), disyunción (∨), condicional (→), y bicondicional (↔), y símbolos auxiliares como los paréntesis para estructurar las expresiones. Las letras proposicionales simbolizan enunciados que pueden ser verdaderos o falsos, y las conectivas lógicas se utilizan para formar proposiciones más complejas. La semántica de estas conectivas se establece a través de tablas de verdad, que determinan el valor de verdad de las proposiciones compuestas basándose en todas las combinaciones posibles de los valores de verdad de sus componentes.

Tablas de Verdad y Satisfacibilidad

Las tablas de verdad son herramientas cruciales en la lógica proposicional, ya que proporcionan un método para evaluar el comportamiento de las fórmulas lógicas frente a todas las asignaciones de valores de verdad posibles. Una fórmula es una tautología si siempre es verdadera, independientemente de la interpretación de sus componentes, y es una contradicción si siempre es falsa. Las fórmulas que no son ni tautologías ni contradicciones se llaman contingentes. La satisfacibilidad se refiere a la existencia de al menos una interpretación en la que una fórmula o conjunto de fórmulas es verdadero. Un conjunto de fórmulas es satisfacible si hay al menos una interpretación que hace verdaderas a todas las fórmulas del conjunto; de lo contrario, se considera insatisfacible.

Validez y Consecuencia Lógica

Una fórmula es válida, o una tautología, si es verdadera en todas las interpretaciones posibles. La validez clasifica las fórmulas en insatisfacibles, satisfacibles y tautologías. Negar una fórmula insatisfacible produce una tautología, y negar una tautología resulta en una insatisfacibilidad. La consecuencia lógica es una relación entre un conjunto de premisas y una conclusión, donde la verdad de las premisas garantiza la verdad de la conclusión. Para determinar si una fórmula es consecuencia lógica de otras, se puede emplear una tabla de verdad para confirmar que, en todas las interpretaciones donde las premisas son verdaderas, la conclusión también lo es.

Equivalencias Lógicas y Formas Normales

Dos fórmulas son lógicamente equivalentes si comparten los mismos valores de verdad en todas las interpretaciones posibles, lo cual se denota como φ ≡ ψ. Esta relación de equivalencia es reflexiva, simétrica y transitiva. Las leyes lógicas, como las leyes de De Morgan y las distributivas, permiten transformar fórmulas en otras equivalentes. Las formas normales, como la forma normal disyuntiva (FND) y la forma normal conjuntiva (FNC), son representaciones estandarizadas de fórmulas que simplifican su análisis. Una fórmula en FND es una contradicción si cada disyunción contiene una variable y su negación, mientras que una fórmula en FNC es una tautología si cada conjunción contiene una variable y su negación.

Introducción a la Lógica de Predicados de Primer Orden

La lógica de predicados de primer orden amplía la lógica proposicional al incorporar cuantificadores y predicados, que expresan propiedades y relaciones entre objetos. Su alfabeto incluye variables, conectivas lógicas, cuantificadores universales (∀) y existenciales (∃), símbolos de puntuación, el símbolo de igualdad (=), constantes, funciones y predicados. Los predicados pueden ser monádicos (atributos de un solo objeto) o poliádicos (relaciones entre varios objetos). La semántica de la lógica de predicados requiere un universo de discurso y asignaciones que determinen la verdad de los predicados en dicho universo. Las interpretaciones deben ser suficientemente completas para evaluar la verdad de las expresiones en el contexto del universo de discurso.

Cuantificadores y su Semántica

Los cuantificadores son elementos esenciales en la lógica de predicados. El cuantificador universal (∀) indica que una propiedad se cumple para todos los elementos del universo de discurso, y el cuantificador existencial (∃) señala que la propiedad se cumple para al menos un elemento. Las variables dentro de una fórmula pueden ser libres o ligadas; una variable está ligada si se encuentra dentro del alcance de un cuantificador. La semántica de los cuantificadores se evalúa según si la propiedad expresada se verifica para todos o algunos elementos del universo. Por ejemplo, la fórmula ∀xPx es verdadera si todos los elementos del universo satisfacen la propiedad P, y es falsa si existe al menos uno que no la cumple.