My problem is with the definition of exclusive disjunction, at least according to Wikipedia. The Wikipedia page for Exclusive Or, at the time of writing, states that "More generally, XOR is true whenever an odd number of inputs is true." This seems useful for computer science, but in logical reasoning I would want a connective that means "only one of these propositions is true" no matter how many propositions there are. For instance, I would like a connective that says "You can either order milk, coffee, or orange juice with your breakfast."

But all of the connectives that Wikipedia lists are binary but yields strange results like that exclusive disjunction is true when an odd number of propositions are true. Is there canonical terminology for what I'm talking about or is there no standard terminology? I want to still call this exclusive disjunction, but it contradicts with the usage on Wikipedia as referenced above.

Also...is there terminology for other connectives over an indeterminate number of propositions?

  • Good question. A chain of 3 XORs is certainly not true when, say, the first two arguments are false and the third true, as you would expect from the "only one of these propositions is true" operator's behavior. It can be defined using inclusive or and not, or it can be defined more generally and explicitly as: (A xxor B xxor ... xxor Z) is true iff the (arithmetic) Sum of A,...,Z is 1. Jun 19 '14 at 23:34

You need to be careful. There is no such thing as a logical connective between more than two propositions. There are no ternary (or n-ary where n > 2) connectives in non-exotic logics, only unary (negation) and binary (conjunction, disjunction, implication, etc.) ones. As always, doing truth tables helps illustrate the concept:

First, this is how you want XOR to work with two inputs (in fact, this is how it actually works):

Table 1: | A | B | XOR | |-------------| | F | F | F | | F | T | T | | T | F | T | | T | T | F |

Next, this is how you want XOR to work with three inputs (but there's an error here):

Table 2: | A | B | C | XOR | |-----------------| | F | F | F | F | | F | F | T | T | | F | T | F | T | | F | T | T | F | | T | F | F | T | | T | F | T | F | | T | T | F | F | | T | T | T | F | (*)

Let's look at the last line marked with an asterisk. XOR(A,B) will yield F per Table 1. Similarly, XOR(B,C) as well as XOR(C,A) will also yield F per Table 1. So, no matter how we decide to commute, we will have to deal with an F and the remaining T. And XOR(T,F) will always yield a T per Table 1. This is why we observe the odd-even alternation of truth values when all operands are true.

It turns out that you don't want to use a XOR in examples like the one in your OP. What you actually want to do is something like (A v B v C) & ~(A & B & C) or (via DeMorgans) (A v B v C) & (~A v ~B v ~C). There is no logical connective that does this since this would require an n-ary connector, e.g. something like atLeastOneButNotAll(A,B,C,...,n) which would only work as a function in FOL.

Here is an interesting paper discussing the ternary exclusive or.

  • 1
    Good points. Interesting paper; will check it out. Jun 20 '14 at 5:24
  • Thanks for the link to the paper. It seems that you don't think this operator should be called a logical connective because it isn't...should I say...composable? Basically, calling my operator xxor (thanks Hunan), it isn't true that xxor(a, b, c) = xxor (a, xxor(b, c)) for all propositions a, b, and c. Guess I didn't realize that the term "logical connective" was so strictly defined. Should I call it a truth functor instead? Or, as you suggest, it could be called a propositional function. Just seems strange that something so basic seems overlooked and esoteric in logic. Jun 20 '14 at 12:57
  • The paper you link to does say: "Our interest is in the formal properties of the ‘exactly one’ sense of exclusive or, since that topic has not been addressed by the logic textbooks (nor by the formal semantic descriptions of natural language). We will be calling this connective the “real” variable-adicity exclusive or, meaning thereby that it is the one that is relevant to formal accounts of natural language. We think that ⊕n might better be called “the odd counting function of adicity n”, and that iterations of ⊕ should be called “addition modulo 2” rather than “exclusive disjunction”." Jun 20 '14 at 13:00

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.