1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 $$

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.