1.6: Tautologías y contradicciones

Tautologías y contradicciones

La mayoría de las aseveraciones son ciertas en algunas situaciones, y falsas en otras. Pero algunas aseveraciones son ciertas en todas las situaciones, y otras son falsas en todas las situaciones.

Definición\(1.6.1\).

• Una tautología es una afirmación de la Lógica Proposicional que es verdadera en todas las situaciones; es decir, es verdad para todos los valores posibles de sus variables.
• Una contradicción es una afirmación de la Lógica Proposicional que es falsa en todas las situaciones; es decir, es falsa para todos los valores posibles de sus variables.

Ejemplo\(1.6.2\).

La aserción\(A \lor B\) es verdadera cuando\(A\) es verdadera (o\(B\) es verdadera), pero es falsa cuando\(A\) y ambas\(B\) son falsas. Así, la aseveración es a veces cierta y a veces falsa; no es ni una contradicción ni una tautología.

Ejemplo\(1.6.3\).

Demostrar que la aseveración no\(\bigl( P \& (\lnot Q \lor \lnot R) \bigr) \Rightarrow (P \Rightarrow \lnot Q)\) es ni una tautología ni una contradicción.

Scratchwork.

Necesitamos encontrar valores de las variables que hagan verdadera la aserción, y otros valores que hagan falsa la aserción.

Es fácil hacer verdadera la aseveración, porque una implicación es cierta siempre que su conclusión es cierta, así que solo tenemos que hacer\(P \Rightarrow \lnot Q\) realidad. Y podemos hacer que esto sea cierto haciendo\(\lnot Q\) realidad. Entonces dejamos\(Q\) ser falsos. Entonces podemos dejar\(P\) y\(R\) ser lo que queramos: probablemente sea más sencillo dejar que ambos sean falsos (lo mismo que\(Q\)).

Para hacer falsa la aseveración, necesitamos hacer que su hipótesis sea cierta y su conclusión falsa.

• Empecemos con la conclusión\(P \Rightarrow \lnot Q\). Para hacer esto falso, necesitamos hacer\(P\) verdadero y\(\lnot Q\) falso. Así, dejamos\(P = \mathsf{T}\) y\(Q = \mathsf{T}\).
• Ahora, consideramos la hipótesis\(P \& (\lnot Q \lor \lnot R)\). Afortunadamente, ya decidimos hacer\(P\) realidad, pero también necesitamos hacer\(\lnot Q \lor \lnot R\) realidad. Como ya decidimos hacer\(Q\) realidad, necesitamos hacer\(\lnot R\) realidad, así que dejamos\(R = \mathsf{F}\).

Solución

Si\(P\),\(Q\), y\(R\) son todos falsos, entonces\[\begin{aligned} \bigl( P \& (\lnot Q \lor \lnot R) \bigr) \Rightarrow (P \Rightarrow \lnot Q) & \quad = \quad \bigl( \mathsf{F} \& (\lnot \mathsf{F} \lor \lnot \mathsf{F}) \bigr) \Rightarrow (\mathsf{F} \Rightarrow \lnot \mathsf{F}) \\& \quad = \quad \bigl( \mathsf{F} \& (\mathsf{T} \lor \mathsf{T}) \bigr) \Rightarrow (\mathsf{F} \Rightarrow \mathsf{T}) \\& \quad = \quad \bigl( \mathsf{F} \& \mathsf{T} \bigr) \Rightarrow (\mathsf{T}) \\& \quad = \quad \mathsf{F} \Rightarrow \mathsf{T} \\& \quad = \quad \mathsf{T} , \end{aligned}\]
mientras que si\(P\) y\(Q\) son verdaderos, pero\(R\) son falsos, entonces\[\begin{aligned} \bigl( P \& (\lnot Q \lor \lnot R) \bigr) \Rightarrow (P \Rightarrow \lnot Q) & \quad = \quad \bigl( \mathsf{T} \& (\lnot \mathsf{T} \lor \lnot \mathsf{F}) \bigr) \Rightarrow (\mathsf{T} \Rightarrow \lnot \mathsf{T}) \\& \quad = \quad \bigl( \mathsf{T} \& (\mathsf{F} \lor \mathsf{T}) \bigr) \Rightarrow (\mathsf{T} \Rightarrow \mathsf{F}) \\& \quad = \quad \bigl( \mathsf{T} \& \mathsf{T} \bigr) \Rightarrow (\mathsf{F}) \\& \quad = \quad \mathsf{T} \Rightarrow \mathsf{F} \\& \quad = \quad \mathsf{F} . \end{aligned}\]
Así, la afirmación es a veces verdadero y a veces falso, por lo que no es ni una tautología ni una contradicción.

