Логические элементы, реализующие элементарные булевы функции

ЛОГИЧЕСКИЕ СХЕМЫ

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

Устройства, реализующие элементарные булевы функции, называют логическими элементами. Их входы соответствуют булевым переменным, а выход - реализуемой функции.

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

Таблица 11.1

Функция	Нормальная форма	Контактная схема	Графическое изображение элемента	Название элемента
Отрицание				Инвертор
Конъюнкция				Совпадение
Дизъюнкция				Разделение
Импликация				Разделение с запретом
Эквиваленция				Равнозначность
Отрицание импликации				Совпадение с запретом
Сумма по модулю 2				Неравнозначность
Штрих Шеффера				Разделение с двумя запретами
Стрелка Пирса				Совпадение с двумя запретами

11.2 Логические схемы. Подобно суперпозиции функций логические схемы образуются суперпозицией элементов посредством объединения их внешних узлов (полюсов). При этом множество всех узлов схемы разбивается на входные, выходные и внутренние узлы. Например, на рис. 11.1, а показана схема, реализующая функцию,которая имеет три входных, один выходной и три внутренних узла. Обычно для упрощения узлы на схемах не изображаются и во избежание излишних пересечений входы рассредоточиваются с указанием связанных с ними переменных (рис.11.1, б).

Рис.11.1 – Примеры логических схем

Корректно построенные схемы должны удовлетворять следующим условиям:

1) не допускать замкнутых контуров, которые могут привести к неоднозначности сигналов на входах элементов;

2) любой вход элемента должен быть связан только с одним входом схемы или выходом другого элемента;

3) выходы элементов, не являющиеся выходами схемы и не связанные со входами других элементов, считаются лишними и исключаются из схемы.

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

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

.

Её реализация в системе базисных элементов {НЕ, И, ИЛИ} показана на рис. 11.2, а.

Если в качестве базиса приняты отрицание и импликация, то функция преобразуется по формулам:

;;;;

;.

Так, для рассматриваемого примера имеем:

Соответствующая логическая схема в базисе {НЕ, →} изображена на рис. 11.2, б. Аналогично реализуются схемы и в других базисах. Как правило, в практике используются неминимальные базисы, так как минимальные базисы не всегда обеспечивают наиболее экономичную реализацию булевых функций.

Рис. 11.2 – Реализация в различных базисах.

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

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

Задача упрощения аналитических выражений решается в конкретном базисе с помощью тождественных преобразований. Чаще всего эту задачу связывают с базисом, состоящим из отрицания, дизъюнкции и конъюнкции, который будем называть булевым базисом. После того как формула выражена через основные операции, она упрощается на основании тождеств булевой алгебры, приведённых в (10.1).

Например, функция из (3) упрощается следующим образом:

Соответствующая логическая схема показана на рис. 11.2, в.

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

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

Формула, представленная в дизъюнктивной нормальной форме, упрощается многократным применением операции склеивания и операций поглощения и (дуальные тождества для конъюнктивной нормальной формы имеют вид:; и). Здесь под a и b можно понимать любую формулу булевой алгебры. В результате приходим к такому аналитическому выражению, когда дальнейшие преобразования оказываются уже невозможными, т.е. получаем тупиковую форму.

Среди тупиковых форм находится и минимальная дизъюнктивная форма, причём она может быть неединственной. Чтобы убедиться в том, что данная форма является минимальной, необходимо найти все тупиковые формы и сравнить их по числу входящих в них букв.

Пусть, например, функция заданна в совершенно нормальной дизъюнктивной форме:

.

Группируя члены и применяя операцию склеивания, имеем

.

При другом способе группировки получим

.

Обе тупиковые формы не являются минимальными. Чтобы получить минимальную форму, нужно догадаться повторить в исходной формуле один член (это всегда можно сделать, так как). В первом случае таким членом может быть.

Тогда.

Добавив член, получим:

.

Перебрав все возможные варианты, можно убедиться, что две последние формы являются минимальными.

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

11.5 Карты Карно. В другом методе графического отображения булевых функций используются карты Карно, которые представляют собой специально организованные таблицы соответствия. Столбцы и строки таблицы соответствуют всевозможным наборам значений не более двух переменных, причём эти наборы расположены в таком порядке, что каждый последующий отличается от предыдущего значения только одной из переменных. Благодаря этому и соседние клетки таблицы по горизонтали и вертикали отличаются значением только одной переменной. Клетки, расположенные по краям таблицы, также считаются соседними и обладают этим свойством. На рис. 11.3 показаны карты Карно для двух, трёх и четырёх переменных.

Рис. 11.3– Карты Карно

Как и в обычных таблицах соответствия, клетки наборов, на которых функция принимает значение 1, заполняется единицами (нули обычно не вписывают, им соответствуют пустые клетки).

а) б)

Рис. 11.4- Представление функции на карте Карно

Например, на рис. 11.4, а показана карта Карно для функции

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

Считывание минитермов с карты Карно осуществляется по простому правилу. Клетки, образующие s-куб, дают минитерм -го ранга, в который входят те переменные, которые сохраняют одинаковые значения на этом s-кубе, причём значениям 1 соответствуют сами переменные, а значениям 0 – их отрицание. Переменные, которые не сохраняют свои значения на s-кубе, в минитерме отсутствуют. Различные способы считывания приводят к различным представлениям функции в дизъюнктивной нормальной форме (рис. 11.5).

Рис. 11.5.