On the Number of Equivalence Classes of Boolean and Invertible Boolean Functions

被引:4
作者
Zivkovic, Miodrag [1 ]
Caric, Marko [2 ]
机构
[1] Univ Belgrade, Dept Informat, Fac Math, Belgrade 11000, Serbia
[2] Natl Bank Serbia, Belgrade 11000, Serbia
关键词
Boolean functions; invertible Boolean functions; permutation group; linear group; affine group; number of equivalence classes; cycle index; integer partitions; AFFINE;
D O I
10.1109/TIT.2020.3025767
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The number U-n of equivalence classes of Boolean functions of n variables and the number V-n of equivalence classes of vectorial Boolean functions of n variables under the action of four groups of transformations are considered. The four groups are the group S n of permutations of variables, the group Gn of permutations and complementations, the linear group GL (n, 2) and the affine group AGL (n, 2). Harrison obtained cycle indexes for these groups and the expressions for U-n and V-n in terms of the corresponding cycle index. He also tabulated the numbers U-n, V-n and the cycle indexes for n <= 6 for S n and Gn, and for n <= 5 for GL (n, 2) and AGL (n, 2). This bound was only recently slightly exceeded. Fripertinger implemented computation of cycle indexes for GL (n, q) and AGL (n, q); if q = 2 this implementation works for about n <= 21. By introducing appropriate precomputed tables, we reduced the cycle index computation to evaluation of a sum over partitions of n for all the four groups. Using this more efficient procedure, we obtained values of U-n, V-n and the explicit cycle index expressions for larger values of n.
引用
收藏
页码:391 / 407
页数:17
相关论文
共 20 条
[11]  
Harrison M.A., 1971, RECENT DEV SWITCHING, P85
[12]   THE NUMBER OF TRANSITIVITY SETS OF BOOLEAN FUNCTIONS [J].
HARRISON, MA .
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1963, 11 (03) :806-828
[13]   ON THE CLASSIFICATION OF BOOLEAN FUNCTIONS BY THE GENERAL LINEAR AND AFFINE GROUPS [J].
HARRISON, MA .
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1964, 12 (02) :285-299
[14]  
Lidl R., 1997, Encyclopedia of Mathematics and Its Applications, V20
[15]  
Lorens C. S., 1962, 21 SPAC GEN CORP
[16]   INVERTIBLE BOOLEAN FUNCTIONS [J].
LORENS, CS .
IEEE TRANSACTIONS ON COMPUTERS, 1964, EC13 (05) :529-&
[17]   Combinatorial number characterisation for groups, graphs and chemical compounds [J].
Polya, G .
ACTA MATHEMATICA, 1937, 68 (01) :145-254
[18]  
PRIMENKO EA, 1984, CYBERNETICS+, V20, P771, DOI 10.1007/BF01072161
[19]   ON THE NUMBER OF SYMMETRY TYPES OF BOOLEAN FUNCTIONS OF NORMAL-VARIABLES [J].
SLEPIAN, D .
CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1953, 5 (02) :185-193
[20]   Computing Affine Equivalence Classes of Boolean Functions by Group Isomorphism [J].
Zhang, Yan ;
Yang, Guowu ;
Hung, William N. N. ;
Zhang, Juling .
IEEE TRANSACTIONS ON COMPUTERS, 2016, 65 (12) :3606-3616