The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design and even in cybersecurity. We show that a DeMorgan circuit is hazard-free if and only if the circuit produces (purely syntactically) all prime implicants as well as all prime implicates of the Boolean function it computes. This extends to arbitrary DeMorgan circuits a classical result of Eichelberger [IBM J. Res. Develop., 9 (1965)] showing this property for special depth-two circuits. Via an amazingly simple
proof, we also strengthen a recent result Ikenmeyer et al. [J. ACM, 66:4 (2019)]: not only the complexities of hazard-free and monotone circuits for monotone Boolean functions do coincide, but every optimal hazard-free circuit for a monotone Boolean function must be monotone. Then we show that hazard-free circuit complexity of a very simple (non-monotone) Boolean function is super-polynomially larger than its unrestricted circuit complexity. This function accepts a Boolean $n\times n$ matrix iff every row and every column has exactly one 1-entry. Finally, we show that every Boolean function of $n$ variables can be computed by a hazard-free circuit of size~$O(2^n/n)$.

A substantial revision of the entire paper is made. Proofs are further simplified; in particular, that of the monotone lower bound (Theorem 1) is reduced to few lines. Duality between 0 and 1 hazards is made explicit (Sect. 6.3). The construction for the order of the Shannon function via the consensus recursion is made more explicit (Sect. 7).

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. We show that a DeMorgan circuit is hazard-free if and only if the circuit produces (purely syntactically) all prime implicants as well as all prime implicates of the Boolean function it computes.
This extends to arbitrary DeMorgan circuits a classical result of Eichelberger [IBM J. Res. Develop., 9 (1965)] showing this property for special depth-two circuits.
Also, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have recently shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the monotone circuit complexity of the monotone Boolean function which accepts an input $x$ iff $f(z)=1$ for some vector $z\leq x$. We give a short and amazingly simple proof of this interesting result. Finally, we give a very simple (non-monotone) Boolean function whose hazard-free circuit complexity is super-polynomially larger than its unrestricted circuit complexity.

The extension of the (classical) result of Eichelberger (Theorem 1) is now "granulated": a more exact characterization of hazards is given (Theorems 4 and 5). The progress towards estimating the Shannon function of hazard-free circuits, recently made by Nitin Saurabh, is now also sketched.

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the monotone circuit complexity of the monotone Boolean function which accepts an input $x$ iff $f(z)=1$ for some vector $z\leq x$. We give a short and amazingly simple proof of this interesting result. We also show that a circuit is hazard-free if and only if the circuit and its dual produce (purely syntactically) all prime implicants of the functions they compute. This extends a classical result of Eichelberger [IBM J. Res. Develop., 9 (1965)] showing this property for depth-two circuits producing no terms containing a variable together with its negation. Finally, we give a very simple non-monotone Boolean function whose hazard-free circuit complexity is super-polynomially larger than its unrestricted circuit complexity.