RUS  ENG
Full version
JOURNALS // Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia // Archive

Dokl. RAN. Math. Inf. Proc. Upr., 2020 Volume 495, Pages 65–68 (Mi danma136)

This article is cited in 1 paper

MATHEMATICS

On implementation of boolean functions by contact circuits with a constant uniform width

K. A. Popkov

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

Abstract: We introduce the concept of the uniform width of a contact circuit. For each Boolean function, we find the minimal possible value of the uniform width of a contact circuit implementing this function. We prove constructively that this value does not exceed 3. We also establish that, for almost all Boolean functions on $n$ variables, it equals 3.

Keywords: contact circuit, Boolean function, uniform width.

UDC: 519.714.22

Presented: B. N. Chetverushkin
Received: 01.09.2020
Revised: 01.09.2020
Accepted: 03.10.2020

DOI: 10.31857/S2686954320060132


 English version:
Doklady Mathematics, 2020, 102:3, 502–504

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024