Задача минимизации ДНФ является наиболее исследованной задачей теории автоматов, и число публикаций, в которых эта задача так или иначе рассматривается, к настоящему времени перевалило, по-видимому, за тысячу. Между тем нередко выражается мнение, звучащее в своей категорической форме так: для того чтобы получить минимальную или кратчайшую ДНФ некоторой булевой функции, совершенно необходимо найти сначала все ее простые импликанты, затем построить из них все безызбыточные ДНФ, а уж потом выбрать среди них оптимальную.
К счастью, это мнение ошибочно. Ниже описывается несколько методов, позволяющих находить точное решение данной задачи, в то же время избегая получения всех простых импликант и, тем более, построения всех безызбыточных ДНФ. Правда, практически могут встретиться ситуации, когда и эти методы окажутся слишком трудоемкими. В таких случаях могут быть рекомендованы приближенные методы, представляющие собой модификации точных методов и также излагаемые ниже.
О п р е д е л я ю щ и е э л е м е н т ы и о б я з а т е л ь н ы е и н т е р в а л ы. Современная технология производства транзисторных матричных схем такова, что основным критерием оптимальности схемы является ее площадь, определяемая произведением числа строк матрицы на число ее столбцов. Число транзисторов в схеме представляет собой менее значительный критерий, который мы примем в качестве дополнительного. В соответствии с этим сосредоточим в дальнейшем внимание на поиске кратчайших ДНФ, однако не любых, а безызбыточных, чтобы учесть по возможности требования, выражаемые дополнительным критерием. Другими словами, будем искать минимальное покрытие характеристического множества М1 заданной булевой функции f максимальными интервалами.
Пусть множество М1 представлено в виде булевой матрицы В. В этом случае задачу минимизации ДНФ заданной булевой функции f можно интерпретировать как задачу максимального сжатия матрицы В, при котором некоторые совокупности строк этой матрицы, образующие интервалы булева пространства М, заменяются соответствующими троичными 'векторами.
Метод Квайна — МакКласки, отправляющийся, по существу, от булевой матрицы В, осуществляет параллельный рост интервалов в множестве- М1 путем склеивания интервалов более высоких рангов, что приводит в конечном счете к получению всех максимальных интервалов множества M1. Между тем не все они понадобятся для построения кратчайших ДНФ, тем более если нам достаточно найти лишь одну из кратчайших ДНФ. Число рассматриваемых максимальных интервалов можно сократить на основе следующих рассуждений. Если некоторый элемент а (булев вектор) множества М1 принадлежит лишь одному из максимальных интервалов этого множества, а именно некоторому интервалу u (троичный вектор), то, очевидно, любое кратчайшее интервальное покрытие множества М1 будет содержать интервал u. В этом случае будем называть элемент а определяющем,. а однозначно определяемый им интервал u —обязательным.
Для того чтобы установить, является ли некоторый элемент а определяющим, достаточно найти все соседние с ним элементы в множестве М1, а затем построить содержащий их минимальный интервал пространства М, называемый минимальным поглощающим интервалом. Если все элементы этого интервала принадлежат множеству М1, то он является интервалом множества М1, максимальным и притом обязательным, а элемент а является определяющим. В противном случае ни интервал, ни элемент данными свойствами не обладает.
Минимальный поглощающий интервал для заданной совокупности элементов булева пространства получается весьма просто. Строится троичный вектор, компоненты которого принимают значения одноименных компонент булевых векторов, представляющих элементы, если эти значения совпадают, и принимают значение «—», если среди значений одноименных компонент булевых векторов встречается как 0, так и 1.
Получить ответ на вопрос, содержится ли интервал и в множестве М1, заданном булевой матрицей В, также несложно. Можно просто перебрать элементы этого интервала и попытаться найти их в множестве М1. Если же
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.