Lógica proposicional

Conceptos básicos

• Proposiciones atómicas o elementales: significados de enunciados (oraciones que son verdaderas o falsas) simples, enunciados cuya verdad o falsedad no puede analizarse en función de enunciados más simples que ellos. Por ejemplo:

  • Mañana lloverá y nevará no es una proposición atómica: podemos analizarla y decir que será verdadera si son verdaderas dos proposiciones más simples que aparecen en ella: una es Mañana lloverá y la otra es Mañana nevará. Y podemos analizar que será falsa si una cualquiera de esas dos proposiciones más simples es falsa. Mientras que será verdadera si las dos proposiciones más simples son verdaderas.

  • No lloverá mañana no es una proposición atómica: su verdad o falsedad dependen de una proposición más simple que ella: Lloverá mañana. Si ésta última proposición es verdadera, su negación será falsa. Y si fuese falsa, su negación será verdadera. Por tanto, No lloverá mañana depende de Lloverá mañana y por eso no es una proposición atómica.

  • Mañana lloverá sí es una proposición atómica: su verdad o falsedad sólo depende de un hecho: que mañana llueva. No hay una oración más sencilla de la que dependa la verdad o falsedad de Mañana lloverá.

• Conectivas lógicas: maneras de combinar la verdad o falsedad de proposiciones atómicas para calcular la verdad o falsedad de proposiciones complejas. Por ejemplo:

  • La conectiva conjunción sirve para calcular el valor de verdad (verdad o falsedad) de la proposición Mañana lloverá y nevará. Cuando Mañana lloverá es verdadera y Mañana nevará son ambas verdaderas la proposición conjunción de ambas es verdadera. En cambio, cuando cualquiera de las dos es falsa, la conjunción es falsa.

  • La conectiva disyunción permite calcular el valor de verdad de la proposición Mañana lloverá o nevará. Cuando Mañana lloverá es verdadera o bien Mañana nevará es verdadera. En cambio, cuando ambas son falsas, la disyunción es falsa.

  • La conectiva implicación permite expresar la relación entre dos proposiciones cuando la verdad de la primera nos permite afirmar la verdad de la segunda: si Juan llega pronto, entonces comerá helado.

  • La conectiva negación sirve para calcular el valor de verdad de la proposición No quiero café. Cuando Quiero café es verdadera, No quiero café es falsa y viceversa.

Símbolos de la lógica de proposiciones

Para escribir las fórmulas de la lógica de proposiciones, emplearemos los siguientes símbolos:

• Proposiciones atómicas: p, q, r, s, ...

• Conectivas entre proposiciones:

  • Negación: ¬

  • Conjunción: ∧

  • Disyunción: ∨

  • Implicación: →

  • Equivalencia: ↔

Definición formal de las conectivas lógicas

Anteriormente hemos presentado cada conectiva lógica (¬, ∧, ∨, →, ↔) relacionándola con determinadas expresiones de nuestra lengua ("no", "y", "o", "si...entonces", "equivale a"). Pero las expresiones de una lengua como el español no son siempre lo suficientementre precisas como para poder definir a partir de ellas otros conceptos que queremos que también sean muy precisos. Por ello, conviene definir las conectivas lógicas de manera más precisa.

Cada conectiva lógica puede definirse de forma precisa haciendo uso del concepto de función. En matemáticas, empleamos rutinariamente el concepto de función aplicado sobre números. Por ejemplo, la función elevar al cuadrado la escribimos así: y = x² o así: f(x) = x². Pero el concepto general de función va más allá de las funciones numéricas.

En general, una función es un tipo especial de relación entre los elementos de dos conjuntos (no necesariamente distintos). Cualesquiera dos conjuntos distintos, o entre los elementos de un mismo conjunto. Por ejemplo, podemos definir la relación "día siguiente" entre los elementos del conjunto de los días de la semana:

siguiente(lunes) = martes

siguiente(martes) = miércoles

...

siguiente(domingo) = lunes.

También podemos escribir la función y = siguiente(x) para todos los días de la semana en forma de tabla:

    x  |   y

    lunes | martes

      martes | miércoles

miércoles | jueves

    jueves | viernes

    sábado | domingo

 domingo | lunes

Podemos generalizar el concepto de función a funciones de más de un argumento. Por ejemplo, la función z = f(x,y) = x² + y² toma dos argumentos: x e y .

Otro ejemplo de función de dos argumentos es la suma de dos colores según se sugiere en esta imagen y que podemos representar mediante la siguiente tabla de doble entrada:

