Proving equivalence of $(P \vee Q \vee R)$

Question

I'm trying to prove the below equivalence without truth table.

$(P \vee Q \vee R)$ and $(P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (R \wedge \neg P) \vee (P \wedge Q \wedge R)$

I begin with the left hand expression using the law:

$P = (P \wedge T) = (P \wedge (Q \vee \neg Q)) = $ $(P \wedge Q) \vee (P \wedge \neg Q)$

Using this, I arrive at the below expression:

$(P \wedge Q) \vee (P \wedge \neg Q) \vee (Q \wedge R) \vee (Q \wedge \neg R) \vee (R \wedge P) \vee (R \wedge \neg P)$

Which can be re arranged to form:

$(P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (R \wedge \neg P) \vee (P \wedge Q) \vee (Q \wedge R) \vee (R \wedge P)$

And this is where I get stuck. Shouldn't the last three terms be equivalent to $(P \wedge Q \wedge R)$?? But if you look at the truth table, they are not. Or does such similarities don't work with these expressions. I think i'm doing something wrong but can't figure out what exactly.

Answer 1

By laws of associativity, commutativity and idempotence, RHS can be rearranged to \begin{align} RHS&=(((P \land \neg Q) \lor (P \land Q \land R))\lor (R \land \neg P)) \\ &\quad\lor(((Q\land \neg R) \lor (P \land Q \land R))\lor(P \land \neg Q)) \\ &\quad\lor(((R\land \neg P) \lor (P \land Q \land R))\lor(Q \land \neg R)) \\ &=I_1\lor I_2\lor I_3 \end{align} First there is \begin{align} I_1&=(P \land (\neg Q \lor (Q \land R)))\lor (R \land \neg P) \\ &=(P \land ((\neg Q \lor Q) \land (\neg Q \lor R)))\lor (R \land \neg P) \\ &=(P \land (\neg Q \lor R))\lor (R \land \neg P) \\ &=(P \land \neg Q)\lor(P \land R)\lor (R \land \neg P) \\ &=(P \land \neg Q)\lor(R \land (P\lor \neg P)) \\ &=(P \land \neg Q)\lor R \end{align} Likewise $$ I_2=(Q \land \neg R)\lor P\quad\text{and }\quad I_3=(R \land \neg P)\lor Q $$ So $$ RHS=I_1\lor I_2\lor I_3=((P \land \neg Q)\lor P)\lor((Q \land \neg R)\lor Q)\lor((R \land \neg P)\lor R) $$ And by by absorption law, $(P \land \neg Q)\lor P=P$ and so on. So $$ RHS=P\lor Q\lor R $$

Answer 2

It's not in general the case that if $\phi\lor \psi$ is equivalent to $\phi\lor \theta$, then $\psi$ is equivalent to $\theta$.

For example, consider $\phi=P$, $\psi=P\land Q$, $\theta=P\land R$.

Answer 3

The most usual approach is to work from the most complex side of the equivalence, and work towards the other side.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\followsfrom}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $

Looking at the symmetries of our goal,$$ \tag 0 P \lor Q \lor R \;\equiv\; (P \land \lnot Q) \lor (Q \land \lnot R) \lor (R \land \lnot P) \;\lor\; (P \land Q \land R) $$ it seems important to first try and rewrite $\;(P \land \lnot Q) \lor (Q \land \lnot R) \lor (R \land \lnot P)\;$. Let's use distribution, and see where that leads us:

$$\calc (P \land \lnot Q) \lor (Q \land \lnot R) \lor (R \land \lnot P) \op=\hint{systematically distribute $\;\lor\;$ over $\;\land\;$, a lot of times} (P \lor Q \lor R) \land (P \lor Q \lor \lnot P) \land {} \\& (P \lor \lnot R \lor R) \land (P \lor \lnot R \lor \lnot P) \land {} \\& (\lnot Q \lor Q \lor R) \land (\lnot Q \lor Q \lor \lnot P) \land {} \\& (\lnot Q \lor \lnot R \lor R) \land (\lnot Q \lor \lnot R \lor \lnot P) \op=\hint{simplify using excluded middle} (P \lor Q \lor R) \land \true \land {} \\& \true \land \true \land {} \\& \true \land \true \land {} \\& \true \land (\lnot Q \lor \lnot R \lor \lnot P) \op=\hint{simplify; DeMorgan on the last conjunct} (P \lor Q \lor R) \land \lnot (P \land Q \land R) \endcalc$$ This last expression contains the same subexpressions as the rest of our goal $\ref 0$, so this should be useful.

Therefore we can now simplify the right hand side of $\ref 0$ as follows: $$\calc (P \land \lnot Q) \lor (Q \land \lnot R) \lor (R \land \lnot P) \;\lor\; (P \land Q \land R) \op=\hint{by the above calculation} ((P \lor Q \lor R) \land \lnot (P \land Q \land R)) \;\lor\; (P \land Q \land R) \op= \hints{absorption: assume $\;P \land Q \land R\;$ is $\;\false\;$ on the} \hint{other side of the rightmost $\;\lor\;$, then simplify} (P \lor Q \lor R) \;\lor\; (P \land Q \land R) \op= \hints{absorption: assume the negation of the left hand side,} \hints{i.e., (by DeMorgan) $\;\lnot P \land \lnot Q \land \lnot R\;$,} \hint{in the right hand side, then simplify} P \lor Q \lor R \endcalc$$ which completes the proof.