ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6717
Скачиваний: 8
Вентили и булева алгебра
143
договоримся всегда располагать строки таблицы истинности по порядку номеров,
то есть для двух переменных в порядке 00, 01, 10, 11, то функцию можно полнос-
тью описать 2"-битным двоичным числом, которое получается, если считывать по
вертикали колонку результатов в таблице истинности Таким образом, НЕ-И —
это 1110, НЕ-ИЛИ - 1000, И - 0001 и ИЛИ - 0111. Очевидно, что существует
только 16 булевых функций от двух переменных, которым соответствуют 16 воз-
можных 4-битных цепочек. В обычной алгебре, напротив, есть бесконечное число
функций от двух переменных, и ни одну из них нельзя описать, дав таблицу значе-
ний этой функции для всех возможных значений переменных, поскольку каждая
переменная может принимать бесконечное число значений.
На рис. 3.3,
а
показана таблица истинности для булевой функции от трех пе-
ременных: M-f(A, В, С) Это функция большинства, которая принимает значе-
ние 0, если большинство переменных равно 0, и 1, если большинство переменных
равно 1. Хотя любая булева функция может быть определена с помощью таблицы
истинности, с возрастанием количества переменных такой тип записи становится
громоздким. Поэтому вместо таблиц истинности часто используется другой тип
записи.
A B C A B C
В—1
А
0
0
0
0
1
1
1
1
в
0
0
1
1
0
0
1
1
с
0
1
0
1
0
1
0
1
м
0
0
0
1
0
1
1
1
ABC
Рис. 3.3. Таблица истинности для функции большинства от трех
переменных (а), схема для этой функции (б)
1 4 4 Глава 3. Цифровой логический уровень
Чтобы увидеть, каким образом осуществляется этот другой тип записи, отме-
тим, что любую булеву функцию можно определить, указав, какие комбинации
значений переменных дают значение функции 1. Для функции, приведенной на
рис. 3.3, а, существует 4 комбинации переменных, которые дают значение функ-
ции 1. Мы будем рисовать черту над переменной, чтобы показать, что ее значение
инвертируется. Отсутствие черты означает, что значение переменной не инверти-
руется. Кроме того, мы будем использовать знак умножения (точку) для обозначе-
ния булевой функции И (знак умножения может опускаться) и + для обозначения
булевой функции ИЛИ. Например, ABC принимает значение 1, только если А=1,
В=0 и С=1.
А Н + В С
принимает значение 1, только если (А=1 и В=0) или (В=1 и
С=0). В таблице на рис. 3.3,
а
функция принимает значение 1 в четырех строках:
ABC, ABC, ABC И ABC. Функция М принимает значение истины (то есть 1), если
одно из этих четырех условий истинно. Следовательно, мы можем написать
М=АВС+АБС+АВС+АВС.
Это компактная запись таблицы истинности. Таким образом, функцию от п
переменных можно описать суммой максимум 2" произведений, при этом в каж-
дом произведении будет по п множителей. Как мы скоро увидим, такая формули-
ровка особенно важна, поскольку она ведет прямо к реализации данной функции с
использованием стандартных вентилей.
Важно понимать различие между абстрактной булевой функцией и ее реализа-
цией с помощью электронной схемы. Булева функция состоит из переменных, на-
пример А, В и С, и операторов И, ИЛИ и НЕ. Булева функция описывается с по-
мощью таблицы истинности или специальной записи, например:
F=ABC+ABC.
Булева функция может реализовываться с помощью электронной схемы (час-
то различными способами) с использованием сигналов, которые представляют
входные и выходные переменные, и вентилей, например, И, ИЛИ и НЕ.
Реализация булевых функций
Как было сказано выше, представление булевой функции в виде суммы максимум
2" произведений делает возможной реализацию этой функции. На рисунке 3.3 мож-
но увидеть, как это осуществляется. На рисунке 3.3,
б
входные сигналы А, В и С
показаны с левой стороны, а функция М, полученная на выходе, показана с правой
стороны. Поскольку необходимы дополнительные величины (инверсии) входных
переменных, они образуются путем провода сигнала через инверторы 1,2 и 3. Что-
бы сделать рисунок понятней, мы нарисовали 6 вертикальных линий, 3 из которых
связаны с входными переменными, а 3 другие — с их инверсиями. Эти линии обес-
печивают передачу входного сигнала к вентилям. Например, вентили 5, 6 и 7 в
качестве входа используют А. В реальной схеме эти вентили, вероятно, будут не-
посредственно соединены проводом с А без каких-либо промежуточных вертикаль-
ных проводов.
Схема содержит четыре вентиля И, по одному для каждого члена в уравнении
для М (то есть по одному для каждой строки в таблице истинности с результа-
том 1). Каждый вентиль И вычисляет одну из указанных строк таблицы истинное-
Вентили и булева алгебра 145
ти. В конце концов все данные произведения суммируются (имеется в виду опе-
рация ИЛИ) для получения конечного результата.
Посмотрите на рис. 3.3,
б,
В этой книге мы будем использовать следующее со-
глашение: если две линии на рисунке пересекаются, связь подразумевается только
в том случае, если на пересечении указана жирная точка. Например, выход венти-
ля 3 пересекает все 6 вертикальных линий, но связан он только с С. Отметим, что
другие авторы могут использовать другие соглашения.
Из рисунка 3.3 должно быть ясно, как реализовать схему для любой булевой
функции:
1. Составить таблицу истинности для данной функции.
2. Обеспечить инверторы, чтобы порождать инверсии для каждого входного
сигнала.
3. Нарисовать вентиль И для каждой строки таблицы истинности с результатом 1.
4. Соединить вентили И с соответствующими входными сигналами.
5. Вывести выходы всех вентилей И в вентиль ИЛИ.
Мы показали, как реализовать любую булеву функцию с использованием вен-
тилей НЕ, И и ИЛИ. Однако гораздо удобнее строить схемы с использованием
одного типа вентилей. К счастью, можно легко преобразовать схемы, построенные
по предыдущему алгоритму, в форму НЕ-И или НЕ-ИЛИ. Чтобы осуществить такое
преобразование, все, что нам нужно, — это способ воплощения НЕ, И и ИЛИ с по-
мощью одного типа вентилей. На рисунке 3.4 показано, как это можно сделать,
используя только вентили НЕ-И или только вентили НЕ-ИЛИ. Отметим, что суще-
ствуют также другие способы подобного преобразования.
Для того чтобы реализовать булеву функцию с использованием только вен-
тилей НЕ-И или только вентилей НЕ-ИЛИ, можно сначала следовать алгорит-
му, описанному выше, и сконструировать схему с вентилями НЕ и И и ИЛИ.
Затем нужно заменить многовходовые вентили эквивалентными схемами с ис-
пользованием двухвходовых вентилей. Например, A+B+C+D можно поменять
на (A+B)+(C+D), используя три двухвходовых вентиля. Затем вентили НЕ и И
и ИЛИ заменяются схемами, изображенными на рис. 3.4.
Хотя такая процедура и не приводит к оптимальным схемам с точки зрения
минимального числа вентилей, она демонстрирует, что подобное преобразование
осуществимо. Вентили НЕ-И и НЕ-ИЛИ считаются полными, потому что можно
вычислить любую булеву функцию, используя только вентили НЕ-И или только
вентили НЕ-ИЛИ. Ни один другой вентиль не обладает таким свойством, вот по-
чему именно эти два типа вентилей предпочтительны при построении схем.
Эквивалентность схем
Разработчики схем часто стараются сократить число вентилей, чтобы снизить цену,
уменьшить занимаемое схемой место, сократить потребление энергии и т. д. Что-
бы упростить схему, разработчик должен найти другую схему, которая может вы-
числять ту же функцию, но при этом требует меньшего количества вентилей (или
может работать с более простыми вентилями, например двухвходовыми вместо
четырехвходовых). Булева алгебра является ценным инструментом в поиске эк-
вивалентных схем.
1 4 6 Глава 3. Цифровой логический уровень
АВ
А+В
Рис. 3.4. Конструирование вентилей НЕ (а), И (б) и ИЛИ
(в)
с использованием
только вентилей НЕ-И или только вентилей НЕ-ИЛИ
В качестве примера использования булевой алгебры рассмотрим схему и таб-
лицу истинности для АВ+АС (рис. 3.5,
а).
Хотя мы это еще не обсуждали, многие
правила обычной алгебры имеют силу для булевой алгебры. Например, выраже-
ние АВ+АС может быть преобразовано в А(В+С) с помощью дистрибутивного за-
кона. На рис. 3.5,
б
показана схема и таблица истинности для А(В+С). Две функ-
ции являются эквивалентными тогда и только тогда, когда обе функции принимают
одно и то же значение для всех возможных переменных. Из таблиц истинности на
рис. 3.5 ясно видно, что А(В+С) эквивалентно АВ+АС. Несмотря на эту эквива-
лентность, схема на рис. 3.5,
б
лучше, чем схема на рис. 3.5, а, поскольку она содер-
жит меньше вентилей.
Обычно разработчик исходит из определенной булевой функции, а затем приме-
няет к ней законы булевой алгебры, чтобы найти более простую функцию, эквива-
лентную исходной. На основе полученной функции можно конструировать схему.
Чтобы использовать данный подход, нам нужны некоторые равенства из буле-
вой алгебры. В табл. 3.1 показаны некоторые основные законы. Интересно отме-
тить, что каждый закон имеет две формы. Одну форму из другой можно получить,
меняя И на ИЛИ и 0 на 1. Все законы можно легко доказать, составив их таблицы
истинности. Почти во всех случаях результаты очевидны, за исключением законов
Де Моргана, законов поглощения и дистрибутивного закона А+ВС=(А+В)(А+С).
Законы Де Моргана распространяются на выражения с более чем двумя перемен-
ными, например АВС=А+В+С.
Вентили и булева алгебра
147
в + с
А
0
0
0
0
1
1
1
1
в
0
0
1
1
0
0
1
1
с
0
1
0
1
0
1
0
1
АВ
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
1
1
I 1
в
0
0
1
1
0
0
1
1
с
0
1
0
1
0
1
0
1
А
0
0
0
0
1
1
1
1
в + с
0
1
1
1
0
1
1
1
А(В + С)
0
0
0
0
0
1
1
1
Рис.
3.5. Две эквивалентные функции: АВ+АС (а); А(В+С)
(б).
Таблица 3 . 1
. Некоторые законы булевой алгебры
Названия законов И ИЛИ
Законы тождества
Законы нуля
Законы идемпотентности
Законы инверсии
Коммуникативные законы
Ассоциативные законы
Дистрибутивные законы
Законы поглощения
Законы Де Моргана
1А=А
ОА=0
АА=А
АА"=0
АВ=ВА
(АВ)С=А(ВС)
А+ВС=(А+В)(А+С)
А(А+В)=А
АВ=Д+В
0+А=А
1+А=1
А+А=А
А+А=1
А+В=В+А
(А+В)+С=А+
£
В+С)
А(В+С)=АВ+АС
А+АВ=А
А+В=ДВ
Законы Де Моргана предполагают альтернативную запись. На рис. 3.6,
а
форма
И дается с отрицанием, которое показывается с помощью инвертирующих входов
и выходов. Таким образом, вентиль ИЛИ с инвертированными входными сигна-
лами эквивалентен вентилю НЕ-И. Из рис. 3.6,
б,
на котором изображена вторая
форма закона Де Моргана, ясно, что вместо вентиля НЕ-ИЛИ можно нарисовать
вентиль И с инвертированными входами. С помощью отрицания обеих форм зако-
на Де Моргана мы приходим к эквивалентным репрезентациям вентилей И и ИЛИ
(см. рис. 3.6,
в
и 3.6,
г).
Аналогичные символические изображения существуют для
различных форм закона Де Моргана (например, n-входовый вентиль НЕ-И стано-
вится вентилем ИЛИ с инвертированными входами).