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

Алгоритм Блейка-Порецкого.





Начало. Задана произвольная ДНФ булевой функции.

Шаг 1. Построим список троичных векторов, представляющих конъюнкции ДНФ. Удалим из списка все векторы, поглощаемые другими. Если останется лишь один вектор, пойдем на конец. Ина­че обозначим второй из оставшихся векторов через α.

Шаг 2. Найдем для вектора α очередной смежный вектор β среди векторов, расположенных в списке выше α. Если такого вектора β нет, то идем на шаг 5. Иначе обобщенно склеим а и β и полученный вектор γ припишем к списку последним.

Шаг 3. Если вектор γ поглощается хотя бы одним вектором из списка, то удалим γ (в частном случае γ может совпадать с одним из векторов списка, тогда удалим именно приписанный вектор γ, иначе произойдет "зацикливание" алгоритма, так как вектор γ будет вновь появляться в списке) и идем на шаг 2. Если вектор γ не поглощается, то удалим все векторы, поглощаемые им.

Шаг 4. Если вектор α не удален, то идем на шаг 2.

Шаг 5. Если вектор α удален, но был не последним в списке, то выберем в качестве нового α следующий по списку вектор и вернемся на шаг 2.

Конец. Векторы, оставшиеся в списке, задают сокращенную ДНФ исходной функции.



Алгоритм Блейка-Порецкого отличается от алгоритма Квайна-МакКласки прежде всего тем, что оперирует с произвольной ДНФ, в то время как алгоритм Квайна-МакКласки требует на входе со­вершенную ДНФ. Конечно, можно перейти от произвольной ДНФ к совершенной, но она может оказаться очень длинной, и применение алгоритма Квайна-МакКласки ста­нет неэффективным.
24 - 25. Поиск кратчайшей ДНФ с помощью таблицы Квайна. Алгоритм поиска всех безызбыточных покрытий.

[24, 25] Определение. Булевой матрицей назовем матрицу, элемен­тами которой являются булевы константы (другими словами, стро­ками и столбцами которой являются булевы векторы).

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

Определение. Таблицей Квайна булевой функции f(x1,..., хn) назовем булеву матрицу, строкам которой поставим в соответ­ствие конъюнкции сокращенной ДНФf (все максимальные интер­валы функции), а столбцам - конъюнкции совершенной ДНФf (все точки). Элемент матрицы, стоящий на пересечении i-й стро­ки и j-то столбца, положим равным единице тогда и только тогда, когда i-я конъюнкция сокращенной ДНФ поглощает j-ю конъ­юнкцию совершенной ДНФ (i-й максимальный интервал функции содержит ее j-ю точку).



Определение.Будем говорить, что строка таблицы Квайна покрывает столбец, если она содержит единицу в этом столбце.

Любое покрытие таблицы Квайна функции f(x1,..., хп) задает подмножество максимальных интервалов, достаточное для функ­ции, так как каждая точка функции принадлежит хотя бы одному из ее максимальных интервалов. Другими словами, любое покры­тие таблицы Квайна задает ДНФf. В частности, покрытие, со­стоящее из всех строк таблицы, задает сокращенную ДНФ.

Определение.Длиной покрытия назовем количество строк, образующих покрытие.

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

Определение.Кратчайшим покрытием таблицы Квайна на­зовем покрытие минимальной длины.

Определение.Рангом, строки таблицы Квайна назовем ранг приписанной ей простой импликанты.

Определение. Минимальным покрытием таблицы Квайна на­зовем покрытие с минимальной суммой рангов строк.

Определение.Столбец булевой матрицы назовем ядерным, если он содержит ровно одну единицу. Строку булевой матрицы назовем ядерной, если она покрывает ядерный столбец.

Правило ядерной строки. Если в матрице есть ядерная стро­ка, то она включается в любое искомое покрытие и удаляется из матрицы вместе со всеми столбцами, которые ядерная строка по­крывает. Удаляются также пустые строки (целиком состоящие из нулей), которые при этом могут появиться.
[24] Алгоритм поиска всех безызбыточных покрытий буле­вой матрицы
(основан на построении КНФ функции покрытия и преобразовании ее в ДНФ с выполнением поглощений).



Начало.Задана булева матрица.

Шаг 1. Применим к матрице правило ядерной строки много­кратно, пока это возможно. Если матрица стала пустой, то идем на конец. Иначе из равных столбцов оставим по одному, пронуме­руем столбцы упрощенной матрицы и припишем строкам булевы переменные s1,...,sm.

