RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2021 Volume 33, Issue 4, Pages 94–109 (Mi dm1652)

On implementation of Boolean functions by contact circuits of minimal uniform width

K. A. Popkov

Keldysh Institute of Applied Mathematics of Russian Academy of Sciences, Moscow

Abstract: For each Boolean function, we find a minimal possible value of the uniform width of a contact circuit implementing this function. We also show that, for almost all $n$-place Boolean functions, this value is equal to $3$.

Keywords: contact circuit, Boolean function, uniform width of a circuit.

UDC: 519.714.5

Received: 24.04.2021

DOI: 10.4213/dm1652


 English version:
Discrete Mathematics and Applications, 2022, 32:6, 403–415


© Steklov Math. Inst. of RAS, 2025