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)?
Best Answer
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.