Minimal contact circuits for symmetric threshold functions. (English. Russian original) Zbl 1477.94086
Math. Notes 108, No. 3, 370-380 (2020); translation from Mat. Zametki 108, No. 3, 397-411 (2020).
Summary: For the monotone symmetric threshold Boolean functions
\[f^n_2(\widetilde{x})=\bigvee_{1\le i<j\le n}x_ix_j,\quad n=2,3,\dots,\]
it is established that a minimal contact circuit implementing \(f^n_2(\widetilde{x})\) contains \(3n-4\) contacts.
MSC:
| 94C11 | Switching theory, applications of Boolean algebras to circuits and networks |
References:
| [1] | Shannon, C. E., The synthesis of two-terminal switching circuits, Bell System Tech. J., 28, 1, 59-98 (1949) · doi:10.1002/j.1538-7305.1949.tb03624.x |
| [2] | Lupanov, O. B., On a method of circuit synthesis, Izv. Vyssh. Uchebn. Zaved. Radioiz., 1, 1, 120-140 (1958) |
| [3] | N. P. Red’kin, “A proof of the minimality of certain circuits of functional elements,” in Problemy Kibernet. (Nauka, Moscow, 1970), Vol. 23, pp. 83-101. · Zbl 0267.94036 |
| [4] | Cardot, C., Quelques résultats sur l’application de l’algèbre de Boole à la synthèse des circuits à relais, Ann. Télécommun., 7, 2, 75-84 (1952) |
| [5] | Nigmatullin, R. G., Complexity of Boolean functions (1983), Kazan: Izd. Kazan. Gos. Un-ta, Kazan |
| [6] | Vartanyan, S. M., A new proof of minimality of the contact circuit realizing a linear function, Metody Diskretnogo Analiza v Izuchenii Realizatsii Logicheskikh Funktsii, 41, 27-34 (1984) · Zbl 0567.94019 |
| [7] | Lozhkin, S. A., A method for obtaining lower bounds for the complexity of contact circuits and some minimal circuits for linear functions, Sbornik Trudov Seminara po Diskretnoy Matematike i Ee Prilozheniyam, 0, 113-115 (1997) |
| [8] | Vasil’ev, Yu. L., Minimal contact schemes for Boolean functions of four variables, Dokl. AN SSSR, 127, 2, 242-245 (1959) · Zbl 0089.12902 |
| [9] | Moore, E. F., Minimal complete relay decoding networks, IBM J. Res. Develop., 4, 5, 525-531 (1960) · Zbl 0099.11403 · doi:10.1147/rd.45.0525 |
| [10] | R. E. Krichevskii, “Minimal circuit of closing contacts for a Boolean function of \(n\) arguments,” in Diskret. Analiz (Novosibirsk, Izd. IM SO AN SSSR, 1965), Vol. 5, pp. 89-92. |
| [11] | Z. E. Koroleva, “A proof of the minimality of contact circuits of a certain type,” in Diskret. Analiz (Novosibirsk, Izd. IM SO AN SSSR, 1969), Vol. 14, pp. 18-27. · Zbl 0195.17702 |
| [12] | N. A. Karpova, “Minimal circuits of make contacts for monotonic functions of five variables,” in Problemy Kibernetiki (Nauka, Moscow, 1973), Vol. 26, pp. 53-94. · Zbl 0259.94037 |
| [13] | Lupanov, O. B., On the comparison of the complexity of the implementation of monotonic functions by contact circuits containing only make contacts, and arbitrary contact circuits, Dokl. AN SSSR, 144, 6, 1245-1248 (1962) · Zbl 0196.51803 |
| [14] | R. E. Krichevskii, “On the complexity of parallel-serial contact circuits that implement a sequence of Boolean functions,” in Problemy Kibernetiki (Nauka, Moscow, 1964), Vol. 12, pp. 45-55. |
| [15] | Grinchuk, M. I., On monotone complexity of threshold functions, Metody Diskretn. Anal. v Teorii Grafov i Slozhnosti, 52, 41-48 (1992) · Zbl 0846.94025 |
| [16] | Lupanov, O. B., Asymptotic Complexity Estimates of Control Systems (1984), Moscow: Izd. Moskov. Univ., Moscow |
| [17] | Lupanov, O. B., The synthesis of contact circuits, Dokl. Akad. Nauk SSSR, 119, 1, 23-26 (1958) · Zbl 0081.20902 |
| [18] | Red’kin, N. P., Reliability and Diagnostics of Circuits (1992), Moscow: Izd. Moskov. Univ., Moscow · Zbl 1358.94118 |
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.
