Families of Boolean functions

Boolean functions belong to the same family, when they can be transformed into each other by negating arguments.
The size of a family is always a power of two. The maximal size is 2^adicity, i.e. the period length of the truth table.
(While the size of faction and clan increases with the chosen arity, the size of a family is fixed.)

The simplest property of a family is its weight, i.e. the number of true entries in each truth table.
An important property is the parity of the weight. Those with odd weight shall be called sharp, those with even weight blunt.
(It is the same as the parity of the quaestor weight.)

A family belongs to a clan (where the arguments are not just negated, but also permuted).
Together with its complement, it forms a super-family. Adding a half-complement forms an ultra-family.

A family matrix is a bitwise XOR table with integers replaced by binary values. Each row (or column) is the truth table of a BF in the family.

two family matrices of 3-ary seals, one with 4 functions (left), the other with 2 (right)

arity to count

arity ${\displaystyle n}$ 0 1 2 3 4 5 Saffron balanced families 0 1 3 14 870 18796230 ${\displaystyle {\frac {(2^{2^{n-1}})(2^{n}-1)}{2^{n}}}}$ NonDubSage closed families 0 1 3 14 240 63488 ${\displaystyle {\frac {2^{2^{n}}}{2^{n}}}~=~2^{(2^{n}-n)}}$ DubSage unclosed families (BF with a particular consul) 2 2 4 32 4096 134217728 ${\displaystyle 2^{n}-n-1}$ Eulerian numbers 0 0 1 4 11 26 ${\displaystyle {\frac {2^{2^{n}}}{2^{n{\color {Red}+1}}}}~=~2^{(2^{n}-n-1)}}$ Sage sharp families (BF with a particular prefect) 1 1 2 16 2048 67108864 ${\displaystyle {\frac {2^{2^{n}}+(2^{2^{n-1}{\color {Red}+1}})(2^{n}-1)}{2^{n{\color {Red}+1}}}}}$ NonSage blunt families super-families 1 2 5 30 2288 67172352 ${\displaystyle {\frac {2^{2^{n}}+(2^{2^{n-1}})(2^{n}-1)}{2^{n}}}}$ Thyme families 2 3 7 46 4336 134281216 TornSage sharp super-families 1 1 8 1024 33554432 Clove blunt super-families 1 4 22 1264 33617920 Aloe families with maximal size ${\displaystyle 2^{n}}$ (diagonal of Olive) 2 1 2 23 3904 134156284 blunt families with maximal size ${\displaystyle 2^{n}}$ 1 0 0 7 1856 67047420 formulas in Python def f_closed(n): a = 2 ** (2 ** (n - 1)) b = 2 ** n - 1 c = 2 ** n result = a * b / c assert result % 1 == 0 # is integer return int(result) def f_unclosed(n): a = 2 ** n - n result = 2 ** a assert result % 1 == 0 # is integer return int(result) def f_sharp(n): a = 2 ** n - n - 1 result = 2 ** a assert result % 1 == 0 # is integer return int(result) def f_blunt(n): a = 2 ** (2 ** n) b = 2 ** (2 ** (n - 1) + 1) c = 2 ** n - 1 d = 2 ** (n + 1) result = (a + b * c) / d assert result % 1 == 0 # is integer return int(result) def f_total(n): a = 2 ** (2 ** n) b = 2 ** (2 ** (n - 1)) c = 2 ** n - 1 d = 2 ** n result = (a + b * c) / d assert result % 1 == 0 # is integer return int(result) closed = [0, 1, 3, 14, 240, 63488, 4227858432] unclosed = [2, 2, 4, 32, 4096, 134217728, 288230376151711744] sharp = [1, 1, 2, 16, 2048, 67108864, 144115188075855872] blunt = [1, 2, 5, 30, 2288, 67172352, 144115192303714304] total = [2, 3, 7, 46, 4336, 134281216, 288230380379570176] assert [f_closed(n) for n in range(7)] == closed assert [f_unclosed(n) for n in range(7)] == unclosed assert [f_sharp(n) for n in range(7)] == sharp assert [f_blunt(n) for n in range(7)] == blunt assert [f_total(n) for n in range(7)] == total for n in range(7): assert closed[n] == blunt[n] - sharp[n] assert unclosed[n] == 2 * sharp[n] assert sharp[n] == blunt[n] - closed[n] assert blunt[n] == sharp[n] + closed[n] == (total[n] + closed[n]) / 2 assert total[n] == sharp[n] + blunt[n] == closed[n] + unclosed[n]

A227725 ${\displaystyle T(n,k)}$ is the number of ${\displaystyle n}$-ary families of size ${\displaystyle 2^{k}}$.
A227724 ${\displaystyle T(n,k)}$ is the number of balanced ${\displaystyle n}$-ary families of size ${\displaystyle 2^{k}}$.
A054724 ${\displaystyle T(n,w)}$ is the number of ${\displaystyle n}$-ary families with weight ${\displaystyle w}$. See here.

Sharp families always have the maximal size.
Each member of sharp family has a unique consul, while all members of a blunt family have the same consul.
All sharp families belong to the same tribe. The tribe of a blunt family is denoted by the binary weight of the consul.

