Geodesic
On the implementation of Boolean functions by contact circuits with uniform width 3
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 350-358 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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.
Mots-clés : contact circuit
Keywords: Boolean function, uniform width. 
@article{UZKU_2020_162_3_a8,
     author = {K. A. Popkov},
     title = {On the implementation of {Boolean} functions by contact circuits with uniform width~3},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {350--358},
     year = {2020},
     volume = {162},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a8/}
}
TY  - JOUR
AU  - K. A. Popkov
TI  - On the implementation of Boolean functions by contact circuits with uniform width 3
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2020
SP  - 350
EP  - 358
VL  - 162
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a8/
LA  - ru
ID  - UZKU_2020_162_3_a8
ER  - 
%0 Journal Article
%A K. A. Popkov
%T On the implementation of Boolean functions by contact circuits with uniform width 3
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2020
%P 350-358
%V 162
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a8/
%G ru
%F UZKU_2020_162_3_a8
K. A. Popkov. On the implementation of Boolean functions by contact circuits with uniform width 3. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 350-358. http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a8/

[1] Lupanov O. B., Asymptotic Complexity Bounds for Control Systems, Izd. Mosk. Univ., M., 1984, 138 pp. (In Russian)

[2] Shannon C. E., “A symbolic analysis of relay and switching circuits”, Trans. AIEE, 57 (1938), 713–723 | DOI

[3] Shannon C. E., “The synthesis of two-terminal switching circuits”, Bell Syst. Tech. J., 28:1 (1949), 59–98 | DOI | MR

[4] Korshunov A. D. Computational complexity of Boolean functions, Russ. Math. Surv., 67:1 (2012), 93–165 | DOI | DOI | MR | Zbl

[5] Madatyan Kh.A., “Synthesis of contact circuits with bounded width”, Probl. Kibern., 14, 1965, 301–307 (In Russian)

[6] Karpova N. A., “On computing with bounded memory”, Mat. Vopr. Kibern., 2, 1989, 131–144 (In Russian)

[7] Okol'nishnikova E. A., “On the complexity of branching programs”, Mat. Vopr. Kibern., 10, 2001, 69–82 (In Russian)

[8] Lozhkin S. A., Lectures on Principles of Cybernetics, Izd. Otd. Fak. VMiK MGU, M., 2004, 253 pp. (In Russian)

[9] Konovodov V. A., “On synthesis of circuits with bounded width”, Proc. VIII Youth Sci. Sch. on Discrete Mathematics and Its Applications, v. 1, Izd. Mekh.-Mat. Fak. MGU, M., 2011, 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., 19, 1967, 285–292 (In Russian)

[11] Red'kin N. P., Reliability and Diagnostics of Circuits, Izd. Mosk. Univ., M., 1992, 192 pp. (In Russian)