Сделай Сам Свою Работу на 5

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





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

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

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

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

Таблица 7

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



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

 

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



 

 

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

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

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

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

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

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

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

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



 

Рисунок 211.

 

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

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

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

Например, функция из (3) упрощается следующим образом: Соответствующая логическая схема показана на рис. 211, в.

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

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

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

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

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

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

6. Многомерный куб.Каждой вершине n-мерного куба (1. 9), можно поставить в соответствии конституенту единицы (2. 5). Следовательно, подмножество отмеченных вершин является отражением на n – мерном кубе булевой функции от n переменных в совершенной дизъюнктивной нормальной форме. На рис. 212 показано такое отражение для функции из (5).

Для отображения функции от n переменных, представленной в любой дизъюнктивной нормальной форме, необходимо установить соответствие между её минитермами (2. 2) и элементами n-мерного куба.

Минитерм -го ранга можно рассматривать как результат склеивания двух склеивания двух минитермов n-го ранга (конституент единицы), т.е. . На n-мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты , соединяющим эти вершины ребром (говорят, что ребро покрывает инцидентные ему вершины). Таким образом, минитермам -го порядка соответствует рёбра n-мерного куба. Аналогично устанавливается соответствие минитермов -го порядка граням n-мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).

Элементы n-мерного куба, характеризующиеся s измерениями, называют s-кубами. Так, вершины являются 0-кубами, рёбра – 1-кубами, грани – 2-кубами и т.д. Обобщая приведённые рассуждения, можно считать, что минитерм -го ранга в дизъюнктивной нормальной форме для функции n переменных отображается s-кубом, причём каждый s-куб покрывает все те s-кубы низшей размерности, которые связаны с его вершинами. В качестве примера на рис.213 дано отображение функции трёх переменных . Здесь минитермы и соответствуют 1-кубам , а минитерм отображается 2-кубом ( ).

 

 

РИСУНОК 212. и РИСУНОК 213

Итак, любая дизъюнктивная нормальная форма отображается на n-мерном кубе совокупностью s-кубов, которые покрывают все вершины, соответствующие конституентам единицы (0-кубы). Справедливо и обратное утверждение: если некоторая совокупность s-кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим s-кубом минитермов является выражением данной функции в дизъюнктивной нормальной форме. Говорят, что такая совокупность s-кубов (или соответствующих им минитермов) образует покрытие функции.

Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число s-кубов которого было бы поменьше, а их размерность s - побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием. Например, для функции из (5) покрытие на рис.214, а соответствует неминимальной форме , а покрытия на рис. 214, б и в – минимальным формам и .

 

 

РИСУНОК 214. А,Б,В

Отображение функции на n-мерном кубе наглядно и просто при . Четырёхмерный куб можно изобразить, как показано на рис. 215, где отображены функция четырёх переменных

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

 

РИСУНОК 215.

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

 

 

 

РИСУНОК 216.

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

РИСУНОК 217.а и б

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

Между отображениями функции на n-мерном кубе и на карте Карно имеет место взаимно-однозначное соответствие. На карте Карно s-кубу соответствует совокупность 2s соседних клеток, размещённых в строке, столбце, квадрате или прямоугольнике (с учётом соседства противоположных краёв карты). Поэтому все положения, изложенные в (6), справедливы и для карт Карно. Так, на рис. 217, б показано покрытие единиц карты, соответствующее минимальной дизъюнктивной форме рассматриваемой функции.

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

 

 

РИСУНОК 218.

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

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

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

Комплекс кубов функции определяется как объединение множеств всех её s-кубов (s=0, 1,…, n), т.е. , причём некоторые из могут быть пустыми. Для записи s-кубов и минитермов функции от n переменных используются слова длины n, буквы которых соответствуют всем n переменным. Входящие в минитерм переменные называются связанными и представляются значениями, при которых минитерм равен единице (1 для и 0 для ). Не входящие в минитерм переменные являются свободными и обозначаются через х. Например, 2-куб функции пяти переменных, соответствующий минитерму , запишется как ( ). 0-кубы, соответствующие конституентам единицы, представляются наборами значений переменных, на которых функция равна единице. Очевидно, в записи s-куба всегда имеется s свободных переменных. Если все n переменных свободны, что соответствует n-кубу, то это означает тождественность единице рассматриваемой функции. Таким образом, для функции, не равных тождественно единице, .

Множество всех s-кубов записывается как совокупность слов, соответствующих каждому s-кубу. Для удобства будем располагать слова s-кубов в столбцы, а их совокупность заключать в фигурные скобки. Например, комплекс кубов, соответствующий представлению функции на трёхмерном кубе (рис. 219, а), выражается как , где

; ;

Для сравнения на рис. 219, б изображён комплекс кубов в принятых обозначениях.

 

РИСУНОК 219. А и Б

