|
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.
Received: 24.04.2021
Citation:
K. A. Popkov, “On implementation of Boolean functions by contact circuits of minimal uniform width”, Diskr. Mat., 33:4 (2021), 94–109; Discrete Math. Appl., 32:6 (2022), 403–415
Linking options:
https://www.mathnet.ru/eng/dm1652https://doi.org/10.4213/dm1652 https://www.mathnet.ru/eng/dm/v33/i4/p94
|
|