Volume 20, No 4, 2013, P. 65-87

UDC 519.95
Kombarov Ya. A.
On minimal circuts in sheffer basis for linear boolean functions

Abstract:
Realizations of pairity function and its negation by Boolean circuits in Sheffer basis are considered. The exact value of complexity of pairity function’s negation is established. Another result is structure description of minimal circuits for the parity function.
Ill. 13, bibliogr. 8.

Keywords: Boolean circuit, pairity function, Sheffer stroke.

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