Простые импликант
Cтраница 3
Поэтому простой импликант К функции / обладает свойством максимальности: он, как говорят, покрывает наибольшее число единиц функции / ( т.е. наборов, на которых функция / равна 1) среди всех импликантов функции /, которые получаются из К умножением на некоторые сомножители. Все эти соображения наводят на мысль, что простые импликанты и дизъюнкция всех простых импликантов должны играть важную роль в вопросах минимизации ДНФ. [31]
Простые импликанты, входящие в ядро, накрывают часть единиц булевой функции. Применительно к импли-кантной таблице более удобно говорить, что простые импликанты накрывают соответствующие этим единицам конституенты функции. Ясно, что накрытыми окажутся все те и только те конституенты, которые обозначают столбцы импликантной таблицы, содержащие звездочки в строках, обозначения которых принадлежат ядру. [32]
Множество всех простых импликант любой булевой функции / накрывает все ее единицы. Однако такое представление обычно не бывает самым экономным, поскольку некоторые простые импликанты могут накрывать единицы, уже накрытые остальными импликантами. [33]
Поэтому простой импликант К функции / обладает свойством максимальности: он, как говорят, покрывает наибольшее число единиц функции / ( т.е. наборов, на которых функция / равна 1) среди всех импликантов функции /, которые получаются из К умножением на некоторые сомножители. Все эти соображения наводят на мысль, что простые импликанты и дизъюнкция всех простых импликантов должны играть важную роль в вопросах минимизации ДНФ. [34]
До того, как были получены упомянутые нижние оценки вида Й ( я5 / 3), был успешно развит следующий подход. Изучались системы, состоящие из булевых функций, чьи простые им-пликанты содержат не менее двух переменных, и вдобавок обладающих тем свойством, что простые импликанты каждой из этих функций не имеют общих переменных. Легко доказать, что реализация каждой из этих функций в отдельности требует по меньшей мере столько элементов Л, сколько имеется простых импликантов. Различные функции этой системы должны быть заданы таким образом, чтобы не существовало лучшей схемы для их совместной реализации, чем та, которая получается комбинированием минимальных схем, реализующих отдельные функции. [35]
Действительно, любая импликанта, являющаяся элементарным произведением, может быть получена из конституент 1 функции / в результате склеивания. Но так как при выполнении операции неполного склеивания все конституенты 1 остаются, то в результате выполнения всех возможных таких операций получим все импликанты, являющиеся элементарными произведениями. Среди них будут находиться и все простые импликанты, для выделения которых необходимо произвести все возможные операции поглощения. Так как никакая собственная часть простой импликанты не является импликантой, то ни одна из простых импликант в результате операции поглощения не пропадает. [36]
 |
Диаграммы Вейча булевой функции четырех переменных. [37] |
Рассматриваются поочередно клетки, содержащие единицы, и анализируются всевозможные варианты склеивания. При этом сначала склеивание выполняется только для тех клеток ( единиц), для которых вариант склеивания единственный. В результате будут выделены обязательные ( или существенные) простые импликанты. [38]
Далее находят все простые импликанты всех возможных совокупностей функций первой системы. Из найденных простых импликант и конституент второй системы составляют импликантную матрицу для системы функций, с помощью которой формируют МДНФ оптимально доопределенных функций заданной системы. Так же, как и для одной функции, доказательство оптимальности данного метода очевидно и основано на том, что наиболее короткие простые импликанты будут у первой системы, а наименьшее число импликант, необходимое для ДНФ функций, будет содержать вторая система. [39]
Основная идея его заключается в предварительной обработке информации моделирования с тем, чтобы получить сокращенную таблицу неисправностей. Сокращенная таблица может быть затем использована непосредственно для составления словаря или же сначала она может быть минимизирована с помощью метода простых импликантов. Метод пересечения наборов тестов часто дает эффективные наборы тестов. Однако он не гарантирует получения минимального набора. [40]
До того, как были получены упомянутые нижние оценки вида Й ( я5 / 3), был успешно развит следующий подход. Изучались системы, состоящие из булевых функций, чьи простые им-пликанты содержат не менее двух переменных, и вдобавок обладающих тем свойством, что простые импликанты каждой из этих функций не имеют общих переменных. Легко доказать, что реализация каждой из этих функций в отдельности требует по меньшей мере столько элементов Л, сколько имеется простых импликантов. Различные функции этой системы должны быть заданы таким образом, чтобы не существовало лучшей схемы для их совместной реализации, чем та, которая получается комбинированием минимальных схем, реализующих отдельные функции. [41]
 |
Таблицы простых импликантов для примера 6. [42] |
Тождество ух V ух - у может быть применимо только к парам, элементы которых лежат в соседних классах. Если мы поместим все у, происшедшие из данной пары соседних классов, в один класс, то на следующем этапе придется снова сравнивать только пары из соседних классов. Члены, входящие в пары такого вида, можно пометить знаком ] /; в дальнейшем они заведомо не останутся в списке простых импликантов. [43]
Совокупность полученных элементарных конъюнкций описывает всю область запрета О: любой ее элемент принадлежит хотя бы одному из интервалов, задаваемых этими конъюнкциями. О - такой булевой функции, которая принимает значение 1 на множестве U и значение 0 на дополнительном множестве U. Каждый ее член представляет собой простую импликанту - элементарную конъюнкцию со следующими двумя свойствами: во-первых, она имплицирует функцию ф ( если конъюнкция принимает значение 1, то и функция тоже), во-вторых, она не имплицирует никакой другой конъюнкции, обладающей первым свойством. Если в ДНФ входят все простые импликанты ( как в данном случае), она называется сокращенной. [44]
ФЗ, содержит только такие конъюнкции, что функциональные зависимости, соответствующие этим конъюнкциям, могут быть выведены из начального набора ФЗ. И наоборот, любая функциональная зависимость, принадлежащая замыканию исходного набора ФЗ, соответствует некоторой импликанте функции, соответствующей исходному набору. Таким образом, чтобы найти замыкание набора ФЗ, достаточно найти сокращенную дизъюнктивную нормальную форму функции, соответствующей этому набору. Это верно, потому что все простые импликанты такой функции имеют только одну переменную с отрицанием. Любая тупиковая дизъюнктивная нормальная форма такой функции соответствует неизбыточному покрытию заданного набора функциональных зависимостей. [45]
Страницы: 1 2 3 4