Функции алгебры логики.
Логический базис
В таблице 1 приведены элементарные ФАЛ двух аргументов. В левой части таблицы перечислены все возможные наборы аргументов и, в правой части приведены значения ФАЛ на соответствующих входных наборах. Значения всей совокупности этих наборов переменных представлены в таблице последовательностью чисел в двоичной системе счисления. При табличном способе ФАЛ задается таблицей истинности, где число всех… Читать ещё >
Функции алгебры логики. Логический базис (реферат, курсовая, диплом, контрольная)
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра радиотехнических устройств РЕФЕРАТ На тему:
«Функции алгебры логики. Логический базис»
МИНСК, 2008
1. Функции алгебры логики (ФАЛ)
Радиоэлектроника в настоящее время во многом определяет научнотехнический прогресс и объединяет ряд отдельных областей науки и техники, развившихся из радиотехники и электроники.
Радиотехника область науки и техники, связанная с разработкой устройств и систем, обеспечивающих генерирование, усиление, преобразование, хранение, а также излучение и прием электромагнитных колебаний радиочастотного диапазона, используемых для передачи информации.
В современных радиотехнических системах и комплексах до 90% разрабатываемых устройств реализуется на элементах цифровой и вычислительной техники и используются цифровые методы обработки сигналов.
В настоящее время бурно развивается по экспоненциальному закону вычислительная техника и ее элементная база. А не так давно первые интегральные микросхемы (1958 год) содержали до десяти транзисторов. Сегодня современные микропроцессоры содержат до 10 миллионов транзисторов на один кристалл, и менее чем через десять лет это число достигнет 100 миллионов транзисторов.
Уже отошла в историю дискретная схемотехника, когда различные узлы строились на печатных платах с использованием отдельных навесных радиоэлектронных компонентов: транзисторов, резисторов, конденсаторов и других элементов. Ранее соединения выполнялись с помощью внешнего печатного монтажа, теперь соединения и монтаж осуществляется внутри кристалла. Поэтому современный инженер электронной техники должен владеть передовыми методами и технологиями, чтобы уметь приспособить их завтра к вычислительной технике будущих поколений, овладеть практическими приемами проектирования устройств на программируемых логических интегральных схемах.
Логические выражения n двоичных переменных с помощью конечного числа логических операций можно рассматривать как некоторую функцию, отражающую взаимную связь между входными и выходными переменными. Логические операции конъюнкции и дизъюнкции можно представить простейшими функциями вида: и. Эти функции называются аналогично логическим операциям — функциями И и ИЛИ.
Такие ФАЛ подобно логическим выражениям могут быть заданы аналитическим и табличным способами.
При аналитическом способе ФАЛ задается в виде логических выражений, получаемых путем логических преобразований с помощью законов и правил Булевой алгебры.
При табличном способе ФАЛ задается таблицей истинности, где число всех возможных наборов (комбинаций) аргументов конечно. Если число аргументов ФАЛ равно n, то число их возможных наборов, а число различных функций, тогда при n=2, F=16. Составим таблицу истинности для функций двух аргументов.
Таблица 1.
Аргументы | Функции | |||||||||||||||||
. | ||||||||||||||||||
В таблице 1 приведены элементарные ФАЛ двух аргументов. В левой части таблицы перечислены все возможные наборы аргументов и, в правой части приведены значения ФАЛ на соответствующих входных наборах. Значения всей совокупности этих наборов переменных представлены в таблице последовательностью чисел в двоичной системе счисления.
Каждая ФАЛ обозначает одну из 16 возможных логических операций над двумя переменными и, имеет свою таблицу истинности, собственное название и условное обозначение.
Основные сведения об элементарных функциях даны в таблице 2. Таблицы истинности для каждой ФАЛ составляются отдельно по таблице 1.
Таблица 2
Функция | Операционные символы | Обозначения, названия | Зарубежные аналоги | |
Константа 0 | Const 0 | |||
И — лог. умножитель | AND — Conjunctor | |||
Запрет | Inhibition | |||
Повторитель | BF — Buffer | |||
Запрет | Inhibition | |||
Повторитель | BF — Buffer | |||
Исключающее ИЛИ | Exlusive — OR | |||
ИЛИ — лог. сумматор | OR — Disjunctor | |||
ИЛИ — НЕ, функция Пирса | NOR, Peers F. | |||
Исключ. ИЛИ — НЕ | EX — NOR | |||
НЕ — инвертор | NOT — Invertor | |||
Импликатор | Implicator | |||
НЕ — инвертор | NOT — Invertor | |||
Импликатор | Implicator | |||
И — НЕ, функция Шеффера | NAND, Shaffer F. | |||
Генератор 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с.