# p xor q xor r -- simplifying into disjunctive normal form with propositional algebra

So, I have $p \oplus q \oplus r$, and my goal is to simplify into disjunctive normal form with propositional algebra.

Step 1: simplyify xor
((($p \wedge \neg q) \vee (\neg p \wedge q)) \wedge \neg r) \vee (\neg((p \wedge \neg q) \vee (\neg p \wedge q))) \vee r)$

Step 2: distribute the NOT on the left hand side
((($p \wedge \neg q) \vee (\neg p \wedge q)) \wedge \neg r) \vee ((\neg(p \wedge \neg q) \wedge \neg(\neg p \wedge q)) \vee r))$

Step 3: distribute the NOTs on the left side again
((($p \wedge \neg q) \vee (\neg p \wedge q)) \wedge \neg r) \vee (((\neg p \vee q) \wedge ( p \vee \neg q)) \vee r))$

Step 4: distribute r on both sides
$((\neg r \wedge (p \wedge q)) \vee (\neg r \wedge(\neg p \wedge q))) \vee ((r \vee (\neg p \vee q)) \wedge (r \vee(p \vee \neg q)))$

Step 5: lose hope
Here is where I'm stuck. What's next on the road to DNF? Is there an easier way (not including truth tables)?

I will simplify $$p \oplus q \oplus r$$ using $$a\oplus b \Longleftrightarrow (a \wedge \neg b) \vee (\neg a \wedge b),$$ in tiny tiny steps. We have $$\Big[\Big((p \wedge \neg q) \vee (\neg p \wedge q)\Big) \wedge \neg r\Big] \vee \Big[\neg\Big((p \wedge \neg q) \vee (\neg p \wedge q)\Big) \wedge r\Big]$$ which becomes $$\Big[\Big((p \wedge \neg q) \vee (\neg p \wedge q)\Big) \wedge \neg r\Big] \vee \Big[\Big(\neg(p \wedge \neg q) \wedge \neg(\neg p \wedge q)\Big) \wedge r\Big]$$ then $$\Big[\Big((p \wedge \neg q) \vee (\neg p \wedge q)\Big) \wedge \neg r\Big] \vee \Big[\Big((\neg p \vee q) \wedge ( p \vee \neg q)\Big) \wedge r\Big]$$ then $$\Big[\Big((p \wedge \neg q \wedge \neg r) \vee (\neg p \wedge q \wedge \neg r)\Big)\Big] \vee \Big[\Big((\neg p \vee q) \wedge ( p \vee \neg q)\Big) \wedge r\Big]$$ and the coup de grace by way of $$\Big((\neg p \vee q) \wedge ( p \vee \neg q)\Big) \Longleftrightarrow \big(\neg p \wedge (p\vee\neg q)\big) \vee \big(q \wedge (p\vee\neg q) \big) \Longleftrightarrow (\neg p\wedge\neg q)\vee(p\wedge q)$$ is $$\Big[\Big((p \wedge \neg q \wedge \neg r) \vee (\neg p \wedge q \wedge \neg r)\Big)\Big] \vee \Big[\Big( (\neg p\wedge\neg q)\vee(p\wedge q)\Big) \wedge r\Big]$$ becoming $$\Big[\Big((p \wedge \neg q \wedge \neg r) \vee (\neg p \wedge q \wedge \neg r)\Big)\Big] \vee \Big[\Big( (\neg p\wedge\neg q\wedge r)\vee(p\wedge q\wedge r)\Big) \Big]$$ and finally $$(p \wedge \neg q \wedge \neg r) \vee (\neg p \wedge q \wedge \neg r) \vee (\neg p\wedge\neg q\wedge r)\vee(p\wedge q\wedge r).$$ Which is exactly what we expect.
• I would say we're distributing $(p\vee\neg q)$ over the LHS, not the other way around. I.e., $(a \vee b) \wedge (c \vee d) \rightarrow a \wedge (c \vee d) \vee b \wedge (c \vee d)$. I'm sure you can distribute the other way around and get the same result. Feb 19, 2014 at 2:35