Minimal Contact Circuits for Symmetric Threshold Functions

N. P. Red'kin

Matematičeskie zametki, Tome 108 (2020) no. 3, pp. 397-411.

Résumé

For the monotone symmetric threshold Boolean functions $$ f^n_2(\widetilde x\mspace{2mu})=\bigvee_{1\le i\le n}x_ix_j,\qquad n=2,3,\dots, $$ it is established that a minimal contact circuit implementing $f^n_2(\widetilde x\mspace{2mu})$ contains $3n-4$ contacts.

Détail

Keywords: Boolean function
Mots-clés : contact circuit, minimal circuit.

Bibliographie

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

[2] O. B. Lupanov, “Ob odnom metode sinteza skhem”, Izv. vuzov. Radiofizika, 1:1 (1958), 120–140

[3] N. P. Redkin, “Dokazatelstvo minimalnosti nekotorykh skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 23, Nauka, M., 1970, 83–101 | MR

[4] C. Cardot, “Quelques résultats sur l'application de l'algèbre de Boole à la synthèse des circuits à relais”, Ann. Télécommun., 7:2 (1952), 75–84 | MR

[5] R. G. Nigmatullin, Slozhnost bulevykh funktsii, Izd-vo Kazanskogo gos. un-ta, Kazan, 1983 | MR

[6] S. M. Vartanyan, “Novoe dokazatelstvo minimalnosti kontaktnoi skhemy, realizuyuschei lineinuyu funktsiyu”, Metody diskretnogo analiza v izuchenii realizatsii logicheskikh funktsii, Metody diskretnogo analiza, 41, Novosibirsk, Izd-vo IM SO AN SSSR, 1984, 27–34 | MR

[7] S. A. Lozhkin, “Ob odnom metode polucheniya nizhnikh otsenok slozhnosti kontaktnykh skhem i nekotorykh minimalnykh skhemakh dlya lineinykh funktsii”, Sb. trudov seminara po diskretnoi matematike i ee prilozheniyam, Izd-vo mekh.-matem. fak-ta MGU, M., 1997, 113–115

[8] Yu. L. Vasilev, “Minimalnye kontaktnye skhemy dlya bulevykh funktsii chetyrekh peremennykh”, Dokl. AN SSSR, 127:2 (1959), 242–245 | MR

[9] E. F. Moore, “Minimal complete relay decoding networks”, IBM J. Res. Develop., 4:5 (1960), 525–531 | DOI | MR

[10] R. E. Krichevskii, “Minimalnaya skhema iz zamykayuschikh kontaktov dlya odnoi bulevoi funktsii ot $n$ argumentov”, Diskretnyi analiz, 5, Novosibirsk, Izd-vo IM SO AN SSSR, 1965, 89–92

[11] Z. E. Koroleva, “Dokazatelstvo minimalnosti kontaktnykh skhem nekotorogo tipa”, Diskretnyi analiz, 14, Novosibirsk, Izd-vo IM SO AN SSSR, 1969, 18–27 | MR

[12] N. A. Karpova, “Minimalnye skhemy iz zamykayuschikh kontaktov dlya monotonnykh funktsii pyati peremennykh”, Problemy kibernetiki, 26, Nauka, M., 1973, 53–94 | MR

[13] O. B. Lupanov, “O sravnenii slozhnosti realizatsii monotonnykh funktsii kontaktnymi skhemami, soderzhaschimi lish zamykayuschie kontakty, i proizvolnymi kontaktnymi skhemami”, Dokl. AN SSSR, 144:6 (1962), 1245–1248 | Zbl

[14] R. E. Krichevskii, “O slozhnosti parallelno-posledovatelnykh kontaktnykh skhem, realizuyuschikh odnu posledovatelnost bulevykh funktsii”, Problemy kibernetiki, 12, Nauka, M., 1964, 45–55 | MR

[15] M. I. Grinchuk, “O monotonnoi slozhnosti porogovykh funktsii”, Metody diskretnogo analiza v teorii grafov i slozhnosti, Metody diskretnogo analiza, 52, Novosibirsk, Izd-vo IM SO AN SSSR, 1992, 41–48 | MR

[16] O. B. Lupanov, Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, M., 1984

[17] O. B. Lupanov, “O sinteze kontaktnykh skhem”, Dokl. AN SSSR, 119:1 (1958), 23–26 | MR | Zbl

[18] N. P. Redkin, Nadezhnost i diagnostika skhem, Izd-vo Mosk. un-ta, M., 1992