It is easy to calculate a family representative of a sharp BF (a male to be precise), namely the one with consul 0.

There are many bijections between blunt and sharp BF.
It would be practical to have one, that assigns all members of a blunt family to members of the same sharp family.
So one sharp family would correspond to a set of blunt families. That would be nice to have, but may not exist.

An important fact (visible in the table of sequences above) is that the number of blunt families is equal to the number of super-families.
The numbers of sharp and closed (self-complementary) families always sum up to the number of blunt families (= the number of super-families).
Arity 1 is a special case, because the one sharp and the one closed family are the same. Apart from that, no sharp familiy is closed.

sharp to unclosed blunt

These images show the 32 unclosed families for arity 3 within their super-families. On the left are the 16 (unclosed) sharp families. On the right are the 16 unclosed blunt families truth tables 0 255 3, 12, 48, 192 63, 207, 243, 252 5, 10, 80, 160 95, 175, 245, 250 6, 9, 96, 144 111, 159, 246, 249 17, 34, 68, 136 119, 187, 221, 238 18, 33, 72, 132 123, 183, 222, 237 20, 40, 65, 130 125, 190, 215, 235 24, 36, 66, 129 126, 189, 219, 231 Zhegalkin indices The families on the left belong to two villages, which correspond to the rows of the 2×8 grid. Those on the right belong to four villages, which correspond to the columns. 128 130 132 134 144 146 148 150 0 1 64, 68, 80, 85 65, 69, 81, 84 32, 34, 48, 51 33, 35, 49, 50 96, 102, 112, 119 97, 103, 113, 118 8, 10, 12, 15 9, 11, 13, 14 72, 76, 90, 95 73, 77, 91, 94 40, 42, 60, 63 41, 43, 61, 62 106, 108, 120, 127 107, 109, 121, 126

closed

These images show the 14 closed (blunt) families for arity 3. On the left are the linear functions except contradiction and tautology. Their Walsh indices 1...7 go from top left to bottom right. On the right are the families with size 8. Their consuls correspond to the Walsh indices on the left. truth tables 85, 170 51, 204 102, 153 15, 240 90, 165 60, 195 105, 150 Zhegalkin indices 2, 3 4, 5 6, 7 16, 17 18, 19 20, 21 22, 23

twin prefects of blunt families
The twin prefect (prefect of the twin) is the essentially the consul, but refined by a sign. The eight images below are in the same 2×8 grid as the matrices shown above. (Here truth tables and Zhegalkin indices are shown within the same image.) The blunt families shown above (extroverted and introverted) are within these patterns. 0 ¬1 ¬2 3 ¬4 5 6 ¬7

The following table shows the 46 3-ary families within the 14 super-clans. That means, each family is shown in its clan, and together with its complement.
In each matrix a family has a distinct color. Complements have the same base color (RGB or beige). Clans have the same shade (light or dark).
(The number of families in a super-clan is 1, 2, 3 or 6.)

tables of super-clans

sharp families by quaestor weight quaestor weight 1 quaestor weight 3 sharp (unclosed) f/c weight quaestor weight rep. truth tables Zhegalkin indices reverse 1 1, 7 1 128 128 Ж 128 1 3, 5 3 150 22 Ж 150 3 3, 5 3 130 42 Ж 130 3 3, 5 1 134 230 Ж 134 blunt unclosed f/c family size weight consul weight quaestor weight rep. truth tables Zhegalkin indices reverse 1 1 0, 8 0 0 0 0 Ж 0 1 4 2, 6 3 0 106 66 Ж 106 3 4 2, 6 2 2 40 40 Ж 40 3 4 2, 6 1 2 8 136 Ж 8 blunt closed f/c family size consul weight quaestor weight 🤥 rep. truth tables Zhegalkin indices reverse 1 2 0 4 honest 22 150 Ж 22 3 2 0 4 honest 2 170 Ж 2 3 2 0 0 honest 6 102 Ж 6 1 8 3 4 dishonest 104 232 Ж 104 3 8 1 2 dishonest 24 120 Ж 24 3 8 2 2 dishonest 44 228 Ж 44

The following table shows the 46 3-ary families within the 30 super-families. That means, each family is shown together with its complement.
An important property (that links the 3-ary to 2-ary families) is the village – seen as columns in the matrices of Zhegalkin indices.
Blunt families have a consul and a solidity. (Sharp families have four solid and four fluid members.)

tables of super-families

