On the synthesis of oriented switching circuits (Q2563384)

Optimal implementation with oriented contact circuits of a logic function is discussed. The asymptotic behaviour of the Shannon function \(\overrightarrow{L}(n)\) is studied. It is well-known that the difference between the upper and the lower bound of \(\overrightarrow{L}(n)\) is of order \({\mathcal O}(2^{n}\log_{2}n/n^{2})\). A new method of contact circuits synthesis is proposed. With its help the upper bound can be improved, and it is shown that the above mentioned difference is of order \({\mathcal O}(2^{n}/n^{2})\).