Prueba de que la expresión es una tautología.

Question

Estoy estudiando para mi examen y tengo algunas dudas.

La expresión:$$¬(P \Leftrightarrow Q) \Leftrightarrow P \oplus Q$ $

El objetivo es saber si es una tautología. No sé el resultado.

Yo hice esto:

$$ ¬ [¬ (P \ oplus Q)] \ Leftrightarrow P \ oplus Q $$ $$ ¬ [¬ ((P \ land ¬Q) \ lor (\ lnot P \ land Q))] \ Leftrightarrow P \ oplus Q $$ $$ ¬ [(¬P \ lor Q) \ land (P \ lor \ lnot Q)] \ Leftrightarrow P \ oplus Q $$

y ahora estoy atascado.

¿Alguna ayuda?

Answer 1

Puesto que sólo tiene dos variables, te sugiero escribir como una tabla:

$$ \begin{array}{lcr} \mbox{P} & \mbox{Q} & \mbox{P}\leftrightarrow \mbox{Q} & \neg (\mbox{P}\leftrightarrow \mbox{Q}) & \mbox{P}\oplus \mbox{Q}\\ T & T & T & F & F\\ T & F & F & T & T\\ F & T & F & T & T\\ F & F & T & F & F\end{array}$$

Por lo tanto, para todos los valores booleanos de $P$ $Q$ tenemos que $\neg(\mbox{P}\leftrightarrow \mbox{Q})$ tiene el mismo valor booleano como $\mbox{P}\oplus \mbox{Q}$, que es lo que queríamos demostrar.

Otra prueba de la lógica de la igualdad, mediante la "prueba de los árboles". Nos assumein contradicción que podemos satisfacer la siguiente expresión $\neg \left( \left(\neg\left(\mbox{P} \leftrightarrow \mbox{Q}\right) \right) \leftrightarrow \left( \mbox{P} \oplus \mbox{Q}\right)\right)$.

por las reglas de la $\leftrightarrow$ deducimos que podemos satisfacer al menos uno de los siguientes:

1. $ \left(\mbox{P} \leftrightarrow \mbox{Q}\right) \wedge \left( \mbox{P} \oplus \mbox{Q}\right)$

2. $ \left(\neg\left(\mbox{P} \leftrightarrow \mbox{Q}\right) \right) \wedge \left( \neg \left( \mbox{P} \oplus \mbox{Q}\right) \right)$

Vamos a empezar desde $1.$:

Por las reglas de la $\wedge$ sabemos que la expresión de $\mbox{P}\leftrightarrow \mbox{Q}$ está satisfecho y el fin es la expresión de la $\mbox{P} \oplus \mbox{Q}$. Por las reglas de la $\leftrightarrow$ sabemos que, desde la $\mbox{P}\leftrightarrow \mbox{Q}$ está satisfecho, tenemos dos sub-opciones:

1.1. $\mbox{P}$ $\mbox{Q}$ están satisfechos, lo que significa $\mbox{P}=\mbox{Q}=true$.

1.2. $\mbox{P}$ $\mbox{Q}$ son ambos no satisfechos, lo que significa $\mbox{P}=\mbox{Q}=false$.

Ahora desde $\mbox{P}\oplus \mbox{Q}$ está satisfecho, por las reglas de la $\oplus$ sabemos que uno de los siguientes casos:

1.3. $\mbox{P}$ está satisfecho y $\mbox{Q}$ no lo es, significado $\mbox{P}=true$$\mbox{Q}=false$.

1.4. $\mbox{P}$ no está satisfecho y $\mbox{Q}$ es, significado $\mbox{P}=false$$\mbox{Q}=true$.

Se puede ver claramente que $1.3.$ contradice tanto $1.2.$$1.1.$, con lo que la opción de $1.3.$ imposible. Pero el que pasa por $1.4.$, haciendo de esta opción imposible así. Por lo tanto, no tenemos opción a elegir, lo que significa llegamos a una contradicción.

Este método se denomina "prueba de los árboles", porque la contradicción se puede ver mejor cuando he escrito esto en un árbol de la forma, cuando usted tiene dos (o más) opciones de dividir el árbol en dos ramas, cada una para cada opción, y cuando sólo tiene una opción - mantener el crecimiento de esta rama en rama.

Ahora, voy a ir en la opción de $2$ se puede hacer de manera muy similar, y yo voy a dejar esto para usted así que usted puede conseguir una mejor sensación de este método.

Buena suerte en tu examen! :)

Answer 2

¿Por qué no hacer una tabla de verdad o falso?

$$\begin{align}&P&Q&&P&\iff Q&&\neg(P\iff Q)&P\rlap{\;\,\cdot}\vee Q\ &T&T&&&T&&F&F\ &T&F&&&F&&T&T\ &F&T&&&F&&T&T\ &F&F&&&T&&F&F\end{align} $$

Suponiendo que $\;P\rlap{\;\,\cdot}\vee Q\;$ iff verdadero sólo es uno de los dos es cierto.

Entonces sí: ambas fórmulas son equivalentes de la lógica.