sharp (unclosed) weight quaestor weight reps. truth tables Zhegalkin indices village sc sf size reverse rep. 1, 7 1 Ж 128 128 128 Ж 128 4 {1, 3, 5, 15} T {8, 4, 2, 1} Z {8, 12, 10, 15} 128 8 Ж 8 3, 5 3 Ж 130 130 42 Ж 130 4 {1, 3, 5, 15} T {8, 4, 2, 1} Z {8, 12, 10, 15} 130 8 Ж 8 3, 5 3 Ж 130 132 76 Ж 132 4 {1, 3, 5, 15} T {8, 4, 2, 1} Z {8, 12, 10, 15} 132 8 Ж 8 3, 5 1 Ж 134 134 230 Ж 134 4 {1, 3, 5, 15} T {8, 4, 2, 1} Z {8, 12, 10, 15} 134 8 Ж 8 3, 5 3 Ж 130 144 112 Ж 144 4 {7, 9, 11, 13} T {14, 7, 11, 13} Z {14, 9, 13, 11} 144 7 Ж 9 3, 5 1 Ж 134 146 218 Ж 146 4 {7, 9, 11, 13} T {14, 7, 11, 13} Z {14, 9, 13, 11} 146 7 Ж 9 3, 5 1 Ж 134 148 188 Ж 148 4 {7, 9, 11, 13} T {14, 7, 11, 13} Z {14, 9, 13, 11} 148 7 Ж 9 3, 5 3 Ж 150 150 22 Ж 150 4 {7, 9, 11, 13} T {14, 7, 11, 13} Z {14, 9, 13, 11} 150 7 Ж 9 blunt unclosed size weight consul 🧊 quaestor weight reps. truth tables Zhegalkin indices village sc sf size reverse rep. 1 0, 8 0 0 fluid 0 Ж 0 0 0 Ж 0 1 {0} T {0} Z {0} 0 0 Ж 0 4 2, 6 1 4 solid 2 Ж 8 8 136 Ж 8 1 {0} T {0} Z {0} 8 0 Ж 0 4 2, 6 1 2 solid 2 Ж 8 32 160 Ж 32 2 {4, 12} T {10, 5} Z {2, 3} 32 10 Ж 2 4 2, 6 2 6 fluid 2 Ж 40 40 40 Ж 40 2 {4, 12} T {10, 5} Z {2, 3} 40 10 Ж 2 4 2, 6 1 1 fluid 2 Ж 8 64 192 Ж 64 2 {2, 10} T {12, 3} Z {4, 5} 64 12 Ж 4 4 2, 6 2 5 solid 2 Ж 40 72 72 Ж 72 2 {2, 10} T {12, 3} Z {4, 5} 72 12 Ж 4 4 2, 6 2 3 solid 2 Ж 40 96 96 Ж 96 2 {6, 14} T {6, 9} Z {6, 7} 96 6 Ж 6 4 2, 6 3 7 fluid 0 Ж 106 106 66 Ж 106 2 {6, 14} T {6, 9} Z {6, 7} 106 6 Ж 6 blunt closed size consul 🧊 🤥 quaestor weight reps. truth tables Zhegalkin indices village sc sf size reverse rep. 2 0 0 fluid honest 4 Ж 2 2 170 Ж 2 1 {0} T {0} Z {0} 2 0 Ж 0 2 0 0 fluid honest 4 Ж 2 4 204 Ж 4 1 {0} T {0} Z {0} 4 0 Ж 0 2 0 0 fluid honest 0 Ж 6 6 102 Ж 6 1 {0} T {0} Z {0} 6 0 Ж 0 2 0 0 fluid honest 4 Ж 2 16 240 Ж 16 1 {8} T {15} Z {1} 16 15 Ж 1 2 0 0 fluid honest 0 Ж 6 18 90 Ж 18 1 {8} T {15} Z {1} 18 15 Ж 1 2 0 0 fluid honest 0 Ж 6 20 60 Ж 20 1 {8} T {15} Z {1} 20 15 Ж 1 2 0 0 fluid honest 4 Ж 22 22 150 Ж 22 1 {8} T {15} Z {1} 22 15 Ж 1 8 1 4 solid dishonest 2 Ж 24 24 120 Ж 24 1 {8} T {15} Z {1} 24 15 Ж 1 8 1 2 solid dishonest 2 Ж 24 36 108 Ж 36 2 {4, 12} T {10, 5} Z {2, 3} 36 10 Ж 2 8 2 6 fluid dishonest 2 Ж 44 44 228 Ж 44 2 {4, 12} T {10, 5} Z {2, 3} 44 10 Ж 2 8 1 1 fluid dishonest 2 Ж 24 66 106 Ж 66 2 {2, 10} T {12, 3} Z {4, 5} 66 12 Ж 4 8 2 5 solid dishonest 2 Ж 44 74 226 Ж 74 2 {2, 10} T {12, 3} Z {4, 5} 74 12 Ж 4 8 2 3 solid dishonest 2 Ж 44 98 202 Ж 98 2 {6, 14} T {6, 9} Z {6, 7} 98 6 Ж 6 8 3 7 fluid dishonest 4 Ж 104 104 232 Ж 104 2 {6, 14} T {6, 9} Z {6, 7} 104 6 Ж 6

3-ary partitions: family (46), reverse family (46), super family (30), ultra family (18), family size (4), quaestor weight (5), tribe (5), is sharp (2)

• c:Category:3-ary truth tables in octeract matrix; ultra-families
• c:Category:3-ary Boolean functions in octeract matrix; super-clans
• c:Category:3-ary Boolean functions in octeract matrix; reverse super-clans

• c:Category:3-ary Boolean functions; small equivalence classes; cubes
• c:Category:Walsh spectra of 3-ary Boolean functions; families

• c:Category:Family to senior nobles to prefects (image set)