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?

  • 3
    $\begingroup$ Have you tried to come up with such a "description" in terms of other operators yourself? $\endgroup$ – lemontree May 14 at 14:12
  • 1
    $\begingroup$ The correctness of such a paraphrase would most easily be proved by a truth table. $\endgroup$ – lemontree May 14 at 14:13
  • $\begingroup$ 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). $\endgroup$ – Mauro ALLEGRANZA May 14 at 14:17
  • $\begingroup$ @lemontree I have so far been able to get descriptions using ∧ , ∨, ¬ but not →. For example: (p ∨ q) ∧ ¬(p ∧ q) $\endgroup$ – Nnamdi Ezeh May 14 at 15:27
  • 1
    $\begingroup$ $(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? $\endgroup$ – 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)?


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.