Funciones de verdad

Consideremos ahora el conjunto formado por dos conceptos abstractos: lo verdadero (V) y lo falso (F), es decir el conjunto {V, F}. Podemos definir de manera precisa las conectivas lógicas como funciones sobre este conjunto. Funciones que toman como argumentos valores de verdad y devuelven como resultado otro valor de verdad.

Negación

Podemos definir de forma precisa la operación de negación con una función que toma un único argumento. La función de verdad negación ( negación(A), o más breve ¬A ) sobre el conjunto {V, F} queda completamente definida con estas dos igualdades:

• ¬V = F

• ¬F = V

Según esta definición, y siendo A una variable que puede tomar como valores lo verdadero (V) o lo falso (F), podemos responder a estas dos preguntas:

1. ¿Cuándo es ¬A = V? Cuando A = F

2. ¿Cuándo es ¬A = F? Cuando A = V

Conjunción

Dado que la conjunción toma dos argumentos, su función toma dos argumentos y puesto que cada uno de ellos puede tomar uno de dos valores, son necesarias en total cuatro igualdades para que quede completamente definida:

• V ∧ V = V

• V ∧ F = F

• F ∧ V = F

• F ∧ F = F

A la vista de esta definición, y siendo A y B dos variables que pueden tomar como valores lo verdadero (V) o lo falso (F), podemos responder a estas dos preguntas:

1. ¿Cuándo es A ∧ B = V? Cuando A = V y B = V

2. ¿Cuándo es A ∧ B = F? Cuando A = F o bien B = F

Disyunción

También la disyunción toma dos argumentos y también son necesarias cuatro igualdades para que la operación quede formalmente definida:

• V ∨ V = V

• V ∨ F = V

• F ∨ V = V

• F ∨ F = F

A la vista de esta definición, podemos responder a estas dos preguntas:

1. ¿Cuándo es A ∨ B = V? Cuando A = V o bien B = V

2. ¿Cuándo es A ∨ B = F? Cuando A = F y B = F

Implicación lógica

Consideremos la siguiente proposición compleja o molecular: Si Pedro está en la fiesta, Juan también está en la fiesta. Es claro que la verdad o falsedad de esta proposición depende de sus dos proposiciones simples:

1. Pedro está en la fiesta

2. Juan está en la fiesta

Pero, ¿cómo es esa dependencia? Analicemos los cuatro casos posibles:

• Supongamos que Pedro está en la fiesta y que Juan también lo está. En ese caso la proposición Si Pedro está en la fiesta, Juan también está es verdadera, pues se ha producido la condición y también la consecuencia.

• Supongamos que Pedro está en la fiesta pero que Juan no lo está. En ese caso la proposición Si Pedro está en la fiesta, Juan también está es falsa. Esta situación es justamente la que no debe suceder si alguien afirma que si Pedro está, Juan también está, pues se ha producido la condición pero no la consecuencia.

• Supongamos que Pedro no está en la fiesta pero que Juan sí lo está. En ese caso la proposición Si Pedro está en la fiesta, Juan también está es verdadera. Quien afirma que "Si Pedro está, Juan también está", puede seguir manteniéndolo cuando Pedro no está pero Juan sí, pues esta consecuencia puede producirse por otros factores distintos a que Pedro esté en la fiesta. 

• Supongamos por último que Pedro no está en la fiesta y que Juan tampoco. En este caso la proposición Si Pedro está en la fiesta, Juan también está sigue siendo verdadera. Quien afirma que si Pedro está, Juan también está, puede seguir manteniéndolo cuando no están ninguno de los dos, pues a lo que él se compromete es a que si Pedro estuviera, entonces Juan también estaría.

En resumen, la implicación lógica (símbolo →) se define formalmente con las igualdades:

• V → V = V

• V → F = F

• F → V = V

• F → F = V

Aplicando esta definición, podemos responder a estas dos preguntas:

1. ¿Cuándo es A → B = V? Cuando ¬A = V o bien B = V. Simplificando, cuando  A = F o bien B = V

2. ¿Cuándo es A → B = F? Cuando A = V y B = F

Condiciones necesarias y condiciones suficientes

Mediante la conectiva implicación podemos formalizar los conceptos de condición necesaria y condición suficiente.

Afirmar que una proposición (A) es condición suficiente para otra proposición (B) es afirmar que si A sucede, entonces B sucederá también (es suficiente con que suceda A para que suceda B). Por tanto, que A es condición suficiente para B queda formalizado con la fórmula A → B puesto que esta fórmula sólo es falsa cuando A es verdadero y B es falso. O dicho de otro modo, si A sucede (es verdadera), B sucede (B es verdadera). Pero si A no sucede (es falsa), entonces B puede ser verdadera o falsa.

