On the implementation of Boolean functions by contact circuits with uniform width 3

K.A. Popkov

Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, Moscow, 125047 Russia

E-mail: kirill-formulist@mail.ru

Received July 6, 2020

Full text PDF

DOI: 10.26907/2541-7746.2020.3.350-358

For citation: Popkov K.A. On the implementation of Boolean functions by contact circuits with uniform width 3 . Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 350–358. doi: 10.26907/2541-7746.2020.3.350-358. (In Russian)

Abstract

Implementation an arbitrary Boolean function by a contact circuit with as little uniform width as possible was studied. In 1965, Kh.A. Madatyan framed the concept of contact circuit width. However, it does not always correspond to the intuitive view of width. In this regard, the concept of the uniform width of the contact circuit, which corresponds to the intuitive perception of width in a number of cases, was introduced in this paper. It was proved that every Boolean function can be implemented by a contact circuit with a uniform width of no more than 3 .

Keywords: contact circuit, Boolean function, uniform width

References

1. Lupanov O.B. Asimptoticheskie otsenki slozhnosti upravlyayushchikh sistem [Asymptotic Complexity Bounds for Control Systems]. Moscow, Izd. Mosk. Univ., 1984. 138 p. (In Russian)
2. Shannon C.E. A symbolic analysis of relay and switching circuits. Trans. AIEE, 1938, vol. 57, pp. 713–723. doi: 10.1109/T-AIEE.1938.5057767.
3. Shannon C.E. The synthesis of two-terminal switching circuits. Bell Syst. Tech. J., 1949, vol. 28, no. 1, pp. 59–98. doi: 10.1002/j.1538-7305.1949.tb03624.x.
4. Korshunov A.D. Computational complexity of Boolean functions. Russ. Math. Surv., 2012, vol. 67, no. 1, pp. 93–165. doi: 10.1070/RM2012v067n01ABEH004777.
5. Madatyan Kh.A. Synthesis of contact circuits with bounded width. Probl. Kibern., 1965, no. 14, pp. 301–307. (In Russian)
6. Karpova N.A. On computing with bounded memory. Mat. Vopr. Kibern., 1989, no. 2, pp. 131–144. (In Russian)
7. Okol’nishnikova E.A. On the complexity of branching programs. Mat. Vopr. Kibern., 2001, no. 10, pp. 69–82. (In Russian)
8. Lozhkin S.A. Lektsii po osnovam kibernetiki [Lectures on Principles of Cybernetics]. Moscow, Izd. Otd. Fak. VMiK MGU, 2004. 253 p. (In Russian)
9. Konovodov V.A. On synthesis of circuits with bounded width. Materialy VIII molodezhnoi nauch. shk. po diskretnoi matematike i ee prilozheniyam [Proc. VIII Youth Sci. Sch. on Discrete Mathematics and Its Applications]. Pt. 1. Moscow, Izd. Mekh.-Mat. Fak. MGU, 2011, pp. 37–41. (In Russian)
10. Kravtsov S.S. On the implementation of logic algebra functions in a single class of circuits consisting of functional and switching elements. Probl. Kibern., 1967, no. 19, pp. 285–292. (In Russian)
11. Red’kin N.P. Nadezhnost’ i diagnostika skhem [Reliability and Diagnostics of Circuits]. Moscow, Izd. Mosk. Univ., 1992. 192 p. (In Russian)

The content is available under the license Creative Commons Attribution 4.0 License.