Answer to Question #267729 in Discrete Mathematics for omar mahdy

Question

 Show that p ↔ q and (p ∧ q) ∨ (¬p ∧ ¬q) are logically equivalent.

Answer 1

1)First method

Lets make truth value table of both statements. Lets denote p ↔ q as S₁, (p ∧ q) as A, (¬p ∧ ¬q) as B, (p ∧ q) ∨ (¬p ∧ ¬q) as S₂.

| p | q | A | B | S₂ | S₁ |

| T | T | T | F | T | T |

| T | F | F | F | F | F |

| F | T | F | F | F | F |

| F | F | F | T | T | T |

2)Second method

$p ↔ q = (p \to q) \land (q \to p) = (\lnot p \lor q) \land (\lnot q \lor p) =$

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

$(\lnot p \land p)$ is always false, as well as $(q \land \lnot q)$, since $(x \lor False)$ is true only if x is true, $(x \lor False) =x$. Using this we can remove $(\lnot p \land p)$ and $(\lnot q \land q)$, which gives as

$p ↔ q =(p \land q) \lor (\lnot p \land \lnot q)$