1
$\begingroup$

I'm currently trying to prove this.

$(p \to q) \land (q \to r) \land (r \to p) \iff p \land q \land r ~\lor~ \lnot p \land\lnot q \land\lnot r$

After this step, I've gotten stuck. Normally I can do these just fine, but this one seems much less obvious than the ones I've been given previously.

$\iff (\lnot p \lor q) \land (\lnot q \lor r) \land (\lnot r \lor p)$ Law of Implication (3x)

$\endgroup$
  • $\begingroup$ The easiest proof is of course a truth table (or karnaugh map). If I was allowed to choose an approach it would be this. $\endgroup$ – user400188 Feb 16 '17 at 5:26
1
$\begingroup$

That's the first step alright. The next would appear to be distribution. But before that some commutation might make things clearer.

$\begin{align} &(p\to q)\land(q\to r)\land (r\to p) \\ \iff &(\lnot p\lor q)\land(\lnot q\lor r)\land(\lnot r\lor p) &&\text{Implication Equivalence} \\ \iff &(p\lor \lnot r)\land(\lnot p\lor q)\land (r\lor\lnot q) && \text{Commutation} \\ \iff &(p\land(\lnot p\lor q)\land (r\lor \lnot q))~\lor~(\lnot r\land(\lnot p\lor q)\land (r\lor\lnot q)) & &\text{Distribution} \\ \iff &(p\land(\lnot p\lor q)\land (\lnot q\lor r))~\lor~(\lnot r\land (r\lor\lnot q)\land(q\lor \lnot p)) && \text{Commutation} \\ \vdots\quad&\end{align}$

Take it from there.

$\endgroup$
  • 1
    $\begingroup$ I'm struggling to understand how you go from step 2 to step 3. Mind explaining that a bit more? Edit. Never mind. I got it. Thanks. $\endgroup$ – Xenorosth Feb 16 '17 at 5:22
  • $\begingroup$ Hey, I got stuck again farther down. Can you give any advice? It isn't the full thing, but it boils down to essentially this. (p ^ q) ^ (¬q v r) ⟺p ^ q ^ r $\endgroup$ – Xenorosth Feb 16 '17 at 6:15
  • $\begingroup$ @Xenorosth (p^q)^(¬q v r) can be expanded into p ^ q ^ r v q(¬q) by distribution. From this is it quite easy to note that q(¬q) (which reads q and not q) is always false, so it may be dropped. Hence (p^q)^(¬q v r) is p ^ q ^ r $\endgroup$ – user400188 Feb 16 '17 at 6:47
  • $\begingroup$ $\qquad (p\wedge q)\wedge(\neg q\vee r) \\ \iff (p\wedge (q\wedge(\neg q\vee r))) \\ \iff p\wedge ((q\wedge\neg q)\vee(q\wedge r)) \\ \iff p\wedge (q\wedge r)$ $\endgroup$ – Graham Kemp Feb 16 '17 at 6:48

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.