0

I got

$$((p\wedge \neg r)\,\vee\, (\neg q \vee r))~\wedge~ ((q\wedge \neg r) \,\vee\, (\neg p \vee r))$$

but I don't know what to do next. I can't apply any laws here so I am really confused.

Graham Kemp
  • 129,094
Rongday
  • 29
  • If $r$ is false then $p\implies r$ is false only if $p$ is true so if $r$ is false $p$ and $q$ are either both true of both false. If $r$ is true then $p \implies r$ is false only if $p$ is false so $p$ and $q$ are either both true or both false. So $p$ and $q$ are always either both true of both false. So $p\iff q$. – fleablood Sep 05 '17 at 01:07
  • 1
    What does it mean exactly "to simplify a formula"? – Taroccoesbrocco Sep 05 '17 at 01:17

2 Answers2

0

First, the last term should be $\neg p \color{red}\lor r$, rather than $\neg p \land r$

Second, because $\lor$ is associative, you can drop some parentheses. So, for example, $(p \land \neg r) \lor (\neg q \lor r)$ can be written as $(p \land \neg r) \lor \neg q \lor r$

Third, you can use:

Reduction

$P \land (\neg P \lor Q) \Leftrightarrow P \land Q$

$P \lor (\neg P \land Q) \Leftrightarrow P \lor Q$

So, you get:

$((p \land \neg r) \lor (\neg q \lor r)) \land ((q \land \neg r) \lor (\neg p \lor r)) \Leftrightarrow \text{ (Association)}$

$((p \land \neg r) \lor \neg q \lor r) \land ((q \land \neg r) \lor \neg p \lor r) \Leftrightarrow \text{ (Reduction)}$

$(p \lor \neg q \lor r) \land (q \lor \neg p \lor r) \Leftrightarrow \text{ (Distribution)}$

$((p \lor \neg q) \land (q \lor \neg p)) \lor r \Leftrightarrow \text{ (Equivalence)}$

$(p \leftrightarrow q) \lor r$

Bram28
  • 100,612
  • 6
  • 70
  • 118
0

$((p\wedge \neg r)\,\vee\, (\neg q \vee r))~\wedge~ ((q\wedge \neg r) \,\vee\, (\neg p \vee r))$

Commute and Reassociate

$(((p\wedge \neg r)\vee r)\vee \neg q)~\wedge~ (((q\wedge \neg r) \vee r)\vee \neg p)$

Distribute

$(((p\vee r)\wedge (\neg r\vee r))\vee \neg q)~\wedge~ ((q\vee r) \wedge(\neg r\vee r)\vee \neg p)$

Complementation and $\vee$ identity

$(p\vee r\vee \neg q)~\wedge~ (q\vee r\vee \neg p)$

Distribute

$r\vee((p\vee\neg q)\wedge(q\vee \neg p))$

$\to$ equivalence, and $\leftrightarrow$ equivalence

$\neg r\to (p\leftrightarrow q)$

Graham Kemp
  • 129,094