Proving Logical Equivalence - $\lnot(( p \leftrightarrow q )) \equiv (p \leftrightarrow ¬( q )))$

42 Views Asked by At

I'm trying to prove that the LHS and RHS of the following are logically equivalent:

$\lnot(( p \leftrightarrow q ) \equiv (p \leftrightarrow ¬( q )))$

This is what I've managed to get so far, but I'm not sure where I can go from there...

$≡ ¬(( p\to q ) ∧ ( q\to p ))]$

$≡ ¬(((¬p) ∨ q ) ∧ ((¬q) ∨ p )))$

$≡ ¬((¬p) ∨ q ) ∨ ¬((¬q) ∨ p ))$

$≡ (p ∧ (¬q)) ∨ (q ∧ (¬p))$

1

There are 1 best solutions below

4
On

All your work, thus far, is correct.

You might want to work on the RHS of the proposed equivalence:

$$(p\iff (-q)) \equiv ((p\to (\lnot q)) \land ((\lnot q) \to p)$$

$$\equiv ((\lnot p) \lor (\lnot q)) \land (q \lor p)$$

$$\equiv ((\lnot p) \land (q\lor p))\lor ((\lnot q)\land (q\lor p))\tag{distributive law}$$

$$\equiv (((\lnot p) \land q) \lor ((\lnot p)\land p))) \lor (((\lnot q) \land q) \lor((\lnot q) \land p)))\tag{dist. law $\times 2$}$$

$$\equiv ((\lnot p) \land q) \lor F \lor F \lor ((\lnot q) \land p$$

$$\equiv ((\lnot p) \land q)\lor ((\lnot q) \land p)$$

$$\equiv (q \land (\lnot p)) \lor (p \land (\lnot q)) \tag{commutativity}$$

$$\equiv (p \land (\lnot q)) \lor (q \land (\lnot p))\tag{commutativity}$$