Complexity of realization of a linear Boolean function in the Sheffer basis / Yu. A. Kombarov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2013. № 2. P. 49-53 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 0].

The paper is focused on realization of linear Boolean functions by circuits of functional elements in the basis {¬(x & y)}. 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.

№ 2/2013