В заданном базисе логических элементов

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

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

Таблица, содержащая все возможные комбинации входных переменных и соответствующие им значения выходных переменных, называется таблицей истинности или комбинационной таблицей. Для устройства, имеющего п входов и m выходов, таблица истинности содержит 2 ⁿ строк и n + m столбцов.

Зависимость выходных переменных F (X), выраженная через совокупность входных переменных Х _{( n -1)}…. Х ₀ с помощью операций алгебры логики, носит название функции алгебры логики (ФАЛ).

Логическое произведение входных переменных произвольной строки таблицы истинности, для которой ФАЛ равна единице, называют конституентой единицы. Так как выходной сигнал комбинационного логического устройства может принимать только два значения («лог. 0» или «лог. 1»), то задать алгоритм устройства можно перечислением конституент единицы.

Рассмотрим составление таблицы истинности на при­ме­­ре полностью определенной ФАЛ трех переменных, при­ни­мающей значения «лог. 1» в случае, если хотя бы две вхо­дные переменные равны «лог. 1». Данная таблица со­держит 8 (+1 для обозначения переменных) строк и 4 сто­л­бца, в трех из которых записаны все возможные ком­бина­ции входных кодов X 2 X 1 X 0, а в четвертом - значения выходного сигнала F (Х). Комбинационная таблица X 2 X 1 X 0 F (Х)                                                                   Данная полностью определенная функция определя­ется четырьмя конституентами единицы. Эти конституенты можно перечислить в любом коде, например в двоичном (011, 101, 110, 111) или в десятичном (3, 5, 6, 7) кодах. При этом заданный список конституент единицы фактически определяет алгоритм работы устройства. Можно также задать полностью определенную ФАЛ перечислением строк, в которых произведение входных кодов равно нулю (перечислением конституент нуля).

Рассмотрим использование таблицы истинности для получения ФАЛ логического устройства.

2.3.2. Получение совершенной дизъюнктивной (CДНФ) и совершенной конъ­юнктивной (СКНФ) нормальных форм записи ФАЛ. Совершенной дизъюнктивной нормальной формой записи ФАЛ называют логическую сумму (операция ИЛИ) логических произведений (операция И) входных переменных, в каждое из которых аргумент или его отрицание входят один раз. СДНФ легко записывается на основе таблицы истинности с использованием следующего алгоритма:

· для каждого набора переменных, на котором ФАЛ равна единице (для каждой конституенты единицы), записывают логическое произведение входных переменных, причем переменные, равные нулю, записывают с инверсией;

· логически суммируют полученные произведения.

Пример 2.3.1. Записать СДНФ для ФАЛ, заданной таблицей истинности,

Фактически СДНФ это логическая сумма конституент единицы, заданной ФАЛ.

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

· для каждого набора переменных, на котором ФАЛ равна нулю (для каждой конституенты нуля), записывают логическую сумму входных переменных, причем переменные, равные единице, записывают с инверсией;

· логически перемножают полученные суммы.

Пример 2.3.2. Записать СКНФ для ФАЛ, заданной таблицей истинности на предыдущей странице,

2.3.3. Минимизация ФАЛ. При увеличении числа переменных, ФАЛ в виде CДНФ или СКНФ достаточно громоздки и их практическая реализация сопряжена со значительными затратами материальных ресурсов. Поэтому, на практике, ФАЛ минимизируют. Целью минимизации является сокращение числа членов исходного выражения. Существует большое число различных методов минимизации, но все они, фактически, базируются на использовании основных теорем алгебры логики:

При большом числе переменных для минимизации ФАЛ используется специальное программное обеспечение. При небольшом числе переменных (не более 5) хорошие результаты дают табличные методы, не требующие привлечения ЭВМ.

Рассмотрим один из этих методов – метод карт Вейча. Данный метод предполагает использование специальных прямоугольных таблиц, построенных на основе таблиц истинности. Для описания этого метода введем понятие соседних кодов.

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

