The Number of Monotone and Self-Dual Boolean Functions

L. Haviarova; E. Toman

doi:10.2478/jamsi-2014-0016

.blurhash-client-img { display: none !important; }

The Number of Monotone and Self-Dual Boolean Functions

Journal of Applied Mathematics, Statistics and Informatics

Volume 10 (2014): Issue 2 (December 2014)

By: L. Haviarova and E. Toman

Open Access

|Jan 2015

Abstract

In the present paper we study properties of pre-complete class of Boolean functions - monotone Boolean functions. We discuss interval graph, the abbreviated d.n.f., a minimal d.n.f. and a shortest d.n.f. of this function. Then we present a d.n.f. with the highest number of conjunctionsand we determinate the exact number of them. We count the number of monotone Boolean functions with some special properties. In the end we estimate the number of Boolean functionthat are monotone and self-dual at the same time.

References

[1] Yablonskiy S. V., Introduction into discrete mathematics, Moscow, Nauka, 1979 (in Russian).
Search in Google Scholar
[2] Yablonskiy S. V. and Lupanov O. B., Discrete mathematics and Mathematical Problems of Cybernetics, Nauka, Moscow, 1974, (in Russian)
Search in Google Scholar
[3] Sapozhenko A. A., Disjunctive Normal Forms, Moscow University Press, Moscow, 1975 (in Russian).
Search in Google Scholar
[4] Sapozhenko A. A., Geometric structure of almost all Boolean, Problemy kibernetiky, Vol. 30, 1975, 227-261, (in Russian)
Search in Google Scholar
[5] Zhuravlev J. I., Set theoretical methods in the algebra of logic, Problemy kibernetiki, Vol. 8, 1962, 5-44, (in Russian).
Search in Google Scholar
[6] Toman E., On the size of a neighbourhood of the first rank, Computers and Artificial Intelligence, Vol.12, No. 2, 1993, 123-130
Search in Google Scholar
[7] Daubner J. and Toman E., Vertex degree in the interval graph of a random Boolean function, Acta Mathematica Universitatis Comenianae, Vol. 79, No. 2, 2010, 151-164
Search in Google Scholar
[8] Toman E., Olejar D. and Stanek M., Average degree in the interval graph of a random Boolean function, Computing and Informatics, Vol. 27, 2008, 627-638
Search in Google Scholar
[9] Daubner J. and Toman E., Neighbourhood of the constant order in the interval graph of a random Boolean functionFundamenta Informaticae, 2012, Vol. 122, 1-2110.3233/FI-2013-790
Search in Google Scholar
[10] Toman E. and Tomanova J., Some estimates of the complexity of disjunctive normal forms of a random Boolean function, Computers and Artificial Intelligence, Vol. 10, No. 4, 1991, 327-340
Search in Google Scholar
[11] Graham, Knuth, Patashnik, Concrete Mathematics a Foundation for Computer Science, Addison-Wesley Publishing Company, 198910.1063/1.4822863
Search in Google Scholar
[12] Dedekind R., Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler, Gesammelte Werke, 1897, Vol. 2, 103-14810.1007/978-3-663-07224-9_1
Search in Google Scholar
[13] Church R., Numerical analysis of certain free distributive structures, Duke Mathematical Journal, 1940, Vol. 6, 732-73410.1215/S0012-7094-40-00655-X
Search in Google Scholar
[14] Ward M., Note on the order of free distributive lattices, Bulletin of the American Mathematical Society, 1946, Vol. 52, 42310.1090/S0002-9904-1946-08568-7
Search in Google Scholar
[15] Gilbert E. N., Lattice theoretic properties of frontal switching functions, J. Math. Physics, 1954, Vol. 33, 57-6710.1002/sapm195433157
Search in Google Scholar
[16] Yamamoto K., Note on the order of free distributive lattices, Science Reports of the Kanazawa University, 1953, Vol. 2, No. 1, 5-6
Search in Google Scholar
[17] [17] Hansel G., Sur le nombre des fonctions boolĂ©ennes monotones de variables, C. R. Acad. Sci. Paris, 1966, Vol. 262, No. 20, 1088-1090 (French)
Search in Google Scholar
[18] Markowsky G., Combinatorial aspects of lattice theory with applications to the enumeration of free distributive lattices, Ph.D. Thesis, Harvard University, 1973
Search in Google Scholar
[19] Kleitman D., Markowsky G., On Dedekind’s problem: the number of isotone Boolean functions. II, Transactions of the American Mathematical Society, 1975, Vol. 21, 373-39010.1090/S0002-9947-1975-0382107-0
Search in Google Scholar
[20] Yamamoto K., Logarithmic order of free distributive lattice, Journal of the Mathematical Society of Japan, 1954, Vol. 6, 343-35310.2969/jmsj/00630343
Search in Google Scholar
[21] Korshunov, A. D., The number of monotone Boolean functions, Problemy Kibernetiki, 1981, Vol. 38, 5-108
Search in Google Scholar
[22] Kleitman D., On Dedekind’s problem: the number of monotone Boolean functions, Proc. Amer. Math. Soc., 1969, Vol. 21, 677-68210.2307/2036446
Search in Google Scholar
[23] Post E., Introduction to a general theory of elementary propositions, American Journal of Mathematics, 1921, Vol. 4, 163-18510.2307/2370324
Search in Google Scholar
[24] Altun M. and Riedel M. D., A Study on Monotone Self-dual Boolean Functions, SIAM Journal on Discrete Mathematics, 2012, 10 pages
Search in Google Scholar
[25] E.Sperner, Ein Satz ̈ber Untermengen einer endlichen Menge, Math.Z., 27(1928), pp. 544-548
Search in Google Scholar
[26] G. Gr ̈tzer, Lattice Theory: Foundation, Springer Basel AG, 201110.1007/978-3-0348-0018-1
Search in Google Scholar
[27] Movsisyan Yu. M., Aslanyan V.A., A functional completeness theorem for De Morgan functions, Discrete Appl. Math., 2014, 162, 1-16 10.1016/j.dam.2013.08.006
Search in Google Scholar

Articles in this issue

DOI: https://doi.org/10.2478/jamsi-2014-0016 | Journal eISSN: 1339-0015 | Journal ISSN: 1336-9180

Journal RSS Feed

Language: English

Page range: 93 - 111

Published on: Jan 27, 2015

Published by: University of Ss. Cyril and Methodius in Trnava

In partnership with: Paradigm Publishing Services

Publication frequency: 2 issues per year

Keywords:

Monotone Boolean function,

self-dual Boolean function,

disjunctive normal form,

interval graph

Related subjects:

Computer sciences,

Information technology,

Mathematics,

Logic and set theory,

Probability and statistics,

Applied mathematics

© 2015 L. Haviarova, E. Toman, published by University of Ss. Cyril and Methodius in Trnava
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 10 (2014): Issue 2 (December 2014)