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.

Introduction

In the second post in this series, we went through a proof sketch showing that NAND and NOR were the only two binary Sheffer functions. In studying these functions, the main mystery is why certain sets of functions are complete, and why some seem to have restrictions on what sort of compositions can be formed.

In this post we’ll use the idea of preservation of relations to great effect: we’ll obtain criteria for a set of functions to be complete, and a simpler one to show that a a given function is Sheffer. As a bonus, we’ll start to build towards a structural understanding of the space of clones. In writing this, I’m following chapter one of

Introduction

Polynomials on \(\mathbb{Z}/2\mathbb{Z}\)

Recall how arithmetic works in the integers mod 2:

The operations of addition and multiplication over \(\mathbb{Z}/2\mathbb{Z}\) behave exactly like the truth functional connectives \(\oplus\) and \(\wedge\) respectively. It makes sense for us to consider the ring \(\mathbb{Z}/2\mathbb{Z}[x_1,\dots, x_n]\) of polynomials in \(n\) variables over this field as some sort of analog of Boolean functions: typically Boolean functions are more complicated than \(\wedge\) or \(\oplus\), and polynomials are a natural way of increasing the complexity of an algebraic expression in a controlled way. What do the polynomials here look like if we consider the argument \(x\) to be some element of this field?

Introduction

In the last post in this series, we defined universality of Boolean functions, went through a few proofs that specific sets were universal, and we showed the existence of two arity 2 Sheffer functions NAND and NOR. In this post, we’ll sketch out a proof showing that these are the only binary Sheffer functions.

Determining that a given function can’t be created by compositions of others from a set seems, at least at the outset, difficult. Who are we to say there is not some absurd combination, maybe involving many thousands layers of composition, that does not replicate the function we want? If there is a key fact that I took from the learning I did for this post, it’s that the properties of Boolean functions that are preserved by composition are the key to understanding their behaviour. If we can show that there is a property preserved by any combination of functions in our set, but that does not hold for all Boolean functions in general, then we have shown it cannot be universal.

Intro

While reading on nonstandard models of arithmetic, I recalled a fact that had come up once in a class on logic. While a formal language with many connectives is nice to work in, it becomes unwieldy to work on, requiring more inductive cases to be covered in the process of proving whatever fact you’re interested on. Because of this, we chose to work on a very simple language with only the connectives for not (\(\neg\)) and implies (\(\rightarrow\)).