Proving $(p \oplus q) \oplus r=p \oplus (q \oplus r)$

Question

I was assigned to prove the associative law on xor.

$(p \oplus q) \oplus r=p \oplus (q \oplus r)$

I'm sure

$(p\oplus q)=(p∧¬q)∨(¬p∧q)$

But I got stuck on

$(p \oplus q) \oplus r=[{(p∧¬q)∨(¬p∧q)}∧¬r]∨[¬{(p∧¬q)∨(¬p∧q)}]∧r$

What tatuologies (laws) would I need to prove the associative law for xor?

How do I relate those $p$ and $q$ to $r$ in order to prove it?

Any tips/advise would be appreciated.

Answer 1

You probably already know that $\oplus$ is commutative. Thus $p \oplus (q \oplus r)$ is obtained from $(p \oplus q) \oplus r$ by exchanging the roles of $p$ and $r$. Therefore it will be enough to find an expression for $(p \oplus q) \oplus r$ that is symmetric in the variables $p$ and $r$.

Your steps to $$(p \oplus q) \oplus r=[\{(p∧¬q)∨(¬p∧q)\}∧¬r]∨[¬\{(p∧¬q)∨(¬p∧q)\}]∧r$$ are correct.

Continue the calculation by applying the distributive law to $\{(p∧¬q)∨(¬p∧q)\}∧¬r$. Then apply De Morgan's Law to $¬\{(p∧¬q)∨(¬p∧q)\}$. After that you will need to apply the distributive law repeatedly to obtain a disjunction on the right.

Answer 2

The matrix of XOR denoted as "J" in Polish notation, indicates the following two if-then rules hold:

1. If the left argument is false, then the value of Jpq is the right argument. Or in short, if p = 0, then Jpq = q.
2. If the left argument is true, then the value of Jpq is the negation of the right argument. Or equivalently, if p = 1, then Jpq = Nq.

Using these rules we have that

J J0b c = Jbc. substituting p with 0 and q with b in the first rule above (p / 0, q / b hereafter) we have J0b = b.

J 0 Jbc = Jbc. in the first rule p / 0, q / Jbc yields this equality exactly.

So, JJ0bc = J0Jbc.

J J1b c = JNbc. in rule 2 p / 1, q / b yields J1b = Nb.

J 1 Jbc = NJbc. in rule 2 p / 1, q / Jbc yields this equality exactly.

Now suppose that b = 0. Then

J N0 c = J1c = Nc.

N J0c = Nc.

And lastly suppose that b = 1.

J N1 c = J0c = c.

N J1c = NNc = c.

Since a = 0 or a = 1, and the above shows that if a = 0 or a = 1, then JJabc = JaJbc, it follows that for XOR, JJpqr = JpJqr.

This proof also ends up proving JNpq = NJpq, or JN = NJ for short.

Answer 3

I would use Venn diagrams to give a visual proof, similar to here.