(apologies in advance for the mixture of math and computer science conventions which is about to occur) A set S of boolean functions is said to be expressively complete if every boolean function (in any number of variables) can be written in terms of the members of S. For instance, the set {AND, NOT} is expressively complete, as is the single-member set {NAND}. We'll call a boolean function expressively complete if the set containing only that function is expressively complete.

Let a(n) = # of expressively complete boolean functions in n variables. Then a(1) = 0 and a(2) = 2 (NAND and NOR are both expressively complete). How many of the 256 3-variable functions are expressively complete? There are several trivial ones where you essentially discard one input and NAND or NOR the other two. What nontrivial ones are there?

In general, how many of the 2^(2^n) n-variable boolean functions are expressively complete? Let f(x, y, z) be a boolean function. We can represent this function as an 8-bit string B; to read f(x,y,z) from the string, we interpret xyz (concatenated) as a binary number, and count that many places from the left. For example, if we represent f as 01110010, then f(1, 0, 1) is the 5th digit after the first, which is 0.

In order for f to be expressively complete, for starters, we must be able to express NOT(x) in terms of f. Since NOT only has one variable, it must be the case that f(x, x, x) = NOT(x). From there, we can obtain ID(x) = f(f(x,x,x), f(x,x,x), f(x,x,x). From this restriction of f, B must start with a 1 and end in a 0. This is true for all n, so we get the upper bound of a(n) <= 2^(2^n - 2) (for n=3, our upper bound is 64).

We also need to be able to express 0(x) and 1(x) in terms of f. Again, we're restricted to the single variable, but since we can express NOT(x) (hereafter referred to as -x) using f, it suffices for, say, f(x, x, -x) = 0(x). Furthermore, we need only construct one of the two constant functions this way; the other will follow from negation. So, either one of the digits in the first half of B is a 0 and so is the corresponding one in the second half (the other digit as far from the middle as this one), or one of the digits in the first half of B (other than the first one) is a 1, and so is the corresponding one in the second half. What this entails is that the second half of B can't be the negation of the reverse of the first half. For instance, 10001110 doesn't meet the conditions just outlined. So for each of the h = 2^(2^(n-1) - 1) allowable first halves, there are h-1 allowable second halves. This reduces the number of candidates to h*(h-1) = 2^(2^n - 2) - 2^(2^(n-1) - 1); for n=3 this leaves us with 56 candidates.

Now that we know we can represent the 1 variable functions in terms of f, we need to move on to the 2-variable. At this point, I suspect it will be easier to find functions that are expressively complete rather than ones that are not. For instance, if we can write NAND(x,y) in terms of f, using x, -x, y, -y, 0, and 1, then we know that f is expressively complete. I'm still working on it, but I suspect that most (all?) of the remaining candidates are expressively complete.

<br><br>The sequence for the upper bound above is 0, 2, 56, 16256, 1073709056, ... .  It turns out t<span style="font-family: arial,sans-serif;">hat this sequence is in the database as <a href="http://akpublic.research.att.com/%7Enjas/sequences/A002542">

A002542</a>, complete Post functions on n variables. Is this a notion related (or identical to) expressive completeness? </span><br><span style="font-family: monospace;"><br></span><span style="font-family: arial,sans-serif;">

Gabe</span><span style="font-family: monospace;"><br></span>