Analysis and Recurrent Computation of MBF of the Maximum Types

doi:10.13189/csit.2019.070303

Journals Information

Computer Science and Information Technology Vol. 7(3), pp. 72 - 81
DOI: 10.13189/csit.2019.070303
Reprint (PDF) (259Kb)

Analysis and Recurrent Computation of MBF of the Maximum Types

Tkachenco V. G. ¹^,*, Sinyavsky O. V. ²
¹ Institute of Radio, Television, Electronics, Odessa National Academy of Telecommunications n.a. A.S.Popov, Ukraine
² Department of Fundamental Sciences, Odessa Military Academy, Ukraine

ABSTRACT

This manuscript is a continuation of the research of monotone Boolean functions (MBF), using the MBF partition into types. An interesting connection is observed between the intersection of the groups of MBF stabilizers of n-1 rank and the number of isomorphic functions of the nth rank. The number of MBFs of the nth rank obtained from the MBF pairs of n-1 rank is computed. The examples of recursive construction of the MBF of the nth rank are shown. The partitioning of the MBF of maximal types into classes is given. The number of classes of functions of the nth rank is computed. A new classification of monotone Boolean function of maximal types into schemes has been developed. Such schemes are given for 3-7 ranks of the MBF. The dependencies between the maximal types of MBF of the nth rank and the n-1 rank are found, which makes it possible to reduce the MBF enumeration by constructing the equivalence classes of the nth rank from the equivalence classes of n-1 rank. The proposed methods are convenient for analyzing large MBF ranks.

KEYWORDS
Monotone Boolean Functions, MBF Types, Maximum Types, MBF Profile, MBF Schemes, MBF Equivalence Classes

Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Tkachenco V. G. , Sinyavsky O. V. , "Analysis and Recurrent Computation of MBF of the Maximum Types," Computer Science and Information Technology, Vol. 7, No. 3, pp. 72 - 81, 2019. DOI: 10.13189/csit.2019.070303.

(b). APA Format:
Tkachenco V. G. , Sinyavsky O. V. (2019). Analysis and Recurrent Computation of MBF of the Maximum Types. Computer Science and Information Technology, 7(3), 72 - 81. DOI: 10.13189/csit.2019.070303.