Dlaczego działa twierdzenie o zagrożeniu rasowym?

12

Zatem dla tych, którzy nie wiedzą, twierdzenie o zagrożeniu rasowym (RHT) stwierdza, że:

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

Rozumiem drugą część RHT, dotyczącą opóźnień czasowych i tym podobnych, ale nie rozumiem, dlaczego powyższe zdanie logiczne powinno być prawdziwe, czy ktoś może mi pomóc to zrozumieć?

Alex Robinson
źródło

Odpowiedzi:

20

Jak zauważyli inni, twierdzenia matematyczne są dokładnie takie same, a dodatkowy termin to „zbędne”. Kopiowanie ich matematycznych dowodów tutaj byłoby również „zbędne”.

Można również łatwo sprawdzić, czy instrukcje są równoważne, tworząc 8-wierszową tabelę prawdy dla trzech kombinacji danych wejściowych.

    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

Dodatkowy termin ma na celu zapobieganie przełączaniu się A, gdy B i C są wysokie.

Jako przykład załóżmy, że istnieje opóźnienie czasowe między A i A '(uzasadnione). Teraz rozważ również, że zarówno B, jak i C są „1”. Jak widać na poniższych przebiegach, na wyjściu występuje usterka.

zaryzykować

Zakładając, że logika jest statyczna CMOS, usterkę można odzyskać. Ale gdyby były to niektóre formy dynamicznej logiki, mogłoby to propagować błąd.

Dodanie zbędnego terminu stanowi rozwiązanie problemu usterki.

jbord39
źródło
2
Oddawanie głosu, ponieważ to nawet nie próbuje odpowiedzieć na zadane pytanie. Odpowiada na inne pytanie.
user253751,
@immibis Oczywiście pytający zgadza się z tą odpowiedzią.
glglgl 11.10.16
@immibis Poza tym bez tej odpowiedzi wiele rzeczy nie było całkiem oczywistych.
glglgl 11.10.16
@glglgl Pytający wyraźnie mówi, że już zna tę część.
user253751,
4
@immibis: Szczerze mówiąc, większość odpowiedzi stanowi tło, ale sedno znajduje się w pierwszym akapicie: napisz tabele prawdy. Dwie strony równania są identyczne, ponieważ ich tablice prawdy są identyczne. Dla wszystkich 8 możliwych wartości A, B i C, lewa i prawa są równe. Pozostała część odpowiedzi wyjaśnia, dlaczego w rzeczywistości nie możemy założyć, że {A,A',B,C}są ograniczone tylko do 8 wartości; istnieje stan przejściowy A = A '.
MSalters
9

Dowód algebry boolowskiej:

A x B + A 'x C [Lewa strona]
= A x B x 1 + A' x C x 1 [Nie upraszczaj AND z prawdą]
= A x B x (1 + C) + A 'x C x ( 1 + B) [Prawda LUB cokolwiek]
= A x B x 1 + A x B x C + A 'x 1 x C + A' x B x C [Dystrybucja]
= A x B + A x B x C + A „x C + A” x B x C [Uprość AND z prawdą]
= A x B + A 'x C + A x B x C + A' x B x C [Zmień terminy]
= A x B + A 'x C + (A + A ') x B x C [Faktoryzuj]
= A x B + A' x C + 1 x B x C [LUB negacja jest prawdziwa]
= A x B + A 'x C + B x C [ Prawa strona]

Dowód według przypadków:

  • Załóżmy, że B x C jest prawdziwe.
    Wtedy B jest prawdziwe, a C jest prawdziwe jednocześnie.
    Tak więc prawa strona staje się A x B + A 'x C + 1 x 1 = 1.
    Lewa strona staje się A x 1 + A' x 1, czyli 1 niezależnie od A.
    Stąd LHS równa się RHS.
  • Załóżmy, że B x C jest fałszem.
    Następnie prawa strona staje się A x B + A 'x C + 0 = A x B + A' x C, co czyni go identycznym z LHS.
    Stąd LHS równa się RHS.

We wszystkich przypadkach LHS równa się RHS. Dlatego dochodzimy do wniosku, że te dwie formuły zawsze mają tę samą wartość.

Bibliografia:

Nayuki
źródło
8

Rozważ sam LHS:
A x B + A 'x C

Jeśli zarówno B, jak i C są prawdziwe w tym stwierdzeniu, to czy warunek A ma jakikolwiek wpływ na wynik?
Nie - ponieważ albo (A x B) albo (A 'x C) będzie prawdziwe, dając wynik true.

Patrząc teraz na RHS, pierwsze 2 terminy AND są po prostu duplikatem LHS, a trzeci termin AND reprezentuje to, co właśnie dowiedzieliśmy się o B&C.

brhans
źródło
3

AB+AC+BC=AB+AC+(A+A)BC -- Multiply BC term by 1=AB+AC+ABC+ABC -- Distribute the term=(AB+ABC)+(AC+ABC) -- regroup=AB(1+C)+AC(1+B) -- factor=AB+AC -- Simplify

pgvoorhees
źródło
2

Rzućmy okiem na mapę karnaugh :

CBCBCBCBA0110A1100

Można wprowadzić 3 grupy po prawej stronie równania , i .A C B CABACBC

Na mapie karnaugh warunki wyścigu są pokazane przez sąsiednie, ale rozłączne regiony (przy liczeniu owijania toroidalnego). Jeśli weźmiesz tylko regiony i , otrzymasz 2 regiony, które sąsiadują, ale nie są połączone. Potrzebujesz terminu aby wypełnić lukę.A C B CABACBC

maniak zapadkowy
źródło