Discrete Math - Propositional Equivalence

Question

Show that this propositional equivalence is true:

¬( ↔ ) ≡ (¬ ∧ ) ∨ ( ∧ ¬)

My try out was to compare by truth table, but it is not that the exercice is asking. I need the resolution using arguments as "the morgan" and other simplifications as "(p-->q) ≡ ~p V q."

When I tryed the simplification on the right side, I could reach something like that:

Changing the sides to be easier...

(~R ^ S) V (R ^ ~S) ≡ ~(R <-> S)

~[(~R ^ S) V (R ^ ~S)] ≡ (R V S)

~[(~R ^ S) V ~(R -> S)] ≡ (R V S)

(R V ~S) ^ ~(R -> S) ≡ (R V S)

Matching those two sides, in truth table, it doesn't get the same result. The left side gets the result: F V F F; and the right side results in F V V F. Proving that my resolution is wrong. Can someone help me with this argumentation? Thanks!

Well, don't keep us waiting, what happens when you try those simplifications? What have you tried? You seen to know how to proceed. — Andrew Tawfeek, Apr 24 '20 at 00:53
Should be noted that it's not "the Morgan", its "DeMorgan's law(s)". Named after Augustus DeMorgan. — David Reed, Apr 24 '20 at 11:11

score 1 · Accepted Answer · answered Apr 24 '20 at 03:15

It is way easier to reformulate and develop the left hand side.

First, we need to reformulate this $\leftrightarrow$ : $$r \leftrightarrow s \equiv (r \to s) \wedge (s\to r) \equiv (\neg r \vee s) \wedge (\neg s \vee r) $$

Now, you just "push" the negation inside using de morgan's laws :

$$\begin{array}{l} {} \neg (r \leftrightarrow s) \\ \equiv \neg \big( (\neg r \vee s) \wedge (\neg s \vee r) \big) \\ \equiv \big(\neg (\neg r \vee s)\big) \vee \big(\neg (\neg s \vee r)\big) \\ \equiv (r \wedge \neg s) \vee (s \wedge \neg r) \end{array}$$

Discrete Math - Propositional Equivalence

1 Answers1