Законы алгебры логики

Законы алгебры логики базируются на аксиомах и позволяют преобразовывать логические функции. Логические функции преобразуются с целью их упрощения, а это ведет к упрощению цифровой схемы. Отмечу особо, что полностью законы алгебры логики сейчас рассматриваются в отдельной дисциплине "дискретная математика". Здесь же приведены только основные из них для того, чтобы напомнить суть процесса минимизации логических выражений. При этом, в отличие от математики, в цифровой технике основное внимание уделяется именно упрощению схем или повышению их быстродействия.

АКСИОМЫ алгебры логики описывают действие логических функций "И" и "ИЛИ" и записываются следующими выражениями:

логическая функция "И" логическая функция "ИЛИ"
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1

В данных выражениях знак '*' используется для обозначения операции логического умножения, а знак '+' — для обозначения операции логического суммирования. Эти же функции могут быть описаны при помощи таблиц истинности.

Таблица 1. Таблица истинности схемы, выполняющей логическую функцию "2И"

x1 x2 F
0 0 0
0 1 0
1 0 0
1 1 1

Таблица 2. Таблица истинности схемы, выполняющей логическую функцию "2ИЛИ"

x1 x2 F
0 0 0
0 1 1
1 0 1
1 1 1

Всего при разработке цифровых комбинационных устройств используется пять законов алгебры логики:

1. Закон одинарных элементов

1 * X = X
0 * X = 0
1 + X = 1
0 + X = X

Этот закон непосредственно следует из приведенных выше выражений аксиом алгебры логики (таблицы истинности логических элементов). Верхние два выражения могут быть полезны при построении коммутаторов, ведь подавая на один из входов элемента "2И" логический ноль или единицу можно либо пропускать сигнал на выход, либо формировать на выходе нулевой потенциал.

Второй вариант использования этих выражений заключается в возможности избирательного обнуления определённых разрядов многоразрядного числа. При поразрядном применении операции "И" можно либо оставлять прежнее значение разряда, либо обнулять его, подавая на соответствующие разряды единичный или нулевой потенциал. Например, в восьмиразрядном двоичном числе требуется обнулить 6, 3 и 1 разряды. Тогда, при выполнении операции поразрядного логического умножения получим:

формула поразрядного логического умножения в алгебре логики

В приведенном примере отчетливо видно, что для обнуления необходимых разрядов в маске (нижнее число) на месте соответствующих разрядов записаны нули (не забываем, что счет начинается с нулевого разряда), в остальных разрядах записаны единицы. В исходном числе (верхнее число) на месте 6 и 1 разрядов находятся единицы. После выполнения операции "И" на этих местах появляются нули. На месте третьего разряда в исходном числе находится ноль. В результирующем числе на этом месте тоже присутствует ноль. Остальные разряды исходного числа, как и требовалось по условию задачи, не изменены.

Записывать логические единицы в нужные нам разряды многоразрядного двоичного числа можно точно таким же образом. В этом случае необходимо воспользоваться нижними двумя выражениями закона одинарных элементов. При поразрядном применении операции "ИЛИ" можно либо оставлять прежнее значение разряда, либо заносить в него единичное значение, подавая на соответствующие разряды нулевой или единичный потенциал. Пусть требуется записать единицы в 7 и 6 биты восьмиразрядного числа.

Тогда, при выполнении операции поразрядного логического суммирования исходного числа с маской устанавливаемых бит, получим:

формула поразрядного логического суммирования (алгебра логики)

Здесь в маску (нижнее число) мы записали единицы в седьмой и шестой биты. Остальные биты содержат нули, и, следовательно, не могут изменить первоначальное состояние исходного числа, что мы и видим в соответствующих разрядах результирующего числа под чертой.

Первое и последнее выражения закона одинарных элементов позволяют использовать логические элементы с большим количеством входов в качестве элементов с меньшим количеством входов, если в схеме уже есть такие свободные элементы и не хочется вводить в состав принципиальной схемы дополнительные микросхемы. Для этого неиспользуемые входы логического элемента "И" должны быть подключены к источнику питания, как это показано на рисунке 1:

