Binary

Nand

Lets look at how NAND can be implemented with just AND or OR gates.

NAND becomes one of:

!(a && b)
!a || !b

Either of these can be seen as short circuiting. The reason that NAND doesn’t exist is that it is easily rewritten as not(a and b)

Xor

XOR, is at its heart, a parity checker. To check the parity of two values, you need to test both values. This is why it is fundamentally not able to short circuit it – you can’t validate if the value is true or false until you test all the values.

Looking at how XOR is written with AND and OR gates:

(a || b) && !(a && b)

If a is true, the OR part of the xor can be short circuited, however it also means that the AND part cannot be short circuited.

N-ary

N-ary operands take any number of inputs (compared to the binary ones that just take two).

Nand

The n-ary NAND is

!(a && b && c && d ... )

This again can be short circuited in that as soon as one of operands evaluates to false, the value of the NAND is true.

Xor

There are two different interpretations of the n-ary xor:

1. An odd number of true operand
2. One and only one true operand

The first one is in common usage (see XOR at Wolfram):

For multiple arguments, XOR is defined to be true if an odd number of its arguments are true, and false otherwise. This definition is quite common in computer science, where XOR is usually thought of as addition modulo 2.

From Wikipedia

Strict reading of the definition of exclusive or, or observation of the IEC rectangular symbol, raises the question of correct behaviour with additional inputs. If a logic gate were to accept three or more inputs and produce a true output if exactly one of those inputs were true, then it would in effect be a one-hot detector (and indeed this is the case for only two inputs). However, it is rarely implemented this way in practice.

The ‘one hot’ xor may be short circuited when evaluating the expression when finding the second true value.

Otherwise, again, the XOR is more commonly implemented as the “odd number of true values” which serves as a parity checker and requires the evaluation of all the operands to determine the truth of the expression as the last value evaluated can always change the truth of the expression.

NAND is either !a || !b or !(a && b) both will be short circuited when a is false.

XOR can’t be short circuited at all as @delnan explained

Perl6 has got short-circuit XOR but its meaning of XOR is specific. I’ve repeat my comment jist here: there are two meanings of XOR:

1. if count of true arguments is odd
2. if only exactly one argument is true

Example for difference: XOR (True, True, True) gives True with the 1st meaning and False with the 2nd meaning. If Perl6 machine detects at least 2 arguments are true, it stops evaluation of rest because result is already determined as False.

But, for the 1st meaning (more traditional), one can’t determine final result until all arguments are evaluated.

I think we should invent special clarification terms for these XOR variants, even if they won’t be used outside of this discussion.

The short answer is because the truth table for XOR doesn’t have a single row of True’s or False’s.

• If the first argument to OR is True, then the answer is True, regardless of the second argument.

• If the first argument of AND is False, then the answer is False regardless of the second argument.

• BUT If the first argument of XOR is True, or False, it still needs the second argument because the truth value may “flip”:

True OR ? = True (always)

False AND ? = False (always)

True XOR ? = False or True

False XOR ? = True or False