Основы анализа и синтеза комбинационных логических устройств Министерство образования Российской Федерации Российский химико-технологический университет им. Д. И. Менделеева Новомосковский институт Основы анализа и синтеза комбинационных логических устройств Новомосковск 2008 Министерство образования Российской Федерации Российский химико-технологический университет им. Д. И. Менделеева Новомосковский институт Основы анализа и синтеза комбинационных логических устройств Методические указания Под редакцией В.И.Воробьева Новомосковск 2008 УДК 681.322 ББК 32.973 О 753 Рецензенты: кандидат технических наук, доцент кафедры «Автоматизация производственных процессов», НИ РХТУ им. Д.И. Менделеева В. З. Магергут , кандидат технических наук, доцент кафедры «Автоматизация производственных процессов», НИ РХТУ им. Д.И. Менделеева С. Л. Сидельников . Составитель: B . C . Прохоров О 753 Основы анализа и синтеза комбинационных логических устройств : Методические указания / Под редакцией В.И. Воробьева; РХТУ им. Д. И. Менделеева, Новомосковский ин-т; Сост.: B . C . Прохоров .– Новомосковск, НИ РХТУ им Д.И. Менделеева, 2008. - 78 с. Рассмотрены вопросы анализа и синтеза комбинационных логических устройств. Даются основы математического аппарата и рассматриваются типовые комбинационные схемы. Ил. 57. Табл. 33. Библиогр.: 8 назв. УДК 681.322 ББК 32.973 ã Новомосковский институт РХТУ им. Д. И. Менделеева, 2008 ОГЛАВЛЕНИЕ Введение 1. Основы математического аппарата анализа и синтеза логических устройств 1.1. Логическая функция 1.1.1. Алгебраическое представление логической функции в совершенной нормальной форме 1.1.2 Графическое представление логической функции в виде Карты Карно (диаграммы Вейча) 1.2 Логические операции 1.3 Аксиомы булевой алгебры. 1.5 Некоторые полезные соотношения 1.6. Минимизация логических функций с помощью карт Карно. 1.7 Аналитические методы минимизации логических функций 1.8 Логический базис 2 Логические элементы, образующие логический базис 2.1 Конъюнктор (элемент И) 2.2 Дизъюнктор (элемент ИЛИ) 2.3......................................... Инвертор (элемент НЕ) 2.4 Элемент Шеффера (элемент И-НЕ) 2.5 Элемент Пирса (элемент ИЛИ-НЕ) 2.6 Функциональная полнота элементов Шеффера (И-НЕ) и Пирса (ИЛИ-НЕ) 3. Взаимное соответствие логической функции и логической схемы 4 Особенности синтеза схем с запрещенными комбинациями 5 Типовые комбинационные схемы 5.1 Мультиплексоры 5.2 Синтез комбинационных схем на мультиплексорах 5.3 Демультиплексоры 5.4 Дешифраторы 5.5 Шифраторы 5.6 Преобразователи кодов 5.7 Сумматоры 5.8 Цифровые компараторы 5.9 Инкрементор 5.9. Коммутатор БИБЛИОГРАФИЧЕСКИЙ СПИСОК Введение В соответствии с типовой программой дисциплины "Схемотехника" подготовка студентов по специальности «Автоматизированные системы обработки информации и управления» ориентирована на изучение цифровых электронных устройств и методов их проектирования с применением систем автоматического проектирования (САПР) . В учебном пособии эти задачи решаются последовательно, начиная с изучения основ математического аппарата и кончая синтезом принципиальных электрических схем цифровых устройств с заданными характеристиками и разработкой для них печатных плат с использованием наиболее распространенной системой проектирования P - CAD . Для лучшего освоения теоретического материала в пособии приведено большое количество примеров. Успешное освоение материала помогает студентам в дальнейшем при изучении более сложных цифровых устройств. Работа предназначена для студентов впервые проводящих анализ и синтез логических схем, поэтому рассмотрен минимальный круг решаемых при этом простейших задач. Специфические задачи и способы их решения могут быть рассмотрены в пособиях по курсовому и дипломному проектированию, а также в лабораторном практикуме. Специфика применения САПР при разработке цифровых электронных устройств Резко сокращаются сроки проектирования изделий при возрастающих требованиях к их качественным характеристикам: Создание любого электронного устройства включает в себя следующие этапы. 1. Формирование технического задания (ТЗ) на разработку, определение структуры и алгоритмов функционирования системы. 2. Разработка схемы электрической принципиальной, перечня элементов и выпуск соответствующей документации. 3. Моделирование или макетирование отдельных узлов или всего устройства в целом. 4. Разработка конструкции печатной платы и выпуск комплекта конструкторской и технологической документации. 5. Подготовка к производству и изготовление печатных плат. 6. Сборка, настройка и регулировка изделия. В современных условиях выполнение проекта ведется силами сравнительно небольшого коллектива с использованием различных систем автоматического проектирования (САПР). Одной из наиболее распространенных в России САПР является система P - CAD . Система P - CAD предназначена для проектирования многослойных печатных плат (ПП) вычислительных и радиоэлектронных устройств. В состав P - CAD входят четыре основных модуля - P - CAD Schematic , P - CAD PCB , P - CAD Library Executive , P - CAD Autorouters и ряд других вспомогательных программ. P - CAD Schematic и P - CAD PCB - графические редакторы, соответственно, принципиальных электрических схем и печатных плат (ПП). Редакторы имеют системы всплывающих меню в стиле Windows , а наиболее часто применяемым командам назначены пиктограммы. Основное назначение графического редактора P - CAD Schematik – построение принципиальных электрических схем электронных устройств. В поставляемых вместе с системой P-CADбиблиотеках зарубежных цифровых интегральных схем (ИМС) имеются три варианта графики: Normal — нормальный (в стандарте США); DeMorgan — обозначение логических функций; IEEE — в стандарте Института инженеров по электротехнике (наиболее близкий к российким стандартам). Редактор печатных плат P - CAD PCB может запускаться автономно и позволяет разместить компоненты на монтажно—коммутационном поле для ручной, полуавтоматической и автоматической трассировки проводников. Если P - CAD PCB вызывается из редактора P - CAD Schematic , то автоматически составляется список соединений схемы и на поле ПП переносятся изображения корпусов компонентов с указанием линий электрических соединений между их выводами. Эта операция называется упаковкой схемы на печатную плату. Затем вычерчивается контур ПП, на нем размещаются компоненты и, наконец, производится трассировка проводников. P-CAD Library Executive - менеджербиблиотек. Интегрированные библиотеки P-CAD содержат как графическую информацию о символах и типовых корпусах компонентов, так и текстовую информацию (число секций в корпусе компонента, номера и имена выводов, коды логической эквивалентности выводов и т.д.). Программа имеет встроенные модули: Symbol Editor — для создания и редактирования символов компонентов и Pattern Editor - для создания и редактирования посадочного места и корпуса компонента. Упаковка вентилей компонента, ведение и контроль библиотек осуществляются модулем Library Executive . Модуль имеет средства просмотра библиотечных файлов, поиска компонентов, символов и корпусов компонентов по всем возможным атрибутам. Разработчик регулярно сталкивается с проблемой создания библиотек компонентов. Как правило; необходимость в этом возникает при создании условных графических изображений компонентов (УГО) в соответствии с действующими стандартами. Для создания библиотечных компонентов используются возможности графических редакторов Schematic и РСВ , а для управления библиотеками — программа Library Executive . P - CAD 2002 имеет интегрированные библиотеки, которые содержат графическую информацию о символах и типовых корпусах компонентов и текстовую упаковочную информацию. Библиотеки, созданные для предыдущих версий P-CAD, переносятся в P-GAD 2002 через текстовый формат PDF . Первым этапом проектирования любого устройства является формирование технического задания (ТЗ) и разработка структуры системы. Как правило, этим занимается разработчик, который в дальнейшем будет создавать и принципиальную схему устройства. На данном этапе основной является текстовая документация, но она почти всегда сопровождается выпуском структурных или функциональных схем. Конечно, существуют и более удобные для выполнения такого рода схем специализированные графические редакторы, например MS Visio 2000 . Они позволяют получить структурную схему возможно качественнее и быстрее, чем редакторы P - CAD Schematic или P - CAD PCB , однако большинству разработчиков гораздо привычнее выполнять структурные и функциональные схемы в той же системе, где будет выполняться и схема электрическая принципиальная. Поэтому рекомендуется выполнять всю конструкторскую документацию в одной среде. Тем более что в P - CAD 2002 возможно использование встроенных механизмов ОС Windows , позволяющих выполнять копирование информации в буфер и ее использование из других приложений, в частности различных текстовых процессоров для оформления документации. После, выработки технического задания и выпуска функциональной и структурной схем начинается этап создания схемы электрической принципиальной и перечня элементов. Практически все современные разработки немыслимы без предварительного моделирования их работы в одном из пакетов схемотехнического проектирования. Поэтому выполненная в пакете САПР печатных плат схема электрическая принципиальная в идеале, с одной стороны, должна быть пригодна для последующей трассировки платы, а с другой стороны, она же должна передаваться в пакет моделирования. К сожалению, в реальности, как правило, картина иная. Наиболее известным в России пакетом, имеющим одновременно как средства моделирования, так и проектирования печатных плат, является DesignLAB разработки фирмы Microsim. Однако данный пакет не получил широкого распространения при проектировании. Для моделирования цифровых и аналоговых электронных схем применяют интегрированный пакет MULTISIM (ElectronicWorkbenchMultisim) – редактор схемотехники и SPICE симулятор. Он позволяет анализировать работу электронных схем. Обширная библиотека компонентов включает генераторы сигналов, осциллографы, тестеры, огромное количество полупроводниковых приборов и микросхем разных фирм. Имеет возможность экспорта схемы в программы РСВ – трассировки. В системе P - CAD 2002 сделан большой шаг вперед. Теперь проблема конвертирования форматов и взаимодействия с пакетами третьих фирм практически решена. В графическом редакторе Schematic имеются необходимые для этого команды По завершению работы над схемой принципиальной электрический наступает этап проектирования печатной платы. Начинается он с рисования контура печатной платы и размещения компонентов. Для этого в P - CAD предусмотрен графический редактор P - CAD РСВ . Особенностью P - CAD 2002 и является наличие еще одного графического редактора Relay . Данный редактор представляет собой упрощенный вариант редактора РСВ . С помощью Relay возможно выполнить предварительное размещение компонентов, задать необходимые для трассировки зазоры и выполнить трассировку наиболее ответственных цепей. Ведение проекта в любой САПР невозможно без различных вспомогательных программ, предназначенных для составления отчетов, генерации текстовых конструкторских документов (перечней и спецификаций), коррекции базы данных, автоматической генерации библиотечных компонентов, конвертирования в форматы САПР третьих фирм, анализа электромагнитной совместимости и целостности сигналов и т. д. В частности, в состав P - CAD 2002 включена программа Document Toolbox , предназначенная для расширения возможностей выпуска технической документации без использования чертежных программ типа AutoCAD . Их применение позволяет существенно сократить как временные затраты, так и повысить качество проектирования и сопровождения конструкций аппаратуры. Следует отметить, что в большинстве случаев для обеспечения удобства электронного оборота конструкторской документации итоговый чертеж или схема выполняются в САПР AutoCAD , поэтому наиболее часто используемой вспомогательной программой является конвертор из формата P - CAD в AutoCAD . 1. Основы математического аппарата анализа и синтеза комбинационных логических устройств Все устройства, оперирующие с двоичной информацией, подразделяются на два класса: - комбинационные (дискретные автоматы без памяти). - последовательные (дискретные автоматы с памятью). Сигналы на выходах комбинационного устройства однозначно определяются сочетанием сигналов на его входах и не зависят от предыдущих состояний. Примерами комбинационных устройств могут служить: 1) логические элементы, реализующие логический базис (логические функции И, ИЛИ, НЕ , а также И-НЕ или ИЛИ-НЕ ) 2) электронные ключи; 3) мультиплексоры; 4) демультиплексоры и дешифраторы; 5) большинство арифметических устройств и т.д. Основой анализа и синтеза логических устройств является алгебра логики (булева алгебра). Связь между входными и выходными сигналами логических устройств устанавливает логическая функция. 1.1 Логическая функция Функция f(x1 ,x2 ,x3 ,...,xn ) называется логической (булевой, переключательной), если она, также как и ее аргументы, может принимать только два значения - “истинно” 1 или “ложно” 0. Для n логических переменных (аргументов) существует 2n логических комбинаций из 0 и 1. Например, для n = 2, x1 x2 = 00, 01, 10, 11. Для каждой комбинации переменных набора логическая функция может принимать значение 0 или 1. Для n переменных существует различных логических функций. Логическая функция может быть задана: 1) словесно; 2) таблицей истинности; 3) алгебраически; 4) графически. Пример словесного описания : функция f(x1 ,x2 ) принимает значение 1, когда значения переменных равны: x1 = x2. При неравенстве переменных x1 ¹x2 функция принимает значение 0. Эту функцию представляют также табл.1.1, которая содержит все 2n возможных наборов значений логических переменных (аргументов) и значения функции, соответствующие каждому из наборов. Таблица 1.1 Таблица истинности . x1 x2 f 0 0 1 0 1 0 1 0 0 1 1 1 1.1.1 Алгебраическое представление логической функции в совершенной нормальной форме Различают две формы алгебраического представления логической функции: совершенная дизъюнктивная нормальная форма (СДНФ); совершенная конъюнктивная нормальная форма (СКНФ). Для перехода от табличного представления функции к алгебраическому в виде ее СДНФ каждому i-ому набору переменных ставится в соответствие минтерм (mi ) (константа единицы) - конъюнкция переменных, которые входят либо в прямом виде, если значение данной переменной в наборе равно 1, либо в инверсном виде, если значение переменной равно 0. Для n переменных составляют q=2n минтермов: m0 , m1 ,... , mq-1 . Алгебраическое выражение логической функции в форме СДНФ представляют в форме суммы: , где fi , mi - значение функции (0 или 1) и минтерм, соответствующий i- ому набору переменных. Для перехода от табличного представления функции к алгебраическому в виде СКНФ каждому i-ому набору переменных ставится в соответствие макстерм (Mi ) - дизъюнкция переменных, которые входят либо в прямом виде, если значение данной переменной равно 0, либо в инверсном виде, если значение переменной равно 1 [1]. Алгебраическое выражение логической функции в форме СКНФ представляют в виде произведения , где fi , Mi - значение функции и макстерм, соответствующий i-ому набору переменных. Пример 1.1. Логическая функция равнозначность (эквивалентность) для двух переменных представлена табл.1.2.: Таблица 1.2. Таблица истинности x1 x2 f 0 0 1 0 1 0 1 0 0 1 1 1 Представить эту функцию в алгебраической форме в виде СДНФ и СКНФ. Решение. 1. Для n=2 переменных составляют q = 2n = 4 минтерма и макстерма, которые вписаны соответственно в 3-ю и 4-ю графы табл.1.3. Таблица 1.3 Минтермы и макстермы x1 x2 mi Mi f 1 2 3 4 5 0 0 0 1 1 0 1 1 2. Алгебраическое представление логической функции в СДНФ 3. Алгебраическое представление логической функции в СКНФ Ускорить процесс нахождения СДНФ и СКНФ можно, если применить другие правила. СДНФ находят по правилу записи логической функции “по единицам”: выписывают ряд произведений всех аргументов и соединяют их знаками дизъюнкции; количество произведений должно равняться числу наборов, на которых заданная функция обращается в единицу; записывают под каждым произведением набор аргументов, на котором функция равна единице, и над аргументами равными 0, ставят знаки отрицания. Пример 1.2. Представить в СДНФ логическую функцию пяти аргументов f(x1 ,x2 ,x3 ,x4 ,x5 ), равную единице на следующих четырех наборах 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 Решение. 1. Запишем четыре произведения аргументов, связанных знаком дизъюнкции, и под каждым из них - один из перечисленных наборов x1 x2 x3 x4 x5 Ú x1 x2 x3 x4 x5 Ú x1 x2 x3 x4 x5 Ú x1 x2 x3 x4 x5 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 2. Расставляя отрицания над аргументами, равными нулю, получим СДНФ логической функции: Ú Ú Ú СКНФ находят по правилу записи переключательной функции “по нулям”: 1) выписывают произведения дизъюнкций всех аргументов с количеством сомножителей, равным числу наборов, на которых заданная функция обращается в нуль; 2) записывают под каждым сомножителем набор аргументов, на котором функция равна нулю, а над аргументами, равными единице ставят знаки отрицания. Пример 1.3. Представить в СКНФ переключательную функцию четырех аргументов f(x1 ,x2 ,x3 ,x4 ), равную нулю на наборах 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 Решение. 1. Запишем четыре произведения дизъюнкций всех аргументов и под каждым из них один из перечисленных наборов: (x1 Úx2 Úx3 Úx4 ) × (x1 Úx2 Úx3 Úx4 ) × (x1 Úx2 Úx3 Úx4 ) × (x1 Úx2 Úx3 Úx4 ) 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 2. Расставляя знаки отрицания над аргументами, равными единице, получим СКНФ логической функции: При выборе совершенной формы записи логической функции следует иметь в виду, что СДНФ является более целесообразной, если число наборов, на которых функция равна 0, превышает число наборов, на которых функция равна 1. В противоположном случае более приемлемой будет СКНФ. Пример 1.4. Необходимо построить мажоритарную ячейку (ячейку голосования) на три входа, т.е. такую ячейку, у которой сигнал на выходе равен единице тогда, когда большинство входных сигналов равно единице, т.е. он равен единице, когда на двух или трех входах присутствует сигнал единицы, в противном случае выходной сигнал равен нулю [2]. Представить логическую функцию мажоритарной ячейки в виде таблицы истинности и в алгебраическом виде в формах СДНФ и СКНФ. Решение. 1. Для трех входных сигналов, т.е. для n=3 переменных существует q=2n =23 =8 различных комбинаций этих сигналов табл.1.4. Таблица 1.4 Таблица истинности x1 x2 x3 f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 2. Для представления логической функции в алгебраическом виде в форме СДНФ нужно представить эту функцию в виде суммы логических произведений аргументов, соответствующих тем строкам таблицы истинности, для которых логическая функция равна единице. При записи этих логических произведений следует брать соответствующий аргумент с инверсией, если этот аргумент в данной строке таблицы равен нулю, и без инверсии, если он равен единице: 3. Для представления логической функции в алгебраическом виде в форме СКНФ нужно представить эту функцию в виде произведения логических сумм аргументов, соответствующих тем строкам таблицы истинности, для которых логическая функция равна нулю. При записи этих логических сумм следует брать соответствующий аргумент с инверсией, если этот аргумент в данной строке таблицы равен единице, и без инверсии, если он равен нулю: Пример 1.5. Полный набор = 16 логических функций двух переменных приведен в табл.1.5. Записать алгебраические выражения этих функций в формах СДНФ и СКНФ. Таблица 1.5 Полный набор логических функций двух переменных Таблица истинности Название функции Условноеобозначение Алгебраическое выражение Функция x1 0 0 1 1 x2 0 1 0 1 СДНФ СКНФ 1 2 3 4 5 6 7 8 9 f0 0 0 0 0 Константа нуль 0 f1 0 0 0 1 Конъюнкция x1 x2 f2 0 0 1 0 Запрет по x2 x1 x2 x1 x2 f3 0 0 1 1 Тождественность x1 x1 f4 0 1 0 0 Запрет по x1 x2 x1 x2 x1 f5 0 1 0 1 Тождественность x2 x2 f6 0 1 1 0 Исключающее ИЛИ Сумма по модулю 2 x1 x2 f7 0 1 1 1 Дизъюнкция x1 Ú x2 x1 + x2 f8 1 0 0 0 Стрелка Пирса x1 ¯ x2 f9 1 0 0 1 Равнозначность x1 ~ x2 f10 1 0 1 0 Инверсия x2 f11 1 0 1 1 Импликация от x2 к x1 x2 ® x1 f12 1 1 0 0 Инверсия x1 f13 1 1 0 1 Импликация от x1 к x2 x1 ® x2 f14 1 1 1 0 Штрих Шеффера x1 / x2 f15 1 1 1 1 Константа единицы 1 1.1.2 Графическое представление логической функции в виде Карты Карно (диаграммы Вейча) Логическая функция может быть представлена графически в виде карт минтермов - карт Карно . Логическую функцию предварительно, исходя из таблицы истинности, приводят к совершенной дизъюнктивной нормальной форме (СДНФ): , Где fi , mi - значение функции (0 или 1) и минтерм, соответствующий i-ому набору переменных. Минтерм - конъюнкция переменных, которые входят либо в прямом виде, если значение данной переменной в наборе равно 1, либо в инверсном виде, если значение переменной равно 0. Минтерм - это простая конъюнкция, в которую входят все аргументы рассматриваемой логической функции [3]. Простой конъюнкцией считается логическое произведение переменных, взятых с отрицаниями или без них, в котором каждая переменная встречается не более одного раза (в простую конъюнкцию не должны входить суммы переменных, отрицания функций двух или нескольких переменных). После представления функции в СДНФ, следует заполнить прямоугольную таблицу, в которой число клеток равно числу возможных минтермов. Эту таблицу называют диаграммой Вейча или картой Карно. Каждой клетке таблицы ставится в соответствие определенная конъюнкция так, чтобы в соседних клетках (снизу и сверху, слева и справа) конъюнкции отличались не более чем одним сомножителем. Для этого нумерацию столбцов и строк таблицы ведут кодом Грея, количество разрядов которого равно количеству переменных, отведенных для строк и столбцов. При заполнении таблицы в соответствующую клетку ставится 1, если логическая функция при данном наборе аргументов равна единице(рис.1.1-1.4). x1 x2 0 1 0 1 Рис.1.1 Карта Карно для логической функции двух аргументов. x1 x2 x3 00 01 11 10 0 1 Рис.1.2 Карта Карно для логической функции трех аргументов. x1 x2 x3 x4 00 01 11 10 00 01 11 10 Рис. 1.3 Карта Карно для логической функции четырех аргументов. x1 x2 x3 x4 x5 000 001 011 010 110 111 101 100 00 01 11 10 Рис.1.4 Карта Карно для логической функции пяти переменных. Между представлением логической функции в табличной (таблица истинности), алгебраической (в виде СДНФ) и графической (на карте Карно) формах имеется однозначное соответствие. Логическая функция на карте Карно представляется совокупностью клеток, заполненных 1, инверсия этой функции представляется совокупностью пустых клеток (или заполненных 0). Для логических функций с числом переменных n ³ 6 наглядность карт Карно теряется и поэтому такие функции представляются в виде композиции функции меньшего числа переменных: , где x1 - выделяемая переменная; функции получаются из функции f подстановкой значений x1 =0 и x1 =1. В качестве выделяемой может использоваться любая переменная. Например, Процесс выделения более простых функций называется декомпозицией. Полученные функции f0 и f1 могут подвергаться дальнейшей декомпозиции. 1.2 Логические операции Множество логических функций n переменных можно образовать посредством трех основных логических операций: 1) Логическое отрицание (инверсия); 2) Логическое сложение (дизъюнкция); 3) Логическое умножение (конъюнкция). Более сложные логические преобразования можно свести к указанным операциям [4]. Логические ф ункции подчиняются принципу дуальности (двойственности) - теоремы Де Моргана; согласно которому операции конъюнкции и дизъюнкции допускают взаимную замену, если одновременно поменять логическую 1 на 0, 0 на 1, знак Ú (+) на Ù(×), а Ù(×) на Ú (+), где Ú или + - обозначение операции дизъюнкции; Ù или × - обозначение операции конъюнкции. 1.3 Аксиомы булевой алгебры Булева алгебра базируется на нескольких аксиомах, из которых выводят основные законы для преобразований с двоичными переменными (табл. 1.6, 1.7) Таблица 1.6 Аксиомы булевой алгебры конъюнкция дизъюнкция 0×0=0 0+0=0 0×1=0 0+1=1 1×1=1 1+1=1 x×0=0 x+0=x x×1=x x+1=1 x×x=x x+x=x Таблица 1.7 Законы булевой алгебры Закон булевой алгебры Конъюнкция Дизъюнкция 1 2 3 Переместительный (коммутативности) x1 x2 = x2 x1 x1 + x2 = x2 + x1 Сочетательный (ассоциативности) x1 x2 x3 = x1 (x2 x3 ) = (x1 x2 )x3 x1 +x2 +x3 = (x1 +x2 )+x3 = =x1 +(x2 +x3 ) Распределительный (дистрибутивности) x1 (x2 +x3 )= x1 x2 +x1 x3 x1 +(x2 x3 )= (x1 +x2 )(x1 +x3 ) Поглощения x1 +x1 x2 = x1 x1 (x1 +x2 ) = x1 Склеивания x1 Де Моргана (инверсии, дуальности) Развертывания Не полного развертывания 1.5 Некоторые полезные соотношения 1.6 Минимизация логических функций с помощью карт Карно При минимизации логических функций в карте Карно обводят прямоугольными контурами все единицы и затем записывают минимизированную функцию в виде суммы логических произведений, описывающих эти контуры. При проведении контуров придерживаются правил: 1) контур должен быть прямоугольным; 2) внутри контура должны быть только клетки, заполненные единицами; 3) число клеток, находящихся внутри контура, должно быть целой степенью числа 2, т.е. можно склеивать 1, 2, 4, 8,... членов; 4) одни и те же клетки, заполненные единицами, могут входить в несколько контуров; 5) при проведении контуров самая нижняя и самая верхняя строки таблицы считаются соседними, то же - для крайнего левого и крайнего правого столбцов; 6) число контуров должно быть как можно меньшим, а сами контуры как можно большим. Пример 1.6. Провести минимизацию логической функции, заданной в форме СДНФ,с помощью карты Карно (рис.1.5). x1 x2 x3 00 01 11 10 0 1 1 1 1 1 1 Рис.1.5 Карта Карно. Решение. С помощью преобразований, выполняемых по законам булевой алгебры, и с учетом объединенных на карте Карно клеток, получают минимизированное выражение (МДНФ) логической функции: ; , . В рассмотренном примере двум клеткам первого объединения соответствуют минтермы, имеющие две общие переменные . Поэтому дизъюнкция этих минтермов равна этим двум общим переменным: . Четырем клеткам второго объединения соответствуют минтермы имеющие одну общую переменную : Дизъюнкция этих минтермов также равна общей переменной . Чем больше клеток входит в объединение, тем меньше переменных входит в соответствующий конъюнктивный член, т.е. проще МДНФ. Процесс получения алгебраического выражения логической функции, представленной на карте Карно, сводится к считыванию объединений клеток. При этом каждое объединение клеток считывают в виде конъюнктивного члена, в который входят переменные или их инверсии, общие для всех минтермов, соответствующих этим клеткам. Необъединенные клетки считывают в виде записанных в них минтермов. Число конъюнктивных членов в МДНФ равно сумме объединений и необъединенных клеток. Пример 1.7. Логическая функция задана табл.1.8 Таблица 1.8 Таблица истинности x1 x2 f 0 0 1 0 1 1 1 0 0 1 1 1 Найти СДНФ этой функции, и провести минимизацию с помощью карты Карно. Решение: 1. Находят минтермы: x1 x2 mi f 0 0 1 0 1 1 1 0 0 1 1 1 2. Логическая функция в форме СДНФ: . 3. Карта Карно логической функции (рис.1.6) x1 x2 0 1 0 1 1 1 1 Рис.1.6 Карта Карно логической функции 4. Получают МДНФ функции . Пример 1.8. Минимизировать с помощью карты Карно (рис.1.7) логическую функцию, заданную в форме СДНФ: x1 x2 x3 00 01 11 10 0 1 1 1 1 1 Рис.1.7 Карта Карно Решение: МДНФ функции: . Пример 1.9. Минимизировать с помощью карты Карно (рис.1.8) заданную в форме СДНФ логическую функцию: . x1 x2 x3 00 01 11 10 0 1 1 1 1 1 1 1 Рис.1.8 Карта Карно: Решение: МДНФ функции: 1.7 Аналитические методы минимизации логических функций Эти методы базируются на применении основных законов булевой алгебры. Алгоритм получения МДНФ логической функции : 1. Логическая функция представляется в СДНФ. Причем, если она задана таблицей истинности, то представляют путем записи “по единицам”; если она задана алгебраической произвольной дизъюнктивной форме - путем применения операций развертывания, формул Де Моргана и др. 2. В полученном СДНФ проводят все возможные операции неполного склеивания и затем поглощения. В результате получают сокращенную дизъюнктивную нормальную форму, т.е. дизъюнкцию самых коротких из всех возможных элементарных произведений (простые импликанты), входящие в данную логическую функцию. 3. Находят минимальные дизъюнктивные нормальные формы по импликантной матрице. Импликантная матрица - это таблица, на вертикальные и горизонтальные входы которой записывают соответственно члены СДНФ и простые импликанты заданной логической функции. Клетки импликантной матрицы, образованные пересечением строк с импликантами и столбцов с поглощательными ими членами СДНФ, отмечают крестиками [5]. МДНФ находят как дизъюнкцию минимального числа импликант, которые совместно накрывают крестиками все колонки импликантной матрицы. Пример 1.10. Минимизировать логическую функцию: Решение: 1. Функция задана в алгебраической форме, применяя операции развертывания получают СДНФ, содержащую шесть членов: 2. Операции склеивания проводят в следующем порядке: 1) выполняются все возможные склеивания 1-ого члена с остальными; 2) выполняются все возможные склеивания 2-ого члена с остальными, кроме 1-ого; 3) выполняются все возможные склеивания 3-ого члена с остальными, кроме 1-ого и второго и т.д. Склеиваться могут только те члены, у которых число переменных с отрицаниями отличается на единицу. Результаты склеивания и поглощения: Звездочками отмечают те члены СДНФ, которые поглощаются произведениями, образовавшимися после склеивания. В рассматриваемом примере поглощаются все шесть исходных членов, поэтому СДНФ заданной функции имеет вид: К этому выражению операции склеивания и поглощения применить нельзя, и, следовательно, оно является сокращенной дизъюнктивной нормальной формой логической функции, а его члены - простыми импликантами. 3. Строят для заданной функции импликантную матрицу (табл.1.9) Таблица 1.9 Импликантная матрица Простые Члены СДНФ импликанты (минтермы) 1 2 3 4 5 6 X X X X X X X X X X Для получения МДНФ необходимо найти минимальное число импликант, которые совместно накрывают крестиками все столбцы импликантной матрицы: Сложность логической функции определяется числом переменных входящих в ее выражение: в заданной функции 14, в минимальной - 9. Первый алгоритм получения МКНФ логической функции : 1. Логическую функцию представляют в СКНФ. Причем, если она задана таблицей истинности, то ее записывают “ по нулям”; если она задана алгебраически в произвольной конъюктивной форме, то для записи в СКНФ выполняют все возможные операции развертывания. 2. В полученной СКНФ выполняют все возможные операции неполного склеивания и затем поглощения. В результате получают сокращенную конъюнктивную нормальную форму, члены которой являются простыми макстермами. 3. МКНФ находят по макстермной матрице. Пример 1.11. Логическая функция задана табл.1.10 Таблица 1.10 Таблица истинности x1 x2 x3 f 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 Найти МКНФ этой функции. Решение: 1. Выписывают заданную функцию в СКНФ “по нулям” таблицы истинности: 2. Проводят операции склеивания и поглощения: В данном примере поглощаются все четыре члена исходного выражения и, следовательно, СКНФ 3. Макстермная матрица задана табл.1.11 Таблица 1.11 Макстермная матрица Простые импликанты Члены СКНФ (макстермы) 1 2 3 4 X X X X X X 4. МКНФ логической функции: . Второй алгоритм получения МКНФ логической функции : 1. Логическая функция представляется в СДНФ заданной функцией, взятой с отрицанием. Если функция задана таблицей истинности, то выписывают ряд произведений всех аргументов и соединяют их знаками дизъюнкции; количество произведений должно равняться числу наборов, на которых заданная функция обращается в нуль; под каждым произведением записывают набор аргументов, на которых функция равна нулю, и над аргументами, равными нулю, ставят знаки отрицания. Если функция заданна алгебраически в произвольной форме, то сначала находят ее СДНФ, а затем записывают дизъюнкцию всех произведений аргументов, которые не вошли в СДНФ.Находят МДНФ по рассмотренному выше алгоритму. От полученной МДНФ берут отрицание и, после преобразований по формулам Де Моргана, получают МКНФ. Пример 1.12. Найти МКНФ, функции заданной табл.1.12 Таблица 1.12 Таблица истинности x1 x2 x3 f 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 Решение: 1. СДНФ, взятая с отрицанием: 2. Результаты склеивания и поглощения: 3. МДНФ, взятая с отрицанием: 4. Взяв от обеих частей последнего равенства отрицание и применив формулу Де Моргана, получают МКНФ логической функции: . 1.8 Логический базис Любую логическую функцию можно представить в виде СДНФ или СКНФ, т.е. с помощью соответствующей комбинации простейших логических функций И, ИЛИ, НЕ. Такой набор простейших логических функций называют функционально полным или логическим базисом . Логический базис называют минимальным , если удаление хотя бы одной из входящих в него функций превращает его в функционально неполный. Логический базис И, ИЛИ, НЕ не является минмальным, так как с помощью закона дуальности (Де Моргана) можно исключить из логических выражений либо функцию И, либо функцию ИЛИ: . В результате получим минимальные базисы: И, НЕ и ИЛИ, НЕ. 2 Логические элементы, образующие логический базис 2.1 Конъюнктур (элемент И) Конъюнктур - реализует операцию “логическое умножение”. Схема имеет два или больше входов и один выход. На выходе сигнал “1” появляется тогда и только тогда, когда на все входы одновременно воздействуют входные сигналы “1” рис. 2.1. Рис.2.1 Условное изображение конъюнктура на функциональных схемах: x1 ,x2 ,... , xn - входы (минимальное число входов -2); y- выход. Логика работы конъюнктура на три входа представлена табл.2.1 Таблица 2.1 Таблица состояний конъюнктура x1 x2 x3 f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 Логическое уравнение работы конъюнктура: . Знаки (×), (L) соответствуют конъюнкции и читаются как союз И. Если на вход конъюнктура поступают сигналы в разные моменты времени и разной длительности, то сигнал на входе определяется как результат пересечения входных сигналов (рис. 2.2) Рис 2.2 Временная диаграмма работы конъюнктура Таким образом , где i=1,2,... ,n С точки зрения физической реализации конъюнктуры могут быть выполнены на различных “вентильных” компонентах (диодах, транзисторах и др.) Функцию И реализуют, например, соединенные последовательно замыкающие контакты нескольких реле. Цепь в этом случае будет замкнута только тогда, когда сработают все реле. 2.2 Дизъюнктор (элемент ИЛИ) Дизъюнктор - реализует операцию "логическое сложение". Схема имеет два или больше входов. На выходе сигнал "1" появляется тогда, когда хотя бы на один вход воздействует сигнал "1"(рис.2.3). Рис. 2.3 Условное изображение дизъюнктора на функциональных схемах: х1 , х2 ,...хn - входы (минимальное число входов - два); у - выход. Логика работы дизъюнктора на три входа представлена табл.2.2 Таблица 2.2 Таблица состояний дизъюнктора       х1 х2 х3 у