1.7: Equivalencia lógica

En tus clases anteriores de matemáticas (como álgebra y trigonometría), encontraste muchos ejemplos en los que dos fórmulas de aspecto diferente resultaron ser iguales. Análogamente, en Lógica, puede haber dos aseveraciones distintas que pasan a tener el mismo valor de verdad en todas las situaciones posibles. (Esto quiere decir que, por cada posible asignación de verdadero o falso a las variables, o ambas aseveraciones son verdaderas, o ambas son falsas). Se dice que tales aseveraciones son lógicamente equivalentes.

Notación\(\PageIndex{1}\)

Escribiremos\({A} \equiv {B}\) para denotar que\({A}\) es lógicamente equivalente a\({B}\).

Puede tomar mucho trabajo verificar que dos aseveraciones son lógicamente equivalentes. Por otro lado, para demostrar que dos aseveraciones no son lógicamente equivalentes, sólo se necesita encontrar un ejemplo de una asignación a las variables, de tal manera que una de las aseveraciones sea verdadera y la otra sea falsa.

Ejemplo\(\PageIndex{2}\)

Si\(A\) es verdadero y\(B\) es falso, entonces\(A \lor B\) es verdadero, pero\(A \Rightarrow B\) es falso. Por lo tanto, las aseveraciones\(A \lor B\) y no\(A \Rightarrow B\) son lógicamente equivalentes.

Ejercicio\(\PageIndex{3}\)

Demostrar que cada uno de los siguientes pares de oraciones no son lógicamente equivalentes.

1. \(A \lor B \lor \lnot C\),\((A \lor B) \& (C \Rightarrow A)\)
2. \((P \Rightarrow Q) \lor (Q \Rightarrow P)\),\(P \lor Q\)
3. \((X \& Y) \Rightarrow Z\),\(X \lor (Y \Rightarrow Z)\)

Ejemplo\(\PageIndex{4}\)

\(\lnot(A \lor B) \equiv \lnot A \& \lnot B\)Demuéstralo.

Solución

Las variables\(A\) y cada una\(B\) puede ser verdadera o falsa, y evaluaremos ambas aserciones para todas las combinaciones posibles. Para dejar claro que ninguna de las posibilidades se ha perdido, procedemos sistemáticamente: para cada valor de\(A\), consideramos los dos valores posibles para\(B\).

1. Supongamos\(A\) que es verdad.
   1. Supongamos\(B\) que es verdad. Tenemos\[\lnot(A \lor B) \quad=\quad \lnot(T \lor T) \quad=\quad \lnot T \quad=\quad F\] y\[\lnot A \& \lnot B \quad=\quad \lnot T \& \lnot T \quad=\quad F \& F \quad=\quad F .\] Ambas aseveraciones son falsas.
   2. Supongamos\(B\) que es falso. Tenemos\[\lnot(A \lor B) \quad=\quad \lnot(T \lor F) \quad=\quad \lnot T \quad=\quad F\] y\[\lnot A \& \lnot B \quad=\quad \lnot T \& \lnot F \quad=\quad T \& F \quad=\quad F .\] Ambas aseveraciones son falsas.
2. Supongamos\(A\) que es falso.
   1. Supongamos\(B\) que es verdad. Tenemos\[\lnot(A \lor B) \quad=\quad \lnot(F \lor T) \quad=\quad \lnot T \quad=\quad F\] y\[\lnot A \& \lnot B \quad=\quad \lnot F \& \lnot T \quad=\quad T \& F \quad=\quad F .\] Ambas aseveraciones son falsas.
   2. Supongamos\(B\) que es falso. Tenemos\[\lnot(A \lor B) \quad=\quad \lnot(F \lor F) \quad=\quad \lnot F \quad=\quad T\] y\[\lnot A \& \lnot B \quad=\quad \lnot F \& \lnot F \quad=\quad T \& T \quad=\quad T .\] Ambas aseveraciones son ciertas.

En todos los casos, o ambas aseveraciones son verdaderas, o ambas son falsas. Por lo tanto, son lógicamente equivalentes.

También podemos resolver el problema sin hacer tanto trabajo:

Solución más fácil

Obsérvese que la aseveración\(\lnot(A \lor B)\) es verdadera si y sólo si\(A \lor B\) es falsa, lo que significa que\(A\) ni ni\(B\) es verdad. Por lo tanto,\[\text{$\lnot(A \lor B)$ is true if and only if $A$ and~$B$ are both false.}\] también,\(\lnot A \& \lnot B\) es cierto si y sólo si\(\lnot A\) y\(\lnot B\) son ambos verdaderos, lo que significa que:\[\text{$\lnot A \& \lnot B$ is true if and only if $A$ and~$B$ are both false.}\]

