Introduction#

In the previous posts in this series, we’ve talked about completeness of sets of Boolean functions, building to a proof of Post’s completeness criterion. In this post, we’ll investigate some applications of this to Sheffer functions. Proofs in this post again come from Pöschel and Rosenberg’s chapter in

  1. Crama Y, Hammer PL, eds. Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge University Press; 2010.

unless otherwise specified.

How to Spot a Sheffer Function#

It turns out that verifying if a function is Sheffer is simpler than verifying if a set is complete. Some of the conditions used Post’s criterion collapse when the set to consider is just a single function, as we’ll see in the next theorem

Theorem: A Boolean function \(f(x_1,\dots,x_n)\) is Sheffer iff

  1. \(f(x,\dots,x) = x'\)
  2. \(f(a_1,\dots,a_n) = f(a_1',\dots,a_n')\) for some tuple \(a_1,\dots,a_n\)

That is to say, if \(f\) is capable of simulating the negation and is not self dual. Note that simulating the negation is the same as saying the function does not preserve the relations \(\{0\}\), \(\{1\}\).

Proof

(\(\Rightarrow\)) This direction follows immediately from Post’s criterion.

(\(\Leftarrow\)) If \(f\) does not preserve \(0\) or \(1\), that means we have

\[f(0,\dots,0) = 1 \geq 0 = f(1,\dots,1)\]

hence \(f \not\in Pol(\leq)\).

Now assume that \(f \in Pol(\lambda)\). Then we can express \(f\) in the form

\[f(x_1,\dots,x_n) = a_0 \dotplus a_1 x_1 \dotplus \dots \dotplus a_n x_n\]

If we hold that \(f\) fails to preserve \(0\) and \(1\) in addition to being linear we have that \(1 = f(0,\dots,0) = a_0\) and \(0 = f(1,\dots,1) = 1 \dotplus a1 \dotplus \dots \dotplus a_n\), which then implies \(\sum_{i=1}^n a_i = 1\). We then have

\[\begin{align} f(x_1',\dots,x_n')' &= 1 + (1 \dotplus a_1(1\dotplus x_1)\dotplus \dots \dotplus a_n(1 + x_n))\\ &= 1 \dotplus 1\dotplus \sum_{i=1}^n a_i \dotplus \sum_{i=1}^n a_i x_i\\ &= 1 \dotplus \sum_{i=1}^n a_i x_i\\ &= f(x_1,\dots,x_n) \end{align}\]

So \(f\) cannot be linear, since we have already established that it is not self dual. \(\blacksquare\)

Counting Sheffer Functions#

If we’re able to count the Sheffer functions, it will give us an indication as to how rare these functions actually are. I like how Pöschel and Rosenberg prove the following identity, so I tried my hand at a proof of it as well. Some of the ideas are similar: for example the way they define a total order on \(\mathbb{B}^n\) is just the standard way of order inputs in a truth table.

As an example, consider the case (n=3). A truth table for such a function will look like this:

\[ \begin{array}{|c|c|c|c|} x & y & z & f(x,y,z)\\ \hline 1 & 1 & 1 & \dots\\ 1 & 1 & 0 & \dots\\ 1 & 0 & 1 & \dots\\ 1 & 0 & 0 & \dots\\ 0 & 1 & 1 & \dots\\ 0 & 1 & 0 & \dots\\ 0 & 0 & 1 & \dots\\ 0 & 0 & 0 & \dots \end{array} \]

From the previous theorem, we know if this function is to be Sheffer, two things must be true:

  1. The first and last rows must be \(0\) and \(1\) respectively
  2. There is at least one tuple such that \(f(a_1,a_2,a_3) = f(a_1',a_2',a_3')\).

There will be a symmetry in how these rows for property 2 are placed in the standard truth table ordering: if we assume that the tuple \((a_1,a_2,a_3)\) is the \(j\)-th row from the bottom, then \((a_1',a_2',a_3')\) will be the \(2^n-j\)-th row from the bottom. For any such pair of rows, call the first one from the bottom a pivot row.

Once we specify the first and last rows of the truth table, that leaves us with a total of \(2^{2^3 - 2}=64\) functions we can make. Of these functions those that fail to be Sheffer will not have any pivot rows. That means the value of the \(j\)-th row is always different from that of the \(n-j\)-th one.

Of course, there is still an implied symmetry here. We need only specify half of the remaining \(2^3-2\) rows in the table, giving us \(2^{3-1}-1\) rows we need a value for, and \(2^{2^{3-1}-1}\) ways to specify the values.

\[ \begin{array}{|c|c|c|c|} x & y & z & f(x,y,z)\\ \hline 1 & 1 & 1 & 0\\ 1 & 1 & 0 & a'\\ 1 & 0 & 1 & b'\\ 1 & 0 & 0 & c'\\ 0 & 1 & 1 & c\\ 0 & 1 & 0 & b\\ 0 & 0 & 1 & a\\ 0 & 0 & 0 & 1 \end{array} \]

This gives us a total of \(2^{2^3 -2} - 2^{2^{3-1}-1}=56\) Sheffer functions of arity 3.

Theorem: There are \(2^{2^n -2} - 2^{2^{n-1}-1}\) Sheffer functions of arity \(n\).

Proof: Replace \(3\) with the arity \(n\) in the above argument.

We know the total number of Boolean functions of arity \(n\) is \(2^{2^n}\), so the proportion of Sheffer functions of arity \(n\) is given by

\[S(n):= \frac{2^{2^n -2} - 2^{2^{n-1}-1}}{2^{2^n}} = \frac{1}{4} - \frac{1}{2^{2^{n-1}+1}}\]

Hence as \(n\rightarrow\infty\) we have \(S(n)\rightarrow \frac{1}{4}\). So Sheffer functions are

  1. Not especially rare.
  2. Stabilize in proportion relatively quickly as \(n\) increases.

Final Thoughts#

I really like the use of combinatorial arguments in Pöschel and Rosenberg’s chapter. They do a further analysis of Sheffer functions when the use of constants for arguments is allowed (as they would be when one is designing a physical circuit for example) which shows that as \(n\) increases the proportion of Sheffer-with-constants functions increases to 1.

I was also happy to see my intuition was on the right track when it came to thinking that Sheffer functions needed to “simulate negation” somehow, as well as seeing how a rigorous argument on the subject could be developed. I quite enjoyed reading this chapter of Boolean Models and Methods in Mathematics.

Open Questions#

  1. How do the proportions of other Boolean functions change as \(n\) increases? I can’t see us getting chaotic, or even cyclical behaviour here. Can we come up with criteria that will determine when a class’s stabilizes to some non-zero value? What does the rate of convergence of such a class tell us about it?

Stumbling Blocks#

  1. I tried longer than I want to admit to prove the criterion for Sheffer functions on my own, only to realize I was missing something obvious on reading the proof in the text.