On the Delay Required to Realize Boolean Functions
- 1 April 1971
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-20 (4) , 459-461
- https://doi.org/10.1109/t-c.1971.223266
Abstract
Using as logic modules two-input one-output arbitrary logic gates, this note considers the problem of the longest chain (number of levels) in a tree-type interconnection realizing a Boolean function of n variables. Specifically, we are interested in the minimum number of levels L(n) by which we can constructively realize all Boolean functions of n variables. It was previously shown that L(n)≤n for n=3, 4 and it was so conjectured for n= 5; in this note we are able to show that this holds for n=5, 6, 7, 8.Keywords
This publication has 1 reference indexed in Scilit:
- On the Time Necessary to Compute Switching FunctionsIEEE Transactions on Computers, 1971