On the enumeration of Boolean functions with distinguished variables
- PDF / 380,558 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 9 Downloads / 239 Views
FOCUS
On the enumeration of Boolean functions with distinguished variables Josep Freixas1
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Boolean functions have a fundamental role in neural networks and machine learning. Enumerating these functions and significant subclasses is a highly complex problem. Therefore, it is of interest to study subclasses that escape this limitation and can be enumerated by means of sequences depending on the number of variables. In this article, we obtain seven new formulas corresponding to enumerations of some subclasses of Boolean functions. The versatility of these functions does the problem interesting to several different fields as game theory, hypergraphs, reliability, cryptography or logic gates. Keywords Boolean functions · 2-Monotonic Boolean functions · Simple games · Complete games · Enumeration of Boolean functions · Dedekind’s problem
1 Introduction Since its origins, mathematics has been interested in classifying and listing the set of solutions to a given problem. As quoted in Hardy (1999) ‘to enumerate a set of objects satisfying some set of properties means to explicitly produce a listing of all such objects.’ Enumerating special types of Boolean functions or simple games is useful for the design of circuits and real-world voting systems that fulfill some desirable properties. This paper concerns enumerations of these structures. A Boolean function has as input n Boolean variables (that is, values that can be either false or true) and produces as output another Boolean variable. It is monotonic if, for every combination of inputs, switching one of the inputs from false to true can only cause the output to switch from false to true and not from true to false. More precisely, a monotonic Boolean function of n variables (or, for short, a function) is a mapping f : {0, 1}n → {0, 1} such that: x ≤ y implies f (x) ≤ f (y). The Dedekind’s problem is given by the sequence M(n) and is the number of monotonic Boolean functions of n variables, or the number of antichains of subsets of an n-set, or the number of elements in a free disCommunicated by Marcello Sanguineti.
B 1
Josep Freixas [email protected] Universitat Politècnica de Catalunya, Av. Bases de Manresa, 61-73, 08242 Manresa, Spain
tributive lattice on n generators, or the number of Sperner families. Recall that an antichain of sets (also known as a Sperner family) is a family of sets, none of which is contained in any other set. The values of the sequence M(n) for the first eight integers are known: 2, 3, 6, 20, 168, 7581, 7,828,354, 2,414,682,040,998, 56,130,437,228,687,557,907,788 (see sequence A000372 in the On-Line Encyclopedia of Integer Sequences, Sloane 1964). The (inequivalent) Dedekind’s number S(n) is the number of different monotonic Boolean functions on n variables that do not differ in the name of the variables. If two Boolean functions are only differentiated in the labels, they are said to be equivalent. Thus, S(n) counts the number of inequivalent monotonic Boolean funct
Data Loading...
