Manuscript Oai119-A@1 · Oai119-A.tex · lemma · fdff7292

Lemma: Four exhaustive orbits

Stages 3 and 6: the complete finite certificate › Exhaustive classification of the sixteen functions · lines 786–813 · proof included or linked

Oai119-A@1#lem:orbits

Back to manuscript

Every Boolean function on belongs to exactly one of the following four classes:

  1. the two constants;

  2. the four signed coordinates;

  3. the two signed parity functions ;

  4. the eight functions with one exceptional vertex, or their complements.

A representative of the last orbit is

Proof. Classify by the size of the positive set. Sizes zero and four give the constants. Sizes one and three give eight functions, all in the exceptional-vertex orbit.

At size two there are six unordered pairs of vertices. Four pairs are edges of the square; their indicators give signed coordinates. The remaining two pairs are diagonals; they give signed parity. This accounts for functions.

Displayed formulas in this passage

  • unlabeled · line 798

Nearby in this section