Satisfacibilidad

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.

1Construiremos 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)]
                 

2A 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
        

3Para 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
    

4Centrémonos en 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
5Seguimos 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...

6Luego 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 es satisfacible 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?

1Construiremos 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)]
                 

2A 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
        

3Para 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
  
   

4Siguiendo 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
5Seguimos 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 falsoos...

6Luego 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

Página siguiente