Un enunciado es satisfacible cuando existe al menos una interpretación de dicho enunciado que lo hace verdadero.
En el apartado anterior veíamos un par de ejemplos que mostraban lo bien que funciona el método de la reducción al absurdo para detectar si un enunciado es o no tautológico. En esta sección veremos cómo este método también puede llevarnos a la conclusión de que no estamos ante una tautología. Y también veremos cómo emplear el método de reduccióna al absurdo para determinar si una fórmula es satisfacible.
La reducción al absurdo para descubrir tautologías
Nos serviremos de este enunciado: (¬p∧q)∨(p∧¬q) , para aplicarle el método de la reducción al absurdo con el fin de averiguar si es o no una tautología.
Construiremos una tabla que nos ayude a llevar adelante todo el proceso, con tantas celdillas como proposiciones y conectivas tenga la fórmula objeto de análisis:
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
A continuación suponemos lo contrario de lo que queremos demostrar, esto es, suponemos que la conectiva principal (la disyunción, en este caso) es falsa:
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| F |
Para que la disyunción sea falsa, tenemos que suponer que los dos términos que la componen sean falsos simultáneamente (siguiendo la definición de la disyunción que ya conocemos). Por lo tanto:
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| F | F | F |
Centrémonos n el sub-enuciado (¬p)
q
de la izquierda, cuya conectiva principal es una conjunción. Para
que sea falsa, es imprescindible que los dos enunciados atómicos
que lo componen (p, q) sean falsos.
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| F | V | F | F | F | F |
Observa que si la negación de p es F, entonces p es V
Seguimos trasladando la conclusión de que p=V y q=F a nuestra tabla:
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| F | V | F | F | F | V | F | F |
Y, por último, si q=F, entonces ¬q debe ser V...
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| F | V | F | F | F | V | F | V | F |
Lo que, a su vez, impide que la conjunción p∧(¬q) sea falsa, pues es una conjunción con dos términos verdaderos...
Luego hay que admitir que la conjunción que forma el sub-enunciado de la derecha p∧(¬q) ha de ser V si p=V y q=F:
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| F | V | F | F | F | V | V | V | F |
Y hay que admitir también que la disyunción principal es verdadera, pues uno de sus términos p∧(¬q) es verdadero.
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| F | V | F | F | V | V | V | V | F |
Y aquí no hay contradicción alguna: es decir, suponer lo contrario de lo que buscamos encontrar no conduce a una contradicción.
En este caso hemos demostrado que al menos hay una interpretación (p=V y q=F) que hace que el enunciado [(¬p)∧q]∨[p∧(¬q)] sea verdadero, pero esto no significa que haya una contradicción ni que estemos ante una tautología. Simplemente sabemos que la interpretación p=V y q=F hace verdadero el enunciado [(¬p)∧q]∨[p∧(¬q)].
En estos casos en los que nos encontramos que hay al menos una interpretación que hace verdadero el enunciado bajo estudio, decimos que dicho enunciado es satisfacible.
La reducción al absurdo para descubrir la satisfacibilidad
Para averiguar si un enunciado essatisfacible o no se puede emplear el método de reducción al absurdo, suponiendo que la conectiva principal de dicho enunciado es verdadero; si se encuentra una interpretación que lo haga verdadero sin contradicción, entonces dicho enunciado es satisfacible. Veámoslo con el mismo ejemplo. ¿Es (¬p∧q)∨(p∧¬q) satisfacible?
Construiremos una tabla que nos ayude a llevar adelante todo el proceso, con tantas celdillas como proposiciones y conectivas tenga la fórmula objeto de análisis:
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
A continuación suponemos que la conectiva principal es verdadera. Si encontramos una interpretación que no nos lleve a contradicción alguna, la fórmula será satisfacible:
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| V |
Para que la disyunción sea verdadera, tenemos que suponer que alguno de los dos sea verdadero (siguiendo la definición de la disyunción que ya conocemos). Supongamos que la conjunción de la izquierda es verdadera:
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| V | V |
Siguiendo en el sub-enuciado ¬p∧q de la izquierda, para que sea verdadero, es imprescindible que los dos enunciados atómicos que lo componen (p, q) sean verdaderos.
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| V | F | F | V | V |
Observa que si la negación de p es V, entonces p es F
Seguimos trasladando la conclusión de que p=F y q=V a nuestra tabla:
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| V | F | F | V | V | F | V |
Y, por último, si q=V, entonces ¬q debe ser F...
| (¬ | p | ∧ | q) | ∨ | (p | ∧ | ¬ | q) |
|---|---|---|---|---|---|---|---|---|
| V | F | F | V | V | F | F | F | V |
Lo que, a su vez, ocasiona que la conjunción p∧¬q sea falsa, pues es una conjunción con dos términos falsos...
Luego hay que admitir que la interpretación p=F y q=V hace verdadero el enunciado (¬p∧q)∨(p∧¬q), que por ello es satisfacible.
Hagamos la tabla de verdad de (¬p∧q)∨(p∧¬q) para comprobar si mediante este método también nos encontramos con que la interpretación p=V y q=F hace verdadero este enunciado, llevándonos a concluir que el enunciado bajo estudio es o no una tautología.
| p | q | ¬p | ¬p∧q | ¬q | p∧¬q | (¬p∧q)∨(p∧¬q) |
|---|---|---|---|---|---|---|
| V | V | F | F | F | F | F |
| V | F | F | F | V | V | V |
| F | V | V | V | F | F | V |
| F | F | V | F | V | F | F |