Studies of Euler diagrams/NP

dummy

Functions in the same NP equivalence class (EC) have Euler diagram with the same shape.

The functions in it can be turned into each other with transformations.
They negate and permute the arguments, i.e. they are signed permutations.

A diagram's symmetry determines the cardinality of the EC, i.e. the number of functions in it.

Let any function in the EC have $k$ transformations to itself. Then the diagram's symmetry group has $k$ elements, and the cardinality of the EC is ${\frac {2^{n}\cdot n!}{k}}$.

So the ECs with the hightest possible cardinality of $2^{n}\cdot n!$ are those whose diagrams have no symmetry.
For arity $n=3$ that would be $8\cdot 6=48$, but no such EC exists. (The hightest cardinality is 24.)
For arity $n=4$ that is $16\cdot 24=384$. An example is the EC of dakota and tinora. See table.

The highest symmetry and lowest cardinality is always in the EC of the multigrade XOR. An example is the EC of selera. See table.

EC of dukeli

diagrams of dukeli and another function in the same EC

The diagrams are mirror symmetric, so the cardinality is 192. (All 382 diagrams are shown, i.e. both mirror images for each function.)

Compare the transformations between dukeli and pamina.

tables

Each NP equivalence class can be partitioned into permutation and negation ECs.
Within the conventions of this project, the P-ECs are rows, and the N-ECs are groups of columns.

The following table shows the NP-EC of takate (Ж 30) and its complement gilera (Ж 31).    (The complements make this an NPN-EC.)

Its contains 24 functions. The columns partition it into 3 N-ECs, each with 8 functions. The rows partition it into 6 P-ECs.
The four rows with mirror symmetric Venn diagrams contain 3, and the other two rows contain 6 functions.
The N-ECs always have the same size, while that of the P-ECs can vary.

W	C			24		36		66
2	3	24	&3_3 3	24 (0, 1, 2) (1, 0, 2)		36 (0, 2, 1) (2, 0, 1)		66 (1, 2, 0) (2, 1, 0)
3	3	25	&2_2 2	25 (0, 1, 2) (1, 0, 2)		37 (0, 2, 1) (2, 0, 1)		67 (1, 2, 0) (2, 1, 0)
3	6	26	&2_2 2	26 (0, 1, 2) (1, 0, 2)	28 (1, 0, 2) (0, 1, 2)	38 (0, 2, 1) (2, 0, 1)	52 (2, 0, 1) (0, 2, 1)	70 (1, 2, 0) (2, 1, 0)	82 (2, 1, 0) (1, 2, 0)
4	6	27	&1_1 1	27 (0, 1, 2) (1, 0, 2)	29 (1, 0, 2) (0, 1, 2)	39 (0, 2, 1) (2, 0, 1)	53 (2, 0, 1) (0, 2, 1)	71 (1, 2, 0) (2, 1, 0)	83 (2, 1, 0) (1, 2, 0)
4	3	30	&0_0 0	30 (0, 1, 2) (1, 0, 2)		54 (0, 2, 1) (2, 0, 1)		86 (1, 2, 0) (2, 1, 0)
5	3	31	&1_1 1	31 (0, 1, 2) (1, 0, 2)		55 (0, 2, 1) (2, 0, 1)		87 (1, 2, 0) (2, 1, 0)

The following tables show NP-ECs with only one N-EC.

These contain the 2-ary OR (Ж 14) and the 3-ary OR (Ж 254):

W C 9 2 1 9 &0_0 0 9 (0, 1) (1, 0) 3 2 11 &1_1 1 11 (1, 0) (0, 1) 13 (0, 1) (1, 0) 3 1 14 &2_2 2 14 (0, 1) (1, 0)

W C 129 2 1 129 &0_0 0 129 (0, 1, 2) (1, 0, 2) (0, 2, 1) (2, 0, 1) (1, 2, 0) (2, 1, 0) 3 3 137 &1_1 1 137 (2, 0, 1) (2, 1, 0) (0, 2, 1) (1, 2, 0) (0, 1, 2) (1, 0, 2) 161 (1, 0, 2) (1, 2, 0) (0, 1, 2) (2, 1, 0) (0, 2, 1) (2, 0, 1) 193 (0, 1, 2) (0, 2, 1) (1, 0, 2) (2, 0, 1) (1, 2, 0) (2, 1, 0) 5 3 171 &2_2 2 241 (0, 1, 2) (1, 0, 2) (0, 2, 1) (1, 2, 0) (2, 0, 1) (2, 1, 0) 205 (0, 2, 1) (2, 0, 1) (0, 1, 2) (2, 1, 0) (1, 0, 2) (1, 2, 0) 171 (1, 2, 0) (2, 1, 0) (1, 0, 2) (2, 0, 1) (0, 1, 2) (0, 2, 1) 7 1 254 &3_3 3 254 (0, 1, 2) (1, 0, 2) (0, 2, 1) (2, 0, 1) (1, 2, 0) (2, 1, 0)

The number of P-ECs is at least 2.
These contain the multigrade XOR (Ж 22) and the complement of equality (Ж 126):

W C 22 3 1 22 &4_13 1 3 22 (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0) (1, 0, 2) (2, 0, 1) (0, 1, 2) (2, 1, 0) (0, 2, 1) (1, 2, 0) (1, 2, 0) (2, 1, 0) (0, 2, 1) (2, 0, 1) (0, 1, 2) (1, 0, 2) (0, 1, 2) (1, 0, 2) (0, 2, 1) (2, 0, 1) (1, 2, 0) (2, 1, 0) 4 1 23 &2_02 0 2 23 (0, 1, 2) (1, 0, 2) (0, 2, 1) (2, 0, 1) (1, 2, 0) (2, 1, 0) (0, 1, 2) (1, 0, 2) (0, 2, 1) (2, 0, 1) (1, 2, 0) (2, 1, 0) (0, 2, 1) (1, 2, 0) (0, 1, 2) (2, 1, 0) (1, 0, 2) (2, 0, 1) (2, 0, 1) (2, 1, 0) (1, 0, 2) (1, 2, 0) (0, 1, 2) (0, 2, 1)

W C 107 5 3 107 &3_12 1 2 107 (0, 1, 2) (0, 2, 1) (1, 0, 2) (2, 0, 1) (1, 2, 0) (2, 1, 0) (1, 2, 0) (2, 1, 0) (1, 0, 2) (2, 0, 1) (0, 1, 2) (0, 2, 1) 109 (1, 0, 2) (1, 2, 0) (0, 1, 2) (2, 1, 0) (0, 2, 1) (2, 0, 1) (0, 2, 1) (2, 0, 1) (0, 1, 2) (2, 1, 0) (1, 0, 2) (1, 2, 0) 121 (2, 0, 1) (2, 1, 0) (0, 2, 1) (1, 2, 0) (0, 1, 2) (1, 0, 2) (0, 1, 2) (1, 0, 2) (0, 2, 1) (1, 2, 0) (2, 0, 1) (2, 1, 0) 6 1 126 &3_03 0 3 126 (0, 1, 2) (1, 0, 2) (0, 2, 1) (2, 0, 1) (1, 2, 0) (2, 1, 0) (0, 1, 2) (1, 0, 2) (0, 2, 1) (2, 0, 1) (1, 2, 0) (2, 1, 0)