# Semantics of exclusive or

How do I get a description of $$\text {XOR}$$ (exclusive or) only using the operators $$\wedge$$, $$\vee$$, $$\neg$$, $$\rightarrow$$

And is it possible to prove the correctness of such description?

• Have you tried to come up with such a "description" in terms of other operators yourself? – lemontree May 14 at 14:12
• The correctness of such a paraphrase would most easily be proved by a truth table. – lemontree May 14 at 14:13
• Exclusive or will be true exactly when one of the two disjuncts is true (but not both). This is the definition in terms of truth-conditions (i.e. the "specification" for the truth table). – Mauro ALLEGRANZA May 14 at 14:17
• @lemontree I have so far been able to get descriptions using ∧ , ∨, ¬ but not →. For example: (p ∨ q) ∧ ¬(p ∧ q) – Nnamdi Ezeh May 14 at 15:27
• $(p \lor q) \land \neg (p \land q)$ uses no more operators than $\land, \lor, \neg \to$ and therefore fulfills your requirement, it doesn't hurt at all if it doesn't use all of them (like $\to$)... What exactly do you want? – lemontree May 14 at 15:35

It is useless to look for correctness here.

" Exclusive OR" is simply the name that has been given to the following truth function , more precisely to the function from {T,F}² to {T,F} such that :

(T,T) --> F

(T,F) --> T

(F,T) --> T

(F,F) --> F

Look at this sagittal representation of the XOR function and ask yourself : what does it mean to say that (A XOR B) is true? If I say that : (A XOR B) , I say something true if and only if it is the case that : .....

If you compare the truth table of the X-OR operator to the truth table of the OR operator, you will see that X-OR is more demanding: in order A XOR B to be true, you need (1) what is required in order A OR B to be true, (2) plus an additional condition ...

So to find your translation, you only have to ask yourself: what does the X-OR operator add to the OR operator? In other words, what happens when an OR ( a disjunction) becomes EXCLUSIVE ( that is, is no longer inclusive)?