Complexity of implementation of parity functions in the implication–negation basis

Yu. A. Kombarov

Lomonosov Moscow State University

Abstract: The paper is concerned with circuits in the basis $\{x \to y, \overline{x}\}$. The exact value of the complexity of implementation of an even parity function is obtained and the minimal circuits implementing an odd parity function are described.

Keywords: circuit, parity function, minimal circuit, complexity circuits.

UDC: 519.714.4

Received: 17.09.2014

DOI: 10.4213/dm1316

 English version: Discrete Mathematics and Applications, 2015, 25:4, 211–231

Bibliographic databases:

• 
• 
• 
•