Gonda 2006: The Five Maximal Boolean Classes

J. Gonda's 2006 paper spans printed pages 91–104. All 14 physical pages and both numbered tables were read and visually inspected. It supplies the modern source that the official Pöschel–Rosenberg excerpt stops just before: the concrete five-class completeness test.

Five obstruction classes #

Printed page 93 defines the classes of zero-preserving, one-preserving, self-dual, monotone, and affine Boolean functions, using symbols $T_0$, $T_1$, SF, $M$, and $A$. It states that these closed classes are maximal and that a generating family must contain a witness outside each one. The notation in GTK maps SF to the common $S$ and $A$ to $L$ for the affine clone; that symbol change is editorial, not a quotation.

The proof of Theorem 6 on printed page 98 uses escape from the same five classes to prove that the generated closure is the whole set $B$ of Boolean functions, closing the sufficiency direction. Combined with containment in a proper closed class for necessity, this yields the exact criterion: a family is functionally complete precisely when it is not wholly contained in any one of the five. Corollary 3 on printed pages 99–100 then constructs a two-function basis using the nullary constant 1.

Constant convention #

Unlike Post's positive-arity historical setup, Gonda explicitly includes both nullary Boolean functions on printed page 94, treats neither as self-dual on page 96, and uses a nullary constant as a witness in the construction on pages 98–100. Functional-completeness claims must therefore state whether constants are supplied as generators or must be synthesized as positive-arity constant functions. The GTK chapter keeps this convention visible rather than silently switching universes.