Counting self-dual monotone Boolean functions

Bartłomiej Pawelski; Andrzej Szepietowski

paper

Counting self-dual monotone Boolean functions

arXiv:2310.12637

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^{n}$ . Two elements of $D_{0}$ are represented as 0 and 1 and any element $g \in D_{n}$ , with $n > 0$ , is represented as a concatenation $g_{0} \cdot g_{1}$ , where $g_{0}, g_{1} \in D_{n - 1}$ and $g_{0} \leq g_{1}$ . For each $x \in D_{n}$ , we have dual $x^{*} \in D_{n}$ which is obtained by reversing and negating all bits. An element $x \in 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 $λ_{9}$ equals 423,295,099,074,735,261,880.