Geodesic
On the conplexity of joint realization of Boolean functions regular systems in the DNF basis
Matematičeskie voprosy kriptografii, Tome 1 (2010) no. 3, pp. 45-65 
V. G. Nikonov; A. V. Sarantsev. On the conplexity of joint realization of Boolean functions regular systems in the DNF basis. Matematičeskie voprosy kriptografii, Tome 1 (2010) no. 3, pp. 45-65. http://geodesic.mathdoc.fr/item/MVK_2010_1_3_a3/
@article{MVK_2010_1_3_a3,
     author = {V. G. Nikonov and A. V. Sarantsev},
     title = {On the conplexity of joint realization of {Boolean} functions regular systems in the {DNF} basis},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {45--65},
     year = {2010},
     volume = {1},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2010_1_3_a3/}
}
TY  - JOUR
AU  - V. G. Nikonov
AU  - A. V. Sarantsev
TI  - On the conplexity of joint realization of Boolean functions regular systems in the DNF basis
JO  - Matematičeskie voprosy kriptografii
PY  - 2010
SP  - 45
EP  - 65
VL  - 1
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MVK_2010_1_3_a3/
LA  - ru
ID  - MVK_2010_1_3_a3
ER  - 
%0 Journal Article
%A V. G. Nikonov
%A A. V. Sarantsev
%T On the conplexity of joint realization of Boolean functions regular systems in the DNF basis
%J Matematičeskie voprosy kriptografii
%D 2010
%P 45-65
%V 1
%N 3
%U http://geodesic.mathdoc.fr/item/MVK_2010_1_3_a3/
%G ru
%F MVK_2010_1_3_a3

Voir la notice de l'article provenant de la source Math-Net.Ru

Some complexity estimates of joint realization of Boolean functions regular systems in the DNF basis are derived. It is shown that the complexity of joint realization of such systems in the orthogonal DNF basis is equal to its maximal value. A description of functions whiah may be used to generate regular systems of Boolean functions by means of transforms from the Jevons group is given.

[1] Blake A., Canonical Expression in Boolean Algebra, Chicago, 1937

[2] Zhuravlëv Yu. I., “Algoritmy postroeniya minimalnykh d. n. f. dlya funktsii algebry logiki”, Diskretnaya matematika i matematicheskie voprosy kibernetiki, Nauka, M., 1974, 67–82

[3] Zhuravlëv Yu. I., “Ob algoritmakh uproscheniya diz'yunktivnykh normalnykh form”, Dokl. AN SSSR, 132:2 (1960), 260–263 | Zbl

[4] Zakrevskii A. D., Logicheskii sintez kaskadnykh skhem, Nauka, M., 1981 | MR

[5] Quine W. V., “The problem of simplifying truth function”, Amer. Math. Monthly, 59 (1952), 521–531 | DOI | MR | Zbl

[6] Mc Cluskey E. J., Jr., “Minimization of boolean functions”, Bell Syst. Techn. J., 35:6 (1956), 1417–1444 | MR

[7] Nigmatullin R. G., Slozhnost bulevykh funktsii, Nauka, M., 1991 | MR | Zbl

[8] Nikonov V. G., “Pokrytiya bulevykh grafov”, Diskret. matem., 6:4 (1994), 21–34 | MR | Zbl

[9] Nikonov V. G., “Klassifikatsiya minimalnykh bazisnykh predstavlenii vsekh bulevykh funktsii ot chetyrekh peremennykh”, Obozrenie prikl. promyshl. matem., 1:3 (1994), 458–545 | MR | Zbl

[10] Nikonov V. G., “Porogovye predstavleniya bulevykh funktsii”, Obozrenie prikl. promyshl. matem. Ser. diskret. matem., 1:3 (1994), 402–458 | MR

[11] Nikonov V. G., “Konechnost nekotorykh klassov bulevykh funktsii s ogranichennym chislom elementarnykh kon'yunktsii v DNF”, Vestnik RUDN, Ser. Prikl. i komp. matematika, 2:1 (2003), 68–78

[12] Nikonov V. G., “O suschestvovanii minimalnoi, no ne kratchaishei ortogonalnoi diz'yunktivnoi normalnoi formy”, Trudy po diskretnoi matematike, 10, FIZMATLIT, M., 2007, 188–201

[13] Nikonov V. G., Sarantsev A. V., “Metody kompaktnoi realizatsii biektivnykh otobrazhenii, zadannykh regulyarnymi sistemami odnotipnykh bulevykh funktsii”, Vestnik RUDN, Ser. Prikl. i komp. matematika, 2:1 (2003), 84–95

[14] Sarantsev A. V., “Postroenie regulyarnykh sistem odnotipnykh dvoichnykh funktsii s ispolzovaniem registra sdviga”, Vestnik MGUL, 2004, no. 1(32), 164–169

[15] Sarantsev A. V., “Regulyarnye sistemy odnotipnykh dvoichnykh funktsii stepeni 3, postroennye s pomoschyu tsiklicheskogo sdviga”, Obozrenie prikl. i promyshl. matem., 14:1 (2007), 147–148