Постановка задачи минимизации БФ

Минимизация БФ

Реализация булевых функций

Для реализации двоичных функций необходимо адекватно представить дискретные (бинарные) значения с помощью физических величин (например: токов, напряжений). Распространено представление логических значений бинарных величин уровнями напряжений. Например:

· высокое напряжение ­ – логическая единица;

· низкое напряжение – логический ноль.

Рассмотрим реализации БФ в виде релейных моделей рис.1.7.1. Здесь ЭМ – электромагнит реле, который при подаче на его вход высокого напряжения (единицы) вызывает замыкание ключа.

Элемент НЕ при подаче на его вход 1 вырабатывает на выходе 0, а при подаче нуля – 1.

Элемент 3ИЛИ-НЕ вырабатывает на выходе 1, если только на все его входы поступают нули. При подаче хотя бы одной единицы на его выходе выдаётся 0.

Элемент 3И-не вырабатывает на выходе 0, если на все его входы подаются единицы, иначе на выходе 1.

Принятые изображения этих элементов показаны на рис. 1.7.2. Внутри каждого элемента (обязательно!) проставляется вид БФ. Инверсия показывается кружочком.

Элементы БФ могут иметь разнообразный вид, быть составными, но принцип должен быть понятен.

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

31+3=34 час

СДНФ используются в основном для составления исходных БФ, но с точки зрения затрат по количеству вентилей эти формы не идеальны. Минимизация (упрощение) БФ производится на основании свойств БФ.

Рассмотрим в качестве иллюстрации сказанного пример БФ:

.

Реализация f_СДНФ показана на рис.1.8.1.а.

Выполним минимизацию БФ

.

В результате склеивания минимизированная БФ не имеет ни одного логического элемента (!) и, соответственно, проще в реализации. Схема f_min представлена на рис.1.8.1.б.

Применение свойств БФ к их выражениям для минимизации довольно трудоёмко для функций имеющих несколько входных переменных. Распространена минимизация с использованием графического представление процесса минимизации. Для этого применяются диаграммы Вейча (ДВ) и карты Карно (КК), которые в принципе представляют собой одно и то же, но КК более формализованы и их использование позволяет избежать множества ошибок при минимизации.

При минимизации с помощью ДВ и КК скрытым образом используется такое свойство БФ как склеивание:

.

Исходными данными для ДВ и КК являются таблицы истинности, описывающие БФ.

Дата добавления: 2014-01-07