Afirmar que una proposición (A) es condición necesaria para que otra proposición (B) suceda es afirmar que si B sucede, entonces podemos inferir que A ha sucedido también (puesto que A es necesario para B). Por tanto, la formalización de que A es condición necesaria para B es B → A puesto que esta fórmula sólo es falsa cuando B es verdadero y A es falso. Pero esto es justamente lo que negamos al afirmar que A es condición necesaria para B: si B sucede, A debe haber sucedido también.

Equivalencia

Por último, la relación de equivalencia lógica entre dos proposiciones es verdadera cuando ambas proposiciones componentes coinciden en su valor de verdad. Es decir, si dos proposiciones son ambas verdaderas o ambas falsas, entonces son equivalentes: su equivalencia es verdadera. Por el contrario, si dos proposiciones difieren en sus valores de verdad (una es verdadera y la otra falsa), entonces la equivalencia entre ambas es falsa.

Las siguientes igualdades definen formalmente la conectiva de equivalencia:

• V ↔ V = V

• V ↔ F = F

• F ↔ V = F

• F ↔ F = V

Según esta definición, podemos responder a estas dos preguntas:

1. ¿Cuándo es A ↔ B = V? Cuando A y B tienen el mismo valor

2. ¿Cuándo es A ↔ B = F? Cuando A y B tienen distintos valores

Resumen de las definiciones de las conectivas proposicionales

Fórmulas de la lógica de proposiciones

Podemos construir fórmulas combinando los símbolos de proposiciones atómicas y los símbolos de conectivas,  ayudándonos si es necesario de paréntesis. No todas las combinaciones resultantes son fórmulas, sólo aquellas que cumplen las siguientes reglas:

• Un símbolo de proposición atómica (p, q, r, ...) es una fórmula (más exactamente, una fórmula atómica).

• Si A es una fórmula, ¬A es también una fórmula (una fórmula molecular).

• Si A y B son ambas fórmulas, A ∧ B, A ∨ B, A → B y A ↔ B son también fórmulas (moleculares).

Valor de verdad de una fórmula

Una proposición atómica es el significado de un enunciado simple. Y dado que los enunciados (a diferencia de las preguntas y las órdenes) pueden ser verdaderos o falsos, en lógica proposicional consideraremos que una proposición atómica puede ser verdadera o falsa. Dado que no sabemos de la mayoría de enunciados simples si son verdaderos o falsos, es razonable pensar en un símbolo de proposición atómica (p, q, r, ...) como en una variable que puede tomar uno de dos valores: lo verdadero (V) o lo falso (F). Por tanto, el valor de una fórmula atómica será siempre o bien V o bien F.

A partir de los valores que toman las proposiciones atómicas y empleando las definiciones dadas para las conectivas, podemos calcular el valor de verdad de fórmulas complejas.

Dada una fórmula cualquiera, si nos dan los valores de que tienen las proposiciones atómicas que aparecen en ella, sólo tenemos sustituir en la fórmula las variables por sus valores y calcular el resultado de las operaciones sobre estos valores.

Por ejemplo, consideremos las fórmulas: ¬p, ¬p ∨ q, p ∧ ¬q, ¬p → q  y por último ¬p ↔ ¬q.

• Si p = V y  q = V, entonces ¬p = F; ¬p ∨ q = V; p ∧ ¬q = F; ¬p → q = V; ¬q → p = F y ¬p ↔ ¬q = V

• Si p = V y  q = F, entonces ¬q = V; ¬p ∨ q = F; p ∧ ¬q = V; ¬p → q = V; ¬q → ¬p = F y ¬p ↔ q = V

También podemos deducir los valores de verdad que han de tomar las proposiciones atómicas a partir del valor de verdad de fórmulas complejas.

Dada una fórmula cualquiera A, podemos resolver las ecuaciones A = V o A = F hallando los valores que deben tomar las variables que aparecen en ella.

Ejemplos:

1. Si (p → q) = F, entonces p = V y q = F, pues estos dos valores son los únicos que producen F.

2. Pero si (p → q) = V, entonces hay varios valores posibles para p y q:

   • p = q = V

   • p = q = F

   • p = F y q = V

3. Si (¬p ∨ q) = F, entonces ¬p = F y q = F, y si ¬p = F, entonces p = V. En definitiva: q = F y p = V.

