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?

jbord39 · Accepted Answer · 2016-10-11T22:53:22.260

21

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.

edited Oct 11 '16 at 22:53

answered Oct 10 '16 at 22:20

jbord39

4,320
1
17
25

2

Downvoting because this doesn't even attempt to answer the question that was asked. It answers a different question. – user253751 Oct 11 '16 at 03:50
@immibis Obviously the asker is ok with this answer. – glglgl Oct 11 '16 at 09:26
@immibis Besides, without this answer, many things weren't quite obvious. – glglgl Oct 11 '16 at 09:39
@glglgl The asker specifically says s/he already knows this part. – user253751 Oct 11 '16 at 09:42
4

@immibis: To be honest, the bulk of the answer is background, but the core is in the first paragraph: write out the truth tables. The two sides of the equation are identical, _because_ their truth tables are identical. For all 8 possible values of A, B and C, the left and right are equal. The rest of the answer then explains why in reality, we cannot assume that `{A,A',B,C}` are restricted to just 8 values; there's this transient A=A' condition. – MSalters Oct 11 '16 at 11:20
@immibis: alright, I added the truth table for ya. But honestly I do not feel it was necessary – jbord39 Oct 11 '16 at 22:54

Nayuki · Answer 2 · 2016-10-10T20:59:33.230

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:

score 8 · Answer 3 · answered Oct 10 '16 at 19:15

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.

score 3 · Answer 4 · answered Oct 10 '16 at 19:20

\$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} \$

ratchet freak · Answer 5 · 2016-10-11T11:07:16.423

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.

Why does the race hazard theorem work?

5 Answers5