Шаг 2. Выберем очередной (j-й) столбец матрицы. Если столб­цы исчерпаны, идем на шаг 3. Иначе построим дизъюнкцию Dj переменных, приписанных строкам, содержащим единицы в j-м столбце, и возвратимся на шаг 2.

Шаг 3. Из полученных дизъюнкций построим конъюнктивную нормальную форму D ...·Dk

Шаг 4. Раскроем скобки в КНФ, выполняя поглощения конъ­юнкций. Получим ДНФ=K1 v...v Kt.

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

 

Поискминимальных и кратчайших покрытий

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

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

Правило строки-предшественницы. Если в булевой матрице есть такие строки а и β, что а≤ β, то строка-предшественница а удаляется из матрицы (при этом кратчайшее покрытие не теряет­ся, так как в любом покрытии строку а можно заменить строкой β, и оно останется покрытием).

Правило столбца-последователя.Если в булевой матрице есть такие столбцы γ и δ, что γ ≤ δ, то столбец-последователь δ удаля­ется из матрицы (так как любое покрытие столбца γ одновременно покрывает столбец δ).

Заметим, что удаление столбцов-последователей может приве­сти к появлению строк-предшественниц, и наоборот, поэтому эти два правила стоит выполнять "циклически" друг за другом.

Определение.Булеву матрицу, не содержащую ни ядерных строк, ни строк-предшественниц, ни столбцов-последователей, на­зовем циклическим остатком.


[25] Алгоритм поиска одного кратчайшего покрытия буле­вой матрицы(основан на построении циклического остатка и поиске всех его безызбыточных покрытий).

Начало. Задана булева матрица.

Шаг 1. Если в матрице есть однострочное покрытие, то вклю­чим его в покрытие, идем на конец.

Шаг 2. Применим правило ядерной строки. Если ядерная стро­ка обнаружилась, идем на шаг 1.

Шаг 3. Применим правило строки-предшественницы. Если та­кая строка обнаружилась, идем на шаг 2.

Шаг 4. Применим правило столбца-последователя. Если такой столбец обнаружился, идем на шаг 3.

Шаг 5. Построим КНФ функции покрытия полученного ци­клического остатка и преобразуем КНФ в ДНФ, раскрывая скоб­ки и выполняя поглощения.

Шаг 6. Конъюнкция минимального ранга полученной ДНФ задает кратчайшее покрытие циклического остатка. Добавим к этому покрытию ядерные строки, выделенные на шаге 2.

Конец. Получено кратчайшее покрытие исходной матрицы.


26. Частичные булевы функции, способы их задания, доопределение

Определение. Неполностью определенной (частичной) бу­левой функцией fх(x1,... ,xn) назовем однозначное отображение подмножества M булева пространства Bn в булево множество B, т.е. .

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

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

1) Задание неполностью определенной булевой функ­ции таблицей истинности.В левой части таблицы истинности представляются, как и раньше, все векторы булева пространства, а в ее правой части либо перечисляются значения функции, либо указывается специальный символ х (если набор в область опре­деления не входит).

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

3) Задание неполностью определенной булевой функ­ции матрицей Грея.В матрице Грея тем же символом х отме­чаются клетки, не входящие в область определения.

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


Определение. Доопределением неполностью определенной бу­левой функции fх(x1,...,xn) назовем любую булеву функцию f(x1,..., xn), удовлетворяющую условиям:

Это означает, что значения любого доопределения должны совпадать со значениями неполностью определенной булевой функ­ции fх(x1,... ,xn) на наборах из характеристических множеств , и, в то же время, доопределение может принимать любые значения на наборах из множества . Из этого и из те­оремы о числе векторов с очевидностью следует утверждение.

Утверждение о числе доопределений.Число различ­ных доопределений неполностью определенной булевой функции

Пример.

 

27.Частичные булевы функции, точный метод их минимизации

Определение. Неполностью определенной (частичной) бу­левой функцией fх(x1,...,xn) назовем однозначное отображение подмножества M булева пространства Bn в булево множество B, т.е. .

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

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

Определение. Минимизировать неполностью определенную булеву функцию - это значит выбрать среди кратчайших ДНФ всех ее доопределений самую короткую ДНФ.

Пример.Для рассмотренной в предыдущем примере (26 билет) непол­ностью определенной булевой функции fх(x, y, z) перебор крат­чайших ДНФ всех восьми доопределений приводит к следующе­му результату: самой короткой оказывается кратчайшая ДНФ до­определения f6(x,y,z).

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

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

Определение.Интервал I назовем допустимым для непол­ностью определенной булевой функции fх(x1,..., xn), если он удо­влетворяет условиям:

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

