Geodesic
Some features of the synthesis of Boolean formulae over complete bases with direct and iterative variables
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 76-83 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The paper studies some issues of complexity of Boolean formulae over different bases that consist of Boolean functions with direct and iterative variables. It is shown that the standard behavior of the Shannon function for the complexity of the formulae $(2^n/\log n)$ does not always take place; the examples of the non-trivial families of bases where this function has the order of growth of $2^n$ are given. Such examples exist in each family in the classification of bases according to their iterative closures, except for two bases, where the Shannon function has the standard order of growth. A new representation of the iterative closure operator $\delta$ (introduced by S. A. Lozhkin) is obtained. The issue about the complexity of an affine function over some classes of bases is considered separately. The examples of radical changes of this complexity in different bases from one family are given.
Mots-clés : Boolean formulae
Keywords: complexity of functions, Shannon function, direct and iterative variables. 
@article{UZKU_2014_156_3_a7,
     author = {V. A. Konovodov},
     title = {Some features of the synthesis of {Boolean} formulae over complete bases with direct and iterative variables},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {76--83},
     year = {2014},
     volume = {156},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a7/}
}
TY  - JOUR
AU  - V. A. Konovodov
TI  - Some features of the synthesis of Boolean formulae over complete bases with direct and iterative variables
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2014
SP  - 76
EP  - 83
VL  - 156
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a7/
LA  - ru
ID  - UZKU_2014_156_3_a7
ER  - 
%0 Journal Article
%A V. A. Konovodov
%T Some features of the synthesis of Boolean formulae over complete bases with direct and iterative variables
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2014
%P 76-83
%V 156
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a7/
%G ru
%F UZKU_2014_156_3_a7
V. A. Konovodov. Some features of the synthesis of Boolean formulae over complete bases with direct and iterative variables. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 76-83. http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a7/

[1] Lozhkin S. A., “O polnote i zamknutykh klassakh funktsii algebry logiki s pryamymi i iterativnymi peremennymi”, Vestn. Mosk. un-ta. Ser. 15. Vychisl. matem. i kibernetika, 1999, no. 3, 35–41 | MR | Zbl

[2] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, M., 1984, 136 pp.

[3] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, M., 1986, 384 pp. | MR

[4] Lozhkin S. A., “O slozhnosti realizatsii funktsii algebry logiki skhemami i formulami, postroennymi iz funktsionalnykh elementov s pryamymi i iterativnymi peremennymi”, Trudy III Mezhdunar. konf. “Diskretnye modeli v teorii upravlyayuschikh sistem”, Krasnovidovo' 98 (M., 22–27 iyunya 1998 g.), Dialog-MGU, M., 1998, 72–73

[5] Konovodov V. A., “O slozhnosti bulevykh formul v bazisakh iz elementov s pryamymi i iterativnymi vkhodami”, Materialy IX molodezhnoi nauch. shk. po diskretnoi matematike i ee prilozheniyam (M., 16–21 sent. 2013 g.), Izd-vo IPM RAN, M., 2013, 57–60

[6] Lozhkin S. A., Realizatsiya funktsii algebry logiki skhemami iz funktsionalnykh elementov s zaderzhkami, Dis. $\dots$ kand. fiz.-mat. nauk, 1979

[7] Kirichenko K. D., “Verkhnyaya otsenka slozhnosti polinomialnykh normalnykh form bulevykh funktsii”, Diskretnaya matem., 17:3 (2005), 80–88 | DOI | MR | Zbl

[8] Cooper J. N., Ellis R. B., Kahng A. B., “Asymmetric binary covering codes”, J. Combin. Theory Ser. A, 100:2 (2002), 232–249 | DOI | MR | Zbl