On Implementation of Boolean Functions by Logic Circuits in an Arbitrary Basis

Issues of implementation of Boolean functions by logic circuits containing functional elements are discussed. A method is proposed for asymptotically best possible implementation of Boolean functions by logical circuits in a complete arbitrary finite basis. This method uses the O.B. Lupanov’s method modified by the author for a basis, consisting of elements with a weight of 1, which implement disjunction, conjunction, and negation, as well as the principle of using incompletely defined functions. This modification is more universal: all units of the circuit are independent of the implemented function that defines only the connections between inputs and outputs of the units. In the case of arbitrary basis, the circuit includes chains of the "cheapest" elements of the basis. These chains implement incompletely defined Boolean functions, which are zeroes on the sets consisting only of zeros, while on the sets containing exactly one 1, they are equal to unity.

References

[1] Lupanov O.B. On a method of synthesis of circuits. Izv. Vyssh. Uchebn. Zaved., Fizika. [Proc. Univ., Physics], 1958, vol. 1, no. 1, pp. 120-140 (in Russ.).

[2] Lupanov O.B. On the synthesis of some classes of control systems. Probl. Kibern. [Probl. Cybern.], 1963, vol. 10, pp. 3-97 (in Russ.).

[3] Yablonskiy S.V. Asimptoticheski nailuchshiy metod sinteza nadezhnykh skhem iz nenadezhnykh elementov [Asymptotically best method for the synthesis of reliable circuits from unreliable elements]. Banach Center Pub., 1982, no. 7, pp. 11-19 (in Russ).