Булева матрица представляет собой прямоугольник с соотношением сторон 1:2 (при нечётном числе аргументов функции) или квадрат (при чётном числе аргументов), разделённые на элементарные квадраты (клетки). Число клеток в матрице всегда кратно степени двойки и определяется формулой (1.1). Таким образом, количество элементарных квадратов равно полному множеству комбинаций, составленных из аргументов функции. Сверху справа и слева сбоку матрицы прямоугольными скобками либо сплошной прямой линией размечаются области единичных значений аргументов (рис.1.2). Причём эти скобки помечают идентификаторами аргументов, которые размещают под скобкой либо справа (внизу) скобок. Условно считают, что область, ограниченная скобкой, является областью единичных значений аргумента, а вне этой области аргумент имеет нулевое значение. Таким образом, помеченная карта Карно, как бы «кодируется» комбинациями аргументов. При этом каждой клетке будет соответствовать одна вполне конкретная комбинация аргументов функции. Сама карта помечается идентификатором функции внизу либо справа.
Чтобы задать картой какую-либо функцию, необходимо поставить в соответствующие клетки значения этой функции (0 или 1, либо ~).
В частности, функции 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 приведены УГО элементов НЕ, рекомендуемые ГОСТом. Как видно, указатель инверсии допускается ставить либо по выходу, либо по входу логического элемента. Согласно ГОСТ можно не ставить метку основной функции «1» в основном поле УГО.
Алгебраическое выражение функции инверсии имеет вид
Х =
и читается «не а». Выходной сигнал элемента НЕ принимает всегда противоположное значение по отношению к значениям входного сигнала. Есть несколько разновидностей ИМС логических элементов, отличающихся способом организации выхода. Например, в ИМС серии К155 есть микросхемы К155ЛН1, содержащих в своём составе 4 логических элемента НЕ со стандартной нагрузочной способностью. Есть элементы НЕ с повышенной нагрузочной способностью, однако все они описываются одним и тем же логическим выражением.
Логические элементы «повторители» так же имеют один вход и один выход, но выходной сигнал повторяет значение входного сигнала. Такие элементы используются для «развязки» выходов логических элементов и для повышения их нагрузочной способности.
Эти элементы реализуют функцию логического умножения (конъюнкции). Функции являются как минимум двухместными либо многоместными и описываются следующими логическими выражениями:
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.4,б и рис.1.4,г матрицами иллюстрируются правила логического умножения, а показанные УГО соответствуют соглашениям положительной логики.
ны два варианта построения логического элемента И с шестью входами (6И) на двухвходовых элементах И (2И).
Все приведённые на рис.1.5 схемы логически эквивалентны и, в свою очередь, они эквивалентны условному графическому обозначению 6-тивходового логического элемента И (рис.1.5,в). Вместе с тем, схемы описываются различными по форме записи логическими выражениями:
X = ((((a·b)·c)·d)·k)·m ― схема рис. 1.5,а; (1.7)
Y = ((ab)·(cd))·(km) ― схема рис. 1.5,б; (1.8)
а условному обозначению элемента 6И соответствует следующее выражение:
Z = abcdkm. (1.9)
Хотя в соответствии с упомянутыми законами булевой алгебры от перемены мест сомножителей логическое произведение не меняется и скобки в выражениях логического произведения можно не ставить, тем не менее, выражения (1.7), (1.8) и (1.9) несут информацию о способах построения схем. Таким образом, указанные выражения можно считать «логико-математическими моделями» приведённых схем и в том числе УГО элемента 6И.
Следует заметить, что при описании логических комбинационных устройств с помощью булевых выражений, как правило, абстрагируются от фактора времени. Такое описание соответствует описанию устройств в статике - при установившихся значениях входных сигналов (и переменных). Считается, что изменение входных и выходных сигналов происходят мгновенно, аналогично меняются значения аргументов и значения самих логических функций. В то же самое время реальные элементы имеют конечное время перехода из одного состояния в другое или, как принято говорить, обладают конечным (не равным нулю) временем распространения сигналов от входов к выходу элемента либо устройства. С учётом сказанного, следует отдать предпочтение схеме рис.1.5,б, в которой время распространения сигналов от входов, помеченных аргументами функций, к выходу схемы в среднем меньше. В источнике [5] содержатся сведения о временных логических функциях, которые можно применять для описания схем с временными задержками.
Логическими элементами ИЛИ реализуется логическая сумма нескольких двоичных сигналов (и входных переменных). Функция, описывающая такие элементы, называется дизъюнкцией или функцией логического сложения. На рис.1.6 приведены условные обозначения (УГО) элементов ИЛИ и карты Карно описывающих их функций.
Алгебраическое выражение логической суммы двух переменных a и b записывается следующим образом
X = a Ú b = a + b. (1.10)
В булевой алгебре для обозначения дизъюнкции используется символ Ú. В технических же её приложениях обычно применяется знак + (арифметического сложения), но только тогда, когда это не приводит к некорректности при записи формул и логических выражений. (Преимущественно этот знак будет использоваться в дальнейшем для обозначения дизъюнкции.)
Как видно из карт рис.1.6,б и рис.1.6,г, функция логического сложения принимает значение лог.0 только в единственном случае, когда все аргументы принимают значение лог.0. Значение же лог.1 она имеет, если первый аргумент или второй, или третий и т.д., или все вместе аргументы принимают значение лог.1. Поэтому эту функцию называют функцией ИЛИ.
Так же, как и к конъюнкции многих переменных, к дизъюнкции применимы переместительный и сочетательный законы булевой алгебры. И следствием этого является логическая равнозначность входов у логических элементов ИЛИ, а также возможность построения многовходовых элементов ИЛИ из аналогичных элементов, но с меньшим числом входов. Если на рис.1.5 все элементы И заменить двухвходовыми элементами ИЛИ (2ИЛИ), то все выводы, сделанные относительно схем рис.1.5, будут справедливыми для схем, полученных такой заменой. Можно так же записать логико-математические модели для полученных схем и УГО элемента 6ИЛИ, заменив в выражениях (1.7), (1.8) и (1.9) все символы логического умножения знаками + (дизъюнкции).
В различных сериях ИМС имеются логические элементы ИЛИ. Например, в серии ТТЛ это микросхема К155ЛЛ1, она содержит 4 элемента 2ИЛИ.
Эти элементы реализуют инверсию логического произведения входных сигналов. Другими словами, элементы И-НЕ описываются функцией «отрицания конъюнкции». В булевой алгебре такие функции называются функциями Шеффера, для их обозначения введён специальный символ « ∕ », называемый штрихом Шеффера. Для простоты чтения мы будем использовать для обозначения функций Шеффера символ инверсии (черта вверху) над выражением конъюнкции переменных. Например, алгебраическая форма записи функции Шеффера от двух аргументов будет иметь следующий вид:
X = a / b = = . (1.11)
В выражении (1.11) знаки равенства соответствуют логической тождественности выражений, причём правая часть выражения соответствует КСНФ функции И-НЕ (функция V13 в табл.1.3). А в целом выражение читается так: «инверсия логического произведения равна логической сумме инверсий аргументов». Это высказывание известно в булевой алгебре как закон де Моргана относительно инверсии логического произведения (инверсии конъюнкции). На рис.1.7 приведены условные графические обозначения элемента 2И-НЕ, его функциональная эквивалентная схема и карта Карно для рассматриваемой функции. Сравнивая карты Карно функций И и функций И-НЕ, нетрудно заметить, что в клетках стоят противоположные значения названных функций. Сопоставляя карты с алгебраическими выражениями функции И и функции И-НЕ, можно сделать следующие выводы:
1. Каждой единице, стоящей в клетке матрицы, соответствует логическое произведение (конъюнкция) всех аргументов функции; взятых один раз со знаком либо без знака инверсии. Если клетка с единицей располагается на области единичных значений аргумента, то этот аргумент входит в конъюнкцию без инверсии. Если же клетка располагается на области нулевых значений аргумента, то этот аргумент входит со знаком инверсии.
2. Каждому нулю, стоящему в клетке матрицы, соответствует логическая сумма (дизъюнкция) всех аргументов функции, взятых один раз со знаком либо без знака инверсии. Если клетка с нулём располагается на области единичных значений аргумента, то этот аргумент входит в дизъюнкцию со знаком инверсии. Если же клетка располагается на области нулевых значений аргумента, то этот аргумент входит без знака инверсии.
Эти выводы носят характер правил отыскания ДСНФ (первый вывод) и КСНФ (второй вывод) по булевым матрицам логических функций. Следует только добавить, что для отыскания ДСНФ функции необходимо эти элементарные конъюнкции «соединять» символами дизъюнкции (плюс), а при отыскании КСНФ функции элементарных дизъюнкций следует соединять символами конъюнкции.
В сериях микросхем есть элементы И-НЕ, различающиеся числом входов, количеством элементов в одной микросхеме, а также способом организации выхода. Например, микросхема К155ЛА3 содержит 4 элемента 2И-НЕ со стандартной нагрузочной способностью. Микросхема К155ЛА8 содержит один элемент 8И-НЕ с повышенной нагрузочной способностью (она равна 30, а стандартная нагрузочная способность равна 10).
Элемент 2И-НЕ является базовым для микросхем транзисторно-транзисторной логики (ТТЛ), т.е. этот элемент положен в основу построения всех названных микросхем и в том числе микросхем ТТЛш.
Функции, описывающие элемент 2ИЛИ-НЕ, в булевой алгебре называют функциями Пирса, для них введён специальный символ ¯ (стрелка Пирса). В технических приложениях эти функции называют «инверсией логической суммы (дизъюнкции)» или просто функциями ИЛИ-НЕ. В частности, двухместная функция Пирса, функция 2ИЛИ-НЕ имеет следующие алгебраические выражения:
Z = a ¯ b = = . (1.12)
В интегральном исполнении выпускаются логические элементы ИЛИ-НЕ с различным числом входов. Примером может служить микросхема К155ЛЕ1, содержащая 4 логических элементов 2ИЛИ-НЕ, или К155ЛЕ3 с двумя элементами 4ИЛИ-НЕ. Как и у элементов ИЛИ, так и у элементов ИЛИ-НЕ все входы логически равнозначны.
Эти двухвходовые элементы получили такое название потому, что сигнал по одному из входов «запрещает» либо «разрешает» прохождение на выход элемента сигнала, поданного на второй вход. Поэтому один вход называется входом запрета - он инверсный, а второй вход называют «информационным». Значения выходного сигнала совпадают со значениями входного информационного сигнала в состоянии разрешения, а в состоянии запрета выходной сигнал имеет значение лог.0 независимо от значения сигнала по информационному входу. В табл.1.3 показаны две функции запрета V1 (запрет b) и функция V4 (запрет а). На рис. 1.9 приведены УГО элемента «запрет а» (запрет по а), алгебраическое выражение и карта Карно функции с аналогичным названием и функциональная эквивалентная схема элемента.
Страницы: 1, 2, 3, 4, 5, 6
