Exclusive Or Properties

Theorems

Exclusive or is commutative:

• $p \oplus q \dashv \vdash q \oplus p$

Exclusive or is associative:

• $p \oplus \left({q \oplus r}\right) \dashv \vdash \left({p \oplus q}\right) \oplus r$

Exclusive or destroys copies of itself:

• $p \oplus p \dashv \vdash \bot$

Proof

Proof by Natural deduction

Commutativity is proved by the Tableau method:

$p \oplus q \vdash q \oplus p$

Line		Pool	Formula	Rule	Depends upon
1		1	$p \oplus q$	P	(None)
2		1	$\neg \left({p \implies q}\right) \lor \neg \left({q \implies p}\right)$	By definition	1
4		1	$\neg \left({q \implies p}\right) \lor \neg \left({p \implies q}\right)$	Comm	1
5		1	$q \oplus p$	By definition	1

$q \oplus p \vdash p \oplus q$ is proved similarly.

$\blacksquare$

Proof of associativity by natural deduction is just too tedious to be considered.

Proof by Truth Table

We apply the Method of Truth Tables to the propositions in turn.

As can be seen by inspection, in all cases the truth values under the main connectives match for all models.

$\begin{array}{|ccc||ccc|} \hline p & \oplus & q & q & \oplus & p \\ \hline F & F & F & F & F & F \\ F & T & T & T & T & F \\ T & T & F & F & T & T \\ T & F & T & T & F & T \\ \hline \end{array}$

$\blacksquare$

$\begin{array}{|ccccc||ccccc|} \hline p & \oplus & (q & \oplus & r) & (p & \oplus & q) & \oplus & r \\ \hline F & F & F & F & F & F & F & F & F & F \\ F & T & F & T & T & F & F & F & T & T \\ F & T & T & T & F & F & T & T & T & F \\ F & F & T & F & T & F & T & T & F & T \\ T & T & F & F & F & T & T & F & T & F \\ T & F & F & T & T & T & T & F & F & T \\ T & F & T & T & F & T & F & T & F & F \\ T & T & T & F & T & T & F & T & T & T \\ \hline \end{array}$

$\blacksquare$

$\begin{array}{|ccc|} \hline p & \oplus & p \\ \hline F & F & F \\ T & F & T \\ \hline \end{array}$

$\blacksquare$