On the Implementation of Boolean functions by Contact Circuits with Uniform Width 3
Кирилл Андреевич Попков · Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki · 2020
Implementation an arbitrary Boolean function by a contact circuit with as little uniform width as possible was studied. In 1965, Kh.A. Madatyan framed the concept of contact circuit width. However, it does not always correspond to the intuitive view of width. In this regard, the concept of the uniform width of the contact circuit, which corresponds to the intuitive perception of width in a number of cases, was introduced in this paper. It was proved that every Boolean function can be implemented by a contact circuit with a uniform width of no more than 3.