On irredundant complexes of faces in the unit cube

I. P. Chukhrov

Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 132-158.

Résumé

The study of properties of irredundant complexes of faces is connected with the problem of minimisation of Boolean functions in the class of disjunctive normal forms (d.n.f.). In researches by S. V. Yablonskii, Yu. I. Zhuravlev, V. V. Glagolev, Yu. L. Vasilyev, A. A. Sapozhenko, on the base of construction and investigation of properties of particular Boolean functions, estimates of the maximum length and number of irredundant d.n.f. have been obtained. The author suggests a different approach to investigations of these objects based on constructing and estimating the cardinality of sets of irredundant complexes of faces. In this paper, with the use of the probabilistic approach, new methods of construction and estimation of characteristics of irredundant complexes of faces are suggested, which give a possibility to improve the known estimates. On the base of a method of construction of irredundant complexes of faces in a belt of the unit cube $B^n$ of width $k$, we obtain estimates of the maximum number of faces and the number of irredundant complexes for the faces of dimension $k(1/4-\varepsilon)n$, where $\varepsilon$ is as small as wished positive constant. By the optimal choice of the parameters we obtain for the logarithm of the number of irredundant complexes of faces the lower bound of order $n2^n$ with constant $1.355\cdot2^{-5}$ for the dimension of the faces $k\approx0.0526n$. Because of equivalence of the problem of minimisation of Boolean functions in the class of d.n.f. and the problem of construction of complexes of faces covering subsets of vertices of the unit cube, the obtained results can be used for estimation of the maximum values of the length and the number of irredundant d.n.f.

Bibliographie

[1] Zhuravlev Yu. I., “Algoritmy postroeniya minimalnykh d.n.f”, Diskretnaya matematika i matematicheskie voprosy kibernetiki, v. 1, Nauka, Moskva, 1974, 67–98

[2] Vasilev Yu. L., Glagolev V. V., “Metricheskie svoistva diz'yunktivnykh normalnykh form”, Diskretnaya matematika i matematicheskie voprosy kibernetiki, v. 1, Nauka, Moskva, 1974, 99–148

[3] Sapozhenko A. A., Chukhrov I. P., “Minimizatsiya bulevykh funktsii v klasse diz'yunktivnykh normalnykh form”, Itogi nauki i tekhniki. Seriya Teoriya veroyatnostei. Matematicheskaya statistika. Teoreticheskaya kibernetika, 25, VINITI AN SSSR, Moskva, 1987, 68–116 | MR | Zbl

[4] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Vysshaya shkola, Moskva, 2003

[5] Zhuravlev Yu. I., “Otsenka dlya chisla tupikovykh d.n.f. funktsii algebry logiki”, Sibirskii matem. zhurnal, 3:5 (1962), 802–804 | Zbl

[6] Vasilev Yu. L., “K voprosu o chisle minimalnykh i tupikovykh diz'yunktivnykh normalnykh form”, Diskretnyi analiz, 2, 1964, 3–9 | MR

[7] Sapozhenko A. A., “O naibolshei dline tupikovoi diz'yunktivnoi normalnoi formy u pochti vsekh bulevykh funktsii”, Matematicheskie zametki, 4:6 (1968), 649–658 | MR | Zbl

[8] Sapozhenko A. A., Diz'yunktivnye normalnye formy, MGU, Moskva, 1975

[9] Chukhrov I. P., “Otsenka chislovykh kharakteristik poyaskovykh funktsii”, Tezisy dokl. V Vsesoyuznoi konf. po problemam teoreticheskoi kibernetiki, Novosibirsk, 1980, 179–180

[10] Chukhrov I. P., “O chisle tupikovykh diz'yunktivnykh normalnykh form”, Doklady AN SSSR, 262:6 (1982), 1329–1332 | MR | Zbl

[11] Yablonskii S. V., “K voprosu ob otsenke dliny tupikovykh diz'yunktivnykh normalnykh form”, Problemy kibernetiki, 7, 1962, 229–230

[12] Glagolev V. V., “O dline tupikovoi diz'yunktivnoi normalnoi formy”, Matematicheskie zametki, 2:6 (1967), 665–672 | MR | Zbl

[13] Gavrilov G. P., Sapozhenko A. A., Zadachi i uprazhneniya po diskretnoi matematike, Fizmatlit, Moskva, 2005