БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра радиотехнических устройств
РЕФЕРАТ
На тему:
«Функции алгебры логики. Логический базис»
МИНСК, 2008
1. Функции алгебры логики (ФАЛ)
Радиоэлектроника в настоящее время во многом определяет научно- технический прогресс и объединяет ряд отдельных областей науки и техники, развившихся из радиотехники и электроники.
Радиотехника - область науки и техники, связанная с разработкой устройств и систем, обеспечивающих генерирование, усиление, преобразование, хранение, а также излучение и прием электромагнитных колебаний радиочастотного диапазона, используемых для передачи информации.
В современных радиотехнических системах и комплексах до 90% разрабатываемых устройств реализуется на элементах цифровой и вычислительной техники и используются цифровые методы обработки сигналов.
В настоящее время бурно развивается по экспоненциальному закону вычислительная техника и ее элементная база. А не так давно первые интегральные микросхемы (1958 год) содержали до десяти транзисторов. Сегодня современные микропроцессоры содержат до 10 миллионов транзисторов на один кристалл, и менее чем через десять лет это число достигнет 100 миллионов транзисторов.
Уже отошла в историю дискретная схемотехника, когда различные узлы строились на печатных платах с использованием отдельных навесных радиоэлектронных компонентов: транзисторов, резисторов, конденсаторов и других элементов. Ранее соединения выполнялись с помощью внешнего печатного монтажа, теперь соединения и монтаж осуществляется внутри кристалла. Поэтому современный инженер электронной техники должен владеть передовыми методами и технологиями, чтобы уметь приспособить их завтра к вычислительной технике будущих поколений, овладеть практическими приемами проектирования устройств на программируемых логических интегральных схемах.
Логические
выражения n
двоичных переменных
с помощью конечного
числа логических
операций можно
рассматривать
как некоторую
функцию, отражающую
взаимную связь
между входными
и выходными
переменными.
Логические
операции конъюнкции
и дизъюнкции
можно представить
простейшими
функциями вида:
и
.
Эти функции
называются
аналогично
логическим
операциям –
функциями И
и ИЛИ.
Такие ФАЛ подобно логическим выражениям могут быть заданы аналитическим и табличным способами.
При аналитическом способе ФАЛ задается в виде логических выражений, получаемых путем логических преобразований с помощью законов и правил Булевой алгебры.
При табличном
способе ФАЛ
задается таблицей
истинности,
где число всех
возможных
наборов (комбинаций)
аргументов
конечно. Если
число аргументов
ФАЛ равно n,
то число их
возможных
наборов
,
а число различных
функций
,
тогда при n=2,
F=16. Составим
таблицу истинности
для функций
двух аргументов.
Таблица 1.
Аргументы | Функции | ||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
В таблице
1 приведены
элементарные
ФАЛ
двух аргументов.
В левой части
таблицы перечислены
все возможные
наборы аргументов
и
,
в правой части
приведены
значения ФАЛ
на соответствующих
входных наборах.
Значения всей
совокупности
этих наборов
переменных
представлены
в таблице
последовательностью
чисел в двоичной
системе счисления.
Каждая ФАЛ
обозначает
одну из 16 возможных
логических
операций над
двумя переменными
и
,
имеет свою
таблицу истинности,
собственное
название и
условное обозначение.
Основные
сведения об
элементарных
функциях
даны в таблице
2. Таблицы истинности
для каждой ФАЛ
составляются
отдельно по
таблице 1.
Таблица 2
|
Операционные символы | Обозначения, названия | Зарубежные аналоги |
|
0 | Константа 0 | Const 0 |
|
|
|
|
|
|
Запрет
|
Inhibition
|
|
|
Повторитель
|
BF
– Buffer
|
|
|
Запрет
|
|
|
|
Повторитель
|
BF
– Buffer
|
|
|
|
|
|
|
|
|
|
|
|
Peers F. |
|
|
|
|
|
|
НЕ
– инвертор
|
NOT
– Invertor
|
|
|
|
|
|
|
НЕ
– инвертор
|
NOT
– Invertor
|
|
|
|
|
|
|
|
|
|
1 |
Генератор 1 |
Generator 1 |
В таблице 2 часто применяемыми являются функции:
-повторители
1-го и 2-го аргументов;
– инверсии
1-го и 2-го аргументов;
– функция
И (конъюнкция),
логическое
умножение;
– функция
И-НЕ (базис Шеффера);
– функция
ИЛИ (дизъюнкция),
логическое
сложение;
– функция
ИЛИ-НЕ (базис
Пирса);
– функция
неравнозначности,
реализуется
ЛЭ “Исключающее
ИЛИ” (сумматор
по модулю два);
– функция
равнозначности
реализуется
ЛЭ “Исключающее
ИЛИ-НЕ”.
Рассмотренные
элементарные
функции двух
аргументов
играют важную
роль при преобразованиях
сложных логических
выражений, а
также при
преобразовании
функциональных
цифровых узлов.
Функции n переменных, значения которых заданы во всех точках области определения, считаются полностью определенными ФАЛ. Если какая-либо функция имеет запрещенные наборы переменных и ее значения на указанных наборах не определены, то такая ФАЛ называется не полностью определенной. Такие наборы будем отмечать в таблицах истинности (*) и при необходимости доопределять их значениями 0 и 1. Эти вопросы будут рассматриваться позже.
Логические функции, которые считаются полностью определенными, могут быть представлены различными формами.
ДНФ – дизъюнктивная нормальная форма записи ФАЛ представляется в виде суммы (дизъюнкции) ряда элементарных членов (минтермов), каждый из которых является произведением (конъюнкцией) аргументов или их инверсий. Термин “нормальная форма” предполагает, что в логическом выражении, задающем функцию, последовательно выполняются не более двух базовых операций (кроме инверсии).
Запишем ФАЛ в ДНФ:
;
(1)
Функцию (3.19) можно записать в виде дизъюнкции минтермов:
,
где
-
конъюнкции
аргументов
ФАЛ, называемые
минтермами.
СДНФ – совершенная дизъюнктивная нормальная форма записи ФАЛ представляется в ДНФ, где в каждом элементарном члене (минтерме), имеющем одинаковую размерность, представлены все аргументы функции или их инверсии.
Запишем ФАЛ в СДНФ:
.
(2)
Если записать ФАЛ в виде:
,
(3)
то
форма представления
данной функции
не является
СДНФ, так как
второй минтерм
не содержит
аргумента
,
а также не является
ДНФ, так как
третий минтерм
не является
элементарным.
Функцию
можно упростить
(минимизировать)
и представить
минимальной
ДНФ (МДНФ).
(4)
Полученные элементарные члены МДНФ называются импликантами.
КНФ – конъюнктивная нормальная форма записи ФАЛ, представляется в виде произведения (конъюнкции) ряда элементарных членов (макстермов), которые являются суммой (дизъюнкцией) аргументов ФАЛ.
Запишем
функцию
в КНФ:
.
(5)
СКНФ – совершенная конъюнктивная нормальная форма записи ФАЛ представляется в КНФ, где в каждом элементарном члене (макстерме) представлены все аргументы функции либо их инверсии.
Запишем
функцию
в СКНФ:
.
(6)
По функциям, представленным в СДНФ и СКНФ, можно построить таблицу истинности и наоборот – по таблице истинности можно записать ФАЛ в СДНФ и СКНФ.
На основании
общей табл. 1
составим таблицу
истинности
функции неравнозначности
и запишем ее
в СДНФ и СКНФ.
На наборах
N(2,3),
где функция
принимает
значения 1,
записываем
ФАЛ в СДНФ, а
на наборах
N(1,4)
– в СКНФ. При
записи ФАЛ в
СДНФ аргументы
x=0
записываются
с инверсией
,
а в СКНФ – без
инверсии.
При записи функции в СДНФ по таблице истинности необходимо записать столько дизъюнктивных членов (минтермов), представляющих собой конъюнкции всех аргументов, сколько единиц содержит функция в таблице. Минтермы соединяются знаком логического суммирования.
Если в наборе значение аргумента равно нулю, то в конъюнкцию входит инверсия данного аргумента.
При записи ФАЛ в СКНФ необходимо записать столько конъюнктивных членов (макстермов), сколько нулей содержит функция. Макстермы (конъюнкции аргументов) соединяются знаком логического умножения. Если в наборе значение аргумента равно нулю, то в дизъюнкцию входит аргумент без инверсии.
2. Логический базис
Логические функции могут быть реализованы простейшими логическими элементами. Совокупность логических элементов И, ИЛИ, НЕ, с помощью которых можно воспроизвести и реализовать любую ФАЛ, будем называть полным логическим базисом.
Базис И, ИЛИ, НЕ обладает избыточностью и не является минимальным. Из этой совокупности ЛЭ можно исключить логический элемент И (либо ЛЭ ИЛИ), тогда наборы И, НЕ и ИЛИ, НЕ также будут обладать свойством базиса.
При проектировании логических схем вычислительной техники самое широкое применение получили базис Шеффера И-НЕ и базис Пирса ИЛИ-НЕ, обладающие свойством логического базиса.
Следует отметить, что одну и ту же логическую функцию (операцию) можно реализовать в различных базисах. Покажем это на примерах простых логических операций дизъюнкции и конъюнкции:
;
.
(7)
Используя
законы инверсии
и
,
преобразуем
логические
выражения
:
;
.
(8)
Выражения (7) отражают принцип двойственности алгебры логики: если в логическом выражении операцию дизъюнкции заменить на операцию конъюнкции (либо наоборот) и проинвертировать все переменные, то результат окажется инверсным прежнему значению.
Используя принцип двойственности алгебры логики, реализуем логическое выражение (7) в различных базисах.
Рис. 2
Из рис.2 следует:
если переименовать
все входы и
выходы логического
элемента ЛЭ1
на инверсные
значения и
заменить ЛЭ
дизъюнкции
на ЛЭ2 конъюнкции,
то функции
дизъюнкции
можно выполнить
с помощью элементов
НЕ, И (ЛС3) либо
базиса Шеффера
И-НЕ (ЛС4).
Все логические схемы (рис. 2) выполняют логическую операцию (функцию) ИЛИ, которую можно реализовать на однотипных логических элементах И-НЕ, а при наличии инверсных сигналов в проектируемом устройстве – на одном ЛЭ И-НЕ.
На рис. 2 ЛС3 и ЛС4 – логические схемы, в состав которых входят несколько логических элементов ЛЭ.
Аналогично можно показать, что логическую операцию (функцию) И можно выполнить в базисах НЕ, ИЛИ либо в базисе Пирса ИЛИ-НЕ (рис. 3).
Рис. 3
Таким образом, логический базис, представляющий собой совокупность типов логических элементов, может быть выполнен на универсальных логических элементах И-НЕ и ИЛИ-НЕ, выпускаемых промышленностью в интегральном исполнении. Полный логический базис И, ИЛИ, НЕ обычно используется на начальной стадии проектирования функциональных узлов для составления функциональных схем.
ЛИТЕРАТУРА
1. Браммер Ю.А. Цифровые устройства: Учеб. пособие для вузов. –М.:Высш. шк., 2004. –229с.
2. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Учеб. пособие для втузов.- СПб.: Политехника, 1996.- 885 с.
3. Угрюмов Е.П. Цифровая схемотехника: Учеб. пособие для вузов.-СПб: БХВ-Петербург, 2000, 2004. – 528с.