Proving equivalence of $(P \vee Q \vee R)$ 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.
 A: 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$.
A: 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
$$
A: 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.
