Journal of Integer Sequences, Vol. 28 (2025), Article 25.6.5

Counting Self-Dual Monotone Boolean Functions


Bartłomiej Pawelski and Andrzej Szepietowski
Institute of Informatics
University of Gdańsk
80-952 Gdańsk
Poland

Abstract:

Let Dn denote the set of monotone Boolean functions with n variables. The cardinality of Dn, denoted by dn, is known as the n-th Dedekind number. Elements of Dn can be represented as strings of bits of length 2n. For each fDn, we have the dual function f*Dn which is obtained by reversing and negating all bits. An element fDn is self-dual if f = f*. Let Λn denote the set of all self-dual monotone Boolean functions of n variables and let λn denote |Λn|. There is a natural action of the permutation group Sn on the set of Boolean functions by permutation of variables. The sets Dn and Λn are closed under this action. We let Rn and Qn denote the sets of all equivalence classes in Dn and Λn, respectively. In this paper, we derive several algorithms for counting self-dual monotone Boolean functions and confirm the known result that λ9 equals 423,295,099,074,735,261,880. Furthermore, we calculate |Q8| to be 6,001,501.


Full version:  pdf,    ps,    latex    


(Concerned with sequences A001206 A008840.)


Received February 26 2024; revised versions received December 11 2024; June 12 2025; October 22 2025. Published in Journal of Integer Sequences, October 31 2025.


Return to Journal of Integer Sequences home page