Минимизации функций методы. Табличные методы минимизации функций

Различают комбинационные и последовательностные логические устройства.

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

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

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

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

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

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

Исторически первыми устройствами, для описания действий которых использовали логические функции, были устройства, выполненные на релейно-контактных элементах. Для проектирования таких устройств была разработана теория релейно-контактных схем (ТРКС). Затем появились бесконтактные устройства, предназначенные только для логических преобразований сигналов и представляющие собой конструктивно оформленные изделия.

Устройства автоматики, действие которых описывается элементарными логическими функциями, обычно называют в соответствии с реализуемой ими логической операцией элементами НЕ, И, ИЛИ, И-НЕ, ИЛИ-HE (см. табл. 4.1).

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

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

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

Сочетательный закон. Результат последовательного сложения переменных или умножения их не зависит от порядка этих действий:

Закон поглощения. Сложение переменной с этой же переменной , умноженной на другую переменную , или умножение переменной на сумму этой же переменной и другой переменной равно первой переменной:

Распределительный закон. Общий множитель можно выносить за скобки , как в обычной алгебре:

Закон склеивания. Сумма произведений первой и второй переменных и второй переменной и инверсии первой переменной равна второй переменной. Произведение суммы двух переменных и суммы инверсии первой переменной со второй переменной равно второй переменной:

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

Инверсия произвольной комбинации двоичных переменных, соединенных знаком «плюс» или «умножение», эквивалентна замене в ней значений перемен-

ных их инверсиями при одновременном изменении знака «плюс» на знак «умножение» и наоборот. Например, x t x 2 +x 3 x 4 =(x l x 2)(x 3 x 4) = (x l +х 2)(х 3 +х 4). Закон инверсии встречается только в алгебре логики.

Таким образом, закон инверсии позволяет заменить операцию ИЛИ операцией И, а при необходимости - наоборот. Это особенно важно, поскольку при широком использовании интегральных логических элементов в построении логических устройств наиболее часто используют элементы базисов И-НЕ, ИЛИ-НЕ.

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

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

Последнее тождество для минимизации получено путем двойной инверсии упрощаемого выражения. Первая инверсия дает

Вторая инверсия дает

Для перехода из базиса И, ИЛИ, НЕ в базис ИЛИ-HE, а также в базис И-НЕ также выполняется преобразование логической формулы с использованием двойного отрицания. Рассмотрим пример перехода для релейной схемы на рис. 4.5, а , реализованной в базисе И, ИЛИ, НЕ (рис. 4.5, б), в базис ИЛИ-HE (рис. 4.5, в):

и в базис И-НЕ (рис. 4.5, г):

Количество черточек сверху формул равно количеству элементов отрицания, т.е. элементов ИЛИ-HE и И-НЕ. В первой формуле шесть отрицаний, и соответственно схема на рис. 4.5, в содержит шесть элементов ИЛИ-HE. Во второй формуле пять отрицаний, и соответственно схема на рис. 4.5, г содержит пять элементов И-НЕ.

Рис . 45.

а - на релейных элементах; б - на элементах ИЛИ, И, НЕ; в - на элементах

ИЛИ-HE; г-на элементах И-НЕ

Пример 4.1

Упростите выражение/ = (х + у)(х + z) и начертите релейный эквивалент до упрощения и после него. Здесь/ - выходной сигнал (состояние замыкающего контакта) релейного элемента F.

Решение

Упростим заданное выражение в соответствии с законами алгебры логики: Учитывая, что х х = х, запишем

Учитывая, что 1 + у + z = 1, окончательно запишем /= х + у z. После упрощения релейный эквивалент выглядит следующим образом:

Упростите выражение f = х-у + х y-z +y-z и начертите релейный эквивалент до упрощения и после него.

Решение

До упрощения релейный эквивалент в соответствии с заданным выражением выглядит следующим образом:

