RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2013 Number 2, Pages 49–53 (Mi vmumm395)

This article is cited in 4 papers

Short notes

Complexity of realization of a linear Boolean function in Sheffer's basis

Yu. A. Kombarov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The paper is focused on realization of linear Boolean functions by circuits of functional elements in the basis $\left\{\overline{x \& y}\right\}$. The exact value of complexity of negation of linear function is obtained in this paper. Another result is the description of all minimal circuts realizing a linear function.

Key words: circuit of functional elements, linear Boolean function, minimal circuit, standard block.

UDC: 519.95

Received: 25.04.2012


 English version:
Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2013, 68:2, 114–117

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025