I have been trying to prove (for my own entertainment) that XOR is associative.

However, having reduced $(p \oplus q ) \oplus r = p \oplus (q \oplus r)$ to canonical form, so that the only logical operations are OR, AND; I end up having something that I cannot reduce without relying on the associative and distributive properties of AND and OR.

It seems rather redundant to prove that one logical operator has a certain property but rely on another to do so.

My question is: Is the associative property of XOR provable algebraically - or is it axiomatic? Does the truth table count as a proof?

EDIT: This is the table I came up with.

enter image description here

  • $\begingroup$ If you want to reduce it anyway to OR and AND, why is it so smelly to use their associativity? $\endgroup$ – Berci Nov 8 '12 at 9:06

The truth table is enough, since truth tables provide a complete model theory for classical propositional logic. You can show this by proving that any formula is equivalent to its disjunctive normal form and then noting that truth tables are essentially a condensed representation of this DNF.

XOR is often defined using its truth table.

  • $\begingroup$ I added my truth table to the OP... Is that convertible to DNF? $\endgroup$ – jsj Nov 8 '12 at 9:45
  • 1
    $\begingroup$ @trideceth12: Yes, it's a ternary operator, with four clauses, one for each row ending with a 1 for the last column. The first row is $\neg p \wedge \neg q \wedge r$, and you or all the clauses together to get the DNF. This process must be described somewhere; I'll take a look. $\endgroup$ – Charles Stewart Nov 8 '12 at 9:49
  • $\begingroup$ @trideceth12: The best I saw was a YouTube video - you have to watch over 3 minutes to see what is going on, so maybe a question here is more useful. Link - youtube.com/watch?v=tpdDlsg4Cws $\endgroup$ – Charles Stewart Nov 9 '12 at 6:34

Note that both $(p\oplus q)\oplus r$ and $p\oplus (q\oplus r)$ are true if and only if odd number of $p,q,r$'s are true.

Similarly, you can consider sets in place of logical statements, then AND corresponds to intersection and OR to union, NOT to complement, and using $$p\oplus q = (p \land \lnot q ) \lor (q\land \lnot p) $$ we get $$ A\oplus B = (A\setminus B) \cup (B\setminus A) $$ this is the symmetric difference of sets, and $x\in A_1\oplus..\oplus A_n$ iff $x$ is element of exactly an odd number of $A_i$'s.


If you want a formal proof according to the definition of proof used in modern logic, then you need some set of axioms or rules of inference from which a proof can get written.

Informally, the truth table indicates associativity of XOR, or equivalently that {[(p⊕q)⊕r]=[p⊕(q⊕r)]} qualifies as a tautology, where "=" indicates the operation of logical equivalence. By the completeness metatheorem (every tautology is a theorem) of really any system of classical propositional logic that you probably will encounter, it follows that {[(p⊕q)⊕r]=[p⊕(q⊕r)]} qualifies as a theorem. So, the truth table does qualify as an informal proof that a theorem exists in the formal system.

Depending on the context, hardly anyone may care about writing or seeing a formal proof... though your computer might "consider" you crazy if you think you can give it an informal proof and it mean anything.

  • $\begingroup$ I care about it just because I like to know where things stand technically. $\endgroup$ – jsj Nov 12 '12 at 13:05
  • $\begingroup$ @trideceth12 From my reading, I think it fair to say that most logicians care that such a proof can in principle get written, but they usually care a lot less about seeing a formal proof or writing a formal proof. $\endgroup$ – Doug Spoonwood Nov 12 '12 at 22:03

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.