Упростим заданное выражение в соответствии с законами алгебры логики, вынося общий множитель за скобки:

Релейно-контактная схема этого выражения примет вид

Здесь учтено, что x-z =x + z иа + а = 1, или x+z+x+z = 1, где a = x + z; а = x+z. Поэтому после преобразования упрощенное выражение примет вид

После упрощения выражения релейный эквивалент выглядит так:

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

Таблица 4.2

Таблица состояния

		X + Z + X-Z

Рассмотрим пример применения алгебры логики для создания системы автоматического регулирования уровня воды в резервуаре Р (рис. 4.6). Исполнительный механизм ИМ осуществляет подачу воды в резервуар путем полного открытия или закрытия подающего вентиля А. В резервуаре имеются два датчика уровня воды: датчик верхнего уровня В и датчик нижнего уровня Н. Когда уровень воды достигнет или превысит положение датчика, сигнал его становится равным единице. Если уровень воды опустится ниже уровня датчика, сигнал на его выходе становится равным нулю.

Рис. 4.6.

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

Рис. 4.7.

на рис. 4.6

Условия работы, т.е. все комбинации входных сигналов и сигнала управления, переведены на язык алгебры логики и представлены на рис. 4.7 в верхней таблице в виде единиц и нулей. В таблице указано, при каких соотношениях входных сигналов имеется или отсутствует сигнал Q на выходе релейной САР. Сигнал на выходе является результатом логических операций над входными сигналами.

Если по данным таблицы мы попытаемся записать условия работы в виде логических функций, то обнаружим, что включенному сигналу управления соответствуют два различных соотношения входных сигналов. То же относится и к выключенному сигналу управления. Получается неоднозначность выходного сигнала в зависимости от сочетания входных сигналов. При В = 0 и Н = 1 есть положение, когда Q = 0 и есть положение, когда Q=l. Это значит, что в схеме должен быть элемент памяти, в качестве которого можно использовать уже знакомый нам RS-триггер Т. Для включения триггера используем появление нулевого сигнала на выходе 11 (II = 0). Этот сигнал инвертируется и подается на устанавливающий вход S триггера Т. Поскольку сигнал В не изменяется, то его не будем учитывать и запишем условие для включения S = Н. Условия для сброса триггера и снятия сигнала управления записываем как R = В.

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

Рассмотрим еще один пример применения алгебры логики для создания логических релейных защит электротехнических объектов на примере релейной защиты силового трансформатора, приведенной на рис. 4.8.

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

Рис. 4.8.

а - силовая схема; б - схема цепей защиты

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

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

Определение места КЗ выполняется следующим образом. При КЗ в Т1 (точка К1) трансформаторы тока ТА 1-ТАЗ обтекаются током КЗ, и срабатывают реле тока КА1-КАЗ. Трансформаторы тока ТА4-ТА5 на выходе трансформатора Т1 не обтекаются током КЗ. Реле тока КА4 и КА5 не срабатывают, их размыкающие контакты замкнуты. В такой ситуации защита должна сработать без выдержки времени. Промежуточное реле KL подает сигнал на отключение выключателя Q1.

Условия работы промежуточного реле KL для отключения без выдержки времени словесно можно сформулировать так: реле KL сработает, если сработает реле КЛ1, ИЛИ сработает реле КА2 ИЛИ, сработает реле КАЗ И НЕ сработают реле КА4 И реле КА5.

В символах математической логики условие срабатывания реле KL записывается так:

При КЗ на участке внешней сети (точка К2) трансформаторы тока ТА4 и ТА5 обтекаются током КЗ, что приводит к срабатыванию реле тока КА4 и КА5 и размыканию их размыкающих контактов в цепи релейной защиты без выдержки времени. Таким образом, работа защиты без выдержки времени блокируется. Резервная защита при КЗ в точке К2 работает с выдержкой времени.

