Complexity of Arbitrary Functions of the Logic Algebra of a Small Number of Variables
https://doi.org/10.17586/0021-3454-2022-65-7-478-491
Abstract
A method for evaluating the complexity of arbitrary function of Boolean algebra is examined, based on presenting such a function as a composition of monotone functions. Accurate upper estimates have been received for the complexity of monotone and arbitrary functions depending on a small number of variables.
About the Author
О. N. Muzychenko
Research and Production Firm Meridian
Russian Federation
Russian Federation
Oleg N. Muzychenko – Dr. Sci., Professor; Chief Designer of Information Control Systems
St. Petersburg
References
1. Shannon C.E. Bell System Technical Journal, 1948, no. 3(July).
2. Lupanov O.B. Problemy kibernetiki, 1963, no. 10, pp. 88–96. (in Russ.)
3. Korshunov A.D. Russian Mathematical Surveys, 2003, no. 5, pp. 929–1001.
4. Ugol'nikov A.B. Problemy kibernetiki, 1976, no. 31, pp. 167–185. (in Russ.)
5. Pippenger N. Math. Systems Theory, 1977/78, vol. 11, рр. 289–316.
6. Lupanov O.B. Problemy kibernetiki, 1965, no. 14, pp. 31–110. (in Russ.)
7. Muzychenko O.N. Spetsializirovannyye metody sinteza logicheskikh skhem. Chast' 1. Metody sinteza logicheskikh skhem simmetrichnykh i porogovykh funktsiy (Specialized Methods for Synthesizing Logic Circuits. Part 1. Methods for Synthesizing Logic Circuits of Symmetric and Threshold Functions), St. Petersburg, 2004, 161 р. (in Russ.)
8. Muzychenko O.N. Metody sinteza logicheskikh skhem (Methods for Synthesizing Logic Circuits), St. Petersburg, 2018, 860 р. (in Russ.)
9. Pospelov D.A. Logicheskiye metody analiza i sinteza skhem (Logical Methods of Analysis and Synthesis of Circuits), Moscow, 1974, 368 р. (in Russ.)
10. Muzychenko O.N. Russian Mathematics, 2017, no. 7, pp. 35–42.
11. Karpova N.A. Problemy kibernetiki, 1973, no. 26, pp. 53–94. (in Russ.)
12. Muzychenko O.N. Automation and Remote Control, 1994, no. 12, pp. 117–128. (in Russ.)
13. Korshunov A.D. Soviet Mathematics. Doklady, 1977, no. 4(233), pp. 543–546. (in Russ.)
14. Korshunov A.D. Problemy kibernetiki, 1981, no. 38, pp. 5–108. (in Russ.)
15. Muzychenko O.N., Lukoyanov V.P. Questions of radio electronics. General questions of radio electronics, 1984, no. 12, pp. 120–128. (in Russ.)
Review
For citations:
Muzychenko О.N. Complexity of Arbitrary Functions of the Logic Algebra of a Small Number of Variables. Journal of Instrument Engineering. 2022;65(7):478-491. (In Russ.) https://doi.org/10.17586/0021-3454-2022-65-7-478-491
Views:
23
Email this article 