The exact circuit complexity of Boolean functions in an infinite basis

V. V. Kochergin^a, A. V. Mikhailovich<sup>b

a</sup> Lomonosov Moscow State University
^b National Research University Higher School of Economics, Moscow

Abstract: The exact value of the complexity of the circuit implementation of an arbitrary Boolean function in a certain basis consisting of negation and all monotone Boolean functions is found. The complexity of a function is defined as the least number of basis elements sufficient to construct a circuit implementation of this function.

Keywords: logic (Boolean) circuit, circuit of functional gates, circuit complexity, negation (inversion) complexity, infinite basis.

UDC: 519.71

Received: 08.08.2024

DOI: 10.4213/mzm14465

 English version: Mathematical Notes, 2025, 117:4, 579–594

Bibliographic databases:

• 
•