View source for Studies of Euler diagrams/NP tables

{{EuDi}}
::<small style="opacity: .5;">''These tables are in category {{c|Studies of Euler diagrams; templates; NP tables}}.''</small>

The natural subdivisions of an [[Equivalence classes of Boolean functions#NP|NP equivalence class]] are [[Equivalence classes of Boolean functions#P|permutation]] and [[Equivalence classes of Boolean functions#N|negation]] equivalence classes.

These tables show all functions of an NP-EC <small>(hereafter just EC)</small> with the P-ECs as rows and the N-ECs as groups of columns.

The functions are represented by their [[Zhegalkin matrix|Zhegalkin indices]], and the order of the rows and columns is based on these numbers.<br>
<small>
The chosen representative is highlighted in violet, and its name is shown in the header.<br>
The [[Studies of Euler diagrams/transformations|transformations]], denoted by number icons, refer to this representative. (Otherwise it has no influence on the table.)
</small>

The following table shows the EC of {{boolfname|takate}} {{zhe|30}} and its complement {{boolflink|gilera}} {{zhe|31}}.<br>
It has three N-ECs, each with 8 functions.<br>
Its six P-ECs contain 3 functions if the Venn diagrams are symmetric, or 6 functions if they are not.

{{Collapsible START|EC 6 &nbsp; {{boolfname|takate}}|open boolf-np}}
{{Studies of Euler diagrams/takate NP table}}
{{Collapsible END}}


{{Collapsible START|mouseovers of Zhegalkin indices|open light}}
{|
|style="vertical-align: top;"|
Hovering over the numbers will show a mouseover.<br>
Its first line is the Zhegalkin index in little-endian binary <small>(which corresponds to the [[algebraic normal form]])</small>.<br>
The second line is the truth table of the Boolean function.<br>
The screenshot on the right shows a mouseover in the table above.<br>
<small>(The diagram to its right shows how the second line is derived from the first.)</small>
|
{{multiple image
 | align = left | total_width = 220
 | image1 = EuDi; NP table screenshot; takate 38 zhe.png
 | image2 = ANF to 0110 0011.svg
}}
|}
{{Collapsible END}}


The number icons denote the [[Studies of Euler diagrams/transformations|transformations]] from the representative to each particular function.<br>
A transformation is a signed permutation, i.e. a negator pattern paired with a permutation &mdash; both of which can be represented by a natural number.<br>
While the permutation index numbers are unambiguous, there is some potential confusion about numbering the negator patterns.<br>
Generally it is more useful to refer to which ''values'' are negated. <small>(See [[Full octahedral group#8×6 matrix|this 8×6 matrix]].)</small><br>
But functions in the same P-EC have the same negated ''places'' in common &mdash; which are thus used as row labels in these tables.<br>
To avoid confusion, the icons referring to negated values are round, and those referring to negated places are square.

{{Collapsible START|signed permutation (~1, 2, ~0)|collapsed light}}
{|
|
This signed permutation is based on the permutation (1, 2, 0) with the index number [[File:Finite permutation number 4.svg|20px]].<br>
The distribution of negators will usually be described as (1, 1, 0) [[File:Cube vertex number 3.svg|20px]], based on which values are negated. <small>(Seen in the rows of the matrix.)</small><br>
But it can also be described as (1, 0, 1) [[File:Cube vertex number 5 in square.svg|20px]], based on which places are negated. <small>(Seen in the columns of the matrix.)</small>
|rowspan="2" style="padding-left: 50px;"|
[[File:Cube permutation 3 4.svg|240px|border]]
|-
|
<source lang="python">
from discretehelpers.sig_perm import SigPerm


sigperm = SigPerm(valneg_index=3, perm_index=4)

sigperm.sequence_string()
# '(~1, 2, ~0)'

sigperm.matrix()
# array([[ 0,  0, -1],
#        [-1,  0,  0],
#        [ 0,  1,  0]])

sigperm.keyneg_index
# 5
</source>
|}
{{Collapsible END}}<!-- signed permutation example-->

So each function corresponds to a set of transformations.<br>
To such a set corresponds a set of <abbr title="key (i.e. place) negation">keyneg</abbr> indices,
a set of <abbr title="value negation">valneg</abbr> indices and a set of <abbr title="permutation">perm</abbr> indices.<br>
P-ECs (rows) have the same set of keyneg indices,
and N-ECs (column groups) have the same set of perm indices in common.<br>
<small>The sets of perm indices are {{w|cosets}} of The {{w|symmetric group}} <math>S_n</math>, where <math>n</math> is the arity. (See {{w|Subgroup#Subgroups of S4|Subgroups of S<sub>4</sub>}}.)</small><br>
The valneg set is shown under each Zhegalkin index. Hovering over it will show a table with the whole set of transformations.

{{Collapsible START|transformations from {{boolfname|takate}} {{zhe|30}} to {{boolfname|tabora}} {{zhe|38}}|open light}}
The representative function of the table above is {{boolfname|takate}} {{zhe|30}}.
The hover table is shown for {{boolfname|tabora}} {{zhe|38}}.<br>
Below is shown how the two transformations turn the Euler diagram of the former into (mirrored) Euler diagrams of the latter.

{| style="text-align: center;"
| [[File:EuDi; takate.svg|thumb|center|150px|{{boolfname|takate}}]]
|style="padding-left: 30px;"| [[File:EuDi; tabora.svg|thumb|center|150px|{{boolfname|tabora}}]]
|style="padding-left: 30px;"| [[File:EuDi; tabora mirrored.svg|thumb|center|150px|{{boolfname|tabora}}]]
|style="padding-left: 50px;"| [[File:EuDi; NP table screenshot; takate 38.png|158px|thumb|center|hover table]]
|-
|
|
[[File:Cube vertex number 5 in square.svg|20px]] &nbsp; [[File:Cube vertex number 3.svg|20px]]&hairsp;[[File:Finite permutation number 2.svg|20px]]<br><br>
<math>
\begin{pmatrix}
{\color{Red}~0} & {\color{ForestGreen}~1} & {\color{Blue}~2} \\
{\color{Red}\neg 0} & {\color{Blue}~2} & {\color{ForestGreen}\neg 1} \\
\end{pmatrix}
</math>
|
[[File:Cube vertex number 6 in square.svg|20px]] &nbsp; [[File:Cube vertex number 3.svg|20px]]&hairsp;[[File:Finite permutation number 3.svg|20px]]<br><br>
<math>
\begin{pmatrix}
{\color{Red}~0} & {\color{ForestGreen}~1} & {\color{Blue}~2} \\
{\color{Blue}~2} & {\color{Red}\neg 0} & {\color{ForestGreen}\neg 1} \\
\end{pmatrix}
</math>
|
|}
{{Collapsible END}}


Often the set of valneg indices of a function contains only a single element.<br>
Two are also common:

{{Collapsible START|EC 15 &nbsp; {{boolfname|makoto}}|collapsed boolf-np}}
{{Studies of Euler diagrams/makoto NP table}}
{{Collapsible END}}

There is only one 3-ary EC with three:

{{Collapsible START|EC 20 &nbsp; {{boolfname|berusa}}|collapsed boolf-np}}
{{Studies of Euler diagrams/berusa NP table}}
{{Collapsible END}}

Eight are an extreme case. This is very rare:<br>
{{Collapsible START|EC 317 &nbsp; {{boolfname|fidele}}|collapsed boolf-np}}
{{Studies of Euler diagrams/fidele NP table}}
{{Collapsible END}}
<small style="opacity: .5;">(This table is wider than most screens. The hover tables on the right can be seen by keeping the mouse on them, and pressing the right arrow key.)</small>