Why does the race hazard theorem work?

Question

So for those who don't know, the race hazard theorem (RHT) states that:

A x B + A' x C = A x B + A' x C + B x C

I understand the other part of the RHT, about time delays and such, but I don't understand why the logic statement above should be true, can someone help me understand this?

Answer 1

As others have pointed out, mathematically the statements are exactly the same, and the additional term is "redundant". It would also be "redundant" for me to copy their mathematical proofs here.

You can also easily verify the statements are equivalent by making a 8 row truth table for the three inputs combinations.

    A B C           A*B + A'*C                       A*B + A'*C + B*C
    0 0 0               0                                    0
    0 0 1               1                                    1
    0 1 0               0                                    0
    0 1 1               1  ** hazard b/w states              1
    1 0 0               0                                    0
    1 0 1               0                                    0
    1 1 0               1                                    1
    1 1 1               1  ** hazard b/w states              1

The purpose of the extra term is to prevent A from causing any toggling whenever both B and C are high.

As an example, suppose there is a finite time delay between A and A' (reasonable). Now also consider that both B and C are '1'. As you can see in the waveforms below, there is a glitch at the output.

Assuming the logic is static CMOS, the glitch is recoverable. But, if it were some forms of dynamic logic it could propagate the error.

The addition of the redundant term is a solution to cover the glitch.

Answer 2

Proof by Boolean algebra:

A x B + A' x C [Left-hand side]
= A x B x 1 + A' x C x 1 [Unsimplify AND with true]
= A x B x (1 + C) + A' x C x (1 + B) [True OR anything]
= A x B x 1 + A x B x C + A' x 1 x C + A' x B x C [Distribute]
= A x B + A x B x C + A' x C + A' x B x C [Simplify AND with true]
= A x B + A' x C + A x B x C + A' x B x C [Rearrange terms]
= A x B + A' x C + (A + A') x B x C [Factorize]
= A x B + A' x C + 1 x B x C [OR negation is true]
= A x B + A' x C + B x C [Right-hand side]

Proof by cases:

• Suppose B x C is true.
  Then B is true and C is true simultaneously.
  So the right-hand side becomes A x B + A' x C + 1 x 1 = 1.
  The left hand side becomes A x 1 + A' x 1, which is 1 regardless of A.
  Hence the LHS equals the RHS.
• Suppose B x C is false.
  Then the right-hand side becomes A x B + A' x C + 0 = A x B + A' x C, making it identical to the LHS.
  Hence the LHS equals the RHS.

In all cases, the LHS equals the RHS. Therefore we conclude that the two formulas always evaluate to the same value.

References:

• https://en.wikipedia.org/wiki/Consensus_theorem
• https://www.nayuki.io/page/boolean-algebra-laws

Answer 3

Consider the LHS by itself:
A x B + A' x C

If both B and C are true in this statement, does the condition of A make any difference to the result?
No - because either (A x B) or (A' x C) will be true, producing a result of true.

So now looking at the RHS, the first 2 AND terms are simply a duplicate of the LHS, and the 3rd AND term represents what we just found out about B & C.

Answer 4

\$AB + A'C + BC = AB + A'C + (A+A')BC \textrm{ -- Multiply BC term by 1}\\ = AB + A'C + ABC + A'BC \textrm{ -- Distribute the term}\\ = (AB + ABC) + (A'C + A'BC) \textrm{ -- regroup} \\ = AB(1+C) + A'C (1 + B) \textrm{ -- factor} \\ = AB + A'C \textrm{ -- Simplify} \$

Answer 5

Lets take a look at the karnaugh map:

$$ \begin{matrix} & C\land B' & C\land B & C'\land B & C'\land B \\ A & 0 & 1 & 1 & 0 \\ A' & 1 & 1 & 0 & 0 \\ \end{matrix} $$

You can make the 3 groups in the right hand side of the equation \$A \land B\$, \$A' \land C\$ and \$B \land C\$.

In a karnaugh map race conditions are shown by adjacent but disjoint regions (when counting the toroidal wrapping). If you only take the \$A \land B\$ and \$A' \land C\$ regions you get 2 regions that are adjacent but not joined. You need the \$B \land C\$ term to bridge the gap.