схема 2И-НЕ, применяющая алгебру логики для сокращения количества корпусов ЦИМС
Рисунок 1. Схема "2И-НЕ", реализованная на логическом элементе "3И-НЕ"

В схеме логического элемента "ИЛИ", согласно закону одинарных элементов алгебры логики, для уменьшения количества входов логического элемента, неиспользуемые входы должны быть подключены к общему проводу схемы, как это показано на рисунке 2.

схема 2ИЛИ-НЕ, применяющая алгебру логики для сокращения количества корпусов ЦИМС
Рисунок 2. Схема "2ИЛИ-НЕ", реализованная на элементе "3ИЛИ-НЕ"

Следующими законами алгебры логики, вытекающими из аксиом алгебры логики являются законы отрицания.

2. Законы отрицания

Существуют следующие законы отрицания:

  • Закон дополнительных элементов
формула первого закона дополнительных элементов в алгебре логики
формула второго закона дополнительных элементов в алгебре логики
  • Двойное отрицание
формула 1 иллюстрирующая закон двойного отрицания в алгебре логики формула 2 иллюстрирующая закон двойного отрицания в алгебре логики формула 3 иллюстрирующая закон двойного отрицания в алгебре логики формула 4 иллюстрирующая закон двойного отрицания в алгебре логики

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

  • Закон отрицательной логики (Де Моргана)
формула иллюстрирующая закон Моргана в алгебре логики
формула иллюстрирующая закон Моргана в алгебре логики

Закон отрицательной логики справедлив для любого числа переменных. Этот закон алгебры логики позволяет реализовывать логическую функцию "И" при помощи логических элементов "ИЛИ" и наоборот: реализовывать логическую функцию "ИЛИ" при помощи логических элементов "И". Это особенно полезно в ТТЛ схемотехнике, так как там легко реализовать логические элементы "И", но при этом достаточно сложно логические элементы "ИЛИ". Благодаря закону отрицательной логики можно реализовывать элементы "ИЛИ" на логических элементах "И". На рисунке 3 показана реализация логического элемента "2ИЛИ" на элементе "2И-НЕ" и двух инверторах.

схема 2ИЛИ, применяющая алгебру логики для ТТЛ микросхем
Рисунок 3. Логический элемент "2ИЛИ", реализованный на элементе "2И-НЕ" и двух инверторах

То же самое можно сказать и о схеме монтажного "ИЛИ". В случае необходимости его можно превратить в монтажное "И", применив инверторы на входе и выходе этой схемы.

3. Комбинационные законы

При применении комбинационных законов можно значительно упростить логическое выражение, описывающее цифровую схему и, тем самым, упростить ее принципиальную схему. Это позволяет сократить занимаемую цифровой схемой площадь на кристалле и потребляемый ею ток. Комбинационные законы алгебры логики во многом соответствуют комбинационным законам обычной алгебры, но есть и отличия.

  • закон тавтологии (многократное повторение)
X + X + X + X = X
X * X * X * X = X

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

Этот же закон позволяет использовать логические элементы с бОльшим количеством входов в качестве элементов с меньшим количеством входов. Например, можно реализовать двухвходовую схему "2И" на элементе "3И", как это показано на рисунке 4:

Логический элемент 2И-НЕ, применяющая алгебру логики для сокращения количества корпусов ЦИМС
Рисунок 4. Схема "2И-НЕ", реализованная на логическом элементе "3И-НЕ"

или использовать схему "2И-НЕ" в качестве обычного инвертора, как это показано на рисунке 5:

Логический элемент НЕ, применяющая алгебру логики для сокращения количества корпусов ЦИМС
Рисунок 5. Схема "НЕ", реализованная на логическом элементе "2И-НЕ"

Однако следует предупредить, что объединение нескольких входов увеличивает входные токи логического элемента и его входную емкость, что увеличивает ток потребления предыдущих элементов и отрицательно сказывается на быстродействии цифровой схемы в целом. Для уменьшения числа входов в логическом элементе лучше воспользоваться законом одинарных элементов, как это было показано выше.

  • закон переместительности
A + B + C + D = A + C + B + D

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

  • закон сочетательности
