Способы минимизации логических функций. Схемотехника

Существует два направления минимизации:

• Ш Кратчайшая форма записи (цель - минимизировать ранг каждого терма);
• Ш Получение минимальной формы записи (цель - получение минимального числа символов для записи всей функции сразу).
• 1. Метод эквивалентных преобразований

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

2. Метод Квайна.

При минимизации по методу Квайна предполагается, что минимизируемая логическая функция задана в виде СДНФ. Здесь используется закон неполного склеивания. Минимизация проводится в два этапа: нахождение простых импликант, расстановка меток и определение существенных импликант.

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

Для этого:

• Ш Составляются таблицы, в строках которых пишутся найденные первичные импликанты, а в столбцах указываются термы первичной ФАЛ.
• Ш Клетки этой таблицы отмечаются в том случае, если первичная импликанта входит в состав какого-нибудь первичного терма.
• Ш Задача упрощения сводится к нахождению такого минимального количества импликант, которые покрывают все столбцы.

Алгоритм метода Квайна (шаги):

• 1. Нахождение первичных импликант (исходные термы из ДНФ записывают в столбик и склеиваю сверху вниз, непомеченные импликанты переходят в функции на этом шаге).
• 2. Расстановка меток избыточности (составляется таблица, в которой строки - первичные импликанты, столбцы - исходные термы, если некоторый min-терм содержит первичный импликант, то на пересечении строки и столбца ставим метку).
• 3. Нахождение существенных импликант (если в каком-либо столбце есть только одна метка, то первичный импликант соответствующей строки является существенным).
• 4. Строка, содержащая существенный импликант и соответствующие столбцы вычеркиваются (если в результате вычеркивания столбцов появятся строки первичных импликант, которые не содержат метки или содержат одинаковые метки в строках, то такие первичные импликанты вычеркиваются, а в последнем случае оставляется одна меньшего ранга).
• 5. Выбор минимального покрытия (из таблицы, полученной на шаге 3 выбирают такую совокупность первичных импликант, которая включает метки во всех столбцах по крайней мере по одной метке в каждом, при нескольких возможных вариантах отдается предпочтение покрытию с минимальным суммарным числом элементов в импликантах, образующих покрытие).
• 6. Результат записывается в виде функции.

Пусть задана функция:

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции F каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2) конституента 2 с конституентой 4 и т. д. В результате получаем:

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

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

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

Импликантная матрица имеет вид см. табл. 1.1

Таблица 1.1 Импликантная матрица

Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной матрицы на пересечении строки (с рассматриваемой простой импликантой) и столбца (с конституентой единицы) отмечается крестиком (табл. 1.). Минимальные ДНФ строятся по импликантной матрице следующим образом:

• 1. ищутся столбцы импликантной матрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными и составляют так называемое ядро булевой функции. Ядро обязательно входит в минимальную ДНФ.
• 2. рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.

Следовательно функция имеет вид:

3. Метод Квайна-Мак-Класки.

Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Формализация производится следующим образом:

• 1. Все конституенты единицы из СДНФ булевой функции F записываются их двоичными номерами.
• 2. Все номера разбиваются на непересекающиеся группы. Признак образования і-й группы: і единиц в каждом двоичном номере конституенты единицы.
• 3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием, звездочкой и т.д.).
• 4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Образуем группы двоичных номеров. Признаком образования і-й группы является і единиц в двоичном номере конституенты единицы (табл.1.2).

Таблица 1.2 Группы двоичных номеров

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

Таблица 1.4 Результаты склеивания 2

По табл. 5. определяем совокупность простых импликант - 0--1 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам:

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

4. Метод диаграмм Вейча.

Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (Рис 1).

Рис.1.

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

Рис.2.

Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (Рис 3).

Рис.3.

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

5. Карты Карно.

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

Построим таблицу метода карт Карно (табл. 1.6).

Таблица 1.6 Карты Карно

Теперь подсчитаем совокупность всех крестиков с метками минимальным количеством крестиков. Таких крестиков в нашем случае будет 5: три четырехклеточных и два двухклеточных. Этим крестикам соответствуют следующие простые импликанты:

для первого - X 3 X 4 ;

для второго - X 1 X 3 ;

для третьего - X 2 X 3 ;

для четвертого - X 1 X 2 X 4 ;

для пятого - X 1 X 2 X 4 ;

Минимальная ДНФ будет выглядеть так:

6. Метод неопределенных коэффициентов.

Этот метод может быть использован для любого числа аргументов. Но так как этот метод достаточно громоздок, то применяется только в тех случаях, когда число аргументов не более 5-6.

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

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

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

