DOI 10.17586/0021-3454-2022-65-7-478-491
UDC 62-507.15
COMPLEXITY OF ARBITRARY FUNCTIONS OF THE LOGIC ALGEBRA OF A SMALL NUMBER OF VARIABLES
Research and Production Firm Meridian JSC; Chief Designer of Information Control Systems;
Read the full article
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.
Keywords: monotone and arbitrary logic functions, complexity
References:
References:
- Shannon C.E. Bell System Technical Journal, 1948, no. 3(July).
- Lupanov O.B. Problemy kibernetiki, 1963, no. 10, pp. 88–96. (in Russ.)
- Korshunov A.D. Russian Mathematical Surveys, 2003, no. 5, pp. 929–1001.
- Ugol'nikov A.B. Problemy kibernetiki, 1976, no. 31, pp. 167–185. (in Russ.)
- Pippenger N. Math. Systems Theory, 1977/78, vol. 11, рр. 289–316.
- Lupanov O.B. Problemy kibernetiki, 1965, no. 14, pp. 31–110. (in Russ.)
- 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.)
- Muzychenko O.N. Metody sinteza logicheskikh skhem (Methods for Synthesizing Logic Circuits), St. Petersburg, 2018, 860 р. (in Russ.)
- Pospelov D.A. Logicheskiye metody analiza i sinteza skhem (Logical Methods of Analysis and Synthesis of Circuits), Moscow, 1974, 368 р. (in Russ.)
- Muzychenko O.N. Russian Mathematics, 2017, no. 7, pp. 35–42.
- Karpova N.A. Problemy kibernetiki, 1973, no. 26, pp. 53–94. (in Russ.)
- Muzychenko O.N. Automation and Remote Control, 1994, no. 12, pp. 117–128. (in Russ.)
- Korshunov A.D. Soviet Mathematics. Doklady, 1977, no. 4(233), pp. 543–546. (in Russ.)
- Korshunov A.D. Problemy kibernetiki, 1981, no. 38, pp. 5–108. (in Russ.)
- Muzychenko O.N., Lukoyanov V.P. Questions of radio electronics. General questions of radio electronics, 1984, no. 12, pp. 120–128. (in Russ.)