Пример.На левой матрице Грея изображены два недопустимых интервала на средней – допустимый интервал I = -00 (но не максимальный), на правой - максималь­ный I' =-­­-0.

 

28. Частичные булевы функции, их минимизация по матрицам в коде Грэя. Метод Закревского

Определение. Неполностью определенной (частичной) бу­левой функцией fх(x1,... ,xn) назовем однозначное отображение подмножества M булева пространства Bn в булево множество B, т.е. .

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

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

Для нахождения всех максимальных интервалов неполностью определенной функции fх(x1,..., xn) можно применить алгоритм Квайна-Мак-Класки или алгоритм Блейка-Порецкого к ее доопре­делению f(x1,...,xn), которое удовлетворяет условию: , а затем исключить из найденных интервалов те, которые не содержат ни одной точки функции fх(x1,..., xn). Таблица Квайна неполностью определенной функции fx(x1,... ,xп) строится ана­логично таблице Квайна булевой функции.

Алгоритм поиска кратчайшей ДНФ неполностью опре­деленной булевой функции(основан на нахождении всех мак­симальных интервалов функции, построении таблицы Квайна и поиске кратчайшего покрытия этой таблицы).

Начало. Задана частичная булева функция fх(x1,..., xn).

Шаг 1. Находим любым алгоритмом все максимальные интер­валы функции fх(x1,..., xn).

Шаг 2. Строим таблицу Квайна функции fx(x1, . . . ,xn).

Шаг 3. Находим кратчайшее покрытие таблицы Квайна, а по покрытию - кратчайшую ДНФ функции fх(x1,..., xn).

Конец.

 

Алгоритм Закревского(ориентирован на матричное пред­ставление функции и визуальный способ решения).

Начало. Задана матрица Грея неполностью определенной бу­левой функции fх(x1,...,xn).

Шаг 1. Для каждой точки вычислим цену - количество со­седних ей векторов из множества . Все точки будем считать неотмеченными.

Шаг 2. Среди неотмеченных точек рассмотрим точку мини­мальной цены и найдем все максимальные интервалы, которым она принадлежит. Выберем из них тот максимальный интервал, который содержит наибольшее число неотмеченных точек. Если таких интервалов несколько, то выберем из них интервал макси­мальной мощности.

Шаг 3. Включим выбранный интервал в решение и отметим его точки. Если не все точки отмечены, то идем на шаг 2.

Конец. Включенные в решение интервалы задают приближен­ную кратчайшую ДНФ функции

 

29. Метод конкурирующих интервалов для минимизации частичной булевой функции.

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

Перед изложением метода введем необходимые определения.

Рассмотрим частичную булеву функцию fх(x1,..., xn), ее точ­ку α и допустимый интервал I.

Определение.Минимальным расширением интервала I до точки α (обозначается [I,α]) называется интервал I' минималь­ной мощности, удовлетворяющий условиям:

Как следует из определения, интервал [I, α] строится так:

- внутренние компоненты интервала I остаются внутренними и в интервале [I, α],

- внешние компоненты интервала I сохраняют свое значение в интервале [I, α], если они совпадают с соответствующими ком­понентами α,

- внешние компоненты интервала I становятся внутренними в интервале [I, α], если они ортогональны соответствующим компо­нентам α.

Пример.

Определение.Интервал I и точка α называются совмести­мыми, если интервал [I,α] является допустимым для функции fх (xi, . . . , xn).

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

Пусть на k-й итерации имеются частичное решение Uk и мно­жество Mk точек функции, не содержащихся ни в одном интерва­ле из Uk (на первой итерации ). Построим бу­леву матрицу совместимости Rk, строкам которой сопоставим точки из Mk, а столбцам - интервалы из Uk. Элемент, стоящий на пересечении i-й строки и j-ro столбца, равен единице, если i-я точка совместима с j-м интервалом. Далее будем обозначать стро­ки и столбцы матрицы совместимости символами сопоставленных им точек и интервалов.

Пусть строка α матрицы совместимости не содержит единиц. Это означает, что в множестве Uk нет ни одного интервала, сов­местимого с точкой α, то есть ни один интервал не может быть расширен на множестве так, чтобы расширение вклю­чало точку α. Значит, в множество Uk следует добавить интервал, совместимый с α. Такой интервал наименьшей мощности это сама точка. Отсюда вытекает следующее правило.

Правило строки без единиц. Если в матрице совместимости есть строка, не содержащая ни одной единицы, то она удаляется из матрицы. В матрицу добавляется столбец, которому сопоста­вляется вектор из удаленной строки.

Правило столбца без единиц. Если в матрице совместимости есть столбец, не содержащий ни одной единицы, то он удаляет­ся из матрицы. Интервал из удаленного столбца расширяется до максимального и добавляется в окончательное решение.