Рис.4.

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

Запишем теперь конъюнкции, соответствующие коэффициентам, равным единицам. Мы получим минимальную ДНФ.

Наиболее употребляемая операция при минимизации функций - это операция склеивания.

AB+ ВB=B (A+ В)=B.

Рассмотрим три наиболее распространенных метода минимизации.

1. Пусть будут заданы номера наборов четырех переменных, на которых логическая функция принимает единичное значение: f (2,5,6,7,10,12,13,14)=1.

Выразим эту логическую функцию в СДНФ (символ конъюнкции писать не будем):

f (0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =

На первом этапе минимизации исходную СДНФ можно упростить за счет использования закона склеивания, тогда получим:

Обращаем внимание на то, что одну и ту же конституенту (импликанту) можно склеивать с другими конституентами (импликантами) многократно, так как в логике Буля действует закон идемпотентности:

поэтому любую конституенту можно размножить.

На втором этапе воспользуемся таблицей Куайна (табл. 8), в соответствии с которой данный метод минимизации получил свое наименование - метод Куайна. В таблице по вертикали перечислены все полученные на первом этапе упрощения импликанты, а по горизонтали - исходные конституенты. Единица в табл. 8 стоит там, где импликанта «накрывает» конституенту. Дело в том, что конституента всегда может быть заменена импликантой или даже отдельным термом по закону поглощения:

Таблица 8

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

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

2. Не менее эффективным способом минимизации логических функций является метод сочетания индексов. Для его изложения составим табл. 9, в графах которой записаны возможные сочетания индексов. В последней графе выписаны значения функции. Анализ таблицы начинается слева по столбцам. Принцип исключения i, j_кода следующий. На пересечении i_столбца, например, с сочетанием индексов 23, и j_строки, например, 3_ей, находится код 10, что соответствует импликанте. Следовательно, в этом столбце везде, где встречается код 10, т. е. в строках 2, 3, 10 и 11, эти коды исключаются, поскольку значение функции в 3_ей строке равно нулю. Теперь возьмем столбец с сочетанием индексов 124. Здесь во 2_ой и 6_ой строках оставлены коды 010, а в 10_ой и 14_ой строках - код 011. Сделано это потому, что эти коды встречаются только на строках со значением функции, равным единице. Напротив, код 110 этого же столбца встречается как при единичных значениях функции, так и при нулевых.

Таблица 9

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

Далее руководствуются следующим правилом. Для того чтобы функция приняла значение, равное единице, достаточно того, чтобы только какая-нибудь одна импликанта на строке приняла единичное значение. Прежде всего, оставляем минимальную импликанту, которая перекрывает единицы в строках 2, 6, 10 и 14. Затем, естественно, обращаемся к 12_ой строке. Здесь оставляем единственный на строке код 011, что отвечает импликанте. Эта же импликанта ответственна за 13_ую строку, оканчивающуюся тоже единицей. Осталось рассмотреть 5_ую и 7_ую строки. Общей для них является импликанта: . Таким образом, тремя импликантами мы перекрыли все единичные значения функции, что совпадает с результатом, полученным на основе таблиц Куайна.

3. Существует графический способ склеивания, который получил название метод карты Карно (представлен в табл. 10). Выделяем смежные единицы, это и будут слагаемые нашей функции.

Таблица 10

Получили два слагаемых

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

Таблица 11

Таблица 12

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

Процедура минимизации

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

Вычисление сил

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

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

Удобно разбить ячейку моделирования на субячейки - параллелепипеды (прямоугольники в двумерном случае). Вследствие сильного отталкивания на малых расстояниях, атомы не могут подходить близко друг к другу. Поэтому можно выбрать такие размеры субячеек, что в каждой из них будет находится не более одного атома.

Таким образом, алгоритм поиска атомов, удаленных от данного атома на расстояние не больше радиуса обрезания, выглядит следующим образом. По номеру атома находим координаты атома и по ним субячейку, в которой находится атом. Затем находим субячейки, удаленные от нее на расстояние не более чем. Атомы, расположенные в этих субячейках, и будут искомыми (см. рис.1). Чтобы найти номер атома, хранящегося в заданной субячейке, удобно ввести массив, каждый элемент которого соответствует определенной субячейке. В этом элементе массива будет хранится номер атома, расположенного в этой субячейке, или нуль, если субячейка пуста. Элементы этого массива обновляются на каждом шаге по времени МД. Ясно, что изложенный алгоритм обеспечивает линейный рост числа операций с ростом числа атомов в системе. Вариации этого алгоритма используются в программах МД “Gromex”, “MOLDY”, “DL_POLY” и др.

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

Рис.1 Схема поиска ближайших атомов.

Если в субячейке находится атом, то вычисляем силу, действующую на него, со стороны ближайших атомов, расположенных в близлежащих субячейках. Если же субячейка пуста, то переходим к следующей. Отметим при этом, что, например, для атома находящегося в субячейке 6 (см. рис.1) необходимо вычислить силу, действующую со стороны атомов расположенных в субячейках 1, 2, 3, 7. Силы, действующие со стороны атомов, расположенных в субячейках 5, 9, 10, 11 в силу третьего закона Ньютона, с точностью до знака уже известны. Они были вычислены, когда вычислялись силы, действующие на атомы, расположенные в этих субячейках. Таким образом, в данной организации вычислений, необходимо рассматривать лишь половину близлежайших субячеек. Далее, при переходе к смежной субячейке 7 нет необходимости исследовать все близлежащие субячейки для поиска находящихся в них близко расположенных атомов. Необходимо лишь исследовать ячейки 4 и 8. И к найденным в них атомам, добавить атомы, найденные для ячейки 6, за исключением атомов находящихся в субячейках 1 и 6. Таким образом, информация о ближайших атомах для данной субячейки не теряется, а используется при поиске ближайших атомов для смежной субячейки. Это естественно приводит к ускорению вычислений.

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

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

практике для нахождения глобального минимума в основном используется сочетание Монте-Карло метода и одного из методов локальной минимизации.

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

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

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

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

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

Среди релаксационных методов наиболее известны градиентные методы. Рассмотрим более подробно одноступенчатые методы градиентного типа. Общая схема их следующая:

В рамках этой схемы можно выделить такие модификации:

а) градиентный спуск с постоянным шагом: единичная матрица;