4. Si (p ∧ ¬q) = V, entonces p = V y ¬q = V, y si ¬q = V, entonces q = F. En definitiva: p = V y q = F.

Tautologías, contradicciones y contingencias

Al calcular el valor de verdad de una fórmula, es interesante notar que toda fórmula posible cae dentro de una y sólo una de las siguientes tres clases:

• Fórmulas contingentes o contingencias: son fórmulas que pueden ser verdaderas o falsas, dependiendo del valor de verdad de las proposiciones atómicas que haya en ellas. Por ejemplo, las fórmulas:

  • p ∨ p ; ¬p ; p → q son verdaderas o falsas según lo sean las fórmulas atómicas p y q.

  • Dicho de otro modo: una fórmula cualquiera A es contingente cuando podemos resolver las ecuaciones A = V y A = F.

• Fórmulas tautológicas o tautologías: son fórmulas que son siempre verdaderas, que nunca son falsas cualquiera que sea el valor de verdad de las proposiciones atómicas que haya en ellas. Por ejemplo, las fórmulas:

  • p ∨ ¬p ; p → p ; p → (q → p) son verdaderas tanto si p y q son verdaderas como si son falsas.

  • Dicho de otro modo: una fórmula cualquiera A es tautológica cuando no podemos resolver la ecuación A = F

• Fórmulas contradictorias o contradicciones: son fórmulas que son siempre falsas, que nunca son verdaderas cualquiera que sea el valor de verdad de las proposiciones atómicas que haya en ellas. Por ejemplo, las fórmulas:

  • p ∧ ¬p ; ¬(p → p) ; (p ∨ ¬p) → (q ∨ ¬q) son falsas tanto si p y q son verdaderas como si son falsas.

  • Dicho de otro modo: una fórmula cualquiera A es contradictoria cuando no podemos resolver la ecuación A = V.

Consecuencia lógica: ⊨

Existe relación de consecuencia lógica entre las premisas y la conclusión de un argumento cuando:

• Aceptando que las premisas (todas ellas) son verdaderas,

• La conclusión es necesariamente verdadera.

Dado un conjunto de fórmulas premisas {A1, A2, ... An} y una fórmula conclusión B, representamos que hay relación de consecuencia lógica entre unas y la otra con un símbolo específico:

{A1, A2, ... An} ⊨ B

Es importante notar varios puntos importantes en la definición de la relación de consecuencia lógica:

1. Afirmar que hay relación de consecuencia lógica no es afirmar que las premisas son verdaderas, ni tampoco que es verdadera la conclusión. Es afirmar que si las premisas son verdaderas, entonces la conclusión es necesariamente verdadera. Si por el contrario las premisas son falsas, la conclusión puede ser falsa o quizás verdadera.

2. Afirmar que la conclusión es necesariamente verdadera es afirmar que no puede ser falsa. Si aceptamos que las premisas son verdaderas, no es posible rechazar la verdad de la conclusión. Sólo podemos rechazar la conclusión si también rechazamos la verdad de alguna (o de todas) las premisas.

3. El conjunto de premisas puede ser el conjunto vacío.

4. Negar que hay relación de consecuencia lógica es afirmar que las premisas son verdaderas y que la conclusión puede ser falsa. Representamos la negación de la relación de consecuencia lógica empleando otro símbolo:

{A1, A2, ... An} ⊭ B

Tautologías, contradicciones y la relación de consecuencia lógica

Dado que una tautología es una fórmula siempre verdadera, siempre es la conclusión lógica de cualquier conjunto de premisas, incluido el conjunto vacío (Ø) de premisas. Es decir, si B es una tautología:

{A1, A2, ... An} ⊨ B, para cualquier {A1, A2, ... An}, n ≥ 0

Ø ⊨ B indica que B es una tautología 

Dado que una contradicción es una fórmula siempre falsa, nunca puede ser la conclusión lógica de un conjunto de premisas que pueda ser verdadero. Es decir, si B es una contradicción:

{A1, A2, ... An} ⊭ B, para cualquier {A1, A2, ... An} que pueda ser verdadero 

Ø ⊭ B

Por último, una fórmula contingente puede ser la conclusión lógica de algunos conjuntos de premisas pero no de otros, depende de qué fórmulas haya en ese conjunto. Es decir, si B es una contingencia:

{A1, A2, ... An} ⊨ B 

o bien

{A1, A2, ... An} ⊭ B

dependiendo de cuáles sean las fórmulas {A1, A2, ... An}.