Abstract:
The problem of enumeration of all Boolean functions of n variables
of the rank k from the Post classes Fμ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
μ
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
μ=2,
k⩽8
(for
k⩽6 they are given at the end of this paper),
μ=3,4,
k⩽6,
and for every
n
were generated by a computer. As a consequence respective results
for the classes
Fμ5 are obtained.
Received: 12.11.1998
Bibliographic databases:
UDC:519.7
Language: Russian
Citation:
V. Jovović, G. Kilibarda, “On the number of Boolean functions in the Post classes Fμ8”, Diskr. Mat., 11:4 (1999), 127–138; Discrete Math. Appl., 9:6 (1999), 593–605
\Bibitem{JovKil99}
\by V.~Jovovi{\'c}, G.~Kilibarda
\paper On the number of Boolean functions in the Post classes $F_8^\mu$
\jour Diskr. Mat.
\yr 1999
\vol 11
\issue 4
\pages 127--138
\mathnet{http://mi.mathnet.ru/dm398}
\crossref{https://doi.org/10.4213/dm398}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1761018}
\zmath{https://zbmath.org/?q=an:0965.06017}
\transl
\jour Discrete Math. Appl.
\yr 1999
\vol 9
\issue 6
\pages 593--605
Linking options:
https://www.mathnet.ru/eng/dm398
https://doi.org/10.4213/dm398
https://www.mathnet.ru/eng/dm/v11/i4/p127
This publication is cited in the following 2 articles:
Kozyra P.M., “On the Number of Antichains and Antichain Covers of Labeled Sets”, J. Integer Seq., 24:4 (2021), 21.4.7
Ilya Shmulevich, Harri Lähdesmäki, Edward R. Dougherty, Jaakko Astola, Wei Zhang, “The role of certain Post classes in Boolean network models of genetic networks”, Proc. Natl. Acad. Sci. U.S.A., 100:19 (2003), 10734