Булевские тождества
Основные тождества, связанные с булевой алгеброй.
Рекомендуемый уровень
начинающий
Предварительное чтение
В этой статье предполагается, что вы прочитали и довольны статьей Boolean Basics (в которой также содержится список ссылок на другие статьи этой серии). Если вы столкнулись с трудностями, следуя концепциям или обозначениям, используемым здесь, вы можете просмотреть эту статью.
Булева идентификация - сводка
Подобно нормальной алгебре, булева алгебра имеет ряд полезных тождеств. «Тождество» - это просто отношение, которое всегда верно, независимо от значений, которые могут принимать любые переменные. Многие из них очень похожи на нормальное умножение и добавление, особенно когда символы {0, 1} используются для {FALSE, TRUE}. Но в то время как это может быть полезно, есть некоторые идентичности, которые отличаются друг от друга, и это вызывает путаницу для многих людей - мы выделим их, когда мы их встретим. Начнем с таблицы, суммирующей эти тождества, а затем продолжим подробно изучать каждую из них.
| ИДЕНТИЧНОСТЬ | ЭКСПРЕССИЯ | |
| Логический инверсный | $$ \ overline {0} = 1;;; \ overline {1} = 0 $$ | |
| инволюция | $$ \ overline { overline {A}} = A $$ | |
| ИЛИ | А ТАКЖЕ | |
| господство | $$ A + 1 = 1 $$ | $$ A \ cdot 0 = 0 $$ |
| тождественность | $$ A + 0 = A $$ | $$ A \ cdot 1 = A $$ |
| идемпотентность | $$ A + A = A $$ | $$ A \ cdot A = A $$ |
| взаимодополняемость | $$ A + \ overline {A} = 1 $$ | $$ A \ cdot \ overline {A} = 0 $$ |
|
Перестановочность |
$$ A + B = B + A $$ | $$ A \ cdot B = B \ cdot A $$ |
| Ассоциативность | $$ (A + B) + C = A + (B + C) $$ | $$ (A \ cdot B) cdot C = A \ cdot (B \ cdot C) $$ |
| Дистрибутивность | $$ A + (B \ cdot C); знак равно (A + B) cdot (A + C) $$ | $$ A \ cdot (B + C) = (A \ cdot B) + (A \ cdot C) $$ |
| абсорбция | $$ A \ cdot (A + B) = A $$ | $$ A \ cdot (A + B) = A $$ |
| де Моргана | $$ A + B = \ overline { overline {A} cdot \ overline {B}} $$ | $$ A \ cdot B = \ overline { overline {A} + \ overline {B}} $$ |
Каждый из этих тождеств можно доказать, просто создав полностью перечисленную таблицу истинности для выражения слева (знака равенства, а не таблицы), а другой для выражения справа и показывая, что они дают тот же результат для всевозможные ввод комбинация. Это будет сделано для каждой личности. Более элегантный способ - использовать ранее проверенные идентификаторы для подтверждения последующих. В общем, мы не будем этого делать, прежде всего потому, что упорядочение приведенной выше таблицы предназначено для отслеживания значительной интуитивной прогрессии и не оптимизировано для поддержки цепочки булевых доказательств.
Обратите внимание, что для каждого тождества, связанного с OR и / или оператором AND, существует соответствующее тождество, в котором роли этих двух операторов меняются на противоположные. Это связано с «двойственностью» AND и OR, предметом, подробно рассмотренным в отдельной статье.
Во всех выражениях в этой статье мы не делаем предположений ни о старшинстве, ни об ассоциативности операторов, что означает, что мы будем в значительной степени полагаться на полностью выраженные выражения в скобках. Поскольку мы будем использовать обозначение overbar для логического отрицания (оператор NOT), мы будем использовать естественное соглашение о том, что выражение под баром оценивается, а результат этого инвертируется (NOTED).
Булевские тождества - подробные пояснения
Теперь мы проработаем наш путь через таблицу тождеств, чтобы делать наблюдения за каждым, обычно включающим неофициальное доказательство «здравого смысла». В дополнение к булевым выражениям каждый идентификатор также будет отображаться графически с использованием стандартных логических схемных символов. Символы для NOT, OR и AND были введены в статью Boolean Basics. В дополнение к этим мы будем использовать символ BUF для представления неинвертирующего буфера. Эти ворота просто копируют свой ввод в свой вывод. Кроме того, хотя мы используем {0, 1} для представления {FALSE, TRUE} в булевых выражениях, мы будем использовать {LO, HI} для представления их на схематических диаграммах.
Обратите внимание, что символ NOT - это просто символ BUF, за которым следует пузырь. Пузырь представляет собой логическую инверсию и является фактическим НЕ ворот. Каждый раз, когда вы видите пузырь, прикрепленный к выходу затвора, вы можете отсоединить его от штифта и вставить отдельный вентиль НЕ на свое место, не затрагивая результирующую логику.
За каждым обсуждением следует формальное доказательство с помощью полнозначных таблиц истинности. Для большинства идентификаторов эти доказательства не будут содержать никаких сюрпризов. Но они заслуживают внимания, потому что некоторые из менее интуитивных доказательств могут иметь больше смысла, когда вы можете увидеть, как логика развивается через таблицы.
Логический инверсный
Это тождество, которое на самом деле является двумя отдельными тождествами, является просто определением логического отрицания, применяемого к каждому из возможных булевых значений.
$$ \ overline {0}; знак равно 1 $$
$$ \ overline {1}; знак равно 0 $$
доказательство
Поскольку это наша первая идентичность, наше доказательство должно основываться на фундаментальных определениях сигналов и операторов (что будет верно для нескольких ранних тождеств). Поскольку единственной операцией, которая здесь является, является отрицание, мы просто устанавливаем определение отрицания и отмечаем, что эти тождества являются просто двумя строками в этом определении.
| 0 |
LHS $$ \ overline {0} $$ |
RHS 1 |
| 0 | 1 | 1 |
| 1 |
LHS $$ \ overline {0} $$ |
RHS 0 |
| 1 | 0 | 0 |
инволюция
В математике функция называется инволютивной, если она является ее собственным обратным. В обычной арифметике обратная функция инволютивна, так как обратная величина обратной величины дает исходное значение, так как умножает значение дважды на -1. В логической логике отрицание является инволютивной функцией, потому что отрицание значения дважды возвращает исходное значение. Это аналогично «двойному отрицательному» в обычном разговоре.
$$ \ overline { overline {A}}; = A $$ или $$ (A ')'; знак равно A $$
Доказательство
| $$ \ overline {A} $$ | $$ \ overline { left ( overline {A} right)}; знак равно \ overline { overline {A}} $$ |
LHS $$ \ overline { overline {A}} $$ |
RHS | |
| 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
господство
При нормальном умножении мы имеем свойство, что все, умноженное на ноль, дает нуль. В некотором смысле это означает, что нуль обладает способностью подавлять, маскировать или доминировать над любым другим значением при умножении. Тождество доминирования - также известное как «подавление» или «маскировка» идентичности - похоже и просто признает, что все, что OR'ed с TRUE, порождает TRUE, в то время как что-либо AND'ed с FALSE производит FALSE.
$$ A + 1 = 1 $$
$$ A \ cdot 0 = 0 $$
В то время как второе свойство выглядит так же, как и нормальное умножение, первое свойство, безусловно, НЕ совпадает с нормальным дополнением. Это нужно иметь в виду, пока вы не овладеете булевой алгеброй, потому что очень легко вернуться к хорошо укоренившимся привычкам и применять правила от нормальной алгебры к булевой алгебре, когда они просто недействительны или не могут использовать правила, которые находятся.
Доказательство
| 1 |
LHS А + 1 |
RHS 1 |
|
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 0 |
LHS $$ A \ cdot 0 $$ |
RHS 0 |
|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 |
Обратите внимание, что технически приведенные здесь доказательства относятся только к случаю, когда первый вход является свободной переменной, а второй вход является доминирующим значением для этой операции. Мы могли бы доказать, что тождество, заключенное с входами, обменивается, но как только мы докажем, что оба OR и AND являются коммутативными, эти доказательства становятся тривиальными и неинтересными.
тождественность
Точно так же, как 0 - единичный элемент для нормального сложения, а 1 - единичный элемент для умножения, то также равны 0 (FALSE) и 1 (TRUE) единичные элементы для OR и AND соответственно.
$$ A + 0 = A $$
$$ A \ cdot 1 = A $$
Это свойство, более чем что-либо другое, является причиной того, что символ добавления используется для логического ИЛИ, а символ умножения используется для логического И. Но важно помнить, что в булевой алгебре мы НЕ «добавляем» или «умножаем» два значения, когда используем эти операторы. Использование этой терминологии является плохой формой и, как правило, неодобрительно (хотя это слышно довольно регулярно). Сказав это, термины «сумма» и «продукт» широко используются и принимаются для результатов логического ИЛИ и логического И, соответственно. Поэтому, хотя это плохая форма говорить о «добавлении A и B», приемлемо говорить о «сумме A и B»; это может показаться странным и даже непоследовательным, но это просто результат компромисса, который сложился между математически строгой терминологией и практическим общим языком - например, проще и чище говорить о «сумме продуктов», OR OF AND ".
Идентичность для OR поступает непосредственно из определения OR, когда второй ввод ограничен 0, тогда как идентификатор для AND поступает непосредственно из его определения, когда второй вход ограничен 1.
Доказательство
Идентичность для OR поступает непосредственно из определения OR, когда второй ввод ограничен 0, тогда как идентификатор для AND поступает непосредственно из его определения, когда второй вход ограничен 1.
| 0 |
LHS А + 0 |
RHS | |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 |
LHS $$ A \ cdot 1 $$ |
RHS | |
| 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Обратите внимание, что технически приведенные здесь доказательства относятся только к случаю, когда первый вход является свободной переменной, а второй вход является значением идентичности для этой операции. Мы могли бы доказать, что тождество, заключенное с входами, обменивается, но как только мы докажем, что оба OR и AND являются коммутативными, эти доказательства становятся тривиальными и неинтересными.
идемпотентность
Термин «идемпотент» описывает операцию, которая может выполняться любое количество раз, и эффект такой же, как если бы он выполнялся только один раз. Если мы либо И, и логическая переменная с самим собой, либо OR с самим собой, получаем тот же результат, что и исходная переменная. Это означает, что И И и ИЛИ являются идемпотентными. Это свойство выражается как
$$ A + A = A $$
$$ A \ cdot A = A $$
Обратите внимание, что это ОЧЕНЬ отличается от обычной арифметики.
Доказательство
Доказательство идемпотенции как для OR, так и для AND следует из рассмотрения определения каждой операции при условии, что оба входа имеют одинаковое значение.
|
LHS А + А |
RHS | ||
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
|
LHS $$ A \ cdot A $$ |
RHS | ||
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
взаимодополняемость
«Дополнение» (в отличие от «комплимента») противоположно чему-то. Фактически, другим именем для логического обратного является дополнение. Когда мы OR или AND булево значение с его дополнением, мы получаем тот же результат независимо от значения переменной. В случае AND, поскольку мы знаем, что либо переменная, либо ее дополнение FALSE, логическое AND переменной с ее дополнением всегда будет давать FALSE, поскольку доминирует FALSE. Точно так же, поскольку мы знаем, что один из них TRUE, логический OR переменной с ее дополнением всегда будет иметь TRUE, потому что доминирует TRUE.
$$ A + \ overline {A} = 1 $$
$$ A \ cdot \ overline {A} = 0 $$
Чтобы иметь свойство комплементарности, все, что требуется от булевого бинарного оператора, состоит в том, что оно симметрично, что означает, что две строки в своей определяющей таблице истинности, имеющие разные входы, дают одинаковый результат. Это удивительно мощная идентичность, которая часто играет роль в сокращении или «упрощении» булевых выражений.
Доказательство
Чтобы иметь свойство комплементарности, все, что требуется от булевого бинарного оператора, состоит в том, что оно симметрично, что означает, что две строки в своей определяющей таблице истинности, имеющие разные входы, дают одинаковый результат.
| $$ \ overline {A} $$ |
LHS $$ A + \ overline {A} $$ |
RHS 1 |
|
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| $$ \ overline {A} $$ |
LHS $$ A \ cdot \ overline {A} $$ |
RHS 0 |
|
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
Обратите внимание, что технически приведенные здесь доказательства применимы только к случаю, когда первый вход является незавершенной свободной переменной, а второй вход - его дополнением. Мы могли бы доказать, что тождество, заключенное с входами, обменивается, но как только мы докажем, что оба OR и AND являются коммутативными, эти доказательства становятся тривиальными и неинтересными.
Перестановочность
Как и в обычной арифметике, порядок операндов для OR и AND не имеет значения, делая их как коммутативными.
$$ A + B = B + A $$
$$ A \ cdot B = B \ cdot A $$
Это также описано, говоря, что И и ИЛИ являются «симметричными» функциями.
Подобно комплементарности, все, что требуется для того, чтобы бинарный логический оператор был коммутативным, состоит в том, что две строки в определяющей таблице истинности, имеющие разные входы, производят один и тот же вывод. Следствием этого является то, что любой бинарный булевой оператор, который является коммутативным, также дополняет, и наоборот.
Доказательство
Подобно комплементарности, все, что требуется для того, чтобы бинарный булевы операторы были коммутативными, состоит в том, что две строки в определяющей таблице истинности, имеющие разные входы, создают одинаковый вывод. Следствием этого является то, что любой бинарный булевой оператор, который является коммутативным, также дополняет, и наоборот.
| В |
LHS A + B |
RHS B + A |
|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| В |
LHS $$ A \ cdot B $$ |
RHS $$ A \ cdot B $$ |
|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Ассоциативность
Опять же, как и в обычной арифметике с добавлением и умножением, порядок, в котором мы применяем операции, когда задействуются два или более одного и того же оператора, не имеет значения.
$$ (A + B) + C = A + (B + C) $$
$$ (A \ cdot B) cdot C = A \ cdot (B \ cdot C) $$
Ассоциативность OR и AND вовсе не очевидна. Заманчиво предположить, что поскольку OR и AND являются коммутативными, они также должны быть ассоциативными. Однако это не так, и некоторые булевы операторы NAND и NOR (обсуждаемые в более поздней статье), которые являются коммутативными, не являются ассоциативными.
Доказательство
| В | С | (A + B) | (B + C) |
LHS (A + B) + C |
RHS A + (B + C) |
|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| В | С | $$ (A \ cdot B) $$ | $$ (B \ cdot C) $$ |
LHS $$ (A \ cdot B) cdot C $$ |
RHS $$ A \ cdot (B \ cdot C) $$ |
|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Дистрибутивность
В обычной арифметике мы часто используем свойство, которое умножение распределяет по добавлению, и известно, что добавление не распространяется по умножению. Однако в булевой алгебре любой оператор распределяется по другому.
$$ A + (B \ cdot C) = (A + B) cdot (A + C) $$
$$ A \ cdot (B + C) = (A \ cdot B) + (A \ cdot C) $$
Это последнее свойство, потому что оно противоречит нашему усвоенному пониманию правил арифметики, кажется очень неестественным, и многие люди не знают, что это правда или активно считают, что это неверно. Это почти полностью непреднамеренное следствие использования знака плюс-знак и знак умножения из обычной арифметики и неспособности запомнить, что логические операторы и арифметические операторы просто не одно и не имеют абсолютно никакого отношения друг к другу, независимо от того, используйте символы для их представления.
Оба эти свойства чрезвычайно полезны и, что не удивительно, многие люди делают свою работу намного сложнее, потому что они не умеют распознавать, где применение disitributivity OR над AND значительно упростит ситуацию.
Доказательство
| В | С | (B + C) | $$ (A \ cdot B) $$ | $$ (A \ cdot C) $$ |
LHS $$ A \ cdot (B + C) $$ |
RHS $$ (A \ cdot B) + (A \ cdot C) $$ |
|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| В | С | $$ (B \ cdot C) $$ | $$ (A + B) $$ | $$ (A + C) $$ |
LHS $$ A + (B \ cdot C) $$ |
RHS $$ (A + B) cdot (A + C) $$ |
|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
абсорбция
Одним из наиболее полезных булевых тождеств является поглощение, поскольку оно позволяет использовать ненужные переменные. Но, кроме того, он также позволяет вводить переменные, которые часто позволяют нам сделать еще большие упрощения.
$$ A + (A \ cdot B) = A $$
$$ A \ cdot (A + B) = A $$
Неформально эти идентичности имеют смысл, рассматривая возможные варианты. В первом случае, если A является FALSE, тогда все выражение FALSE, а если A - TRUE, тогда (A + B) имеет значение TRUE независимо от значения B, а выражение в целом равно TRUE. Таким образом, в любом случае общее выражение равно значению А. Во втором случае это еще более очевидно. Если A TRUE, то общее выражение TRUE, а если A - FALSE, второй член FALSE независимо от значения B, а общее выражение FALSE. Опять же, общее выражение равно значению А.
Эти два идентичностей, как правило, являются теми, которые трудно вспомнить людям, поэтому полезно видеть алгебраическое доказательство, потому что манипуляции часто легче для людей видеть и применять, чем сами личности.
В первом идентификаторе мы можем либо «разложить» A, используя дистрибутивное свойство AND над OR, либо просто распределить OR над AND. Давайте используем первый подход, так как это тот, который обычно легче увидеть на практике.
Второе идентичность на самом деле более интуитивно понятна, поскольку сначала можно распределить А, используя дистрибутивное свойство И над ИЛИ, а затем, применяя идемпотентность, отбрасывая его обратно.
Доказательство
| В | $$ (A + B) $$ |
LHS $$ A \ cdot (A + B) $$ |
RHS | |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| В | $$ (A \ cdot B) $$ |
LHS $$ A + (A \ cdot B) $$ |
RHS | |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
С ранее доказанными тождествами идентичности поглощения могут быть доказаны алгебраически в очень коротком порядке.
Вышеприведенное доказательство фактически содержит доказательство для тождества поглощения при И, начиная со второй строки.
де Моргана
Тождества DeMorgan, более известные как теоремы ДеМоргана, являются чрезвычайно мощными и сильно используемыми свойствами логической логики. По сути, они говорят, что и логический элемент ИЛИ может быть заменен логическим элементом И (и наоборот) без изменения реализуемой логической функции при условии, что ВСЕ входы и выходы в ворота также инвертируются.
$$ A + B = \ overline { overline {A} cdot \ overline {B}} $$
$$ A \ cdot B = \ overline { overline {A} + \ overline {B}} $$
Вспоминая, что пузырь на входе или выходе затвора представляет собой логическую инверсию, теоремы ДеМоргана можно зафиксировать очень компактно следующим образом:
Доказательство
| В | A + B | $$ \ overline {A} $$ | $$ \ overline {B} $$ | $$ \ overline {A} cdot \ overline {B} $$ |
LHS $$ A + B $$ |
RHS $$ \ overline { overline {A} cdot \ overline {B}} $$ |
|
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| В | $$ A \ cdot B $$ | $$ \ overline {A} $$ | $$ \ overline {B} $$ | $$ \ overline {A} + \ overline {B} $$ |
LHS $$ A \ cdot B $$ |
RHS $$ \ overline { overline {A} + \ overline {B}} $$ |
|
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Вывод
Вооружившись представленными здесь тождествами, вы можете манипулировать логическими логическими выражениями и логическими диаграммами. Тем не менее, эти идентификаторы являются всего лишь самым фундаментальным из инструментов, доступных вам в качестве логического дизайнера. Чтобы стать действительно опытным в искусстве, вы также должны изучить некоторые из многих мощных методов анализа и дизайна, основанных на этих фундаментальных принципах.