Ramble, Part 54: "Or...?"

[stoutfellow]

In the last Ramble, I mentioned the distinction between exclusive "or" ("x or y, but not both") and inclusive "or" ("x and/or y"). This time, I'm going to discuss why mathematicians prefer the latter to the former; in the next Ramble, I'll look at the question from a linguistic point of view.

I'll be talking about several different logical operations: negation ("it is not true that x"), conjunction ("x and y are both true"), disjunction (inclusive or), and exclusive or. Rather than bring in the specialized symbols of symbolic logic, I'll represent them by the capitalized strings NOT, AND, OR, and XOR respectively. I'll also use TRUE and FALSE as logical constants.

From the mathematical point of view, the superiority of OR to XOR has a strong aesthetic component; certain symmetries are made readily apparent by the use of OR that are obscured by XOR. There is a sense in which AND and OR are mirror images of each other: the statement x AND y is TRUE when, and only when, x and y are both TRUE, while x OR y is FALSE when, and only when, x and y are both FALSE. More broadly, if you have a logical theorem involving only AND, OR, NOT, TRUE, and FALSE, then interchanging AND with OR and TRUE with FALSE produces another theorem. For instance: x AND NOT x is always FALSE; the interchange tells us that x OR NOT x is always TRUE. Again, we have a distributive law: x AND (y OR z) is equivalent to (x AND y) OR (x AND z).

In order for the first expression to be true, x must be true, and so must either y or z. In the first case, x AND y is true; in the second, x AND z is true.

Making the interchange gives us another distributive law: x OR (y AND z) is equivalent to (x OR y) AND (x OR z). Yet again, we have the matched set of DeMorgan's Laws: NOT (x AND y) is equivalent to (NOT x) OR (NOT y), and NOT (x OR y) to (NOT x) AND (NOT y).

This sort of symmetry is an example of a "duality". For the last two centuries, mathematicians have come to dote on dualities; I can't think of a major area of mathematics in which duality doesn't play a part. (For you engineering types, Fourier series and the Fourier transform are manifestations of a kind of duality.) Having one available here is not only aesthetically pleasing but mathematically useful, and it would not be there - or not so easily visible - if XOR were chosen over OR.

Another, lesser, reason for the preference for OR over XOR is this. Mathematicians are fond of binary operations, but in ordinary speech "and" and "or" (in both meanings) can group arbitrarily many things together: "this and that and the other thing". AND and OR behave nicely here - we can handle arbitrary collections two at a time: x AND (y AND z) means that all three of x, y, z are true, and x OR (y OR z) means that at least one of them is true. Applying exclusive "or" to three things, though, ought to mean that exactly one of them is true, but that is not what x XOR (y XOR z) means; this last expression is true if exactly one of x, y, z is true, or else if all three are true. (Check it out yourself!) In other words, the generalized "and" and inclusive "or" of ordinary speech can be captured by binary operations (which makes mathematicians happy), but the exclusive "or" cannot.

There's more going on, though. It turns out, on close linguistic examination, that the "or" of ordinary speech is best interpreted as inclusive, despite what one's own intuition might say; that will be the subject of the next (digressive, and not so mathematical) Ramble.

Previous Next

Ramble Contents

Comments

[countrycousin.livejournal.com]

heh. Look forward to the next one. Not sure what my intuition says - I've worked with the operators for too long - but my experience is that many I talk to use "or" linguistically exclusively. Some add "or both" or "but not both" to disambiguate when it might be important, but often the "but not both" is implied.

Haven't responded much recently - we're selling and moving to a condo and I'm getting rid of tons of junk - haven't had as much time. But I have been reading and enjoying this series. Thanks!

[gareth-wilson.livejournal.com]

There's a joke where a robot points a gun and says "surrender or die". The punchline should be pretty obvious from the above.