@article{a733ea6c86fa4be89068762af5d53e88,
title = "Four-valued reasoning and cyclic circuits",
abstract = "Allowing cycles in a logic circuit can be advantageous, for example, by reducing the number of gates required to implement a given Boolean function, or a set of functions. However, a cyclic circuit may easily be ill behaved. For instance, it may have some output wire oscillation instead of reaching a steady state. Propositional three-valued logic has long been used in tests for good behavior of cyclic circuits; a symbolic evaluation method known as ternary analysis provides one criterion for good behavior under certain assumptions about wire and gate delay. We revisit ternary analysis and argue for the use of four truth values. The fourth truth value allows for the distinction of undefined and underspecified behavior. Ability to under specify behavior is useful, because, in a quest for smaller circuits, an implementor can capitalize on degrees of freedom offered in the specification. Moreover, a fourth truth value is attractive because, rather than complicating (ternary) circuit analysis, it introduces a pleasant symmetry, in the form of contra-duality, as well as providing a convenient framework for manipulating specifications. We use this symmetry to provide fixed point results that clarify how two-, three-, and four-valued analyses are related, and to explain some observations about ternary analysis.",
keywords = "Boolean functions, circuit optimization, combinational circuits, multivalued logic",
author = "Graeme Gange and Benjamin Horsfall and Lee Naish and Harald S{\o}ndergaard",
year = "2014",
month = jan,
day = "1",
doi = "10.1109/TCAD.2014.2304176",
language = "English",
volume = "33",
pages = "1003--1016",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "IEEE, Institute of Electrical and Electronics Engineers",
number = "7",
}