A combinational logic network is one that is free of synchronous elements. This is not a particularly helpful definition -- we will use only the fact that a combinational circuit that is also free of directed cycles implements a pure function. The outputs depend only on the value of the inputs and not on their history.

The circuit is implemented using wires, transistors, *etc*.
This obvious fact has two important consequences. First, to be
useful the circuit is attached to a source of inputs and those
inputs change over time. Secondly, the outputs do not instantaneously
change in response to a change in the inputs; some finite delay is
involved.

Quite sophisticated treatments of this delay have been studied.
For our purposes it will suffice to consider just the gross maximum
delay: the time between the inputs becoming *stable* and the
outputs reliably taking on the function value corresponding to
those inputs. To a very loose first approximation the lower bound on
delay for realizations of a given function is proportional to the
logarithm of the number of input bits.

Mon Dec 11 17:02:42 CST 2000