Geodesic
A generalization of Shannon function
Diskretnaya Matematika, Tome 29 (2017) no. 2, pp. 70-83.

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

When investigating the complexity of implementing Boolean functions, it is usually assumed that the basis in which the schemes are constructed and the measure of the complexity of the schemes are known. For them, the Shannon function is introduced, which associates with each Boolean function the least complexity of implementing this function in the considered basis. In this paper we propose a generalization of such a Shannon function in the form of an upper bound that is taken over all functionally complete bases. This generalization gives an idea of the complexity of implementing Boolean functions in the “worst” bases for them. The conceptual content of the proposed generalization is demonstrated by the example of a conjunction.
Keywords: Boolean function, Boolean circuit, complexity of a Boolean function, Shannon function. 
@article{DM_2017_29_2_a5,
     author = {N. P. Red'kin},
     title = {A generalization of {Shannon} function},
     journal = {Diskretnaya Matematika},
     pages = {70--83},
     publisher = {mathdoc},
     volume = {29},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2017_29_2_a5/}
}
TY  - JOUR
AU  - N. P. Red'kin
TI  - A generalization of Shannon function
JO  - Diskretnaya Matematika
PY  - 2017
SP  - 70
EP  - 83
VL  - 29
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2017_29_2_a5/
LA  - ru
ID  - DM_2017_29_2_a5
ER  - 
%0 Journal Article
%A N. P. Red'kin
%T A generalization of Shannon function
%J Diskretnaya Matematika
%D 2017
%P 70-83
%V 29
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2017_29_2_a5/
%G ru
%F DM_2017_29_2_a5
N. P. Red'kin. A generalization of Shannon function. Diskretnaya Matematika, Tome 29 (2017) no. 2, pp. 70-83. http://geodesic.mathdoc.fr/item/DM_2017_29_2_a5/

[1] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izdatelstvo MGU, Moskva, 1984, 138 pp.

[2] Yablonskii S.V., Vvedenie v diskretnuyu matematiku, Izdatelstvo «Vysshaya shkola», Moskva, 2003, 384 pp. | MR

[3] Nechiporuk E.I., “O slozhnosti skhem v nekotorykh bazisakh, soderzhaschikh netrivialnye elementy s nulevymi vesami”, Problemy kibernetiki, 1962, 123–160 | MR | Zbl

[4] Lupanov O.B., “Ob odnom metode sinteza skhem”, Izvestiya vuzov. Radiofizika, 1:1 (1958), 120–140

[5] Redkin N.P., Diskretnaya matematika, Fizmatlit, Moskva, 2009

[6] Soprunenko E.P., “O minimalnoi realizatsii nekotorykh funktsii skhemami iz funktsionalnykh elementov”, Problemy kibernetiki, 1965, no. 15, 117–134 | MR

[7] Gorelik E.S., “O slozhnosti realizatsii elementarnykh kon'yunktsii i diz'yunktsii v bazise $x/\ y$”, Problemy kibernetiki, 1973, no. 26, 27–36 | Zbl

[8] Novikov S.V., Komissarov V.E., Suprun V.P., “Minimalnaya realizatsiya funktsii $f=x_1 x_2\dots x_r$ skhemami iz elementov shefferovskogo tipa”, Vestn. Beloruss. un-ta, 1:2 (1975), 13–17

[9] Kochergina G.A., “O slozhnosti realizatsii elementarnykh kon'yunktsii i diz'yunktsii skhemami v nekotorykh polnykh bazisakh”, Matematicheskie voprosy kibernetiki, 2002, no. 11, 219–246 | MR | Zbl

[10] Redkin N.P., “O polnykh proveryayuschikh testakh dlya skhem iz funktsionalnykh elementov”, Matematicheskie voprosy kibernetiki, 1989, no. 2, 198–222 | Zbl

[11] Redkin N.P., “Dokazatelstvo minimalnosti nekotorykh skhem iz funktsionalnykh elementov.”, Problemy kibernetiki, 1970, no. 23, 83–101 | MR | Zbl