0

What I mean is, for example, we can understand A xor B as "true if A is different from B, false otherwise".

Is it possible to understand the "collective xor" of multiple logic variables

A1 xor A2 xor ... xor An

with a single short sentence? The task is trivial for and or or.

2

There are two ways of interpreting it, one in the spirit of the binary operation asking "are these mutually exclusive and exhaustive options", in which case the sentence is

... is true when one, and only one, of the n sentences is true.

as Christopher says.

The other is like the result of putting this into a computer. As XOR is both commutative and associative, we can put any statement of the form

A1 xor A2 xor ... xor An

into a cannonical form, putting all the trues first and all the falses last

T xor T xor F xor T xor F

could be written

(((T xor T) xor T) xor F) xor F

so it is only the number of trues and falses that matters. XOR can be identified with addition mod 2, with false being 0 and true being 1 . So it is the number of ones (trues) makes a difference to the final result, i.e.

X xor F -> X (nothing changes)
X xor T -> not X (value flips)

so, the truth is determined by whether there is an odd or even number of "trues". Then we have

T xor T is false

so even numbers of trues give false, and the sentence you would be looking for is

... is true when the number of true sentences is odd?

1

See Wiki : Exclusive or :

Exclusive disjunction or exclusive or is a logical operation that outputs true whenever both inputs differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR, EOR, EXOR. The opposite of XOR is logical biconditional, which outputs true whenever both inputs are the same.

It gains the name "exclusive or" because the meaning of "or" is ambiguous when both operands are true; exclusive or excludes that case. This is sometimes thought of as "one or the other but not both".

More generally, XOR is true whenever an odd number of inputs is true. A chain of XOR's — a XOR b XOR c XOR d (and so on) — is true whenever an odd number of the inputs are true and is false whenever an even number of inputs are true.

If you "restore" the parentheses in it : (((a XOR b) XOR c) XOR d) and evaluate it staritng from the inner one, of course you will get the same result: after the first T, each time you meet a new T it "flips" from T to F and from F to T. So it will be T if an odd number of T is present.

1

... is true when one, and only one, of the n sentences is true.

This is not right, because the following should turn out to be true (substituting truth values for sentence names: (T xor F) xor (T xor T). The right term there is False, so the whole is True. My error!

  • Is that correct, or am I misunderstanding your answer? For example 1 xor 1 xor 1 = 0 xor 1 = 1. – D.F.J. Mar 17 '14 at 3:08
  • I do not understand your comment ... The "XOR" connective is "exclusive OR", i.e. "the ball is black OR the ball is white" may be written with "XOR" because the two possibilities are mutually exclusive. If we have a multiple "xor-junction", we must read it restoring parentheses : "(b XOR w) XOR r" is "(the ball is black OR the ball is white) OR the ball is red". We must start from the inner sub-formula to unwind it: if the ball is red, the inner sub-f gives true and the full formula gives true; if the ball is green, we will have false. – Mauro ALLEGRANZA Mar 17 '14 at 10:10
  • @MauroALLEGRANZA I don't see why you would need to restore any parenthesis (after all, XOR is associative and commutative). In any case, like Christopher, I understood from the OP that "collective xor" is supposed to be an n-ary operation that need not be reduced to binary connectives (though it gives a different answer). – Lucas Mar 17 '14 at 10:30
  • @Lucas - associative means that ((a XOR b) XOR c) is the same as (a XOR (b XOR c)); so you are saying that there is a n-ary connective XOR' such that (a XOR' b XOR' c) is not one of the above ? – Mauro ALLEGRANZA Mar 17 '14 at 10:48
  • @MauroALLEGRANZA I'm kind of saying that. I'm saying that one might like to write an operation XOR'(a,b,c) that does what this answer says in a serial manner. – Lucas Mar 17 '14 at 11:02

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.