Counting self-dual monotone Boolean functions

2023/10/19 by Bartłomiej Pawelski, Pawelski, Bartłomiej, Andrzej Szepietowski +1 · 1 citation
Computer Science · #06E30 #Advanced Algebra and Logic #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2310.12637

openalex publication_date 2023/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let D_n denote the set of monotone Boolean functions with n variables. Elements of D_n can be represented as strings of bits of length 2ⁿ. Two elements of D₀ are represented as 0 and 1 and any element g∈ D_n, with n>0, is represented as a concatenation g₀⋅ g₁, where g₀, g₁∈ D_n-1 and g₀≤ g₁. For each x∈ D_n, we have dual x^*∈ D_n which is obtained by reversing and negating all bits. An element x∈ D_n is self-dual if x=x^*. Let λ_n denote the cardinality of the set of all self-dual monotone Boolean functions of n variables. The value λ_n is also known as the n-th Hosten-Morris number. In this paper, we derive several algorithms for counting self-dual monotone Boolean functions and confirm the known result that λ₉ equals 423,295,099,074,735,261,880.

Cited by

• Finite-n Estimate of Dedekind Numbers by Layer-Ratio Monte Carlo

Related

• Counting inequivalent monotone Boolean functions
• On the number of inequivalent monotone Boolean functions of 9 variables
• Counting unate and balanced monotone Boolean functions
• On the number of inequivalent monotone Boolean functions of 8 variables
• Counting interval sizes in the poset of monotone Boolean functions