б) наискорейший градиентный спуск: , где определяется из условия минимума

в) метод Ньютона-Рафсона: , где - гессиан в точке

г) промежуточные схемы: . К числу наиболее распространенных двухступенчатых градиентных методов можно отнести методы сопряженных градиентов; примером двухступенчатой схемы является метод сопряженных градиентов Флетчера - Ривза:

Методы a) и б) при достаточно общих условиях (первый - при достаточно малом а) сходятся к локальному минимуму со скоростью геом. прогрессии. Метод в) при достаточно общих условиях сходится из достаточно малой окрестности минимума с квадратичной скоростью. Промежуточная схема г) более гибкая и позволяет при определенной регулировке последовательностей также получить квадратическую скорость сходимости при более слабых требованиях на начальное приближение.

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

Если градиент разрывен, перечисленные выше методы не применимы. Поэтому большое значение имеют методы минимизации выпуклых (не обязательно дифференцируемых) ф-ций; эти методы можно условно разбить на 2 группы: 1) методы градиентного типа и 2) методы «секущих плоскостей». К 1-й группе относятся различные модификации обобщенных градиентов метода, а также схемы с ускоренной сходимостью, основанные на растяжении простр. в направлении градиента или разности двух последовательных градиентов. К методам 2-й группы относится, напр., метод Келли. Пусть ЗП - выпуклое (ограниченное) мн-во, на котором определена последовательность точек, в которых вычисляется обобщенный градиент . Тогда находится как решение задачи: найти

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

Для решения спец. классов многоэкстремальных задач используются методы программирования динамического.

В наст, время создаются оптим. алгоритмы минимизации ф-ций разных классов. Пусть класс ф-ций, определенных в кубе , и имеющих в частные производные до s-го порядка, удовлетворяющие условию Липшица с константой L. Любой алгоритм минимизации из , использующий информацию о значениях f и ее производных до порядка включительно не более чем в N точках эквивалентен (в смысле результата) некоторому алгоритму А получения последовательности итераций (1) для и аппроксимации искомого значения при помощи итоговой операции

где - некоторая вычислимая ф-ция. Введем следующие обозначения:

Алгоритм, для которого достигается оптимальным. Условия означают соответственно асимптотическую оптимальность и оптимальность по порядку алгоритма Можно показать, что

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

где миним. сеть в .

