Упрощение логических выражений и конструирование цифровых схем на их основе

Размещено на http://www.allbest.ru/

"Упрощение логических выражений и конструирование цифровых схем на их основе"

Введение

булевой выражение символический логика

Цель работы: изучить основные инструменты для решения задач символической логики, получить навыки работы с картами Карно для упрощения булевых выражений и конструирования цифровых схем на их основе.

1. Теоретические указания

Существуют три основных инструмента для решения задач символической логики: условные обозначения (символы) логических элементов, таблицы истинности и булевы выражения.

1.1 Конструирование схем на основе булевых выражений

Предположим, что вам задали булево выражение A + B + C = Y (оно читается так: А, или В, или С равно Y) и предложили построить схему, которая реализует эту логическую функцию. Посмотрев на выражение, вы легко заметите, что для получения нужного результата на выходе Y каждый вход следует объединить с другими входами функцией ИЛИ. На рисунке 1.1 показан необходимый для этого логический элемент (вентиль).

Рисунок 1.1 Принципиальная схема, реализующая булево выражение A+B+C=Y

Допустим, что нам задано булево выражение (оно читается так: не А и В, или А и не В, или не В и С равно выходу Y). Как сконструировать схему, выполняющую операции, соответствующие этому выражению? Прежде всего, внимательно изучив булево выражение, вы заметите, что в нем требуется выполнить логическую операцию ИЛИ над , и . На рисунке 1.2, а показан первый шаг в конструировании логической схемы, т. е. как необходимый результат на выходе Y можно сформировать с помощью логического элемента ИЛИ с тремя входами. Эту же схему можно изобразить по-другому, как показано на рисунке 1.2.

Рисунок 1.2 Первый шаг в конструировании логической схемы

Второй шаг в конструировании логической схемы на основе данного булева выражения проиллюстрирован на рисунке 1.3. Обратите внимание на то, что здесь (рисунок 1.3 а) с целью формирования комбинации на входе элемента ИЛИ в схему добавлен элемент И, а для получения на входе элемента И (под номером 2) в схему введен инвертор. На рисунке 1.3, в схему добавлен элемент И под номером 3 с целью формирования на входе элемента ИЛИ. Наконец, на рисунке 1.3, в введен еще один элемент И под номером 4 и инвертор под номером 6, чтобы получить на входе элемента ИЛИ. Рисунок 1.3 в представляет собой схему, которую надо собрать, чтобы реализовать требуемую логическую функцию в соответствии с заданным булевым выражением .

Рисунок 1.3 Второй шаг в конструировании логической схемы

Заметим, что мы начали с выхода логической схемы и постепенно переходили к ее входам. В этом и состоит способ конструирования комбинационных логических схем на основе булевых выражений.

Булевы выражения встречаются в двух основных формах. Одну из них сумму произведений мы уже видели на рисунке 1.2 и можем привести еще один пример: . Вторая форма булева выражения произведение сумм; например, (D + Е)(Е + F) = Y. Булево выражение в виде суммы произведений в технической литературе называют дизъюнктивной нормальной формой (ДНФ), а булево выражение в виде произведения сумм специалисты называют конъюнктивной нормальной формой (КНФ).

1.2 Таблицы истинности для булевых выражений

Булевы выражения это удобный метод описания принципа работы логической схемы. Таблица истинности это другой точный метод описания того, как работает логическая схема. Поскольку вы будете иметь дело с цифровыми электронными устройствами, вам нужно будет уметь преобразовывать информацию, представленную в форме таблицы истинности, в булево выражение.

Обратимся к таблице истинности, изображенной на рисунке 1.4 а. Заметьте, что только две из восьми возможных комбинаций двоичных сигналов на входах А, В и С дают на выходе логическую 1. Эти две возможные комбинации представлены выражениями (читается так: не С и В и А) и (читается так: С и не В и не А). На рисунке 1.4 б показано, каким образом эти две комбинации связываются логической функцией ИЛИ, чтобы получить булево выражение для данной таблицы истинности. Как таблица истинности на рисунке 1.4 а, так и булево выражение на рисунке 1.4 б демонстрируют принцип действия одной и той же логической схемы.

Рисунок 1.4 Построение булева выражения на основе таблицы истинности

В большинстве случаев конструирование логических схем начинается с составления таблицы истинности. Поэтому вы должны уметь преобразовывать информацию в форме таблицы истинности в булевы выражения так, как это делается в данном разделе. Запомните, что нужно искать те комбинации переменных, которые дают логическую 1 в таблице истинности.

Иногда вам придется выполнять процедуру, обратную только что рассмотренной, т.е. вы должны будете по известному булеву выражению восстанавливать таблицу истинности. Рассмотрим булево выражение на рисунке 1.5 а. Это выражение означает, что две комбинации входов А, В и С дают на выходе логическую l. На рисунке 1.5 б проиллюстрировано, каким образом мы находим нужные комбинации А, В и С, которые даны в булевом выражении, и отмечаем соответствующие единицы в столбце значений выхода. Все другие выходы в таблице истинности дают 0. Как булево выражение на рисунке 1.5 а, так и таблица истинности на рисунке 1.5 б исчерпывающим образом описывают действие некоторой логической схемы.

