Analysis and Recurrent Computation of MBF of the Maximum Types

Autor:	V G Tkachenco, O V Sinyavsky
Rok vydání:	2019
Předmět:	Combinatorics Continuation Environmental Engineering Monotone boolean function Computer science Computation Enumeration Partition (number theory) Industrial and Manufacturing Engineering
Zdroj:	Computer Science and Information Technology. 7:72-81
ISSN:	2331-6071 2331-6063
DOI:	10.13189/csit.2019.070303
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::0fb6af53f84197b395c63eb0db82ec48 https://doi.org/10.13189/csit.2019.070303 Zobrazit plný text záznamu