В булевой алгебре и в дальнейшем в логических выражениях принято обозначать функции прописными буквами латинского алфавита, а аргументы функций - строчными (малыми) буквами того же алфавита.
1.3.3. Способы и формы задания логических функций
При описании логических устройств оказывается, что способ задания (определения) логических функций и форма их представления существенно влияют на трудность достижения конечного результата. В зависимости от поставленной цели способы задания и формы представления функций могут быть различными. Например, при построении логических устройств на программируемых постоянных запоминающих устройствах (ППЗУ) алгебраические формы логических функций нежелательны и не целесообразны. Однако при построении устройств на микросхемах малой степени интеграции, на ИМС логических элементов, требуются минимальные алгебраические формы логических функций, так как в противном случае не обеспечить минимальные аппаратурные затраты. Таким образом, выбор способа задания зависит от поставленной цели описания устройств.
Различают табличный, матричный, графический и аналитический способы задания.
При табличном задании используются так называемые «таблицы истинности» логических функций, в которых указываются значения функций на всём множестве комбинаций их аргументов. Таким образом число столбцов в таблице истинности определяется числом аргументов и числом функций, а количество строк - по формуле (1.1). Таблицы истинности используются для общего ознакомления с работой комбинационных устройств, когда число входов (аргументов функций) и число выходов (число функций) не превышает 4-х. Таблицы истинности становятся громоздкими при большем числе аргументов, а поэтому они мало пригодны для анализа. По таблицам истинности достаточно просто отыскиваются алгебраические формы функций в ДСНФ либо в КСНФ, а для поиска минимальных алгебраических форм они непригодны.
Матричный способ задания (или задание функций с помощью булевых матриц) основан на графическом отображении всего множества комбинаций аргументов функции на «плоскости» (в двумерном пространстве). Понятие «булевы матрицы» было введено А.Д. Закревским, им же был предложен визуально-матричный метод минимизации логических функций [3]. В зарубежной литературе этот способ задания и минимизации логических функций известен под названием «метода задания и минимизации с помощью карт Карно». (Не следует путать понятие «матриц», используемое в математике, с понятием «булевы матрицы»). Наряду с понятием булева матрица в дальнейшем будет употребляться понятие карта Карно, как понятия синонимы.
Булева матрица представляет собой прямоугольник с соотношением сторон 1:2 (при нечётном числе аргументов функции) или квадрат (при чётном числе аргументов), разделённые на элементарные квадраты (клетки). Число клеток в матрице всегда кратно степени двойки и определяется формулой (1.1). Таким образом, количество элементарных квадратов равно полному множеству комбинаций, составленных из аргументов функции. Сверху справа и слева сбоку матрицы прямоугольными скобками либо сплошной прямой линией размечаются области единичных значений аргументов (рис.1.2). Причём эти скобки помечают идентификаторами аргументов, которые размещают под скобкой либо справа (внизу) скобок. Условно считают, что область, ограниченная скобкой, является областью единичных значений аргумента, а вне этой области аргумент имеет нулевое значение. Таким образом, помеченная карта Карно, как бы «кодируется» комбинациями аргументов. При этом каждой клетке будет соответствовать одна вполне конкретная комбинация аргументов функции. Сама карта помечается идентификатором функции внизу либо справа.
Чтобы задать картой какую-либо функцию, необходимо поставить в соответствующие клетки значения этой функции (0 или 1, либо ~).
Так, на рис.1.2 приведены карты Карно для функций 4-х, 5-ти и 6-ти аргументов.
В частности, функции X и Y полностью определены, а функция Z недоопределена, так как наряду с фиксированными значениями 1 и 0 в клетках показаны «условные» значения, помеченные символом ~ (типографский символ - тильда). Условные значения логических функций используют в тех случаях, когда конкретные значения (0 либо 1) нельзя определить заранее. Такие случаи возникают, например, при синтезе устройств по неполностью заданным условиям, либо когда комбинации аргументов, соответствующих клеткам с символом ~ не могут возникнуть по каким-либо причинам. В процессе отыскания минимальных логических выражений недоопределённых функций, эти условные значения доопределяют значениями 1 либо 0, стараясь получить наиболее простые алгебраические выражения.
В принципе матричная форма задания логических функций более удобна для поиска минимальных алгебраических форм функций вплоть до 10 (и более) аргументов. Последовательность построения карты Карно для функций от большого числа аргументов можно уяснить, сопоставляя рис.1.2,а с рисунками 1.2,б и в.
Графический способ задания логических функций основан на использовании n-мерных кубов. Размерность куба определяется числом n аргументов функции, например, функцию от трёх аргументов можно задать 3-мерным кубом, каждая вершина которого соответствует определённой комбинации аргументов. Чтобы задать функцию с помощью 3-мерного куба, вершины куба соответствующим образом помечают. Этот способ не нашел широкого применения, и мы им пользоваться не будем.
Аналитический способ задания функций используется наиболее широко для отыскания функциональных схем синтезируемых устройств. Благодаря условным графическим обозначениям (УГО) логических элементов, существует возможность непосредственно от алгебраического выражения адекватно перейти к функциональной схеме и, наоборот, по функциональной схеме получить алгебраическое выражение функции, описывающей выходной сигнал устройства. Кроме того, пользуясь законами и следствиями алгебры логики можно выполнять эквивалентные преобразования логических выражений и, тем самым, получать новые варианты функциональных схем.
В булевой алгебре различают несколько видов алгебраических форм функций, в частности, в табл.1.3 были приведены две формы ДСНФ и КСНФ. Первая получается, когда функция определяется условиями истинности (по 1), а вторая - когда функция определяется по «нулям».
Например, функция Х, заданная картой рис.1.2,а, будет иметь следующие совершенные формы:
ДСНФ:
(1.3)
КСНФ:
(1.4)
Как видно по рис.1.2,а, так и из выражений (1.3) и (1.4), следует, что функция принимает значение «1», если нечётное число аргументов принимают значение лог.1, в противном же случае она принимает значение «0». Такие функции реализуются схемами «контроля чётности/нечётности» или логическими элементами «сумма по mod2». Если использовать условное обозначение суммы по mod2 (функция неравнозначности V5 в табл.1.3), то можно записать
X = a Å b Å c Å d. (1.5)
Это выражение более короткое и оно эквивалентно выражению (1.3). Обратите внимание (рис.1.2,а), функции сумма по mod2 и её инверсии соответствует «шахматный узор» на карте Карно. Этим можно будет пользоваться в дальнейшем при поиске иных алгебраических форм логических функций. Кстати, эти функции не имеют нормальных минимальных дизъюнктивных и конъюнктивных форм - МДНФ и МКНФ.
Рассмотрим часто применяемые ИМС логических элементов, при этом будем использовать различные формы описания логических функций, реализуемых этими элементами.
1.3.4. Логические элементы НЕ
Это - наиболее простые элементы, имеющие один вход и один выход. Такие элементы описываются логической функцией отрицания, инверсии и называются просто функциями НЕ. На рис.1.3 приведены УГО элементов НЕ, рекомендуемые ГОСТом. Как видно, указатель инверсии допускается ставить либо по выходу, либо по входу логического элемента. Согласно ГОСТ можно не ставить метку основной функции «1» в основном поле УГО.
Алгебраическое выражение функции инверсии имеет вид
Х =
и читается «не а». Выходной сигнал элемента НЕ принимает всегда противоположное значение по отношению к значениям входного сигнала. Есть несколько разновидностей ИМС логических элементов, отличающихся способом организации выхода. Например, в ИМС серии К155 есть микросхемы К155ЛН1, содержащих в своём составе 4 логических элемента НЕ со стандартной нагрузочной способностью. Есть элементы НЕ с повышенной нагрузочной способностью, однако все они описываются одним и тем же логическим выражением.
Логические элементы «повторители» так же имеют один вход и один выход, но выходной сигнал повторяет значение входного сигнала. Такие элементы используются для «развязки» выходов логических элементов и для повышения их нагрузочной способности.
1.3.5. Логические элементы И
Эти элементы реализуют функцию логического умножения (конъюнкции). Функции являются как минимум двухместными либо многоместными и описываются следующими логическими выражениями:
X = a&b = a Ù b = a·b = ab. (1.6)
Символы конъюнкции & и Ù допускается заменять точкой, либо совсем не ставить. Выходной сигнал элемента И принимает значение лог.1 только в том случае, если все входные сигналы принимают значение лог.1. На рис.1.4 приведены условные графические обозначения и карты Карно для двухвходового (рис.1.4,а и б) и трёхвходового (рис.1.4,в и г) логического элемента И.
Рис.1.4. Условные графические обозначения элементов И: двухвходового (а),
трёхвходового (в), карты Карно логических функций 2И (б) и 3И (г)
Как видно из приведённых булевых матриц, конъюнкция равна лог.1 только в единственном случае, когда все аргументы - и первый, и второй, и третий и т.д. - одновременно принимают значение лог.1. Поэтому такие элементы называют схемами совпадения, реже встречается название «конъюнкторы», а описывающие их функции, иногда - функциями И. В сериях ИМС выпускаются различные логические элементы И, например, микросхема К155ЛИ1 содержит 4 элемента 2И (двухвходовых). Отличие заключается в разном числе входов у различных элементов.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
