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
Every Boolean function on belongs to exactly one of the following four classes:
the two constants;
the four signed coordinates;
the two signed parity functions ;
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