Ayuda para demostrar una equivalencia lógica

Question

¿Cómo puedo demostrarlo utilizando equivalencias lógicas?

$(p \rightarrow q) \lor (q \land r) \equiv \neg ((p \land \neg r) \land \neg q) \land \neg (r \land (\neg q \land p))$

Cualquier sugerencia o consejo será muy apreciado. Gracias de antemano.

EDITAR: Cosas que he probado hasta ahora:

Utilizar la ley de la implicación para cambiar la $p \rightarrow q$ en $\neg p \lor q$

Parece que $r$ aparece en ambos lados de la $\land$ en la expresión final, así que probé a ampliar el único $r$ en $q \land r$ en $r \land r$ para dar $q \land (r \land r)$ pero eso no parece llevarme a ninguna parte

Answer 1

Reclamación: $$ (p \rightarrow q) \lor (q \land r) \equiv \neg ((p \land \neg r) \land \neg q) \land \neg (r \land (\neg q \land p)) $$ LHS: $$ (p \rightarrow q) \lor (q \land r) \equiv (\neg p \lor q) \lor (q \land r) \equiv ((\neg p \lor q) \lor q ) \land ((\neg p \lor q) \lor r) \equiv \\ (\neg p \lor q ) \land ((\neg p \lor q) \lor r) \equiv (\neg p \lor q) $$ RHS: $$ \neg ((p \land \neg r) \land \neg q) \land \neg (r \land (\neg q \land p)) \equiv \\ \neg [((p \land \neg r) \land \neg q) \lor (r \land (\neg q \land p))] \equiv \\ \neg [((\neg q \land p) \land \neg r) \lor ((\neg q \land p) \land r)] \equiv \\ \neg [((\neg q \land p) \land (r \lor \neg r)] \equiv \\ q \lor \neg p \equiv (\neg p \lor q) $$

por lo que LHS = RHS y la afirmación es verdadera.

Answer 2

Una pista: Convierte cada lado en DNF (un OR de ANDs) usando las identidades:

• $x \to y \equiv \neg x \lor y$
• $\neg (x \lor y) \equiv \neg x \land \neg y$
• $\neg (x_1 \land \cdots \land x_n) \equiv \neg x_1 \lor \cdots \lor \neg x_n$

Answer 3

Primero recordemos algunas leyes.

• definición de implicación: $a\implies b \equiv \lnot a \lor b$
• Las leyes de DeMorgan:
  • $a \lor b \equiv \lnot(\lnot a \land \lnot b)$
  • $a \land b \equiv \lnot(\lnot a \lor \lnot b)$
• Conmutación:
  • $a \lor b \equiv b \lor a$
  • $a \land b \equiv b \land a$
• Asociación:
  • $(a \lor b) \lor c \equiv a \lor (b \lor c)$
  • $(a \land b) \land c \equiv a \land (b \land c)$
• Distribución:
  • $a \lor (b \land c) \equiv (a \lor b) \land (a \lor c)$
  • $a \land (b \lor c) \equiv (a \land b) \lor (a \land c)$
• Idempotencia:
  • $a \lor a \equiv a$
  • $a \land a \equiv a$
• La identidad:
  • $a \lor \bot \equiv a$
  • $a \land \top \equiv a$
• Cero:
  • $a \lor \top \equiv \top$
  • $a \land \bot \equiv \bot$

Empezando por el lado derecho y trabajando hacia atrás, \begin{align} \lnot((p \land \lnot r) \land \lnot q) &\land \lnot(r \land (\lnot q \land p))\\ \lnot(p \land \lnot q \land \lnot r) &\land \lnot(p \land \lnot q \land r) \quad\text{Association and Commutation}\\ (\lnot p \lor q \lor r) &\land (\lnot p \lor q \lor \lnot r) \quad\text{DeMorgan}\\ ((p \implies q) \lor r) &\land ((p \implies q) \lor \lnot r) \quad\text{dfn. of impl.}\\ (p \implies q) &\lor (r \land \lnot r) \quad\text{Distribution}\\ (p \implies q) &\lor \bot \quad\text{dfn. of Contradiction}\\ p &\implies q \quad\text{Identity}\\ \end{align}

Ahora comenzando con el LHS y trabajando hacia adelante, \begin{align} (p \implies q) &\lor (q \land r)\\ ((p \implies q) \lor q) &\land ((p \implies q) \lor r) \quad\text{Distribution}\\ ((\lnot p \lor q) \lor q) &\land ((p \implies q) \lor r) \quad\text{dfn. of impl.}\\ (\lnot p \lor q) &\land ((p \implies q) \lor r) \quad\text{Associativity and Idempotency}\\ (p \implies q) &\land ((p \implies q) \lor r) \quad\text{dfn. of impl.}\\ ((p \implies q) \lor \bot) &\land ((p \implies q) \lor r) \quad\text{Identity}\\ (p \implies q) &\lor (\bot \land r) \quad\text{Distribution}\\ (p \implies q) &\lor \bot \quad\text{Zero}\\ p &\implies q \quad\text{Identity}\\ \end{align}

Por lo tanto, tanto el LHS como el RHS son lógicamente equivalentes a $p \implies q$ y por Transitividad de la equivalencia, el LHS y el RHS son lógicamente equivalentes entre sí.