3
$\begingroup$

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)?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ very awesome. can you tell me a little bit more about the coup de grace? it seems that you are distributing the not p and q over the second parenthesis. what rule does this use? $\endgroup$
    – compguy24
    Feb 18, 2014 at 22:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeff Snider
    Feb 19, 2014 at 2:35
  • 1
    $\begingroup$ If you think this is a good answer, don't forget to upvote and select it. $\endgroup$
    – Jeff Snider
    Feb 19, 2014 at 20:20
  • 1
    $\begingroup$ ah, of course. unfortunately, my reputation doesn't yet permit me to upvote yet. $\endgroup$
    – compguy24
    Feb 19, 2014 at 20:25
  • 1
    $\begingroup$ in the step from the penultimate line to the last line, i've seen that done with ANDs because of some commutative property, but does it also apply to strings of ORs? $\endgroup$
    – compguy24
    Feb 19, 2014 at 20:32

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.