The problem of counting all inequivalent monotone boolean functions of nine variables is considered. We solve the problem using known algorithms and deriving new ones when necessary. We describe methods to count fixed...
详细信息
The problem of counting all inequivalent monotone boolean functions of nine variables is considered. We solve the problem using known algorithms and deriving new ones when necessary. We describe methods to count fixed points in sets of all monotonebooleanfunctions under a given permutation of input variables. With these techniques as a basis, we tabulate the cardinalities of these sets for nine variables. By applying Burnside's lemma and the numbers obtained, we calculate the number of inequivalent monotone boolean functions of 9 variables, which equals 789,204,635,842,035,040,527,740,846,300,252,680.
This paper considers inequivalent monotone boolean functions of an arbitrary number of variables, two monotonebooleanfunctions are equivalent if one can be obtained from the other by permuting the variables. It focu...
详细信息
This paper considers inequivalent monotone boolean functions of an arbitrary number of variables, two monotonebooleanfunctions 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.
monotonebooleanfunctions (MBFs) are booleanfunctions f : {0, 1}(n) -> {0, 1} satisfying the monotonicity condition x <= y double right arrow f(x) <= f(y) for any x, y is an element of {0,1}(n)(.) The numbe...
详细信息
monotonebooleanfunctions (MBFs) are booleanfunctions f : {0, 1}(n) -> {0, 1} satisfying the monotonicity condition x <= y double right arrow f(x) <= f(y) for any x, y is an element of {0,1}(n)(.) The number of MBFs in n variables is known as the nth Dedekind number. It is a longstanding computational challenge to determine these numbers exactly: these values are only known for n at most 8. Two monotonebooleanfunctions are equivalent if one can be obtained from the other by permuting the variables. The number of inequivalent MBFs in n variables was known only for up to n = 6. In this paper we propose a strategy to count inequivalent MBFs by breaking the calculation into parts based on the profiles of these functions. As a result we are able to compute the number of inequivalent MBFs in 7 variables. The number obtained is 490013148. (C) 2013 Elsevier B.V. All rights reserved.
暂无评论