## Logical Design of VLSI Circuit with Extension of Uncertainty
(or monotonic functional completeness of Kleene ternary logic)

**Sun, Yong**
*Abstract:* We consider that traditional 2-valued boolean
algebra is not sufficient in representing VLSI circuit (say at
gate-level), although it seems to be the case for combinational
circuit. Instead of introducing the common technique of
register-and-transfers to represent sequential circuit, we seek an
alternative which is to define an *invertor*, a
*nor-gate* and a *nand-gate* according to actual circuit.
We identify all uncertain voltages as one, which is denoted as \bot
(bottom or uncertain voltages). Other voltages with certainty are,
as usual, denoted definitely as 0 (low voltage or ground) and 1
(high voltage or power). The resulting logic turns out to coincide
with Kleene 3-valued logic with generalized fixed-point
operators.

Unfortunately, Kleene 3-valued logic is functionally incomplete.
This means that not every gate can be constructed from invertors,
nor-gates and nand-gates if gates are viewed to be equivalent to
functions from their inputs to outputs. However, by applying cpo
domain theory [Plotkin 85] to our derived 3-valued logic system, we
discover that this system is functionally monotonic complete. This
implies that all constructible gates share the following property:
*whenever the certainty of input voltages of a gate increases, so
does the certainty of output voltages of the gate.* As
by-products, we also obtain two main facts about logic design of
VLSI circuit.

(a) For any gate, if its input voltages are uncertain, then we
cannot expect to be certain about its output voltages; and

(b) even if we can always supply voltages to inputs of every
gate with great certainty, there exists a constructible gate which
output voltages are always with uncertainty.

So far, our results are mainly semantical ones. We are very
interested in pursuing this research further but from a different
point of view, i.e. from the point of view of syntactical
derivability, since such research would enable us to derive
mathematical secure circuit with more reality to actual circuit
design. Recent Avron's work can be regarded as a few steps towards
this direction [Avron 87, Avron 88]. We should also mention that
Mukaidono has independently obtained the same result in [Mukaidono
86], although his approach is not as coherent as ours.

*ECS-LFCS-89-95*

Previous |

Index |

Next