The Complexity of Self-Dual Monotone 7-Input Functions

The study of the complexity of Boolean functions has recently found applications in logic synthesis and optimization algorithms, as for instance in logic rewriting. Previous works have focused on the minimum length of Boolean chains for functions up to 5 inputs, being represented in terms of 2- and 3-input operators. In this work, we study the complexity of selfdual monotone 7-input Boolean functions in terms of 3-input majority operators. We use enumeration-based and SAT-based exact methods to find (i) the minimum number of operators in the shortest formula of a Boolean function, and (ii) the minimum length of its Boolean chain. Different generalizations and restrictions of majority Boolean chains are considered to represent functions. For instance, we consider leafy Boolean chains in which each step has at least one fanin that is an input variable, or majority Boolean chains that use complemented edges.