Expressively complete boolean functions

[Gabriel Cunningham]

(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.

The sequence for the upper bound above is 0, 2, 56, 16256, 1073709056, ...
.  It turns out that this sequence is in the database as
A002542<http://akpublic.research.att.com/%7Enjas/sequences/A002542>,
complete Post functions on n variables. Is this a notion related (or
identical to) expressive completeness?

Gabe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061216/98e0f694/attachment-0001.htm>