На рис. 2.3.1 приведены карты Вейча для двух, трех и четырех переменных.

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

Рис. 2.3.1. Карты Вейча для функций двух, трех и четырех переменных а) б) в) В качестве примера рассмотрим минимизацию ФАЛ, описанной выше в таблице истинности. Заполненная карта Вейча, соответствующая данной таблице, приведена на рис. 2.3.2. При минимизации ФАЛ можно использовать либо ее единичные, либо нулевые значения. При объединении единичных значений ФАЛ получают выражение для самой функции, а при объединении нулевых значении – выражение для функции, инверсной исходной. Минимизация ФАЛ выполняется по следующему алгоритму: · на карте Вейча ФАЛ выделяют прямоугольные области, объединяющие клетки с выбранным значением функции «лог 1» или «лог. 0». Каждая область должна содержать 2 ^k клеток, где k - целое число (0, 1, 2, 4, 8, …). Выделенные области могут пересекаться, т. е. одна клетка может входить в несколько различных областей; · каждая из выделенных областей описывается произведением переменных, которые для этой области остаются неизменными. Каждое произведение должно содержать n – k переменных;

· из полученного множества выбирают минимальное число максимально больших областей, включающих все клетки с выбранным значением ФАЛ;

· логически суммируют выбранные произведения.

Полученное выражение является минимальной дизъюнктивной ФАЛ.

Рис. 2.3.2. Карта Вейча для заданной функции

Рис. 2.3.3. Выделенные области карты Вейча для единичных значений ФАЛ

Воспользуемся приведенной методикой для минимизации вышеприведенной фун­кции. Произведем объединение областей с единичными значениями функции. Имеем три области (см. рис. 2.3.3). Для области I неизменными остаются переменные X 1 и X 0. Для области II - постоянны переменные Х 2 и Х0. Для области III – неизменны Х 2 и Х 1. Суммируя произведения неизменных переменных для каждой из выделенных областей, получим минимальную дизъюнктивную форму искомой ФАЛ в виде:

В правильности полученной ФАЛ можно убедиться, подставляя в неё различные комбинации входных переменных. Например, для входного кода 001 имеем ¸ что соответствует приведенной таблице истинности.

Рис. 2.3.4. Выделенные области карты Вейча для нулевых значений ФАЛ

Объединяя клетки, содержащие нулевые значения функции, так же получим три области. Это область I, для которой неизменны переменные и , область II для которой неизменны и и область III с неизменными и . Суммируя произведения переменных для каждой области, получим ФАЛ, инверсную заданной:

.

Подставив, для проверки, в полученную ФАЛ входной код 001 найдем:

или F (X) = 0.

Рис. 2.3.5. Объёмное представление Карты Вейча функции 3-х переменных Интересно отметить, что в рассмотренном примере область II была получена объединением клеток, расположенных на противоположных краях таблицы. Это следует из основного правила построения таблицы. Коды рядом расположенных клеток должны быть соседними, т. е. отличаться только в одном разряде. Нижней правой клетке рассматриваемой таблицы соответствует код 000, а левой нижней клетке – код 010, т. е. они соседние. Поэтому реально рассматриваемая таблица является объемной фигурой и представляет собой поверхность цилиндра (рис. 2.3.5).То же самое можно сказать и о таблице 4-х переменных. Здесь соседним кодам попарно соответствуют как нижняя и верхняя строки таблицы, так и правый и левый крайние ее столбцы. Поэтому таблица ФАЛ 4-х переменных как бы размещена на поверхности тора. На рис. 2.3.6 показаны возможные варианты объединения в области клеток карты Вейча 4-х переменных. Вполне очевидно, что распределение переменных по клеткам на плоском варианте карты Вейча может не совпадать с приведенным выше. Описание Описание: Описание Рис. 2.3.6. Возможные варианты объединения ячеек в области Например, клетки, соответствующие переменной Х 0, можно поменять местами с клетками, соответствующим переменной Х 3. Но все­гда дол­жен выполняться основной принцип заполнения карты – рядом расположенные клетки (по горизонтали и вертикали) должны соответствовать соседним кодам. 2.3.4. Приведение ФАЛ к заданному базису логических элементов. Для реа­­лизации ФАЛ произвольной сложности достаточно иметь элементы, выполняющие три основные логические операции. Это операция И (дизъюнкция), ИЛИ (конъюнкция) и НЕ (отрицание). Такая совокупность логических элементов называется фун­кциональ­но полной совокупностью логических элементов. Используя принцип двойственности, согласно которому логические операции И и ИЛИ могут быть взаимно преобразованы, функционально полную систему логических элементов можно уменьшить до двух элементов. Это совокупности элементов И и НЕ или ИЛИ и НЕ. На практике, нашли применение элементы, которые совмещают две функции. Это элементы И-НЕ и ИЛИ-НЕ. Согласно вышесказанному, один такой элемент является функционально полной системой логических элементов и на его основе можно построить логическое устройство произвольной сложности.