Рисунок 1.5 Построение таблицы истинности на основе булева выражения

Предположим, что нам задано булево выражение (рисунок 1.6 а). На первый взгляд кажется, что этому выражению должны соответствовать лишь два выхода с логической 1. Однако если вы внимательно посмотрите на рисунке 1.6 б, то увидите, что булево выражение на самом деле дает в столбце выхода три логических единицы. Следовательно, при анализе булевых выражений требуется особое внимание, чтобы не упустить из виду подобные неожиданности. Необходимо иметь твердую уверенность в том, что учтены все возможные комбинации входов, которые дают логическую единицу в таблице истинности. Булево выражение на рисунке 1.6 а и таблица истинности на рисунке 1.6 б описывают одну и ту же логическую схему.

Рисунок 1.6 Построение таблицы истинности на основе булева выражения

1.3 Упрощение булевых выражений

Рассмотрим булево выражение , приведенное на рисунке 1.7 а. В процессе составления логической схемы для данного булева выражения выясняется, что нам необходимы три элемента И, два инвертора и один элемент ИЛИ с тремя входами. На рисунке 1.7 б изображена схема, реализующая логику булева выражения . На рисунке 1.7, в дана таблица истинности для булева выражения и логической схемы, показанных соответственно на рисунке 1.7 а и б. Вы сразу можете узнать в ней таблицу истинности для логического элемента ИЛИ с двумя входами. Как показано на рисунке 1.7 г, упрощенное булево выражение для элемента ИЛИ с двумя входами есть . Такая схема ИЛИ с двумя входами в простейшей ее форме представлена на рисунке 1.7 д.

Рисунок 1.7 Упрощение булевых выражений

Пример, приведенный на рисунке 1.7, показывает, каким образом мы должны пытаться упростить заданное булево выражение, чтобы получить как можно более простую (а следовательно, и менее дорогую) логическую схему. В данном случае нам просто повезло, и мы догадались, что таблица истинности принадлежала элементу ИЛИ. Однако обычно приходится использовать более общие методы упрощения булевых выражений. Эти методы основаны на приложениях булевой алгебры и построении так называемых карт Карно.

Булева алгебра была развита Джорджем Булем (1815-1864 гг.). Эта алгебра в 30-х годах двадцатого столетия была применена для анализа цифровых логических схем; она является основой всех «хитростей», которые мы будем использовать для упрощения булевых выражений

Карты Карно-весьма практичный метод упрощения булевых выражений, известны и другие широко распространенные методы упрощения , булевых выражений: например, диаграммы Вейча, диаграммы Венна и табличный метод

1.4 Карты Карно

В 1953 г. Морис Карно опубликовал статью о разработанной им системе графического представления и упрощения булевых выражений. Карта Карно показана на рисунке 1.8. Четыре квадрата (1, 2, 3, 4) соответствуют четырем возможным комбинациям A и B в таблице истинности с двумя переменными. При таком изображении квадрат 1 на карте Карно соответствует произведению , квадрат 2-произведению и т. Д.

Рисунок 1.8 Обозначение квадрантов на карте Карно

Предположим теперь, что нам надо составить карту Карно для логической задачи, проиллюстрированной на рисунке 1.7. Исходное булево выражение для удобства еще раз переписано на рисунке 1.9 а. Разместим логические единицы во всех квадратах, которым соответствуют произведения в исходном булевом выражении на рисунке 1.9 а.

Рисунок 1.9 Нанесение единиц на карту Карно

Заполненная таким образом карта Карно теперь готова для построения, и эта процедура демонстрируется на рисунке 1.10. В соответствии с ней соседние единицы объединяются в один контур группами по две, четыре или восемь единиц. Построение контуров продолжается до тех пор, пока все единицы не окажутся внутри контуров. Каждый контур представляет собой новый член упрощенного булева выражения. Заметим, что на рисунке 1.10 у нас получилось только два контура. Это означает, что новое, упрощенное булево выражение будет состоять только из двух членов, связанных функцией ИЛИ.

Рисунок 1.10 Объединение единиц группами в один контур на карте Карно

Теперь упростим булево выражение, принимая во внимание два контура на рисунке 1.10, повторенные на рисунке 1.11. Взяв сначала нижний контур, замечаем, что А здесь встречается в комбинации с B и . В соответствии с правилами булевой алгебры B и дополняют друг друга и их можно опустить. Тогда в нижнем контуре остается один член А. Аналогично этому вертикально расположенный контур содержит A и , которые можно также опустить, оставив только В. Оставшиеся в результате А и В затем объединяются функцией ИЛИ, что приводит к упрощенному булеву выражению А + В= Y.

Рисунок 1.11 Упрощение булевых выражений на основе карты Карно

