Information theory and the complexity of switching networks

Abstract

Our purpose in this paper is to establish some relationships between two areas pioneered by Shannon: information theory and the complexity of switching networks that realize Boolean functions. We investigate the following three questions. 1. How does the complexity of a function depend on the number of 1\u27s and 0\u27s in its truth table? 2. How does the complexity of an incompletely specified function depend on the number of unspecified entries in its truth table? 3. If we do not insist that a function be realized exactly, but allow a certain number of entries in its truth table to be changed, what reduction in complexity is possible? These questions are answered by combinatorial arguments, but in each case the answer admits an information-theoretic interpretation that renders it more memorable. This interpretation has only heuristic significance, however, and does not provide an alternate means of deriving our results