При проектировании узлов и устройств ЦВМ широко используются методы анализа и синтеза логических схем, которые получили название методов логического проектирования. Они основаны на использовании алгебры логики или булевой алгебры. Основным понятием алгебры логики является высказывание – любое утверждение, в отношении которого имеет смысл говорить, что оно истинно или ложно. При этом считается, что каждое высказывание не может быть одновременно и истинно и ложно. Каждое высказывание можно обозначить определенным символом. Запись Xj = 1 означает, что высказанное истинно, а Xj = 0 – что высказывание ложно.
В алгебре логики высказывания могут быть простыми и сложными. Высказывание, значение истинности которого не зависит от значений истинности других высказываний, называется простым. При анализе и синтезе логических схем простое высказывание рассматривается как независимая переменная, принимающая два значения: 0 и 1. Высказывание Y(X1, X2, …, Xn), значение истинности которого зависит от значения истинности других высказываний, составляющих его, называется сложным и также может принимать два значения: 0 и 1.
При технической реализации переключательных функций переменные X1, X2, …, Xnотождествляются с входящими сигналами, поступающими на физическую схему, реализующую переключательную функцию, а значение Y(X1, X2, …, Xn) представляет собой выходной сигнал схемы. Совокупность значений n переменных называется набором.
Одной из распространенных форм задания переключательных функций является таблица истинности, где переменные X1, X2, …, Xn обычно располагаются в порядке возрастания двоичных чисел, образованных набором. Для переключательной функции n переменных существует различных наборов, на которые она может принимать значение 0 или 1.
В таблице 2 приведен полный перечень функций двух аргументов. Функции, образованные логическими переменными, можно преобразовывать в соответствии с правилами или законами алгебры логики. При этом стремятся минимизировать логическое выражение, т.е. привести его к виду, удобному для практической реализации на логических элементах.
В электронных цифровых устройствах элементарные логические операции над двоичными переменными реализуются простыми логическими схемами, которые называются логическими элементами или вентилями. Число входов логического элемента соответствует числу переменных реализуемой им переключательной функции. В таблице 3 приведены названия переключательной функции двух переменных и логического элемента, реализующего эту функцию, а также условное обозначение элемента (УГО) структурных и функциональных схем цифровых устройств. В последней графе этой таблицы даются некоторые названия логических элементов, которые встречаются в отечественной и зарубежной литературе.
Основное требование, предъявляемое к функционально полному набору логических элементов, состоит в том, чтобы с помощью этого набора можно было построить любую сложную логическую схему. Ввиду того, что законы функционирования элементов однозначно описываются переключательными функциями, применяя операцию суперпозиции, можно получить любую, сколь угодно сложную переключательную функцию.
Таблица 2
X1
Название переключательной
функции
Основное обозначение
Сложное
высказывание
Выражение через конъюнкцию, дизъюнкцию инверсию
X2
Y0
Константа нуль
Всегда ложно
Y0 = 0
Y1
Конъюнкция
(логическое
произведение)
X1·X2
X1и X2
Y1 = X1 ∙ X2
Y2
Операция запрета по X2
X1∆X2
Неверно, что если X1, тоX2
Y3
Переменная X1
X1
Высказывание не зависит от X2
Y3 = X1
Y4
Операция запрета по X1
X2∆X1
Неверно, что
если X2, то X1
Y5
Переменная X2
X2
Высказывание
не зависит от X1
"Y5 = X2
Y6
Сумма по mod 2 (неравнозначность)
X1неравнозначно X2
Y7
Дизъюнкция (логическое сложение)
X1 илиX2
Y8
Операция Пирса
Ни X1, ниX2
Y9
Логическая равнозначность
X1~X2
X1равнозначно X2
Y10
Инверсия X2(отрицание)
2
Не X2
Y11
Импликация от X2к X1
Если X2, то X1
Y12
Инверсия
X1(отрицание)
1
Не X1
Y13
Импликация от X1к X2
Если X1, тоX2
Y14
Операция Шеффера
X1ïX2
Неверно, что
X1 и X2
Y15
Константа единица
Всегда истинно
Y15=1
Таблица 3
Название переключательных функций
Название логического элемента
Другие
названия логического элемента
УГО логического элемента
УГО в среде Electronics Workbench
Конъюнкция
Элемент И, схема совпадения
Конъюнктор,
клапан И, вентиль И
Дизъюнкция
Элемент ИЛИ, схема разделения
Дизъюнктор, клапан ИЛИ, вентиль ИЛИ
Инверсия
(отрицание)
Элемент НЕ, схема отрицания
Инвертор
Операция
Пирса
Элемент ИЛИ–НЕ
Схема НЕ–ИЛИ, клапан НЕ–ИЛИ, вентиль НЕ–ИЛИ, схема НИ
Операция
Шеффера
Элемент И–НЕ
Схема НЕ–И, клапан НЕ–И, вентиль НЕ–И
Сумма по mod 2
ИЛИ–ИЛИ, схема сложения по mod 2
Исключающая ИЛИ
Сумма по mod 2
и инверсия
ИЛИ–ИЛИ-НЕ,
схема сложения
по mod 2
Исключающая
ИЛИ-НЕ
Операция
запрета
Элемент НЕТ, схема запрета
«Запрет»
–
Логическая равнозначность (эквивалентность)
Схема логической равнозначности
Эквивалентность
–
Импликация
Схема импликации
Импликатор
–
Функционально полный набор переключательных функций является несократимым, если исключение любой функции набора нарушает его полноту. Такой набор можно состроить с помощью одной, двух, трех и четырех функции.
Примером полных несократимых наборов переключательных функций трех, двух и одной переменной могут служить:
Однако наборы логических элементов и соответствующие им наборы переключательных функций, как правило, обладают функциональной избыточностью, например, широко используемый для построения логических схем цифровых устройств набор, состоящий из переключательных функций конъюнкции; дизъюнкции и отрицания, который реализуется логическими элементами И, ИЛИ, НЕ соответственно. Этот набор элементов дает возможность достаточно гибко и экономично строить схемы, например, на полупроводниковых приборах. Кроме того, с помощью этого набора функций наиболее просто перейти от широко распространенной записи переключательной функции в канонической форме к структурной схеме на логических элементах И, ИЛИ, НЕ, и др.
Задача логического проектирования на первом этапе полностью эквивалентна математической задаче представления заданной переключательной функции переключательными функциями выбранной функционально полной системы. При проектировании логических схем сначала необходимо записать переключательную функцию в определенной исходной форме: совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ). Однако эти формы, как правило, достаточно сложные. Поэтому их минимизируют или с помощью диаграмм Вейча, или путем преобразования выражений для переключательных функций с помощью формул и тождеств, приведенных в таблице 4.
Например, для функции дизъюнкции логическое выражение на основании таблицы истинности (табл. 2) будет иметь вид:
.
Таблица 4
Название
тождества
Тождество
для дизъюнкции
для конъюнкции
Элементарное высказывание
-“-
-“-
-“-
-“-
Сочетательные (ассоциативные)
Переместительные (коммуникативные)
Распределительные (дистрибутивные)
Поглощения
Склеивания
Соотношение двойственности (формула де Моргана)
При минимизации на основании тождеств (табл. 4) получим следующее выражение:
.
Если число логических переменных не превышает 5-6, минимизацию логических уравнений удобно производить с помощью карт Карно или диаграмм Вейча. Минимизацию проводят путем объединения наборов (термов) на карте Карно. Причем объединяемые наборы должны иметь одинаковые значения функции (все 0 или все 1).
Рассмотрим пример: требуется минимизировать логическую функцию двух переменных дизъюнкцию. На основании таблицы истинности (таблица 2) составим карту Карно (рисунок 4), в которой наименования столбцов и строк представляют собой значения переменных, причем переменные располагаются в таком порядке, чтобы при переходе к соседнему столбцу или строке изменялось значение только одной переменной.
Таблицу заполняют значениями функции, соответствующими комбинациям значений переменных. На карте Карно отмечают группы, состоящие из 2n ячеек (n – число переменных) и содержащие 1, т.к. они описываются простыми логическими выражениями. Каждый группа объединяет две ячейки, соответствующие логическим преобразованиям:
X1
X2\X1
X2
Рисунок 4
;
.
Компактное выражение, описывающее функцию, представляет собой дизъюнкцию логических выражений, полученных при помощи карт Карно. В результате получаем выражение в СДНФ, совпадающее с переключательной функцией дизъюнкции:
.
Контрольные вопросы
1. Какие функциональные схемы называют комбинационными?
2. Что представляет из себя таблица истинности для переключательных функций?
3. Какие требование, предъявляются к функционально полному набору логических элементов?
4. Почему штрих Шеффера обладает функциональной полнотой?
5. Чем отличаются схема исключающее ИЛИ и равнозначность?
6. Как осуществляется процесс синтеза цифровых логических схем?
7. С какой целью проводится минимизация булевых функций?
8. Каким образом маркируются интегральные микросхемы?
9. Как обозначаются ЛЭ на схемах электрических функциональных и принципиальных?
различных наборов, на которые она может принимать значение 0 или 1.
2
1
.
.
X2\X1
;
.
.