Por que o teorema do risco de corrida funciona?

12

Portanto, para quem não sabe, o teorema do risco de corrida (RHT) afirma que:

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

Entendo a outra parte do RHT, sobre atrasos e outras coisas, mas não entendo por que a afirmação lógica acima deve ser verdadeira. Alguém pode me ajudar a entender isso?

Alex Robinson
fonte

Respostas:

20

Como outros já apontaram, matematicamente, as declarações são exatamente as mesmas e o termo adicional é "redundante". Também seria "redundante" para mim copiar suas provas matemáticas aqui.

Você também pode verificar facilmente se as instruções são equivalentes criando uma tabela verdade de 8 linhas para as três combinações de entradas.

    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

O objetivo do termo extra é impedir que A cause qualquer alternância sempre que B e C estiverem altos.

Como exemplo, suponha que haja um atraso de tempo finito entre A e A '(razoável). Agora considere também que B e C são '1'. Como você pode ver nas formas de onda abaixo, há uma falha na saída.

perigo

Supondo que a lógica seja CMOS estática, a falha é recuperável. Mas, se houvesse algumas formas de lógica dinâmica, poderia propagar o erro.

A adição do termo redundante é uma solução para cobrir a falha.

jbord39
fonte
2
Voto negativo, porque isso nem tenta responder à pergunta que foi feita. Responde a uma pergunta diferente.
user253751
@immibis Obviamente o autor da pergunta está bem com esta resposta.
glglgl
@immibis Além disso, sem essa resposta, muitas coisas não eram muito óbvias.
glglgl
@glglgl O autor da pergunta diz que ele já conhece essa parte.
user253751
4
@immibis: Para ser sincero, a maior parte da resposta é contextual, mas o núcleo está no primeiro parágrafo: escreva as tabelas da verdade. Os dois lados da equação são idênticos, porque suas tabelas de verdade são idênticas. Para todos os 8 valores possíveis de A, B e C, esquerda e direita são iguais. O restante da resposta explica por que, na realidade, não podemos assumir que {A,A',B,C}estejam restritos a apenas 8 valores; existe essa condição transitória A = A '.
MSalters 11/11/16
9

Prova de álgebra booleana:

A x B + A 'x C [lado esquerdo]
= A x B x 1 + A' x C x 1 [Não simplifique AND com verdadeiro]
= A x B x (1 + C) + A 'x C x ( 1 + B) [Verdadeiro OR qualquer coisa]
= A x B x 1 + A x B x C + A 'x 1 x C + A' x B x C [Distribuir]
= A x B + A x B x C + A 'x C + A' x B x C [Simplifique AND com verdadeiro]
= A x B + A 'x C + A x B x C + A' x B x C [Reorganize os termos]
= A x B + A 'x C + (A + A ') x B x C [Fatorar]
= A x B + A' x C + 1 x B x C [A negação OR é verdadeira]
= A x B + A 'x C + B x C [ Lado direito]

Prova de casos:

  • Suponha que B x C seja verdadeiro.
    Então B é verdadeiro e C é verdadeiro simultaneamente.
    Portanto, o lado direito se torna A x B + A 'x C + 1 x 1 = 1.
    O lado esquerdo se torna A x 1 + A' x 1, que é 1 independentemente de A.
    Portanto, o LHS é igual ao RHS.
  • Suponha que B x C seja falso.
    Então o lado direito se torna A x B + A 'x C + 0 = A x B + A' x C, tornando-o idêntico ao LHS.
    Portanto, o LHS é igual ao RHS.

Em todos os casos, o LHS é igual ao RHS. Portanto, concluímos que as duas fórmulas sempre avaliam o mesmo valor.

Referências:

Nayuki
fonte
8

Considere o LHS por si só:
A x B + A 'x C

Se B e C forem verdadeiros nesta afirmação, a condição de A faz alguma diferença no resultado?
Não - porque (A x B) ou (A 'x C) será verdadeiro, produzindo um resultado verdadeiro.

Então, agora, olhando para o RHS, os dois primeiros termos AND são simplesmente uma duplicata do LHS, e o terceiro termo AND representa o que acabamos de descobrir sobre B & C.

brhans
fonte
3

UMAB+UMAC+BC=UMAB+UMAC+(UMA+UMA)BC - Multiplique o termo BC por 1=UMAB+UMAC+UMABC+UMABC - Distribua o termo=(UMAB+UMABC)+(UMAC+UMABC) - reagrupar=UMAB(1+C)+UMAC(1+B) - fator=UMAB+UMAC -- Simplificar

pgvoorhees
fonte
2

Vamos dar uma olhada no mapa de karnaugh :

CBCBCBCBUMA0 0110 0UMA110 00 0

UMABUMACBC

UMABUMACBC

catraca arrepiante
fonte