Open Algorithms

Commutative functions

A function is commutative when the order of its arguments does not matter. We can show conjunction is a commutative function simply by proving 0 AND 1 = 1 AND 0. We can do this for any two-valued functions, such as OR, XOR, etc. How many cases do we have to check for three-valued functions? Let's explore:

f(0, 1) = f(1, 0)
f(0, 2) = f(2, 0)
f(1, 2) = f(2, 1)

Well yeah, but what about four-valued functions?

f(0, 1) = f(1, 0)
f(0, 2) = f(2, 0)
f(0, 3) = f(3, 0)
f(1, 2) = f(2, 1)
f(1, 3) = f(3, 1)
f(2, 3) = f(3, 2)

I'm not going to show you the cases for five-valued functions. The pattern is 2 choose 2, 3 choose 2, 4 choose 2, which evaluate to one, three, and six respectively.

Now let's explore the number of commutative two, three, and four-valued functions. We could test them all, but for higher-valued functions their is just too many. For example, there are 4294967296 binary four-valued functions. That's too many for my taste. So how can we count the number of two-valued functions? In order for a two-valued function to be commutative, it must conform to the following specification:

    [f(0, 1) = f(1, 0) = 0 or 1]
and [f(0, 0) = 0 or 1]
and [f(1, 1) = 0 or 1]

In the specification, there are two possibilities for each line. The number of lines is (2 choose 2) + 2 = 3. Therefore, there are 2^3 = 8 commutative two-valued functions. These include the constant functions 0 and 1, as well as AND, NAND, OR, NOR, XOR, and XNOR.

Great, now let's check out the spefication for commutative three-valued functions:

    [f(0, 1) = f(1, 0) = 0, 1, or 2]
and [f(0, 2) = f(2, 0) = 0, 1, or 2]
and [f(1, 2) = f(2, 1) = 0, 1, or 2]
and [f(0, 0) = 0, 1, or 2]
and [f(1, 1) = 0, 1, or 2]
and [f(2, 2) = 0, 1, or 2]

Here there are 3 possibilities per line, and (3 choose 2) + 3 = 6 lines. Therefore, there are 3^6 = 729 commutative three-valued functions. The pattern for n-valued functions is n possibilities per line, and (n choose 2) + n lines. This means that the number of commutative functions is related to the triangular numbers, since (n choose 2) + n = n(n + 1)/2. So all in all, the number of commutative n-valued functions is n^(n(n + 1)/2), giving the sequence 1, 8, 729, 1048576, and so on.