4. Логические схемы

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

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

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

.................

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

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

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

Например, функция из (3) упрощается следующим образом:

y = (x₁ / x₂) + (x̅₃ → x₁) =

= ¬(x₁x₂) + (x₃ ∨ x₁) =

= x₁x₂(x₃ ∨ x₁) ∨ ¬(x₁x₂)x₃ ∨ x̅₁ =

= x₁x₂ ∨ ¬(x₁x₂)(x₃ ∨ x₁) =

= x₁x₂ ∨ ¬(x₁ ∨ x₃).

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

Каноническая задача синтеза логических схем в булевом базисе сводится к минимизации булевых функций, т.е. к представлению их в дизъюнктивной нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. При каноническом синтезе предполагается, что на входы схемы подаются как сигналы х_i, так и их инверсии x̅_i. Формула, представленная в дизъюнктивной нормальной форме, упрощается многократным применением операции склеивания ab ∨ ab̅ = a и операций поглощения a ∨ ab = a; и a ∨ ab̅ = a ∨ b (дуальные тождества для конъюнктивной нормальной формы имеют

- 539 -

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

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

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

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

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

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

Минитерм (n - 1)-го ранга φ_n-1 можно рассматривать как результат склеивания двух минитермовn-го ранга (конституент единицы), т. е. φ_n-1 = φ_n-1x₁ ∨ φ_n-1x̅₁.На n-мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты x_i, соединяющим эти вершины ребром (говорят, что ребро покрывает инцидентные ему вершины). Таким образом,

- 540 -

минитермам (n - 1)-го порядка соответствуют ребра n-мерного куба. Аналогично устанавливается соответствие минитермов (n - 2)-го порядка граням n-мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).

Рис. 212. Отображение на терхмерном кубе функции, представленной в совершенной дизъюктивной нормальной форме.

Рис. 213. Покрытие функции y = x̅₁x₂ ∨ x₁x̅₂ ∨ x₃ совокупностью s-кубов.

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

примера на рис. 22 дано отображение функции трех переменных y = x̅₁x₂ ∨ x₁x̅₂ ∨ x₃. Здесь минитермы x̅₁x₂ и x₁x̅₂ соответствуют 1-кубам (s = 3 – 2 = 1), а минитерм x₃ отображается 2-кубом (s = 3 - 1 = 2).

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

Стремление к минимальной форме интуитивно понимается как поиск такого покрытия, число s-кубов которого было бы поменьше, а их размерность s - побольше. Покрытие, соответствующее минимальной форме, называют минимальным покрытием. Например, для функции из (5) покрытие на рис. 23, а соответствует неминимальной форме y = x̅₁x₂ ∨ x₁x̅₂ ∨ x₂x₃,а покрытия на рис. 23, б и в - минимальным формам y = x̅₁x₂ ∨ x₁x₂ ∨ x₂x₃ и y = x̅₁x₂ ∨ x₁x₂ ∨ x₁x₃.

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

а б в

Рис. 214. Покрытие функции y = x̅₁x₂x̅₃ ∨ x̅₁x₂x₃ ∨ x₁x̅₂x̅₃ ∨ x₁x̅₂x₃ ∨ x₁x₂x₃:

а – неминимальное; б, в – минимальное.

рис. 215, где отображены функция четырех переменных и ее минимальное покрытие, соответствующие выражению y = x₁x̅₃ ∨ x₂x₄ ∨ x̅₁x₃x₄. Использование этого метода при n > 4 требует настолько сложных построений, что теряются все его преимущества.

Рис. 215. Отображение функции y = x₁x̅₃ ∨ x₂x₄ ∨ x̅₁x₃x₄ на четырехмерном кубе

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

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

- 542 -

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

Между отображениями функции на n-мерном кубе и на карте Карно имеет место взаимно-однозначное соответствие. На карте

- 543 -

Карно s-кубу соответствует совокупность 2 соседних клеток, размещенных в строке, столбце, квадрате или прямоугольнике (с учетом соседства противоположных краев карты). Поэтому все положения, изложенные в (6), справедливы и для карт Карно.

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

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

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

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

Комплекс кубов K(у) функции у = f(х₁, х₂, ..., х_n) определяется как объединение множеств K^s(у) всех ее s-кубов (s = 0, 1, .... n),

- 544 -

т. е.

Рис. 219. Комплекс кубов функци трех переменных (а) и его символическое представление (б).

Очевидно, в записи s-куба всегда имеется s свободных переменных. Если все n переменных свободны, что соответствует n-кубу, то это означает тождественность единице рассматриваемой функции. Таким образом, для функций, не равных тождественно единице, Kⁿ(y) = ∅.

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

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

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

- 545 -

формам. Так, для рассматриваемого примера имеем тупиковое покрытие

которое соответствует y = x̅₂x₃ ∨ x₂x̅₃ ∨ x̅₁. В данном случае это покрытие являетcя и минимальным.

Для двух булевых функций операция дизъюнкции соответствует объединению их комплексов кубов K(y₁ ∨ y₂) = K(y₁) ∪ K(y₂), а операция конъюнкции - пересечению комплексов кубов K(y₁y₂) = K(y₁) ∩ K(y₂).Отрицанию функции соответствует дополнение комплекса кубов, т. е. K(y̅) = K̅(y), причем K̅(y) определяется всеми вершинами, на которых функция принимает значение 0. Таким образом, имеет место взаимно-однозначное соответствие (изоморфизм) между алгеброй булевых функций и алгеброй множеств, представляющих комплексы кубов.

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

9. Реализация в различных формах. Реализация функции в дизъюнктивной нормальной форме представляет собой логическую схему И-ИЛИ. Например, функция y = x̅₁x₂ ∨ x₁x̅₂ ∨ x₂x₃ реализуется логической схемой. Более экономичная реализация получается, если общий множитель вынести за скобки: y = x₂(x̅₁ ∨ x₃) ∨ x₁x̅₂. При использовании элементов со многими входами получаем двухуровневую логическую схему И—ИЛИ.

В соответствии с принципом двойственности (2.1), заменяя в дизъюнктивной нормальной форме операции конъюнкции на дизъюнкции, операции дизъюнкции на конъюнкции и беря отрицание

- 546 -

каждой переменной, получаем конъюнктивную нормальную форму, которая выражает функцию y̅, обратную к у. Ее реализация с помощью многовходовых элементов представляет собой двухуровневую логическую схему ИЛИ—И. Для рассматриваемой функции y̅ = (x₁ ∨ x̅₂)(x̅₁ ∨ x₂)(x̅₂ ∨ x̅₃) соответствующая реализация показана на рис. 26, г. Если требуется получить схему для данной функции у, то используется инвертор или элемент, реализующей операцию НЕ—И.

Конъюнктивную нормальную форму можно получить и другим путем. Для этого используются рассуждения и методы, дуальные рассмотренным по отношению к дизъюнктивным нормальным формам. На многомерном кубе ищется покрытие множества вершин для нулевых значений функции, а на карте Карно - покрытие нулевых клеток. Рассматриваемый пример иллюстрируется на рис. 221, а и б. Соответствующая конъюнктивная нормальная форма y = (x₁ ∨ x₂)(x̅₁ ∨ x̅₂ ∨ x₃) реализуется соответствующей схемой. Комплекс кубов этой функции и его дополнение имеют вид:

а их покрытия

Покрытию С соответствует дизъюнктивная нормальная форма для отрицания функции y̅ = x₁x₂x̅₃ ∨ x̅₁x̅₂, откуда можно получить приведенное выше выражение функции в конъюнктивной нормальной форме.

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

- 547 -

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

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

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