# Combinatorial devices

Lifting a definition from Ward and Halstead's *Computation Structures* (ISBN 0-262-23139-5), pp4--5:

A combinatorial device is a circuit element have the following properties:

- One or more discrete-valued
inputterminals;- One or more discrete-valued
outputterminals;- A
functional specification, detailing the value of each output for each of the possible combinations of input values; and- A
timing specification, consisting (at minimum) of an upper boundt_{pd}on the time required for the device to compute the specified output values from an arbitrary set of input values.

*t*_{pd} is known as the *propagation delay* of a device, and interpreted as a maximum time before outputs reflect the provided inputs (a minimum delay, if specified, is known as *contamination delay*). Thus, inputs provided and maintained for *t* seconds can be read for at least *t* - *t*_{pd} seconds. Combinatorial devices are closed under combinatorial composition:

A circuit is a combinatorial device if it consists of interconnected circuit elements such that:

- Each circuit element is itself combinatorial,
- Every node of the circuit is either designated as an input to the circuit or connects to exactly one output terminal of the circuit element, and
- The circuit contains no directed cycles.

Each output of a composed combinatorial device has its own *t*_{pd}, equal to the maxmium cumulative propagation delays encountered on any path from an input to that output.