On the enumeration of some inequivalent monotone Boolean functions

Abstract

This paper considers inequivalent monotone Boolean functions of an arbitrary number of variables, two monotone Boolean functions are equivalent if one can be obtained from the other by permuting the variables. It focuses on some inequivalent  monotone Boolean functions with three and four types of equivalent variables, where the variables are either dominant or dominated. The paper provides closed formulas for their enumeration as a function of the number of variables. The problem we deal with is very versatile since inequivalent monotone Boolean functions are monotonic simple games, structures that are used in many fields such as game theory, neural networks, artificial intelligence, reliability or multiple-criteria decision-making.

Keywords:

• Dedekind numbers
• inequivalent monotone Boolean functions
• simple games
• enumeration of tripartite and quadripartite simple games
• enumeration of Boolean functions

Mathematics Subject Classifications:

• 40B05
• 65Q30
• 68R05
• 91A12
• 91A80
• 91B12

Disclosure statement

No potential conflict of interest was reported by the author.

Additional information

Funding

This publication is part of the I+D+i project/PID2019-104987GB-I00, financed by MCIN/AEI/10.13039/501100011033/; Spanish Ministry of Science and Innovation.