Entonces las dos aseveraciones\(\lnot(A \lor B)\) y\(\lnot A \& \lnot B\) son verdaderas exactamente en la misma situación (es decir, cuándo\(A\) y\(B\) son ambas falsas); y ambas son falsas en todas las demás situaciones. Por lo tanto, son lógicamente equivalentes.

Ejercicio\(\PageIndex{5}\)

Verificar cada una de las siguientes equivalencias lógicas importantes. Para la mayoría de estos, no debe ser necesario evaluar las aserciones para todos los valores posibles de las variables.

1. reglas de negación:\[\begin{aligned} \lnot \lnot A \qquad &\equiv \qquad A \\ \lnot(A \& B) \qquad &\equiv \qquad \lnot A \lor \lnot B \\ \lnot(A \lor B) \qquad &\equiv \qquad \lnot A \& \lnot B \\ \lnot ( A \Rightarrow B) \qquad &\equiv \qquad A \& \lnot B \\ \lnot ( A \Leftrightarrow B) \qquad &\equiv \qquad A \Leftrightarrow \lnot B \end{aligned}\]
2. conmutatividad de\(\&\),\(\lor\), y\(\Leftrightarrow\):\[\begin{aligned} A \& B \qquad &\equiv \qquad B \& A \\ A \lor B \qquad &\equiv \qquad B \lor A \\ A \Leftrightarrow B \qquad &\equiv \qquad B \Leftrightarrow A \end{aligned}\]
3. asociatividad de\(\&\) y\(\lor\):\[\begin{aligned} (A \& B) \& C \qquad &\equiv \qquad A \& (B \& C) \\ (A \lor B) \lor C \qquad &\equiv \qquad A \lor (B \lor C) \end{aligned}\]

Las reglas de negación para\(\&\) y a menudo\(\lor\) se llaman Las leyes de De Morgan, en honor al matemático británico Augustus De Morgan (1806—1871, http://en.Wikipedia.org/wiki/Augustus_De_Morgan).

Las reglas de negación pueden ser utilizadas para simplificar la negación de cualquier aserción.

Ejemplo\(\PageIndex{6}\)

Simplificar\(\lnot \bigl( (A \lor B) \Rightarrow (A \& \lnot C) \bigr)\).

Solución

Tenemos\[\begin{aligned} \lnot \bigl( (A \lor B) \Rightarrow (A \& \lnot C) \bigr) &\equiv (A \lor B) \& \lnot (A \& \lnot C) \\& \equiv (A \lor B) \& (\lnot A \lor \lnot \lnot C) \\& \equiv (A \lor B) \& (\lnot A \lor C) . \end{aligned}\]

Si\({A} \equiv {B}\), entonces\({A}, \ \therefore {B}\) es una deducción válida. Por ejemplo, el ejemplo anterior muestra que\[\lnot \bigl( (A \lor B) \Rightarrow (A \& \lnot C) \bigr), \ \therefore (A \lor B) \& (\lnot A \lor C)\] es una deducción válida.

Ejercicio\(\PageIndex{7}\)

Utilice las reglas de negación para simplificar cada una de las siguientes aserciones (hasta que la negación no se aplique a nada más que a variables).

1. \(\lnot \bigl( (A \lor B) \Rightarrow (C \& D) \bigr)\)
2. \(\lnot \bigl( (A \Rightarrow B) \lor (C \& D) \bigr)\)
3. \(\lnot \Bigl( A \Rightarrow \bigl( B \Rightarrow( C \Rightarrow D) \bigr) \Bigr)\)
4. \(\lnot \Bigl( \bigl( (A \Rightarrow B) \Rightarrow C \bigr) \Rightarrow D \Bigr)\)
5. \(\lnot \bigl( (P \lor \lnot Q) \& R \bigr)\)
6. \(\lnot (P \& Q \& R \& S)\)
7. \(\lnot \Bigl( \bigl( P \Rightarrow ( Q \& \lnot R) \bigr) \lor (P \& \lnot Q) \Bigr)\)

Ejercicio\(\PageIndex{8}\)

Utilizar las reglas de negación para simplificar la negación de cada una de estas aseveraciones. Exprese sus respuestas en inglés.

1. Si está lloviendo, entonces el autobús no llegará a tiempo.
2. Estoy enfermo, y estoy cansado.
3. O el Papa está aquí, o la Reina y el Registrador están los dos aquí.
4. Si Tom olvidó su mochila, entonces Sam comerá ya sea un pepinillo o una papa, y o Bob no almorzará, o Alice conducirá a la tienda.