The operator can be either Xor or Equal (6 or 9).

For n = 2 , the largest number of such operations is 6, achieved by Nor ; for n = 3 , it is 14, achieved by Xor (rule 150); for n = 4 , it is 27, achieved by rule 5737, which is Not[Xor[##]] & except when all inputs are True .

Rules 150 and 105 are additive, and correspond to Xor and its negation.

A major result from the 1980s is that it requires a formula with depth at least Log[n]/(c + Log[Log[n]]) to make it possible to represent an Xor of n variables using a polynomial number of And , Or and Not operations.

Equal (if and only if) is common in more mathematical settings, while Xor is widespread in discrete mathematics.

Standard operations in logic can be generalized as Not[a_] = 1 - a , And[a_, b_] = Min[a, b] , Or[a_, b_] = Max[a, b] , Xor[a_, b_] = Abs[a - b] , Equal[a_, b_] = 1 - Abs[a - b] , Implies[a_, b_] = 1 - UnitStep[a - b](a - b) .

It also turns out that BitXor[2a, b] + 1 works, though in this case even for 2 the smallest representation is (1 ∘ 1) ∘ (1 ∘ ((1 ∘ 1) ∘ 1)) .

Of the 24 possible reversible s = 2 gates, none can yield anything other than additive Boolean functions (as formed from Xor and Not ).

With more than two piles it was discovered in 1901 that one player can in general force the other to lose by arranging that after each of their moves Apply[BitXor, h]  0 , where h is the list of heights.

Given an integer a for which IntegerDigits[a, 2] gives the cell values for a cellular automaton, a single step of evolution according say to rule 30 is given by BitXor[a, 2 BitOr[a, 2a]] where (see page 871 ) BitXor[x, y]  BitOr[x, y] - BitAnd[x, y] and a is assumed to be padded with 0's at each end. The corresponding form for rule 110 is BitXor[BitAnd[a, 2a, 4a], BitOr[2a, 4a]] The final equation is then obtained from {1 + x 4 + x 12  2 (1 + x 3 ) (x 1 + 2 x 3 ) , x 2 + x 13  2 x 1 , 1 + x 5 + x 14  2 x 1 , 2 x 3 x 5 + 2 x 1 + 2 x 3 x 6 + 2 x 1 + x 3 x 15 + x 16  x 4 , 1 + x 15 + x 17  2 x 3 , 1 + x 16 + x 18  2 x 3 , 2 1 + x 3 (1 + x 1 + 2 x 3 ) (-1 + x 2 ) - x 10 + x 11  2 x 4 , x 7  BitAnd[x 6 , 2 x 6 ] ∧ x 8  BitOr[x 6 , 2 x 6 ], x 9  BitAnd[x 6 , 2 x 7 ] ∧ x 19  BitOr[x 6 , 2 x 7 ], x 10  BitAnd[x 9 , 2 x 8 ] ∧ x 11  BitOr[x 9 , 2 x 8 ]} where x 1 through x 4 have the meanings indicated in the main text, and satisfy x i ≥ 0 .