Элементарные логические

наоборот, содержащей все буквы) поставлены знаки отрицания. Ранг элементарной конъюнкции — это число входящих в нее аргументов. Дизъюнктивной нормальной формой (ДНФ) БФ называется дизъюнкция конечного множества попарно различных элементарных конъюнкций. ДНФ функции у(х\, . . ., XL), все элементарные конъюнкции которой имеют ранг L, называется совершенной ДНФ этой функции. Любая БФ может быть представлена в совершенной ДНФ, для чего необходимо: выбрать в таблице задания функции все наборы значений аргументов, на которых она обращается в 1; выписать конъюнкции, соответствующие этим наборам значений аргументов (xi вписывается в конъюнкцию без изменения, если его значение в 1-м компоненте набора равно 1, и со знаком отрицания, если его значение в 1-м компоненте набора равно 0) ; все полученные конъюнкции объединить знаком дизъюнкции. Например, совершенная ДНФ функции у, заданная табл. 1.1, запишется так:

тации области определения функции трех переменных (число переменных, равное трем, выбрано лишь из соображений наглядности). Элементам куба поставим в соответствие элементарные конъюнкции различного ранга. На 1.2 вершинам куба сопоставлены конъюнкции третьего ранга, ребрам —• второго ранга, граням — первого ранга. При этом каждый геометрический эквивалент меньшей размерности покрывается соответствующими геометрическими эквивалентами большей размерности. По аналогии говорят, что конъюнкции большего ранга по-

Карно (Karnaugh), которые можно рассматривать как отображение на плоскость вершин L-мерного куба. Использование карт Карно позволяет легко выделять графически элементарные конъюнкции, для которых выполняются правила типа:

Для минимизации БФ по методу Квайна все элементарные конъюнкции в записи ее совершенной ДНФ сравниваются попарно. Если две конъюнкции таковы, что имеют вид axi и axi, то вместо них выписывается единственная конъюнкция a (L— 1)-го ранга. Конъюнкции

L-ro ранга, для которых произошло склеивание, отмечаются. После построения всех конъюнкций (L — 1)-го ранга их вновь сравнивают попарно, в результате формируются конъюнкции (L — 2) -го ранга и отмечаются склеивающиеся конъюнкции (L — 1)-го ранга. Рассмотренные действия заканчиваются, когда на очередном этапе полученные конъюнкции /-го ранга уже не склеиваются между собой. Все неотмеченные элементарные конъюнкции называются простыми импликантами (им соответствуют все максимальные интервалы БФ). Пусть задана БФ

в которой пять элементарных конъюнкций третьего ранга. Образуем конъюнкции второго ранга: xtx2, xtx3, xtx3, XiXz, х2х3. Все элементарные конъюнкции третьего ранга оказались отмеченными. Далее находим конъюнкцию первого ранга: Xi. Из неотмеченных конъюнкций х?х3 и х\ формируется сокращенная ДНФ: (/=XiV*2*3.

Для нахождения минимального покрытия максимальными интервалами необходимо произвести выбрасывание некоторых простых импликант. С этой целью строится так называемая импликантная матрица, число столбцов которой совпадает с числом элементарных конъюнкций в записи совершенной ДНФ минимизируемой БФ, а число строк равно числу полученных простых импликант. Каждому столбцу (строке) приписывается соответствующая элементарная конъюнкция из совершенной ДНФ (простая импликанта) минимизируемой функции. Если k-я простая импликанта является частью р-й элементарной конъюнкции, то на пересечении й-й строки и р-го столбца ставится метка. Искомое покрытие представляет собой множество интервалов, соответствующих тем строкам импликантной матрицы, которые покрывают метками все ее столбцы. В приведенном ранее примере минимальное покрытие включает обе элементарные конъюнкции Х2Х3 и х\ и ДНФ y= является минимальной.

Мак-Класки предложил модернизацию первой части метода Квай-на, позволяющую существенно сократить число попарных сравнений различных элементарных конъюнкций. Согласно методу Мак-Класки элементарные конъюнкции записываются в виде L-разрядных троичных

С помощью метода Квайна — Мак-Класки можно также минимизировать частичные БФ. Для этих целей находится сокращенная ДНФ функции, доопределенной единичными значениями на безразличных наборах значений аргументов. Далее импликантная матрица строится, как и раньше, но ее столбцам приписываются лишь элементарные конъюнкции, соответствующие наборам значений аргументов, на которых исходная БФ определена и равна 1. Все остальные процедуры синтеза сохраняются без изменений.

Аналогичным образом любая ДНФ системы 6 булевых функций г/ь . . ., ун входных переменных х\, . . ., XL может быть реализована двухуровневой матричной схемой, на первом уровне которой образуются различные элементарные конъюнкции, а на втором — дизъюнкции у\, . . ., у к соответствующих конъюнкций. В итоге построение схем с матричной структурой сводится к определению точек пересечения

1. Матрица MI разделена на две части: M'i и М"ь Матрица M'i расположена над матрицей М2, а М", — под ней. Это позволяет при необходимости разрезать промежуточные шины в матрице М2 и реализовать на верхней и нижней частях одной и той же промежуточной шины различные элементарные конъюнкции входных переменных.

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

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

3. Какие существуют элементарные логические операции, что они собой представляют?

мени деблокировки В2 и некоторые элементарные логические органы ИЛИ1, ИЛИ2, И1, И2, НЕ1 и НЕ2; однако их взаимодействие оригинально. Ниже сигналы на выходе обозначены: ПО — x,Bl—Xi,B2 — xz, ИЛИ2 — х3 и блокировки в целом — у. При этом работа схемы в символах алгебры логики (см. гл. 1) представляется в_виде (см., например, [11]) г/ = = (x+y)Xi и Х3 = х+у+х2.х3.

Простейшая схема ДТЛ, реализующая функцию И — НЕ, представлена на 6.4. Схема содержит т входных диодов, которые вместе с резистором R\ реализуют функцию И. Диоды Дсм1 и ДСм2 предназначены для увеличения порога запирания схемы, а следовательно, для увеличения ее помехоустойчивости. Смещающие диоды включают для того, чтобы падение напряжения на входных диодах не влияло на переключение транзистора. Простой инвертор выполняет логическую функцию НЕ и усиление сигнала. Необходимым элементом схемы является резистор Rz, который в закрытом состоянии инвертора задает ток через смещающие диоды. При подключении к резистору Rz отдельного источника питания увеличиваются быстродействие и порог запирания схемы. Поскольку элементарные логические операции И (ИЛИ) и НЕ осуществляются различными элементами схемы ДТЛ, легко увеличить число входов путем добавления входных диодов. В этом одно из преимуществ схем ДТЛ по сравнению со схемами ТЛНС, РТЛ и РЕТЛ.

В табл. 2-1 представлены наиболее характерные элементарные логические функции одного и двух аргументов, чаще всего реализуемые на магнитных импульсных элементах.

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

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

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

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

Любая, сколь угодно сложная логическая операция может быть разложена на элементарные логические функции «НЕ», «ИЛИ» и «И». Обозначим через Х\, X2 и Х3 входные величины, а через У — выходную величину и рассмотрим подробно элементарные функции для трех входов.