Почему работает расовая стратегия?

Таким образом, для тех, кто не знает, теорема о расовой опасности (RHT) утверждает, что:

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

Я понимаю другую часть RHT, о задержках времени и тому подобных, но я не понимаю, почему логическое утверждение выше должно быть правдой, может кто-нибудь помочь мне понять это?

12 голосов | спросил Cursed 10 +03002016-10-10T21:59:23+03:00312016bEurope/MoscowMon, 10 Oct 2016 21:59:23 +0300 2016, 21:59:23

5 ответов


20

Как отмечали другие, математически утверждения точно совпадают, а дополнительный термин «избыточен». Для меня также было бы «избыточным», чтобы скопировать их математические доказательства здесь.

Вы также можете легко проверить, что утверждения эквивалентны, сделав таблицу истинности 8 строк для трех комбинаций входов.

    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

Цель дополнительного термина заключается в том, чтобы предотвратить случайное переключение A, когда оба уровня B и C высоки.

В качестве примера предположим, что существует конечная временная задержка между A и A '(разумная). Теперь также рассмотрим, что оба B и C являются «1». Как вы можете видеть в приведенных ниже формах сигналов, на выходе появляется сбой.

 опасность

Предполагая, что логика является статическим CMOS, сбой восстанавливается. Но если бы это были некоторые формы динамической логики, это могло бы распространять ошибку.

Добавление избыточного термина - это решение для устранения сбоя.

ответил jbord39 11 +03002016-10-11T01:20:53+03:00312016bEurope/MoscowTue, 11 Oct 2016 01:20:53 +0300 2016, 01:20:53
9

Доказательство по булевой алгебре:

A x B + A 'x C [Левая сторона]
= A x B x 1 + A 'x C x 1 [Unimimify AND with true]
= A x B x (1 + C) + A 'x C x (1 + B) [Истинный ИЛИ ничего]
= A x B x 1 + A x B x C + A 'x 1 x C + A' x B x C [Распределить]
= A x B + A x B x C + A 'x C + A' x B x C [Упростить AND с истинным]
= A x B + A 'x C + A x B x C + A' x B x C [Переупорядочить условия]
= A x B + A 'x C + (A + A') x B x C [Factorize]
= A x B + A 'x C + 1 x B x C [ИЛИ отрицание истинно]
= A x B + A 'x C + B x C [Правая сторона]

Доказательство по случаям:

  • Предположим, что B x C истинно. Тогда B истинно, а C истинно одновременно.
    Таким образом, правая часть становится A x B + A 'x C + 1 x 1 = 1.
    Левая часть становится A x 1 + A 'x 1, которая равна 1 независимо от A.
    Следовательно, LHS равно RHS.
  • Предположим, что B x C неверно. Тогда правая часть становится A x B + A 'x C + 0 = A x B + A' x C, что делает ее идентичной LHS.
    Следовательно, LHS равно RHS.

Во всех случаях LHS равно RHS. Поэтому мы заключаем, что две формулы всегда оцениваются с одинаковым значением.

Литература:

ответил Nayuki 10 +03002016-10-10T23:51:27+03:00312016bEurope/MoscowMon, 10 Oct 2016 23:51:27 +0300 2016, 23:51:27
8

Рассмотрим LHS самостоятельно:
A x B + A 'x C

Если оба B и C истинны в этом утверждении, делает ли условие A какое-либо значение для результата?
Нет - потому что либо (A x B), либо (A 'x C) будет истинным, создавая результат истины.

Итак, теперь, глядя на RHS, первые 2 AND-выражения - просто дубликат LHS, а третий И-член представляет то, что мы только что узнали о B & С.

ответил brhans 10 +03002016-10-10T22:15:10+03:00312016bEurope/MoscowMon, 10 Oct 2016 22:15:10 +0300 2016, 22:15:10
3

\ $ AB + A'C + BC = AB + A'C + (A + A ') BC \ textrm {- умножить BC на 1} \\  = AB + A'C + ABC + A'BC \ textrm {- Распределить член} \\  = (AB + ABC) + (A'C + A'BC) \ textrm {- regroup} \\  = AB (1 + C) + A'C (1 + B) \ textrm {- factor} \\  = AB + A'C \ textrm {- Simplify} \ $

ответил pgvoorhees 10 +03002016-10-10T22:20:35+03:00312016bEurope/MoscowMon, 10 Oct 2016 22:20:35 +0300 2016, 22:20:35
2

Давайте посмотрим на карту karnaugh :

$$ \ Начать {матрица} & Амп; C \ land B '& C \ land B & C '\ land B & C '\ land B \\ A & 0 & 1 & 1 & 0 \\ A & 1 & 1 & 0 & 0 \\ \ Конец {матрица} $$

Вы можете сделать 3 группы в правой части уравнения \ $ A \ land B \ $, \ $ A '\ land C \ $ и \ $ B \ land C \ $.

В условиях карна-карты условия гонки показаны соседними, но непересекающимися областями (при подсчете тороидальной обертки). Если вы берете только области $ \ A \ land B \ $ и \ $ A '\ land C \ $, вы получаете 2 региона, которые смежны, но не объединены. Для преодоления разрыва вам нужен термин \ C $ \ \ C \ $.

ответил ratchet freak 11 +03002016-10-11T13:48:31+03:00312016bEurope/MoscowTue, 11 Oct 2016 13:48:31 +0300 2016, 13:48:31

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132