A set of Boolean functions $B$ is said to be "functionally complete" if its closure under composition gives you all possible Boolean functions.

For example $B = \{\land, \lnot\}$, $B = \{\lor, \lnot\}$, $B = \{\lor, \land, \lnot\}$, $B = \{\bar \land\}$ (NAND), $B = \{\bar \lor\}$ (NOR), etc, are all functionally complete.

However, what's also true is the contrapositive of this statement. If you don't get all Boolean functions from closure under composition, it turns out that it means $B$ is a subset of at least one of the following "Boolean classes":

  • Functions where $f$ preserves zero $(T_0)$
  • Functions where $f$ preserves one $(T_1)$
  • Functions where $f$ is linear/affine $(L)$
  • Functions where $f$ is monotone $(M)$
  • Functions where $f$ is self-dual $(S)$

Where do these five classes come from? How do we even find/categorize these classes? How do we know that these are the main classes for which their subsets under closure under composition does not give you all Boolean functions?

Like I'm sure we could show that for each of these five classes, from closure under composition we would be unable to achieve certain types of Boolean functions, but my question is how do we know these are the five classes, or the only such classes? What leads us to this organization/categorization of classes?

More directly I am asking "how do you derive Post's Completeness Theorem" but I am hoping there is a more intuitive explanation.

  • 1
    $\begingroup$ There are many more clones of boolean functions (i.e., classes that are closed under composition and projection). The point about the five classes that you list is that they are coatoms in Post's lattice so a set of boolean functions that does not contain one of these classes must be functionally complete. To understand this more deeply, I think you will need to read the proofs. $\endgroup$ – Rob Arthan Mar 16 '18 at 20:12
  • $\begingroup$ @RobArthan That's basically what I am asking though, why these five classes in particular? Is there an intuitive reason or is it more complicated and requires reading the proof? $\endgroup$ – user539262 Mar 16 '18 at 20:32
  • 1
    $\begingroup$ I think you need to read the proof. $\endgroup$ – Rob Arthan Mar 16 '18 at 20:35
  • $\begingroup$ Which version of the proof would you say answers the question and is the most accessible? $\endgroup$ – user539262 Mar 16 '18 at 21:31
  • $\begingroup$ Why not start with Post's original paper about this? $\endgroup$ – Rob Arthan Mar 16 '18 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.