Комплекс кубов образует максимальное покрытие функции. Исключая из него все те s-кубы, которые покрываются кубами высшей размерности, получаем покрытия, соответствующие тупиковым формам. Так, для рассматриваемого примера (рис. 219) имеем тупиковое покрытие

которое соответствует функции . В данном случае это покрытие является и минимальным.

Для двух булевых функций операция дизъюнкции соответствует объединению их комплексов кубов , а операция конъюнкции - пересечению комплексов кубов . Отрицанию функции соответствует дополнение комплекса кубов, т.е. , причём определяется всеми вершинами, на которых функция принимает значение 0. Таким образом, имеет место взаимно-однозначное соответствие (изоморфизм) между алгеброй булевых функций и алгеброй множеств, представляющих комплексы кубов.

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

9. Реализация в различных формах.Реализация функции в дизъюнктивной нормальной форме представляет собой логическую схему И – ИЛИ. Например, функция реализуется логической схемой (рис. 220, а). Более экономичная реализация получается, если общий множитель вынести за скобки: (рис. 220, б). При использовании элементов со многими входами получаем двухуровневую логическую схему И – ИЛИ (рис. 220, в)

 

РИСУНОК 220

В соответствии с принципом двойственности (2. 1), заменяя в дизъюнктивной нормальной форме операции конъюнкции на дизъюнкции, операции дизъюнкции на конъюнкции и беря отрицания каждой переменной, получаем конъюнктивную нормальную форму, которая выражает функцию , обратную к . Её реализация с помощью многовходовых элементов представляет собой двухуровневую логическую схему ИЛИ – И. Для рассматриваемой функции соответствующая реализация показана на рис. 220, г. Если требуется получить схему для данной функции то используется инвертор или элемент, реализующий операцию НЕ – И.

Конъюнктивную нормальную форму можно получить и другим путём. Для этого используется рассуждения и методы, дуальные рассмотренным по отношению к дизъюнктивным нормальным формам. На многомерном кубе ищется покрытие множества вершин для нулевых значений функции, а на карте Карно - покрытие нулевых клеток. Рассматриваемый пример иллюстрируется на рис. 221, а и б.

 

РИСУНОК 221 а, б, в.

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

;

а их покрытия

;

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

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

 

РИСУНОК. 222

Задача сводится к выбору для каждой функции такого покрытия, которое включало бы возможно большое число s-кубов, содержащихся в покрытиях других функций. Этому требованию удовлетворяют, например, покрытия для трёх функций (рис. 222). Соответствующая трёхвыходная схема показана на рис. 223. Если бы для функции было выбрано другое покрытие, то схема получилась бы менее экономичной.

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

 

ЗАДАЧИ И УПРАЖНЕНИЯ

1. Представьте равнозначность и неравнозначность контактными схемами, соответствующими конъюнктивным нормальным формам функций и .

2. Постройте логические схемы в базисе {НЕ, И, ИЛИ} для логических элементов, представленных в табл. 7.

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

a. ;

b. ;

c. ;

d. .

4. Постройте логические схемы, реализующие функцию , в следующих функционально полных системах логических элементов:

a. совпадение и инвертор;

b. разделение и инвертор;

c. разделение с двумя запретами;

d. совпадение с двумя запретами.

5. Представьте функцию на трёхмерном кубе и на карте Карно. Запишите различные покрытия этой функции в дизъюнктивной и конъюнктивной нормальных формах.

6. Дана булева функция четырёх переменных:

a. Представьте данную функцию на четырёхмерном кубе и на карте Карно.

b. Запишите для этой функции комплекс кубов, а также все тупиковые покрытия в символической форме.

c. Найдите минимальное покрытие и соответствующую ему дизъюнктивную форму.

d. Постройте логическую схему, реализующую данную функцию в булевом базисе {НЕ, И, ИЛИ}.

7. Запишите дизъюнктивную нормальную форму функции в соответствии с заданным покрытием:

Является ли это покрытие тупиковым? Если нет, то какие s-кубы необходимо исключить из , чтобы получить тупиковое покрытие? Рассмотрите всевозможные варианты решения этой задачи.

8. Нанесите на карту Карно покрытие из задачи 7. Запишите совершенные дизъюнктивную и конъюнктивную формы соответствующей этому покрытию функции. Укажите на карте найденные в задаче 7 тупиковые покрытия.

РИСУНОК 224 и РИСУНОК 225

9. Запишите всевозможные формы функции на основе заданной карты Карно (рис. 224) и найдите минимальную форму. Запишите минимальное покрытие как подмножество комплекса кубов.

10. Представьте булеву функцию, соответствующую контактной схеме (рис. 225):

a. таблицей соответствия;

b. на многомерном кубе;

c. на карте Карно;

d. комплексом кубов.

Постройте логическую схему, реализующую эту функцию в базисе {НЕ, И, ИЛИ}.


 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.