×

On the realisation of Boolean functions by informational graphs. (English. Russian original) Zbl 1180.94095

Discrete Math. Appl. 18, No. 6, 581-593 (2008); translation from Diskretn. Mat. 20, No. 4, 29-41 (2008).
Summary: We consider the problem of the realisation of Boolean functions by informational graphs. The exact expression of the Shannon function for the realisation in the class of tree-like informational graphs is obtained. For almost all Boolean functions we obtain the order of the complexity of the realisation by informational graphs and the asymptotics of the complexity of the realisation by informational trees.

MSC:

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. E. Gasanov and V. B. Kudryavtsev, Theory of Data Storage and Information Retrieval. Fizmatlit, Moscow, 2002 (in Russian). · Zbl 1042.68039
[2] Yu. I. Shutkin, Realisation of Boolean functions by informational graphs. In: Proc. IX Intern. Conf. ‘Intellectual Systems and Computer Science’. Mech.Math. Dept, Moscow Univ. Press, Moscow, 2006 (in Russian). · Zbl 1180.94095
[3] O. B. Lupanov, Asymptotic Estimates of Complexity of Control Systems. Moscow Univ. Press, Moscow, 1984 (in Russian).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.