Studies of Euler diagrams/clans

dummy


Functions in the same NP equivalence class (clan) have Euler diagrams 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 clan, i.e. the number of functions in it.

Let any function have transformations to itself. Then the diagram's symmetry group has elements, and the cardinality of the clan is .

So the clans with the hightest possible cardinality of are those whose diagrams have no symmetry.
For arity that would be , but no such clan exists. (The hightest cardinality is 24.)
For arity that is . An example is the clan of dakota. See table.

Apart from constants, multigrade XOR has the highest symmetry, and thus corresponds to the lowest cardinality of 2. An example is the that of selera. See table.


diagrams of dukeli and another function in the same clan

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.


Each clan can be partitioned into smaller equivalence classes based only on permutation (factions) or negation (families).
Within the conventions of this project, the factions are rows, while families partition the table in vertical stripes. (They shall be called columns.)

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

Its contains 24 functions. The columns partition it into 3 families, each with 8 functions. The rows partition it into 6 factions.
The four rows with mirror symmetric Venn diagrams contain 3, and the other two rows contain 6 functions.
The families always have the same size, while that of the factions 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 clans with only one family. They 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 factions is at least 2. These contain the multigrade XOR (Ж 22) and the complement of equality (Ж 126):

W C       
22
3 1 22 &4_13
13
    
 
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
02
    
 
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
12
      
 
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
03
  
 
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)