Другой подход к построению оптим. алгоритмов минимизации связан с обобщением идей последовательных статистических решений. Алгоритм минимизации рассматривается как управляемая последовательность опытов, каждый из которых дает тот или иной исход. На совокупности исходов определяется априорная вероятностная мера. После получения конкретного исхода очередного опыта происходит перераспределение вероятностей по ф-ле Байеса и выбирается следующий опыт или принимается окончательное решение. Алгоритмы отличаются друг от друга правилом, по которому выбирается следующий опыт, правилами остановки и выбора окончательного решения. Качество решения определяется ф-цией потерь, которая усредняется в соответствии с полученным на данном этапе вероятностным распределением. В этих терминах ставится задача выбора оптим. алгоритма как построения последовательного байесовского правила поиска решений. Такая постановка интересна тем, что в ее рамках можно учитывать статистические свойства класса решаемых задач, сопоставлять «средние» потери, связанныз с погрешностью решения, с затратами, связанными с уточнением решения. Лит.: Любич Ю. И., Майстровский Г. Д. Общая теория релаксационных процессов для выпуклых функционалов. «Успехи математических наук», 1970, т. 25, в. 1; Михалевич В. С. Последовательные алгоритмы оптимизации и их применение. «Кибернетика», 1965, N5 1-2; Иванов В. В. Об оптимальных алгоритмах минимизации функций некоторых классов. «Кибернетика», 1972, № 4; Уайлд Д. Дк. Методы поиска экстремума. Пер. с англ. М., 1967.

В. В. Иванов, В. С. Михалевич, Н. 3. Шор.

Продолжительность: 2 часа (90 мин.)

14.1 Ключевые вопросы

14 Лекция №13. Минимизация логических функций 1

14.1 Ключевые вопросы 1

14.2 Текст лекции 1

14.2.1 Минимизация логических функций 1

14.2.1.1 Расчетный метод 1

14.2.1.2 Карты Карно 4

14.2.2 Минимизация систем логических уравнений 7

14.2.3 Минимизация частично определенных логических функций 8

14.2.4 Вопросы для контроля 10

14.2 Текст лекции

14.2.1 Минимизация логических функций

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

расчетный;

карт Карно.

14.2.1.1 Расчетный метод

Здесь применяют:

– склеивание,

– поглощение,

– развертывание.

Склеивание

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

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

Замечание:
и дистрибутивном законе конъюнкции относительно дизъюнкции (см. Лекцию № 10)

.

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

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

Замечание: Это правило основано на законе дополнительности

и дистрибутивном законе дизъюнкции относительно конъюнкции (см. Лекцию № 10)

в) Правила обобщенного склеивания.

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

Поглощение

а) Если в выражении встречается сумма двух произведений, одно из которых является частью другого, то эту сумму можно заменить меньшим произведением:

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

a (ab ) = a ; a (ab )(ac )…= a ; (ab )(abc )= ab .

Развертывание

Развертывание позволяет восстановить в формулах «потерянные» (например, в результате минимизации) переменные или перейти от ДНФ и КНФ к совершенным формам – СДНФ и СКНФ. Восстановление переменных для ДНФ и КНФ производится по–разному. Рассмотрим примеры.

Пусть имеем ДНФ

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

Пусть имеем КНФ
, где также потеряна переменнаяy . Для ее восстановления к сумме
добавляется 0, затем 0 заменяется произведением недостающей переменной на ее инверсию и применяется дистрибутивный закон

Используя развертывание, можно раскрыть смысл понятий «конституента единицы» и «конституента нуля».

Пусть n = 2 (переменныеa иb ).

Развернем единицу 1.

1= 1=
=.

Получили СДНФ функции двух переменных f = 1, где каждая конъюнкция является составляющей (конституентой) единицы.

Развернем 0.

Получили СКНФ функции двух переменных f = 0, где каждая дизъюнкция является составляющей (конституентой) нуля.

Полезность развертывания показывает пример доказательства правил обобщенного склеивания (см. п. 4.1.1):

Рассмотрим первое правило

Развернем левую часть тождества, в первом произведении которой недостает переменной c , во втором произведении недостаетb , а в третьем нетa .

После приведения подобных членов, применив простое склеивание

получаем правую часть, следовательно, тождество доказано.

Рассмотрим второе правило

Развернем левую часть тождества.

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

После приведения подобных членов, применив простое склеивание, будем иметь

Получили правую часть, следовательно, правило доказано.

Общий порядок проведения минимизации функции, заданной СДНФ, здесь следующий.

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

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

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

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

Пример 1: Минимизировать функцию

После применения операции склеивания и приведения подобных членов получаем

Обобщенное склеивание здесь можно проводить по нескольким вариантам, которые дают следующие результаты:

.

Исключены
,
,
: (
), (
), (
).

В скобках показаны термы, участвующие в обобщенном склеивании.

Исключены
,
,
: (
), (
), (
).

Как видим, здесь имеется две минимальных нормальных формы. По сложности они одинаковы.

Пример 2: Продолжая решение задачи по созданию устройства рис. 3, проведем минимизацию мажоритарной функции (см. табл. 12), для которой выше были получены СДНФ и СКНФ.

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