On the number of Boolean functions in the Post classes $F_8^\mu$

V. Jovović ; G. Kilibarda

Diskretnaya Matematika, Tome 11 (1999) no. 4, pp. 127-138

Résumé

The problem of enumeration of all Boolean functions of $n$ variables of the rank $k$ from the Post classes $F^\mu_8$ is considered. This problem expressed in terms of the set theory is equivalent to the problem of enumeration of all $k$-families of different subsets of an $n$-set having the following property: any $\mu$ members of such a family have a non-empty intersection. A formula for calculating the cardinalities of these classes in terms of the graph theory is obtained. Explicit formulas for the cases $\mu=2$, $k\le 8$ (for $k\le 6$ they are given at the end of this paper), $\mu=3,4$, $k\le 6$, and for every $n$ were generated by a computer. As a consequence respective results for the classes $F^\mu_5$ are obtained.