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/