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.

Published in:
[Proceedings of the 28th International Workshop on Logic & Synthesis (IWLS 2019)]
Presented at:
28th International Workshop on Logic & Synthesis (IWLS 2019), Lausanne, Switzerland, June 21-23, 2019
Jun 21 2019

Note: The status of this file is: Anyone

 Record created 2019-09-27, last modified 2020-04-20

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)