Процедура упрощения булева выражения сложна лишь на первый взгляд. На самом деле после некоторой тренировки ее легко освоить, выполняя последовательно шесть шагов, указанных ниже:

Начните с булева выражения в дизъюнктивной нормальной форме.

Нанесите единицы на карту Карно.

Объедините соседние единицы контурами, охватывающими два или восемь квадратов.

Проведите упрощения, исключая члены, дополняющие друг друга внутри контура.

Объедините оставшиеся члены (по одному в каждом контуре) функцией ИЛИ.

Запишите полученное упрощенное булево выражение в дизъюнктивной нормальной форме.

1.5 Карты Карно с тремя переменными

Рассмотрим исходное булево выражение , приведенное на рисунке 1.12 а. Карта Карно для случая трех переменных показана на рисунке 1.12 б. Обратите внимание на то, что имеется восемь возможных комбинаций переменных А, В и С, которые представлены восемью квадратами на карте. В них занесены четыре единицы, отображающие каждый из четырех членов исходного булева выражения. Заполненная карта Карно повторена на рисунке 1.12 в, где каждая группа из двух соседних единиц обведена контуром.

Нижний контур содержит B и , вследствие чего B и можно опустить. После этого в составе нижнего контура сохраняются лишь A и , которые дают член . В верхний контур входят C и , поэтому C и опускаются, в результате чего остается только член . Булево выражение в дизъюнктивной нормальной форме получается введением символа операции ИЛИ. Упрощенное булево выражение, записанное на рисунке 1.12 г, имеет вид =Y.

Рисунок 1.12 Упрощение булевых выражений на основе карты Карно

Очевидно, что это упрощенное булево выражение потребует для своей реализации значительно меньше электронных компонентов, чем исходное выражение. Интересно отметить тот факт, что столь непохожее на оригинал упрощенное булево выражение описывается той же самой таблицей истинности, что и исходное булево выражение.

Существенно, чтобы карта Карно была составлена именно так, как показано на рисунке 1.12. Заметьте, что по мере того как вы смещаетесь вниз по левой части карты, на каждом шагу изменяется лишь одна переменная. Сверху слева записано произведение , а строкой ниже (где только заменено на В). Далее при продвижении от к вниз переходит в А. Наконец, смещение вниз от к приводит к замене В на . Если карту Карно составить неправильно, она не будет давать ожидаемого эффекта.

1.6 Карты Карно с четырьмя переменными

Таблица истинности для четырех переменных включает 16 возможных комбинаций. В связи с этим задача упрощения булева выражения с четырьмя переменными кажется сложной, однако применение карты Карно облегчает и эту задачу.

Рассмотрим булево выражение

, записанное на рисунке 1.13 а. Карта Карно с четырьмя переменными, показанная на рисунке 1.13 б, допускает 16 возможных комбинаций А, В, С и D. Эти комбинации представлены соответственно 16 квадратами карты. Нанесем на карту шесть единиц, которые соответствуют шести членам в заданном булевом выражении. Полученная карта Карно вторично изображена на рисунке 1.13 е. Группы из двух и четырех единиц объединены контурами. Нижний контур из двух единиц дает возможность опустить и . После этого в нем остается член (). Далее в верхнем контуре из четырех единиц попарно опускаются и , и , так что в результате этого верхний контур дает член . Наконец, члены и объединяем символом операции ИЛИ. Упрощенное булево выражение в дизъюнктивной нормальной форме имеет вид =Y (рисунок 1.13 г).

Рисунок 1.13 Упрощение булевых выражений на основе карты Карно

Отметим, что для упрощения булевых выражений с двумя, тремя и четырьмя переменными применяются общая процедура и одинаковые правила и чем больше размеры объединяющих контуров, тем больше переменных можно опустить. Чтобы убедиться в этом, достаточно еще раз внимательно сопоставить карты, показанные на рис. 1.111.13.

Задания

1. Для заданной логической (булевой) функции построить таблицу истинности. Проверить результаты путем составления и моделирования цифровой схемы, эквивалентной представленной логической функции.

Таблица 2.1

Согласно номеру варианта, представленному в двоичной системе счисления A₄A₃A₂A₁A₀, используя карту Карно, упростить логическое выражение представленное таблицей истинности Таблица 2.2. Проверить результаты путем составления и моделирования цифровой схемы, эквивалентной полученной логической функции.

Таблица 2.2

Содержание отчета

Отчет по лабораторной работе должен содержать:

1. Титульный лист (Приложение А).

2. Цель лабораторной работы.

3. Основные теоретические сведения.

4. Описание хода выполнения индивидуального задания согласно полученному варианту.

5. Выводы по лабораторной работе

Контрольные вопросы

1. Каковы основные инструменты для работы с элементами символической логики?

2. Как составить таблицу истинности для заданного логического выражения?

3. Назовите и продемонстрируйте основные этапы работы с картой Карно.

4. Размещено на Allbest.ru