Geodesic
On minimal realizations of linear Boolean functions
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 39-57.

Voir la notice de l'article provenant de la source Math-Net.Ru

The article deals with the realization of linear Boolean functions by circuits of functional elements in the classical basis (conjunction, disjunction, and negation). It is established that all minimal circuits realizing linear functions in this basis have a block structure. Ill. 10, bibliogr. 10.
Keywords: circuit of functional elements, linear Boolean function, standard block, standard reduction.
Mots-clés : minimal circuit 
@article{DA_2012_19_3_a3,
     author = {Yu. A. Kombarov},
     title = {On minimal realizations of linear {Boolean} functions},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {39--57},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_3_a3/}
}
TY  - JOUR
AU  - Yu. A. Kombarov
TI  - On minimal realizations of linear Boolean functions
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 39
EP  - 57
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_3_a3/
LA  - ru
ID  - DA_2012_19_3_a3
ER  - 
%0 Journal Article
%A Yu. A. Kombarov
%T On minimal realizations of linear Boolean functions
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 39-57
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_3_a3/
%G ru
%F DA_2012_19_3_a3
Yu. A. Kombarov. On minimal realizations of linear Boolean functions. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 39-57. http://geodesic.mathdoc.fr/item/DA_2012_19_3_a3/

[1] Kombarov Yu. A., “O minimalnykh realizatsiyakh lineinykh bulevykh funktsii skhemami iz funktsionalnykh elementov v bazise $\{x\to y,\overline x\,\\,y\}$”, Tr. VIII mezhdunar. konf. “Diskretnye modeli v teorii upravlyayuschikh sistem” (Moskva, 6–9 aprelya 2009 g.), MAKS Press, M., 2009, 145–149

[2] Lozhkin S. A., “O strukture minimalnykh skhem iz funktsionalnykh elementov v bazise $\{\,\vee,\neg\}$, realizuyuschikh lineinuyu funktsiyu”, Tr. V mezhdunar. konf. “Diskretnye modeli v teorii upravlyayuschikh sistem” (Ratmino, 26–29 maya 2003 g.), Izd. otd. fak. VMiK MGU im. M. V. Lomonosova, M., 2003, 50

[3] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyaemykh sistem, MGU, M., 1984, 136 pp.

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

[5] Redkin N. P., “O minimalnoi realizatsii lineinoi funktsii skhemoi iz funktsionalnykh elementov”, Kibernetika, 1971, no. 6, 31–38 | MR

[6] Redkin N. P., “O minimalnykh i asimptoticheski minimalnykh skhemakh dlya nekotorykh individualnykh bulevykh funktsii”, Mat. IX mezhdunar. seminara “Diskretnaya matematika i eë prilozheniya”, posvyaschënnogo 75-letiyu so dnya rozhdeniya akademika O. B. Lupanova (Moskva, 18–23 iyunya 2007 g.), Izd-vo mekh.-mat. fak. MGU, M., 2007, 11–19

[7] Redkin N. P., “O minimalnoi realizatsii dvoichnogo summatora”, Problemy kibernetiki, 38, 1981, 181–216 | MR

[8] Shkrebela I. S., “O slozhnosti realizatsii lineinykh bulevykh funktsii skhemami iz funktsionalnykh elementov v bazise \{$x\to y,\overline x$\}”, Diskret. matematika, 15:4 (2003), 100–112 | MR | Zbl

[9] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986, 384 pp. | MR

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