Comment by adrian_b | Hacker News Reader

Comment by adrian_b | Hacker News Reader

I strongly dislike the ubiquitous use of the name XOR a.k.a. "exclusive or" for this logical function, because almost always what is meant is "sum modulo 2" a.k.a. "parity", and not "exclusive or".

"Sum modulo 2" a.k.a. "parity" and "exclusive or" are 2 distinct logical functions, which happen to coincide only for the case of 2 input operands (because there exists only a single odd number less than or equal to 2).

For 3 or more input operands, what most people call XOR is actually parity, i.e. the logical function whose value is "1" when an odd number of input operands are "1".

For 3 or more input operands, "exclusive or" is the logical function whose value is "1" only if there exists only a single input operand whose value is "1", while all the other input operands are "0".

For computer hardware, parity is a much more important logical function than "exclusive or" (mainly because addition modulo 2 is used as a building block for implementing addition modulo greater numbers).

On the other hand, in mathematics "exclusive or" is a much more important logical function than parity.

For example, the quantifiers that express that some predicate is true for some elements of a set, for all elements of a set, or for a unique element of a set (like saying that an equation has solutions, or it has no solutions, or it has a unique solution), are based on the logical functions "or", "and" and "exclusive or".

In natural language, "or" always means either "inclusive or" or "exclusive or". It never means parity, i.e. what many programmers call "exclusive or" a.k.a. XOR.

While in programming the "exclusive or" logical function is a function whose computation is seldom needed, it is very frequently used for describing the behavior of a program, e.g. when saying that in a select/case/switch compound statement of some programming language either the 1st statement or the 2nd statement or the 3rd statement or ..., is executed, or when describing the types that the current value of a union/sum typed variable can have.

IEC 60617, the standard for electrotechnical symbols, gets that one right - the XOR gate gets labeled with =1, the parity gate with 2k + 1. But when you use circuit design software for PCBs or FPGAs you can still sometimes get bitten because you are getting something different than what you expected.

> On the other hand, in mathematics "exclusive or" is a much more important logical function than parity.

This is called uniqueness quantification and has its own symbol, ∃!

> For 3 or more input operands, "exclusive or" is the logical function whose value is "1" only if there exists only a single input operand whose value is "1", while all the other input operands are "0".

Citation needed.

One could easily find quotations in plenty of logic and grammar texts from hundreds of years or even of millennia ago, wherever the meaning of the various words used for "or" is discussed and where the distinction between words expressing "inclusive or" and word expressing "exclusive or" is discussed.

However there is no need for quotations if you know English. English does not have distinct words for "inclusive or" and for "exclusive or", but the context usually allows to differentiate between the 2 meanings and "or" never means parity. Without enough context, "or" more frequently means "exclusive or", which is why people sometimes feel the need to say "and/or" instead of "or", to clearly signal that they mean "inclusive or".

When someone says to you: "This belongs either to Alice or to Bob or to Charlie", do you consider that this sentence would be true if you know that "This belongs to Alice and to Bob and to Charlie" is a true sentence?

That implication would be correct if English "or", when used with the meaning of "exclusive or", would mean the same as what "exclusive or" = XOR means for programmers.

Moreover, even if you accepted that implication, would you be able to claim that in this case your understanding is compatible with "or" having been used to mean "exclusive or" in that sentence? If you believed that implication to be true, what would "inclusive or" mean for you?

I am too lazy to give longer examples, but if you would not understand what "exclusive or" means in a natural language, but you would think that it means the same as in programming, then when someone would utter a compound of e.g. 6 sentences connected by "exclusive or", you would consider the compound to be true when any 3 or any 5 of the component sentences would be true, which is not the intended meaning of "exclusive or", which is that only one of the component sentences is true. Parity is neither "inclusive or" nor "exclusive or", because when "or" is taken to be "inclusive or", any even subset of component sentences may also be true, not only the odd subsets, like for parity.

Mathematics isn't English. You don't wear the ring of integers on your finger, and you can't play football on the field of real numbers.

You're the first person I ever see that pretends to be confused by what XOR means. It means what it means, what is this semantic debate going to do for you?

This interpretation is covered in the essay.

Reply on news.ycombinator.com