Правило столбца с одной единицей. Если в матрице совмести­мости есть столбец I, содержащий ровно одну единицу (в строке α), то эта строка удаляется из матрицы, а интервал I заменяется на интервал [I, α].

Определение. Рангом столбца матрицы совместимости на­зовем ранг сопоставленного столбцу интервала.

Правило столбца наибольшего ранга. Если к матрице совме­стимости не применимо ни одно из трех предыдущих правил, то в ней выбирается столбец I наибольшего ранга. Среди совместимых с ним точек находится точка α с минимальным числом компонент, ортогональных внешним компонентам интервала I. Из матрицы удалются строки, которым сопоставлены точки из [I, α]. Интер­вал I заменяется на [I, α] и столбец I пересчитывается.

 


30.Система булевых функций. Кратчайшая и безызбыточная системы ДНФ.

Определение.Множество булевых функций,

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

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

Определение. Длиной системы ДНФ называется число раз­личных конъюнкций, входящих во все ДНФ системы.

Определение. Рангом системы ДНФ называется сумма ран­гов различных конъюнкций, входящих во все ДНФ системы.

Пример.Рассмотрим систему ДНФ.

В ДНФ системы входят шесть различных конъюнкций, сумма их рангов равна 15. Значит, длина этой системы 6, ранг 15.

Определение.Кратчайшей системой ДНФ (Dкрат) систе­мы булевых функций на­зывается система ДНФ наименьшей длины из всех систем ДНФ, задающих систему F.

Определение. Безызбыточной системой ДНФ(Dбез) систе­мы булевых функций на­зывается система такая, что:

- удаление любой конъюнкции K из любой ДНФ Di приводит к тому, что Di перестает задавать функцию fi(x1,... ,xn),

- если конъюнкция K входит в ДНФ Di1,...,Dik, то удале­ние любой буквы из K приводит к тому, что по крайней мере одна из этих ДНФ перестает задавать функцию fij (x1, . . . , xn).

Понятно, что система безызбыточных ДНФ будет также и безыз­быточной системой ДНФ, обратное же не всегда верно.

 

 


31. Получение приближенной кратчайшей системы ДНФ методом конкурирующих интервалов.

Определение. Минимизировать систему булевых функций это значит построить ее кратчайшую систему ДНФ.

Конечно, как и в случае одной булевой функции, возможны и другие постановки задач: построить все кратчайшие системы ДНФ, систему наименьшего ранга и так далее. Кроме того, так как минимизация системы булевых функций более сложна, чем минимизация одной функции, часто на практике строится при­ближенная кратчайшая система ДНФ, то есть система ДНФ, близкая по длине к кратчайшей.

Кроме того, часто ставится задача построения безызбыточной системы ДНФ. Это связано как с тем, что безызбыточные системы ДНФ часто оказываются близкими по длине к кратчайшим, так и с тем, что схемы, построенные по безызбыточным системам ДНФ, удобны для диагностики.

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

Во-первых, точки и интервалы сопровождаются обозначени­ями или номерами функций. Так, запись α(1) означает точку α функции f1(x1,..., xn), а запись I(1, 3) - интервал I, допустимый для функций f1(x1,..., xn) и f3(x1,..., xn) и включенный в до­статочное множество этих функций.

Во-вторых, расширение интервала I(j1, . . . ,jk) до точки α(i) сопровождается номерами функций (i, j1,..., jk).

В-третьих, интервал I(j1, . . ., jk) и точка α(i) совместимы, если и только если интервал I'(i,j1, ...,jk) = [I(j1, . . .,jk),α(i)] допу­стим для функции fi(x1, . . . , xn), fj1 (x1, . . . , xn),. . ., fjk (x1,...,xn).

Пример.Рассмотрим систему F из предыдущих примеров.

Рассмотрим точку α(f) = 1100 и интервал I(g,h) = 111-. Минимальное расширение интервала I(g,h) до точки α(f) (интервал I'(f,g,h) = 11 ) не является допустимым для функции h(a, b, c, d) и, следовательно, не может быть включен в решение. Однако если рассмотреть интервал I(g) = 111- и ту же точку α(f), то интервал I'(f,g) = [I(g),α(f)] = 11-- будет допусти­мым для функций f(a, b, c, d), g(a, b, c, d) и может быть включен в решение для этих функций.

В-четвертых, интервал I(j1,... ,jk) при применении правила столбца без единиц расширяется так, чтобы он оставался допу­стимым для всех функций fj1(x1,...,xn),..., fjk(x1,...,xn).

 

 








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



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