Файл: 1. Основные параметры и характеристики логических элементов.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 22.11.2023
Просмотров: 295
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
7. Аксиомы и законы булевой алгебры
Булева алгебра базируется на нескольких аксиомах, из которых выводят основные законы для преобразований с двоичными переменными. Обоснованность выбора этих аксиом подтверждается таблицами истинности для рассмотренных операций. Каждая аксиома представлена в двух видах, что вытекает из принципа дуальности (двойственности) логических операций, согласно которому операции конъюнкции и дизъюнкции допускают взаимную замену, если одновременно поменять логическую 1 на 0, 0 на 1, знак на ∙, а ∙ на .
Аксиомы операции отрицания: , .
Аксиомы операций конъюнкции и дизъюнкции:
1. ; ; (2.1)
2. ; ; (2.2)
3. ; . (2.3)
Законы булевой алгебры вытекают из аксиом и также имеют две формы выражения: для конъюнкции и дизъюнкции. Их правильность легко проверить по таблицам истинности либо путем подстановки 0 и 1 вместо соответствующих значений переменных.
1. Переместительный закон
; . (2.4)
2. Сочетательный закон
; . (2.5)
3. Закон повторения (тавтологии)
; . (2.6)
4. Закон обращения: если , то . (2.7)
5. Закон двойной инверсии . (2.8)
6. Закон нулевого множества
; . (2.9)
7. Закон универсального множества
; . (2.10)
8. Закон дополнительности
; . (2.11)
9. Распределительный закон
; . (2.12)
10. Закон поглощения
; . (2.13)
11. Закон склеивания
; . (2.14)
12. Закон инверсии (закон Де Моргана)
; (2.15)
или после инвертирования левых и правых частей
; . (2.16)
8. Формы представления логических функций
Логическая функция может быть задана словесно, алгебраическим выражением и таблицей, которая называется таблицей истинности.
Словесное представление, отражающее словесную взаимосвязь ее аргументов со значениями функции (например, функция трех аргументов принимает значения единицы, если два или более ее аргументов равные единице, во всех других случаях функция равна нулю). Словесное представление логической функции предшествует любому другому способу представления, поскольку оно отражает неформальную взаимосвязь между аргументами и функцией.
Табличный способ, когда логическая функция задается в виде таблицы соответствия (таблицы истинности, состояния). При этом функция представляется в виде таблицы, в которой выписываются все возможные наборы аргументов в порядке возрастания их номеров, и для каждого набора устанавливается значение функции. Число наборов аргументов, а значит, и число значений функции равно , где – число переменных. В таблице 2.4 представлена функция, словесно заданная в предыдущем примере.
Таблица 2.4
№ набора | Аргументы | Функция | |||
| | | | ||
0 | 0 | 0 | 0 | 0 | |
1 | 0 | 0 | 1 | 0 | |
2 | 0 | 1 | 0 | 0 | |
3 | 0 | 1 | 1 | 1 | |
4 | 1 | 0 | 0 | 0 | |
5 | 1 | 0 | 1 | 1 | |
6 | 1 | 1 | 0 | 1 | |
7 | 1 | 1 | 1 | 1 |
Аналитический способ задания функции заключается в том, что логическая функция задается в виде алгебраического уравнения, в котором переменные связаны между собой знаками логических операций (таблица 2.3).
Существуют две основные формы записи логических функций в алгебраическом виде, называемые нормальными. Первая – дизъюнктивная нормальная форма (ДНФ) – представляет собой логическую сумму элементарных логических произведений (или дизъюнкцию элементарных конъюнкций), в каждое из которых аргумент или его отрицание входит не более одного раза. Например,
. (2.17)
Вторая форма, или конъюнктивная нормальная форма (КНФ), есть логическое произведение элементарных логических сумм (или конъюнкция элементарных дизъюнкций). Например,
. (2.18)
Элементарными называются такие дизъюнкции или конъюнкции, число переменных в которых меньше полного числа переменных, от которых зависит функция. Например, функции (2.17) и (2.18) зависят от трех переменных, а две из трех составляющих их дизъюнкций и конъюнкций соответственно включают только две переменные. Третьи дизъюнкция и конъюнкция включают полное число переменных, поэтому они являются неэлементарными.
Рассмотрим функцию, представленную таблицей 2.4. Она равна единице на наборах переменных с номерами 3, 5, 6, 7, а на остальных наборах равна нулю. Отсюда формулировка записи этой функции по единичным значениям может быть представлена так:
. (2.19)
Такая конъюнкция, включающая в себя полный набор переменных, на котором функция равна единице, называется конституентой единицы (минтермом), а запись функции в виде суммы конституент единицы (т.е. дизъюнкция конституент единицы) называется совершенной дизъюнктивной нормальной формой (СДНФ).
Аналогично конъюнкция, включающая полный набор переменных, на котором функция равна нулю, называется конституентой нуля (макстермом), а запись функции в виде суммы конституент нуля называется совершенной конъюнктивной нормальной формой (СКНФ а запись функции в виде суммы конституент нуля называется совершенной конъюктивной нормальной формой ()итуентой нуля ()которых).
. (2.20)
Используя закон Де Моргана (2.15), выражение (2.20) можно переписать в виде
;
. (2.21)
Таким образом, любая функция из табличной формы записи может быть преобразована в аналитическую с использованием элементарных функций И, ИЛИ, НЕ.
Числовой способ задания функции используется для сокращения ее записи, при этом логическая функция записывается в виде логической суммы десятичных номеров двоичных наборов, на которых функция равна единице, например, для функции, заданной таблицей 2.4.
. (2.22)
9. КНФ, ДНФ, СДНФ, СКНФ. Функционально полные системы логических функций
Приведенная в таблице 2.3 система шестнадцати элементарных функций составляет максимальную систему. Однако каждую элементарную логическую функцию можно записать с помощью только функций И, ИЛИ, НЕ в дизъюнктивной или конъюнктивной нормальных формах. Следовательно, существуют наборы логических функций, с помощью которых можно реализовать все остальные логические функции. В частности, такими наборами являются:
1. И, ИЛИ, НЕ;
2. И–НЕ;
3. ИЛИ–НЕ.
Система таких логических функций называется функционально полной. В современной интегральной микросхемотехнике преимущественное распространение системы И–НЕ, ИЛИ–НЕ и И, ИЛИ, НЕ получили в силу просторы преобразований, выполняемых с этими функциями, способности иметь большое число входов, минимума логических элементов.
СДНФ функции, представленной в таблицей истинности 2.4 или уравнением (2.19) в аналитической форме, легко может быть преобразована в структурную логическую схему, если операции И, ИЛИ, НЕ, описывающие эту функцию, представить в виде логических элементов, реализующих эти операции. При этом каждая конституента единицы реализуется в виде элементов И, на входы которых поданы соответствующие значения переменных, а выходы элементов И, реализующие все конъюнкции, объединяются общим элементом логического суммирования ИЛИ. Структурная схема этой функции представлена на рис. 2.1.
Рис. 2.1. Структурная схема функции, заданной выражением (2.19)
Однако в подавляющем большинстве случаев структура схемы, реализующей функцию ее в СДНФ или СКНФ, является избыточной и может быть существенно упрощена на основании ряда формальных операций, которые называются минимизацией логических схем. Целью минимизации является получение логической схемы, содержащей минимальное число логических элементов с минимальным числом входов.
Наиболее широкое распространение в силу своей простоты и наглядности получили способы, использующие карты Карно или Вейча. Эти карты представляют собой таблицы истинности, преобразованные таким образом, что у функции, нанесенной на такую карту, соседние конъюнкции находятся либо рядом, либо на заранее известных местах.
Карты Карно для двух, трех и четырех переменных приведены на рис. 2.2.
Рис. 2.2. Карты Карно для двух, трех и четырех переменных
Карты Карно для пяти и более переменных рассматриваются как состоящие из отдельных подкарт для четырех переменных: для – из двух подкарт, для – из четырех подкарт и т.д.
Для поиска соседних конъюнкций на карту Карно необходимо сначала нанести функцию, т.е. поставить на местах десятичных номеров той или иной карты значения логической функции на этих номерах наборов. Например, для функции, приведенной в таблице 2.4, выбираем карту Карно для трех переменных и на местах наборов 3, 5, 6, 7 ставим единицы, а на остальных нули (рис. 2.3)
Рис. 2.3. Минимизация с помощью карты Карно функции (2.19)
Порядок операций при минимизации функций при помощи карт Карно:
1. Наносятся на карту все единичные значения полностью определенной функции, а если булева функция является частично определенной (недоопределенной, имеет безразличные состояния), то отмечаются и клетки, соответствующие наборам, на которых функция не определена.
2. Выполняются накрытия всех единичных (или всех нулевых) значений функции минимальным числом максимальных по площади правильных прямоугольников. Площадь прямоугольников подчиняется закону , т.е. допустимое число клеток равно 1, 2, 4, 8 и т.д. Чем больше площадь накрытия, тем меньше переменных входит в результат, а чем меньше число накрытий, тем меньше конъюнкций будет в результате.
3. Записывается результат в виде логической суммы конъюнкций, составляющих каждое отдельное накрытие. Каждый член МДНФ (минимальная дизъюнктивная нормальная форма) составляется лишь из тех аргументов, которые для клеток соответствующей области имеют одинаковое значение (с инверсией либо без инверсии).
Для получения МКНФ функции замкнутыми областями охватываются клетки с нулевыми значениями функции, и при записи членов логического выражения берутся инверсии аргументов, на пересечении которых находятся области. Так, для функции, приведенной в таблице 2.4, МКНФ
(2.23)