Приведение ФАЛ к заданному базису логических элементов означает приведение его к заданному типу элементов (И-НЕ или ИЛИ-НЕ), причем число входов этих элементов так же должно быть заданным.

Таким образом, проблема приведения ФАЛ к заданному базису логических элементов распадается на две самостоятельные задачи:

· приведения ФАЛ к заданному типу логических элементов (операций);

· приведение числа входов элемента к заданному.

2.3.5. Приведение ФАЛ к заданному типу логических элементов. Для удобства практического использования операции И-НЕ и ИЛИ-НЕ принято изображать специальными символами:

· операция И-НЕ - операция штрих Шеффера;

· операция ИЛИ-НЕ - операция стрелка Пирса.

Алгоритм приведения базируется на использовании двух теорем алгебры логики:

· , причем дважды инвертировать можно как всё выражение, так и любую его часть;

· - теоремы де-Моргана, являющиеся формальным представлением принципа двойственности.

Проиллюстрируем сказанное примерами. Пусть задана ФАЛ

Пример 2.3.3. Привести ФАЛ к базису элементов И-НЕ.

В результате имеем 3 элемента 2И-НЕ и один элемент 3И-НЕ.

Пример 2.3.4. Привести ФАЛ к базису элементов ИЛИ-НЕ.

В результате имеем 3 элемента 2ИЛИ-НЕ, один элемент 3ИЛИ-НЕ и один инвертор, который так же можно выполнить на элементе ИЛИ-НЕ.

2.3.6. Приведение к заданному числу входов логического элемента. Здесь возможно два случая:

· число реальных входов логического элемента больше требуемого ФАЛ;

· число реальных входов логического элемента меньше требуемого ФАЛ.

В первом случае используются следующие теоремы:

;

.

Пример 2.3.5. Задана ФАЛ . Привести к виду логических элементов с тремя входами (3И-НЕ)

Пример 2.3.6. Задана ФАЛ .

Привести к виду логических элементов с тремя входами (3ИЛИ-НЕ)

Во втором случае можно воспользоваться теоремой , применяя ее к части выражения.

Пример 2.3.7. Преобразовать ФАЛ трехвходового элемента 3И-НЕ

к базису элементов 2И-НЕ

Пример 2.3.8. Преобразовать ФАЛ четырехвходового элемента 4И-НЕ

к базису элементов 2И-НЕ.

,

или .

Последнее преобразование менее предпочтительно, так как при реализации приводит к большим задержкам получения результата.

Аналогично преобразуется число входов и элементов ИЛИ-НЕ.

Пример 2.3.9.

2.3.7. Вычерчивание схемы устройства по его ФАЛ. Графические эквиваленты типовых элементов ФАЛ приведены в таблице 2.3.1.