RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1999 Volume 11, Issue 4, Pages 127–138 (Mi dm398)

This article is cited in 2 papers

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

V. Jovović, G. Kilibarda


Abstract: 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.

UDC: 519.7

Received: 12.11.1998

DOI: 10.4213/dm398


 English version:
Discrete Mathematics and Applications, 1999, 9:6, 593–605

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024