§ 2.5. Проблема минимизации устройств, реализующих логические функции

При построении устройств, реализующих заданные функции, естественно возникает следующая задача: задан некоторый набор блоков (элементов), реализующих элементарные логические функции;

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

где — число элементов определенного вида, — цена одного элемента, а — число различных элементов в наборе.

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

Предложены многочисленные алгоритмы частичного решения этой задачи.

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

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

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

Опишем метод Квайна [214] для решения этой задачи. Последовательность операций в этом методе такова. Проводятся все возможные сокращения членов совершенной формы путем использования тождества

где А может быть конъюнкцией нескольких переменных. Затем эта же операция проделывается по отношению ко всем конъюнкциям, полученным в результате первого сокращения и т. д. до тех пор, пока дальнейшее сокращение станет невозможным. Пары конъюнкций (из числа членов совершенной формы и полученных в результате сокращений), к которым упрощающее тождество (2.1) нельзя применить, называются простыми импликантами F. Квайном доказано, что любое минимальное дизъюнктивное нормальное выражение F есть дизъюнкция некоторых простых импликатов F. Поэтому следующим этапом нахождения минимальных выражений F является определение комбинаций простых импликантов, дизъюнкции которых давали бы минимальные выражения. Для этого с помощью некоторых искусственных приемов (см. [185]) строятся такие комбинация простых импликантов F, дизъюнкция которых эквивалентна F и удаление из дизъюнкции хотя бы одного простого импликанта нарушило бы условие эквивалентности F. Такие дизъюнкции называются «тупиковыми» выражениями F. Затем в каждом из тупиковых выражений подсчитывается число знаков и отбираются те из них, у которых суммарное число этих знаков наименьшее. Эти выражения и являются минимальными (при принятом критерии минимальности).

Приведем пример. Пусть задана булева функция

В результате всех возможных попарных сокращений членов совершенной формы (причем каждый из членов дизъюнктивной формы может входить более чем в одну пару) получаем конъюнкции

не допускающие дальнейших сокращений. Они же являются единственными конъюнкциями, не давшими ни одного последующего сокращения. Значит все они — простые импликанты F. Хотя дизъюнкция всех простых импликантов эквивалентна F, непосредственной проверкой можно установить, что вычеркивание конъюнкции не нарушает условия эквивалентности и нельзя вычеркнуть никакую конъюнкцию из числа оставшихся, не нарушив эквивалентности. Следовательно,

— одно из тупиковых выражений. Можно показать также, что

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

Мы показали здесь на примере применение алгоритма Квайна. В настоящее время известны десятки алгоритмов отыскания простых импликантов логических функций. Некоторые из них более удобны для ручных вычислений, другие — для вычислений на цифровых универсальных машинах, третьи используются главным образом при теоретических исследованиях, связанных с вопросами минимизации. Различны и способы минимизации: с этой целью пользуются специальными диаграммами [180], построениями на -мерных кубах [33], цифровыми вычислениями [161], [127] и т. д.

Для построения минимальных нормальных выражений из простых импликантов также известно несколько алгоритмов (см., например, [33]).

Поскольку нахождение минимальных нормальных выражений логических функций уже сравнительно небольшого числа переменных (например, шести или семи) - весьма трудоемкий процесс, разработан ряд упрощенных алгоритмов, позволяющих получить нормальные выражения, близкие к минимальным [216—218].

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

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

имеет 13 знаков и . минимальное конъюнктивное нормальное выражение этой же функции

имеет знак следовательно, (2.2) есть минимальное нормальное выражение. Тем не менее выражение этой же функции

содержит всего 9 знаков .

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

Например, та же функция (2.2) имеет еще более минимальное выражение

которое можно получить из (2.3), представив первый член дизъюнкции в более развернутом виде

а затем воспользоваться распределительным законом.

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

В связи с этим была поставлена задача разработки алгоритма, позволяющего находить такие выражения заданной функции, о которых можно было бы с уверенностью сказать, что не существует других выражений этой же функции, минимальнее найденных [120, 121]. Такие выражения были названы абсолютно минимальными. Алгоритмы получения абсолютно минимальных выражений во много раз сложнее алгоритмов получения минимальных нормальных выражений, поэтому мы не будем их здесь подробно излагать, ограничимся лишь указанием, что каждый нетривиальный алгоритм должен включать два момента:

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

2) определение абсолютно минимальных выражений заданной функции в границах найденной максимальной сложности.

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

В данном случае ими будут два выражения вида «дизъюнкция конъюнкций дизъюнкций»

и одно «вырожденное» выражение вида «конъюнкция дизъюнкций конъюнкций»

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

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

Например, имея абсолютно минимальное выражение функции

можно сразу же построить схему из десяти элементов. Тем не менее схему, реализующую эту же функцию, можно построить и на восьми элементах (рис. 2.33).

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

где

и, строя его, дважды использовали одну и ту же реализацию (2.5).

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

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

Рис. 2.33.

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

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

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