Volume 19, No 3, 2012, P. 39-57

UDC 519.95
Yu. A. Kombarov
On minimal realizations of linear boolean functions

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, minimal circuit, standard block, standard reduction.

Kombarov Yurii Anatol’evich 1
1. M. V. Lomonosov Moscow State University,
Lenin Gory, MSU, 119991 Moscow, Russia
e-mail: yuri.kombarov@gmail.com

 © Sobolev Institute of Mathematics, 2015