A + B + C + D = A + (B + C) + D = A + B + (C + D)

Этот закон позволяет составлять многовходовые логические элементы из логических элементов с меньшим количеством входов. Причем комбинации элементов могут быть самыми разнообразными.

  • закон распределительности
X1(X2 + X3) = X1X2 + X1X3
X1 + X2X3 = (X1 + X2)(X1 + X3)

Докажем это выражение путём раскрытия скобок в правой части равенства:

(X1 + X2)(X1 + X3) = X1X1 + X1X3 + X1X2 + X2X3 = X1(1 + X3 + X2) + X2X3 = X1 + X2X3
  • Правило поглощения (одна переменная поглощает другие)
X1 + X1X2X3 =X1(1 + X2X3) = X1

Одна переменная (в данном случае логическая переменная x1) поглощает другие.

  • Правило склеивания (выполняется только по одной переменной)
формула правила склеивания

Обратите внимание, что это правило выполняется только по одной переменной.

Также как в обычной математике в алгебре логики имеется старшинство операций. При выполнении логических выражений первым выполняется:

  1. Действие в скобках
  2. Операция с одним операндом (одноместная операция) — "НЕ"
  3. Конъюнкция — "И"
  4. Дизъюнкция — "ИЛИ"
  5. Сумма по модулю два.

Операции одного ранга выполняются слева направо в порядке написания логического выражения. Алгебра логики линейна и для неё справедлив принцип суперпозиции.

Дата последнего обновления файла 15.04.2020

Литература:

  1. Микушин А.В., Сажнев А.М., Сединин В.И. Цифровые устройства и микропроцессоры. СПб, БХВ-Петербург, 2010.
  2. Угрюмов Е. П. Цифровая схемотехника. СПб, БХВ-Петербург, 2010.
  3. Шило В. Л. Популярные цифровые микросхемы. М, Радио и связь, 1987.
  4. Дискретная математика

Вместе со статьей "Законы алгебры логики" читают:

Синтез комбинационных цифровых схем по произвольной таблице истинности Любая логическая схема без памяти полностью описывается таблицей истинности... Для реализации таблицы истинности достаточно рассмотреть только те строки...
https://digteh.ru/digital/SintSxem.php

Дешифраторы (декодеры) Декодеры (дешифраторы) позволяют преобразовывать одни виды бинарных кодов в другие. Например...
https://digteh.ru/digital/DC.php

Шифраторы (кодеры) Достаточно часто перед разработчиками цифровой аппаратуры встаёт обратная задача. Требуется преобразовать восьмиричный или десятичный линейный код в...
https://digteh.ru/digital/Coder.php

Мультиплексоры Мультиплексорами называются устройства, которые позволяют подключать несколько входов к одному выходу...
https://digteh.ru/digital/MS.php

Демультиплексоры Демультиплексорами называются устройства... Существенным отличием от мультиплексора является...
https://digteh.ru/digital/DMS.php




Автор Микушин А. В. All rights reserved. 2001 ... 2019

Предыдущие версии сайта:
http://neic.nsk.su/~mavr
http://digital.sibsutis.ru/

Поиск по сайту сервисом Яндекс
Поиск по сайту сервисом ГУГЛ
Об авторе:
к.т.н., доц., Александр Владимирович Микушин

Кандидат технических наук, доцент кафедры САПР СибГУТИ. Выпускник факультета радиосвязи и радиовещания (1982) Новосибирского электротехнического института связи (НЭИС).

А.В.Микушин длительное время проработал ведущим инженером в научно исследовательском секторе НЭИС, конструкторско технологическом центре "Сигнал", Научно производственной фирме "Булат". В процессе этой деятельности он внёс вклад в разработку систем радионавигации, радиосвязи и транкинговой связи.

Научные исследования внедрены в аппаратуре радинавигационной системы Loran-C, комплексов мобильной и транкинговой связи "Сигнал-201", авиационной системы передачи данных "Орлан-СТД", отечественном развитии системы SmarTrunkII и радиостанций специального назначения.

А.В.Микушин является автором более 82 научных и научно-методических работ, в том числе 18 книг.

Top.Mail.Ru


Яндекс.Метрика