View source for Noble Boolean functions

{{Boolf header}}
{{Zhegalkin stuff}}
Noble Boolean functions are those who are their own [[Zhegalkin twins]], i.e. the binary expression of their [[Algebraic normal form|ANF]] is equal to their truth table.<br>
They correspond to {{w|Fixed point (mathematics)|fixed points}} in the [[Zhegalkin matrix#Zhegalkin permutation|Zhegalkin permutation]].<br>
They are all even, i.e. the first digit of their truth table is false.<br>
When a Boolean function is noble, its whole [[Boolf-EC#P|faction]] is noble.<br>
<small style="opacity: .5;">Within the [[Studies of Boolean functions|this project]] it is slightly misleading to apply the term ''noble'' to [[Boolf-term#BF|Boolean functions]]. It is a property of a [[Boolf-term#TT|truth table]] with a specific length.</small>

{{Zhegalkin matrix/Triangle Pi|collapsed}}

{{Zhegalkin matrix/Triangle Phi|collapsed}}

{{Collapsible START|3-ary nobles <small>(Venn diagrams)</small> assigned to juniors <small>(tesseract vertices)</small>|open gap-below}}
[[File:3-ary nobles in tesseract.svg|500px]]
{{Collapsible END}}

{{Collapsible START|3-ary and 4-ary nobles assigned to juniors <small>(in square matrices)</small>|collapsed gap-below}}
These matrices show the 2-ary and 3-ary Boolean functions, represented by the big gray integers <small>(corresponding to the truth tables)</small>.</small><br>
The small black integers above them are the senior nobles <small>(i.e. one arity above)</small>.<br>
<small style="opacity: .5;">(The highlighted big numbers are the king indices.)</small>
{|
| [[File:2T principality; overview.svg|thumb|center|250px|3-ary nobles]]
| [[File:3T principality; overview.svg|thumb|center|600px|4-ary nobles]]
|}
{{Collapsible END}}

{{Collapsible START|illustration of fixed points <math>\Phi_3</math> in permutation <math>\Pi_3</math>|collapsed gap-below}}
[[File:Zhegalkin 256; fixed.svg|1320px]]
{{Collapsible END}}

{{Collapsible START|<math>\Phi_3</math> as 8×16 matrix {{spaces|8}} <math>\Phi_4</math> as 16×256 matrix|collapsed  gap-below}}
[[File:Fixed points in Zhegalkin permutation 3.svg|thumb|left|195px|row 3]]
{{clear}}
[[File:Fixed points in Zhegalkin permutation 4.svg|thumb|left|1440px|row 4]]
{{clear}}
The images show how <math>\Phi_n</math> is derived from <math>\Pi_{n-1}</math>, the permutation of the same length.<br>
The long matrices have two halves:<br>
In the upper half the bit pattern in column <math>k</math> is that of <math>\Xi_{n-1,~k} ~ = ~ \Pi_{n-1,~k} \oplus k</math>.
&nbsp;&nbsp;&nbsp;<small>(Compare triangle Ξ in the next section.)</small><br>
The bit pattern in the lower half is identical to that of the gray column indices.

<math>\Phi_{n,~k} ~~ = ~~ \Xi_{n-1,~k} + \bigl(2^{2^{n-1}} \cdot k \bigr) ~~ = ~~ \bigl(\Pi_{n-1,~k} \oplus k \bigr) + \bigl(2^{2^{n-1}} \cdot k \bigr)</math>

The small matrices on the left are divided in the same way:<br>
The upper half is a Sierpiński triangle without the main diagonal, and the lower half is the main diagonal.

These properties of noble Boolean functions can be derived from this:<br>
* They are even, i.e. place 0 is always false.
* The 1-bit places (e.g. 1, 2, 4, 8) have the same truth value. <small>(Those where it is false/true shall be called weak/strong.)</small>
* Half of them are evil/odious, which is indicated by the last place being false/true. <small>(The odious ones are on the right, just like in triangle &Pi;.)</small>
{{Collapsible END}}

{{Noble Boolean functions/row sums}}

===quadrants===

It is easily seen, that the left and right half of each row differ only in the last digit.<br>
Those on the left/right have even/odd weight. They shall be called evil/odious.

{{Noble Boolean functions/Python half rows}}

There is a second way to partition the nobles in two halves:<br>
Those in even/odd places of the triangle row have false/true entries in all 1-bit places of their truth table. They shall be called weak/strong.

So the nobles can be partitioned into four quadrants by depravity and strength.

{{Collapsible START|illustration of quadrants for ''n'' &equals; 3|open}}
Vertically adjacent quadrants contain relative complements. Horizontally adjacent quadrants differ only in the central vertex.<br>
<small>(40 and 214 are relative complements. 40 and 168 differ only in the central vertex.)</small><br>

The 16 noble 3-ary Boolean functions form 8 factions. So there are 2 royal factions.
[[File:Noble 3-ary Boolean functions.svg|650px|center]]
{{Collapsible END}}

Nobles that are evil and weak shall be called '''''royal'''''.<br>
Each noble corresponds to a royal, and can easily be derived from it. <small style="opacity: .5;">(A royal corresponds to itself.)</small><br>
When a Boolean function is royal, its whole [[Boolf-EC#P|faction]] is royal.<br>
The function with the smallest Zhegalkin index in a faction shall be called '''''king''''', and be used to represent it.<br>
So all nobles of a given arity can effectively be represented by a rather short list of kings.

{{Noble Boolean functions/royal triangle|collapsed}}

{{Collapsible START|4-ary royals in 16×64 matrix|collapsed light gap-below}}
The columns of this matrix are the 4-ary royal Boolean functions.<br>
[[File:4-ary royal Boolean functions in matrix.svg|x180px]]<br>
Compare <math>\Phi_4</math> as 16×256 matrix, shown above.<br>
<small>The 16×6 matrix on the left is shown as the 16×8 matrix from that file, with the left and right column blacked out.</small>
{{Collapsible END}}

{{Noble Boolean functions/triangle of kings|collapsed}}

{{Collapsible START|representatives of 4-ary noble factions|collapsed}}
[[File:Representatives of 4-ary noble factions.svg|1200px]]

The top left corner in each 2×2 matrix is a king. The other corners are its equivalents in the other quadrants.<br>
<small style="opacity: .5;">(Vertically adjacent quadrants contain relative complements. Horizontally adjacent quadrants differ only in the central vertex.)</small>

The two tables below correspond to the image above. The one on the left shows the same numbers as the image.<br>
The one on the right shows the [[smallest Zhegalkin index]] for each of the 44 factions. <small style="opacity: .5;">(They differ only for the odd factions, i.e. those with green and blue background.)</small>

{| style="width: 100%;"
| {{Noble reps/outer/match}}
| {{Noble reps/outer/minimal}}
|}

The black integers are Zhegalkin indices. The gray numbers below are their noble indices, i.e. the positions in the sequence of nobles.<br>
The beige numbers in the image are faction sizes, i.e. the number of different permutations of the example shown.
{{Collapsible END}}

{{Collapsible START|4-ary kings|collapsed light gap-above}}
[[File:Representatives of 4-ary royal factions.svg|800px]]
{{Collapsible END}}

===group under exclusive or===

With XOR as a group operation the ''n''-ary noble and royal Boolean functions form a power of the {{w|cyclic group}} C<sub>2</sub>.

{{Collapsible START|Python example|collapsed light gap-below}}
The 3-ary nobles form the group C<sub>2</sub><sup>4</sup>.

The Python operator <code>^</code> represents the {{w|bitwise operation#XOR|bitwise XOR}}.

<source lang="python">
nobles = [0,  30,  40, 54,  72, 86, 96, 126, 128, 158, 168, 182, 200, 214, 224, 254]

for i, a in enumerate(nobles):
    for j, b in enumerate(nobles):
        assert nobles.index(a ^ b) == i ^ j
</source>

This works for any row of the noble triangle <math>\Phi</math>, or from the royal triangle. <small>(But not from the triangle of kings.)</small>
{{Collapsible END}}


==patrons==

The XOR of twins is noble, i.e. the XOR of a key and a value in <math>\Pi_n</math> is an entry of <math>\Phi_n</math>.<br>
For a Boolean function this means, that the XOR of its ANF and its truth table is a noble Boolean function, which shall be called its '''''patron'''''.<br>
The patron of a noble is the contradiction.

{{Zhegalkin matrix/triangle Xi|collapsed}}

For <math>n \ge 1</math> the entries in <math>\Xi_n</math> are repetitions of those in <math>\Phi_n</math>. <span style="opacity: .6;">E.g. <math>\Xi_2</math> contains the entries <math>\{0, 6, 8, 14\}</math>, each repeated four times.</span>

The set of places where <math>\Xi_n</math> has entries <math>\Phi_{n,~k}</math> can be calculated by XORing <math>\Pi_{n-1,~k}</math> with the entries of <math>\Phi_n</math>.

===3-ary Boolean functions with patron 168===

{{Zhegalkin matrix/matrix pi xor phi}}

{{Zhegalkin matrix/clusters with patron 168}}

{{Collapsible START|positions in matrix|collapsed gap-above}}
[[File:3-ary Boolean functions; patrons 10.svg|thumb|center|500px|Boolean functions with patron 168 in octeract matrix<br><small>(This is the transpose of [[c:File:3-ary Boolean functions; quaestor 03 (indices).svg|Zhegalkin indices with quaestor 3]].)</small>]]
{{Collapsible END}}


[[Category:Boolean functions; Zhegalkin stuff]]