Условие срабатывания реле времени резервной защиты формулируется словесно так: реле времени КТ сработает, если сработает реле КА1, ИЛИ сработает реле КА2, ИЛИ сработает реле КАЗ.

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

Полностью условие срабатывания промежуточного реле KL, отключающего выключатель Q1 без выдержки времени и с выдержкой времени, записывается так:

Схема на рис. 4.8, б построена в соответствии с уравнениями (4.13) и (4.14). Срабатывание защиты без выдержки времени (логической защиты) фиксируется указательным реле КН1. Срабатывание защиты с выдержкой времени фиксируется указательным реле КН2.

Продолжительность: 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), для которой выше были получены СДНФ и СКНФ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Все логические функции задаются либо в виде формулы, либо в виде таблицы значений. Иногда бывает нужно определить простейшую форму записи этой функции с минимальным количеством элементарных логических функций И, ИЛИ, НЕ для удобства работы. Для этого используются все рассмотренные операции начиная с №4 и методы Квайна и Вейча.

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

Метод Вейча (карты Карно)

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

1) Функция одной переменной:

2) Функция двух переменных:

3) Диаграмма для дизъюнкции:

4) Диаграмма для конъюнкции:

5) Для трех аргументов:

6) Для четырех аргументов:

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

б)

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

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

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

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

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

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

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

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

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

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

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

Система приведена на следующей странице.

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

V = 1 VVVVVV = 1 VVV V VV = 1 V = 1 VVV = 1 VVVVVV = 1 VVV = 1 VVVVV = 1 VVV = 1

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

= 1 = 1 = 1 = 1 = 1

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

F(X 1 X 2 X 3 X 4) = X 1 X 3 V X 2 X 3 V X 3 X 4 V X 1 X 2 X 4 V X 1 X 2 X 4 .

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

Задание 2.

2.1 Схема алгоритма для метода Квайна

1. Начало.

2. Ввести матрицу ДСНФ исходной функции.

3. Проверить на склеиваемость i-ю (i=1,m-1: где m – количество строк в ДСНФ) и j-ую (j=i+1, m) строки. Если строки склеиваются, то перейти к пункту 6, в противном случае перейти к пункту 5.

4. Формировать массив простых импликант, предварительно пометив символом ‘*’ ту переменную, по которой данные строки склеиваются.

5. Перейти к пункту 2.

6. Строку, которая не склеилась ни с одной другой строкой записать в конечный массив.

7. Перейти к пункту 2.

8. Вывод полученной матрицы.

Логическая схема алгоритма в нотации Ляпунова

V H V 1 Z 1 ­ V 2 ¯ V 3 V 4 V K

V H – начало.

V 1 – ввести матрицу ДСНФ исходной функции.

V 2 – формировать массив простых импликант, предварительно пометив символом ‘*’ ту переменную, по которой данные строки склеиваются.

V 3 – строку, которая не склеилась ни с одной другой строкой записать в конечный массив.

V 4 – вывод полученной матрицы.

Z 1 – если строки склеиваются, то перейти к пункту 3, в противном случае перейти к пункту 5.

V K – конец.

Граф-схема алгоритма.

Описание машинных процедур

Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2: byte);

Данная процедура склеивает два, передаваемых ей дизъюнкта. Дизъюнкты задаются в параметрах S1, S2. Индексы IndexS1, IndexS2 определяют индексы этих дизъюнктов в главном рабочем массиве. Алгоритм работы процедуры следующий: сначала ищется количество склеивающихся символов. Если их 0, то они одинаковые, и в конечный массив записывается только один из них. Если 1, то определяется местоположение символа, по которому данные две дизъюнкции склеиваются, и заменяем этот символ на ‘*’. Все полученные результаты заносятся в массив REZ.

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

2.2 Схема алгоритма для метода Петрика

1. Начало.

2. Ввести матрицу ДСНФ исходной функции и простые импликанты, полученные в методе Квайна.

3. Составить таблицу меток.

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