0

I have the following expression

$(P\rightarrow Q) \wedge (Q\rightarrow R) \wedge (R \rightarrow P)$

and I want to create a DNF. I've gotten as far as getting rid of the implication, but I'm not sure how to get to the nice answer Wolfram Alpha gives me:

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

When I try to expand things out I just get complicated expressions that I'm not sure how to simplify, and I want to avoid using the truth tables if possible.

Hiraphor
  • 179
  • Replace $P\rightarrow Q$ with $Q\vee\lnot P$, etc. and distribute. Then cancel out terms involving $P\land\lnot P$ etc. – user10354138 Oct 14 '18 at 16:53
  • As I said, the simplification part is where I'm stuck, I don't know how to just cancel those terms. – Hiraphor Oct 14 '18 at 17:03

1 Answers1

1

Removing the implications with disjunctions, you get $$ (Q\lor\lnot P)\land(R\lor\lnot Q)\land(P\lor\lnot R) $$ distributing the first $\land$, $$\require{cancel} \begin{align*} &(Q\lor\lnot P)\land(R\lor\lnot Q)\\ &=((Q\lor\lnot P)\land R)\lor((\color{red}{Q}\lor\lnot P)\land\lnot Q)\\ &=(Q\land R)\lor(\lnot P\land R)\lor\cancel{(\color{red}{Q\land\lnot Q})}\lor(\lnot P\land\lnot Q) \end{align*} $$ So $$ \begin{align*} &(Q\lor\lnot P)\land(R\lor\lnot Q)\land(P\lor\lnot R)\\ &=[(Q\land R)\lor(\lnot P\land R)\lor(\lnot P\land\lnot Q)]\land(P\lor\lnot R) \end{align*} $$ and distribute again, $$ \begin{align*} &=\{[(Q\land R)\lor(\color{red}{\lnot P}\land R)\lor(\color{red}{\lnot P}\land\lnot Q)]\land P\}\\ &\quad \lor\{[(Q\land\color{red}{R})\lor(\lnot P\land\color{red}{R})\lor(\lnot P\land\lnot Q)]\land\lnot R\}\\ &=[(Q\land R\land P)\lor\cancel{(\color{red}{\lnot P}\land R\land\color{red}{P})}\lor\cancel{(\color{red}{\lnot P}\land\lnot Q\land\color{red}{P})}]\\ &\quad \lor[\cancel{(Q\land\color{red}{R\land\lnot R})}\lor\cancel{(\lnot P\land\color{red}{R\land\lnot R})}\lor(\lnot P\land\lnot Q\land\lnot R)]\\ \end{align*} $$ leaving precisely $$ (P\land Q\land R)\lor(\lnot P\land\lnot Q\land\lnot R) $$ as the DNF.

user10354138
  • 33,239