Вычислительная техника и информационные технологии |
Глава 2 |
назад | оглавление | вперёд |
2. Основы алгебры логики
Основные понятия:
Логическая переменная – переменная величина Х, которая может принимать одно
из 2х значений – 0 или 1 (ложно или истинно).
Логическая функция – функция логических переменных y=f(x1, ..., xn) =
{0,1} (тоже может принимать 2 значения). Логическая функция может задаваться
таблицей истинности.
Таблица истинности – совокупность всех возможных комбинаций, значений
переменных и функций.
Уровни логического нуля и единицы.
Цифровые
схемы характеризуются тем, что могут находиться только в двух состояниях.
Состояния цифровых микросхем могут быть описаны двумя цифрами: 0 и 1. При этом
можно состояние микросхемы характеризовать различными параметрами. Например,
током или напряжением в цепях микросхемы, открыты или заперты транзисторы на
выходе микросхемы, светится или нет светодиод (если он входит в состав
микросхемы).
В
качестве логических состояний цифровых микросхем условились воспринимать
напряжение на их входе и выходе. При этом высокое напряжение договорились
считать единицей, а низкое напряжение – нулем. В идеальном случае напряжение на
выходе микросхем должно быть равным напряжению питания или общего провода
схемы.
В
реальных схемах так не бывает. Даже на полностью открытом реальном транзисторе
есть падение напряжения. В результате на выходе цифровой микросхемы напряжение
всегда будет меньше напряжения питания или больше потенциала общего провода.
Поэтому договорились напряжение, меньшее заданного уровня (уровень логического
нуля) считать нулём, а напряжение, большее заданного уровня (уровень логической
единицы), считать единицей. Если же напряжение на выходе микросхемы будет
больше уровня логического нуля, но меньше уровня логической единицы, то такое
состояние микросхемы будем называть неопределённым.
На
рисунке 2.1 приведены уровни выходных логических сигналов, допустимые для
цифровых ТТЛ микросхем.
Рисунок 2.1 -
Уровни логических сигналов на выходе цифровых ТТЛ микросхем
2.1 Основные элементарные
логические функции и элементы
Простейшим
логическим элементом является инвертор, который просто изменяет значение
входного сигнала на прямо противоположное значение. Его функция записывается в
следующем виде:
,
где
черта над входным значением обозначает изменение его значения на
противоположное. То же самое действие можно записать при помощи таблицы
истинности, приведённой в таблице 2.1. Так как вход у этого логического
элемента только один, то его таблица истинности состоит только из двух строк.
Х |
Y |
0 |
1 |
1 |
0 |
Таблица 2.1 -
Таблица истинности логического инвертора
Рисунок 2.2 -
Условное графическое изображение инвертора
Эквивалентная
схема простейшего инвертора приведена на рисунке 2.3.
Рисунок 2.3 -
Эквивалентная схема простейшего инвертора
При
подаче на вход уровня логического «0» ключ разомкнут и напряжение на выходе
Uвых =5В (Y=1). При подаче на вход уровня логической «1» ключ замкнут,
напряжение на выходе равно потенциалу общего провода, т.е. Uвых = 0 (Y=0). В
качестве ключа можно использовать биполярный транзистор. Схема инвертора на
биполярном транзисторе приведена на рисунке 2.4.
Рисунок 2.4 -
Схема инвертора на биполярном транзисторе
В
этой схеме если Uвх =0, то транзистор заперт (режим отсечки), ток коллектора Iк » 0, Uвых » 5В. При подаче на вход уровня логической «1» (Uвх=5В), транзистор
отпирается (переходит в режим насыщения), напряжение на его коллекторе
уменьшается практически до нуля (Uвых » 0), что соответствует уровню логического «0» (Y=0).
Недостатком такой схемы является большой ток потребления от источника питания
при нулевом состоянии на выходе Iпотр » Eпит/Rк.
Для
уменьшения потребляемого тока, инвертор выполняется на двух ключах К1 и К2
(рис.2.5), причем когда К1 замкнут – К2 разомкнут и наоборот. В этом случае ток
потребления практически равен 0 независимо от состояния инвертора.
Рисунок 2.5 -
Эквивалентная схема инвертора на двух ключах
Реализовать
такое устройство (два МДП транзистора с разным типом каналов) можно на КМДП
структуре (рис.2.6) При подаче на вход схемы Uвх=0, нижний n-канальный
транзистор заперт, а верхний p-канальный открыт, при этом Uвых=E пит. При
подаче на вход Uвх = 5В (X=1), наоборот нижний транзистор отпирается, а верхний
закрыт, Uвых = 0 (Y=1). Следует обратить внимание на то, что исток верхнего
транзистора подключен к плюсу источника питания, а исток нижнего транзистора –
к общему проводу.
Рисунок 2.6 -
КМДП инвертор
2.1.2 Функция «И» (логическое умножение,
конъюнкция)
Y=X1 × X2
Рисунок 2.7 -
Условное графическое изображение элемента «И»
То
же самое действие можно записать при помощи таблицы истинности, приведённой в
таблице 2.2. В формуле, приведенной выше, использовано два аргумента. Поэтому
элемент, выполняющий эту функцию, имеет два входа. Такой элемент обозначается
"2И". Для элемента "2И" таблица истинности будет состоять
из четырех строк (22=4).
Х1 |
X2 |
Y |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Таблица 2.2 -
Таблица истинности схемы, выполняющей логическую функцию "2И"
Как
видно из приведённой таблицы истинности активный сигнал на выходе этого
логического элемента появляется только тогда, когда и на входе X и на входе Y
будут присутствовать логические единицы. То есть этот логический элемент
действительно реализует операцию "И".
Проще
всего понять, как работает такой элемент при помощи схемы, построенной на
идеализированных ключах с электронным управлением, как это показано на рисунке
2.8. В приведённой схеме ток будет протекать только тогда, когда оба ключа
будут замкнуты, а значит, единичный уровень на выходе схемы появится только при
двух логических единицах на входе.
Рисунок 2.8 -
Эквивалентная схема, реализующая логическую функцию "2И"
2.1.3
Функция “ИЛИ”, логическое сложение (дизъюнкция)
Следующим
простейшим элементом является схема, реализующая операцию логического умножения
"ИЛИ":
Y=X1+X2
То
же самое действие можно записать при помощи таблицы истинности, приведённой в
таблице 2.3. В формуле, приведенной выше, использовано два аргумента. Поэтому
элемент, выполняющий эту функцию, имеет два входа. Такой элемент обозначается
"2ИЛИ". Для элемента "2ИЛИ" таблица истинности будет
состоять из четырех строк (22 = 4).
Х1 |
X2 |
Y |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Таблица 2.3 -
Таблица истинности схемы, выполняющей логическую функцию "2ИЛИ"
Как
и в случае, рассмотренном для схемы логического умножения, воспользуемся для
реализации схемы логического элемента "2ИЛИ" идеализированными
ключами с электронным управлением. На этот раз соединим ключи параллельно.
Эквивалентная схема, реализующая таблицу истинности 2.3, приведена на рисунке
2.9. Как видно из приведённой схемы, уровень логической единицы появится на её
выходе, как только будет замкнут любой из ключей, то есть схема реализует
таблицу истинности, приведённую в таблице 2.3.
Рисунок 2.9 -
Эквивалентная схема, реализующая логическую функцию "2ИЛИ"
Так
как функция логического суммирования может быть реализована различными
принципиальными схемами, то для условно-графического обозначения этой функции используется
специальный символ "1", как это приведено на рисунке 2.10.
Рисунок 2.10
- Условно-графическое изображение схемы, выполняющей логическую функцию
"2ИЛИ"
2.1.4 Функция «И-НЕ», умножение с
инверсией
Х1 |
X2 |
Y |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Таблица 2.4 -
Таблица истинности схемы, выполняющей логическую функцию "2И-НЕ"
Как
видно из таблицы, ноль на выходе этого элемента появляется только в том случае,
когда X1=X2=1.
Условное
графическое обозначение элемента И-НЕ приведено на рисунке 2.11.
Рисунок 2.11
- Условное графическое обозначение элемента И-НЕ
Рассмотрим
схему, реализующую этот элемент (рисунок 2.12). Так как в этой схеме
используются диоды и транзисторы, она получила название диодно-транзисторная
логика (ДТЛ).
Рисунок 2.12
- Диодно-транзисторная логика (ДТЛ)
Если
Uвх1 = Uвх2 = +5В (на обоих входах
уровень логической «1»), диоды VD1 и VD2 заперты. Ток от плюса источника
питания через резистор Rб и диод VD3 протекает по базе транзистора, открывая
его. Напряжение между коллектором и эмиттером открытого и насыщенного
транзистора составляет порядка 0.1 В. Таким образом напряжения на выходе схемы
соответствует уровню логического «0». При подаче на один из входов (или на оба
входа) уровня логического «0», что примерно соответствует потенциалу общего
провода, диоды VD1 или VD2 открываются. При условии, что диоды кремниевые,
падение прямого напряжения на них составляет около 0.7В. Таким образом
напряжение в точке «а» будет Uа = 0.7В относительно общего провода. Этого
напряжения не достаточно для отпирания транзистора. Напряжение на коллекторе
запертого транзистора будет равно Еп = 5В (что соответствует уровню логической
«1»). В современных схемах диоды VD1, VD2, VD3 заменяют многоэмиттерным
транзистором. Говорят, что эти схемы представляют транзисторно-транзисторную
логику (ТТЛ).
Более
экономичной с точки зрения потребляемого тока является схема КМДП логики,
эквивалентная схема которой представлена на рисунке 2.13.
Рисунок 2.13
- Эквивалентная схема элемента КМДП «И-НЕ»
Уровень
логического «0» на выходе возможен только, когда нижние ключи замкнуты, а
верхние разомкнуты. Электрическая схема КМДП логики изображена на рисунке 2.14.
Рисунок 2.14
- Электрическая схема КМДП логики «И-НЕ»
При
подаче на оба входа уровней логической «1» два нижних n – канальных транзистора открыты, а
верхние р - канальные транзисторы
заперты. В этом случае на выходе устанавливается уровень логического «0», при
этом потребляемый ток почти отсутствует. Ток, потребляемый от источника питания
возможен только в короткий переходный промежуток времени, когда нижние ключи
еще не успели закрыться, а верхние уже открылись.
2.1.5 Функция «ИЛИ-НЕ», сложение с
инверсией
Х1 |
X2 |
Y |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
Таблица 2.5 - Таблица истинности схемы,
выполняющей логическую функцию "2И-НЕ"
Условное
графическое обозначение элемента ИЛИ-НЕ приведено на рисунке 2.15.
Рисунок 2.15
- Условное графическое обозначение элемента ИЛИ-НЕ
Эквивалентная
схема с идеализированными электронными ключами изображена на рисунке 2.16.
Рисунок 2.16
- Эквивалентная схема ИЛИ-НЕ
По
сравнению со схемой И-НЕ здесь все наоборот. «1» на выходе появляется только в
одном случае, когда нижние два ключа разомкнуты, а верхние замкнуты. Электрическая
схема КМДП логики, соответствующая этой идеализированной схеме, изображена на
рисунке 2.17.
Рисунок 2.17
- Электрическая схема КМДП логики ИЛИ-НЕ
2.1.6 Функция исключающее «ИЛИ»
Х1 |
X2 |
Y |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Таблица 2.6 -
Таблица истинности схемы, выполняющей логическую функцию исключающее
"ИЛИ"
Условное
графическое обозначение элемента исключающее «ИЛИ» приведено на рисунке 2.18.
Рисунок 2.18
Условное графическое обозначение элемента исключающее «ИЛИ»
Схема
исключающее «ИЛИ» отличается от схемы «ИЛИ» тем, что когда на обоих входах
установлены «1», то на выходе получается «0».
Законы
алгебры логики базируются на аксиомах и позволяют преобразовывать логические
функции. Логические функции преобразуются с целью их упрощения, а это ведет к
упрощению цифровой схемы.
АКСИОМЫ алгебры логики описывают действие логических функций
“И” и ”ИЛИ” и записываются следующими выражениями:
0
* 0 = 0 0 + 0 = 0
0
* 1 = 0 0 + 1 = 1
1
* 0 = 0 1 + 0 = 1
1
* 1 = 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 биты числа.
Тогда:
Здесь
в маску (нижнее число) мы записали единицы в седьмой и шестой биты. Остальные
биты содержат нули, и, следовательно, не могут изменить первоначальное
состояние исходного числа, что мы и видим в
результирующем числе под чертой.
Первое
и последнее выражения позволяют использовать логические элементы с большим
количеством входов в качестве элементов с меньшим количеством входов. Для этого
неиспользуемые входы в схеме “И” должны быть подключены к источнику питания,
как это показано на рисунке 2.19,
Рисунок 2.19
- Схема “2И-НЕ”, реализованная на элементе “3И-НЕ”
а
неиспользуемые входы в схеме “ИЛИ” должны быть подключены к общему проводу
схемы, как это показано на рисунке 2.20.
Рисунок 2.20
- Схема “НЕ”, реализованная на элементе “2И-НЕ”
2. Законы отрицания
a. Закон
дополнительных элементов
,
Выражения
этого закона широко используется для минимизации логических схем. Если удаётся
выделить из общего выражения логической функции такие подвыражения, то можно
сократить необходимое количество входов элементов цифровой схемы, а иногда и
вообще свести всё выражение к логической константе.
b. Двойное
отрицание
,
,
,
c.
Закон отрицательной логики
Закон
отрицательной логики справедлив для любого числа переменных. Этот закон
позволяет реализовывать логическую функцию “И” при помощи логических элементов
“ИЛИ” и наоборот: реализовывать логическую функцию “ИЛИ” при помощи логических
элементов “И”. Это особенно полезно в ТТЛ схемотехнике, так как там легко
реализовать логические элементы “И”, но при этом достаточно сложно логические
элементы “ИЛИ”. Благодаря закону отрицательной логики можно реализовывать
элементы “ИЛИ” на логических элементах “И”. На рисунке 2.21 показана реализация
логического элемента “2ИЛИ” на элементе “2И-НЕ” и двух инверторах.
Рисунок 2.21
- Логический элемент “2ИЛИ”, реализованный на элементе “2И-НЕ” и двух
инверторах
То
же самое можно сказать и о схеме монтажного “ИЛИ”. В случае необходимости его
можно превратить в монтажное “И”, применив инверторы на входе и выходе этой
схемы.
3. Комбинационные законы
Комбинационные
законы алгебры логики во многом соответствуют комбинационным законам обычной
алгебры, но есть и отличия.
a. Закон
тавтологии (многократное повторение)
Этот
закон позволяет использовать логические элементы с большим количеством входов в
качестве элементов с меньшим количеством входов. Например, можно реализовать
двухвходовую схему 2И на элементе 3И, как это показано на рисунке 2.22,
Рисунок 2.22
- Схема “2И-НЕ”, реализованная на элементе “3И-НЕ”
или
использовать схему 2И‑НЕ в качестве обычного инвертора, как это показано
на рисунке 2.23.
Рисунок 2.23
- Схема “НЕ”, реализованная на элементе “2И-НЕ”
Однако
следует предупредить, что объединение нескольких входов увеличивает входные
токи логического элемента и его ёмкость, что увеличивает ток потребления
предыдущих элементов и отрицательно сказывается на быстродействии цифровой
схемы в целом.
Для
уменьшения числа входов в логическом элементе лучше воспользоваться законом
одинарных элементов, как это было показано выше.
b.
Закон переместительности
A+B+C+D=A+C+B+D
c.
Закон сочетательности
A+B+C+D=A+(B+C)+D=A+B+(C+D)
d. Закон
распределительности
X1(X2+X3)=
X1X2 + X1X3
X1+X2X3=(X1+X2)(X1+X3)=/
докажем это путём раскрытия скобок/=
=
X1X1+ X1X3+ X1X2+ X2X3= X1(1+X3+X2)+ X2X3= X1+X2X3
5. Правило поглощения (одна
переменная поглощает другие)
X1+X1X2
X3 =X1(1+X2 X3 )=X1
6. Правило склеивания (выполняется
только по одной переменной)
Также
как в обычной математике в алгебре логики имеется старшинство операций. При
этом первым выполняется:
-
действие в скобках
-
операция с одним операндом (одноместная операция) – НЕ
-
конъюнкция - И
-
дизъюнкция - ИЛИ
-
сумма по модулю два
Операции
одного ранга выполняются слева направо в порядке написания логического выражения.
Алгебра
логики линейна и для неё справедлив принцип суперпозиции.
2.3 Аналитическая форма
представления функции алгебры логики
Знание
аналитического уравнения необходимо для синтеза схемы цифрового устройства.
Исходной информацией для синтеза схемы обычно является таблица истинности. По
таблице составляют аналитическое уравнения, затем с целью упрощения устройства
его минимизируют и далее разрабатывают схему, реализующую полученное логическое
выражение.
Совершенная дизъюнктивная нормальная
форма (СДНФ).
Функция
представляется суммой групп; каждая группа состоит из произведения, в которую
входят все переменные.
Например:
Совершенная конъюнктивная нормальная
форма (СКНФ).
Функция
представляется произведением групп; каждая группа состоит из суммы, в которую
входят все переменные.
Например:
СДНФ
составляется на основе таблицы истинности по следующему правилу: для каждого
набора переменных, при котором функция равна 1, записывается произведение, в котором
с отрицанием берутся переменные, имеющие
значение «0».
Пример:
Х1 |
Х2 |
Х3 |
У |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
СКНФ
составляется на основе таблицы истинности по правилу: для каждого набора
переменных, при котором функция равна 0, записывается сумма, в которой с отрицанием берутся
переменные, имеющие значение 1.
Х1 |
Х2 |
Х3 |
У |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
На
основе полученных выражений можно составить схему устройства, реализующего
заданную функцию. Схема устройства, полученная на основе СДНФ, изображена на
рисунке 2.24.
Рисунок 2.24
- Схема устройства, полученная на основе СДНФ
Сложность
логической схемы оценивается числом входов всех её элементов, которое условно
называются ценой схемы. При этом инверторы не учитываются. Цена схемы на
рисунке 2.24 составляет 12.
Используя
законы алгебры логики можно упростить исходную функцию.
На
основе полученного выражения составим новую схему устройства (рис. 2.25).
Рисунок 2.25
- Минимизированная схема
Очевидно,
что эта схема намного проще предыдущей.