One of the problems of modern discrete mathematics is Dedekind's problem on the number of monotone booleanfunctions. For other precomplete classes, general formulas for the number of functions of the classes had ...
详细信息
One of the problems of modern discrete mathematics is Dedekind's problem on the number of monotone booleanfunctions. For other precomplete classes, general formulas for the number of functions of the classes had been found, but it has not been found so far for the class of monotone booleanfunctions. Within the framework of this problem, there are problems of a lower level. One of them is the absence of a general formula for the number of booleanfunctions of intersection MS of two classes-the class of monotone functions and the class of self-dualfunctions. In the paper, new lower bounds are proposed for estimating the cardinality of the intersection for both an even and an odd number of variables. It is shown that the majorityvoting function of an odd number of variables is monotone and self-dual. The majorityvoting function of an even number of variables is determined. Free votingfunctions, which are functions with fictitious variables similar in properties to majorityvotingfunctions, are introduced. Then the union of a set of majorityvotingfunctions and a set of free votingfunctions is considered, and the cardinality of this union is calculated. The resulting value of the cardinality is proposed as a lower bound for vertical bar MS vertical bar. For the class MS of monotone self-dualfunctions of an even number of variables, the lower bound is improved over the bounds proposed earlier, and for functions of an odd number of variables, the lower bound for vertical bar MS vertical bar is presented for the first time.
暂无评论