Ejercicio\(1.6.4\).

Demostrar que cada una de las siguientes afirmaciones no es ni una tautología ni una contradicción.

1. \(A \Rightarrow (A \& B)\)
2. \((A \lor B) \Rightarrow A\)
3. \((A \Leftrightarrow B) \lor (A \& \lnot B)\)
4. \((X \Rightarrow Z) \Rightarrow (Y \Rightarrow Z)\)
5. \(\bigl( P \& \lnot(Q \& R) \bigr) \lor (Q {\Rightarrow} R)\)

Ejemplo\(1.6.5\) (Law of Excluded Middle).

Es fácil ver que la afirmación\(A \lor \lnot A\) es verdadera cuando\(A\) es verdadera, y también cuando\(A\) es falsa. Así, la aserción es cierta para ambos valores posibles de la variable\(A\), por lo que es una tautología:

Solución

\[\begin{aligned} A \lor \lnot A \text{ is a tautology} \end{aligned}\]

Obrar\(1.6.6\).

A la tautología anterior se le llama la “Ley del Medio Excluido” porque dice que toda afirmación es verdadera o falsa: no hay término medio donde una afirmación sea parcialmente verdadera y en parte falsa.

Ejemplo\(1.6.7\).

Es fácil ver que la afirmación\(A \& \lnot A\) es falsa cuando\(A\) es verdadera, y también cuando\(A\) es falsa. Así, la afirmación es falsa para ambos valores posibles de la variable\(A\), por lo que es una contradicción:

Solución

\[\begin{aligned} A \& \lnot A \text{ is a contradiction} \end{aligned}\]

Obrar\(1.6.8\).

Las aseveraciones\(A \lor \lnot A\) y\(A \& \lnot A\) son los ejemplos más importantes (y más comunes) de tautologías y contradicciones. Sin embargo, por lo general surgirán con alguna otra expresión enchufada a la variable\(A\). Por ejemplo, al dejar que\(A\) sea la aseveración\((P \lor Q) \Rightarrow R\), obtenemos la tautología\[\bigl( (P \lor Q) \Rightarrow R \bigr) \lor \lnot \bigl( (P \lor Q) \Rightarrow R \bigr) ,\]
que es un ejemplo más complicado de la Ley del Medio Excluido, y también obtenemos la contradicción\[\bigl( (P \lor Q) \Rightarrow R \bigr) \& \lnot \bigl( (P \lor Q) \Rightarrow R \bigr) .\]

Ejemplo\(1.6.9\).

También podemos dar ejemplos en inglés, más que en símbolos; considera estas afirmaciones:

27. Está lloviendo.
28. O está lloviendo, o no lo está.
29. A la vez está lloviendo y no lloviendo.

Para saber si la Aserción 27 es cierta, habría que verificar el clima. Lógicamente hablando, podría ser verdadero o falso, por lo que no es ni una tautología ni una contradicción.

La aserción 28 es diferente. No es necesario mirar afuera para saber que es cierto, independientemente de cómo sea el clima. Entonces es una tautología.

Tampoco es necesario consultar el clima para conocer la Aserción 29. Debe ser falso, simplemente como cuestión de lógica. Puede estar lloviendo aquí y no lloviendo al otro lado de la ciudad, o podría estar lloviendo ahora pero deje de llover incluso mientras lee esto, pero es imposible que esté lloviendo y no lloviendo en una situación determinada (en cualquier momento y lugar en particular). Así, la tercera afirmación es falsa en toda situación posible; es una contradicción.

Ejercicio\(1.6.10\).

¿Cuáles de las siguientes son posibles? Para los que son posibles, dar un ejemplo. Para los que no lo son, expliquen por qué.

1. Una deducción válida cuya conclusión es una contradicción.
2. Una deducción válida cuya conclusión es una tautología.
3. Una deducción válida que tiene una tautología como una de sus hipótesis.
4. Una deducción válida que tiene una contradicción como una de sus hipótesis.
5. Una deducción inválida cuya conclusión es una contradicción.
6. Una deducción inválida cuya conclusión es una tautología.
7. Una deducción inválida que tiene una tautología como una de sus hipótesis.
8. Una deducción inválida que tiene una contradicción como una de sus hipótesis.