Search code examples
mathboolean-logicxor

Proof of identity for XOR definitions

I'd like to show the tautologies of the various definitions of XOR. There is a proof in wikipedia, which shows that the first and last line are equivalent.

Unfortunately I don't get the first transformation. Can anyboday shed some light on which operations were applied?

p ⊕ q = ( p ∧ ¬ q ) ∨ ( ¬ p ∧ q )

= ( ( p ∧ ¬ q ) ∨ ¬ p ) ∧ ( ( p ∧ ¬ q ) ∨ q ) (!)

= ( ( p ∨ ¬ p ) ∧ ( ¬ q ∨ ¬ p ) ) ∧ ( ( p ∨ q ) ∧ ( ¬ q ∨ q ) )

= ( ¬ p ∨ ¬ q ) ∧ ( p ∨ q )

= ¬ ( p ∧ q ) ∧ ( p ∨ q )

Solution

  • It's distributivity.

    Imaging ( p ∧ ¬ q ) is a simple variable x

    So simple distributivity will be:

    x ∨ (¬ p ∧ q) = (x ∨ ¬ p) ∧ (x ∨ q)

    and now set ( p ∧ ¬ q ) for x and you get:

    (( p ∧ ¬ q ) ∨ ¬ p) ∧ (( p ∧ ¬ q ) ∨ q)

    just what you want.

    Hope that helped

    you can find more about on wikipedia: https://en.wikipedia.org/wiki/Boolean_algebra