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

Работа по теме

МЕТОДЫ МИНИМИЗАЦИИ
ЛОГИЧЕСКИХ ФУНКЦИЙ

Ключевые понятия: логические выражения, логические функции, методы минимизации, инверсия, конъюнкция, дизъюнкция, импликация, эквиваленция.

Содержание

Введение

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

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

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

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

В связи с этим минимизация логических функций особенно актуальна.

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

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

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

Задачи исследования:

изучить основные элементы математической логики;

исследовать методы минимизации логических функций;

подобрать задачи для самостоятельной работы;

решить описанными методами подобранные задачи.

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

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

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

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

В заключении подводятся общие итоги исследования.

Логические основы функционирования ЭВМ

Элементы математической логики

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

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

Логика (от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон») – это древнейшая наука, изучающая правильность суждений, рассуждений и доказательств.

Математическая логика – это математическая дисциплина, изучающая технику доказательств .

Основоположником математической логики является великий немецкий математик Готфрид Вильгельм Лейбниц (1646 – 1716 гг.). Он выдвинул идею о применении в логике математической символики и построении логических исчислений, поставил задачу логического обоснования математики, сыграл важную роль в истории создания электронно-вычислительных машин: предложил использовать для целей вычислительной математики бинарную систему счисления. На заложенном Лейбницем фундаменте ирландский математик Джордж Буль построил здание новой науки – математической логики, – которая в отличие от обычной алгебры оперирует не числами, а высказываниями. В честь Д.Буля логические переменные в языке программирования «Паскаль» впоследствии назвали булевскими.

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

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

Различные логические выражения (высказывания) могут принимать только два значения: «истинно» или «ложно». Каждая логическая переменная может принимать только одно значение. Существуют разные варианты обозначения истинности и ложности:

Истина

True

Ложь

False

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

Рассмотрим логические операции, с помощью которых можно записать любое логическое выражение.

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

Таким образом, отрицанием некоторого высказывания называется такое высказывание, которое истинно, когда ложно, и ложно, когда истинно .

Логическая операция НЕ является унарной, т.е. имеет всего один операнд. Определение отрицания может быть записано с помощью так называемой таблицы истинности, в которой указано, указано, какие значения истинности (1, 0) принимает отрицание в зависимости от значений истинности исходного высказывания :

Логическое И (логическое умножение или конъюнкция) – это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложное выражение ложно. Конъюнкцию высказываний и обозначают: , а иногда пишут просто . Высказывания в составе конъюнкции соединены союзом «и». Определение конъюнкции может быть записано в виде таблицы истинности, в которой для каждого из четырех возможных наборов значений исходных высказываний и задается соответствующее значение конъюнкции :

Определение конъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: конъюнкция А 1 & A 2 & A 3 &...& A N истинна тогда и только тогда, когда истинны все высказывания А 1 , A 2 , A 3 , ...A N (а, следовательно, ложна, когда ложно хотя бы одно из этих высказываний) .

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

Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: дизъюнкция А 1 А 2 А 3 ... А N истинна тогда и только тогда, когда истинно хотя бы одно из высказываний А 1 , А 2 , А 3 , ..., А N (а следовательно, ложна, когда ложны все эти высказывания).

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

Логическое следование (импликация) – это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием ( ), а второе ( ) является следствием. Обозначим импликацию символом и запись « » будем читать: «Из следует ».

Запишем это определение в виде таблицы истинности:

Высказывание «Если , то » с логической точки зрения имеет тот же смысл, что и высказывание «неверно, что истинно и ложно». Это означает, что функцию импликации можно заменить комбинацией двух функций (отрицания и конъюнкции).

Логическое тождество (эквиваленция) – это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность. Обозначают эквиваленцию символом и запись « » читают « эквивалентно », или « равносильно », или « , если и только если », « тогда и только тогда, если ». Определение эквиваленции может быть записано в виде таблицы истинности:

Логические функции и их преобразование

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

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

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

;

Основываясь на законах, можно выполнять упрощение сложных логических выражений.

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

Прежде чем перейти к СДНФ и СКНФ введем некоторые понятия.

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

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

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

Например, выражение является ДНФ.

Всякую конъюнкцию элементарных дизъюнкций называют конъюнктивной нормальной формой, то есть КНФ .

Например, выражение является КНФ.

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

Например, выражение является ДНФ, но не является СДНФ; выражение является СДНФ.

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

Например, выражение .

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

переход от произвольного задания функции к ДНФ

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

Например:

переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения. Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Второй способ перехода от ДНФ к КНФ – использование дистрибутивного закона:

переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения):

переход от КНФ к СКНФ

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

переход от ДНФ к СДНФ

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

Для получения СДНФ и СКНФ из таблиц истинности необходимо выполнить следующие 4 пункта алгоритма :

СДНФ

СКНФ

Конструирование СДНФ и СКНФ начинается с таблицы истинности.

Отметим те строки таблицы, выходы которых равны

Выписываем для каждой отмеченной строки комбинацию переменных через знак

конъюнкция (&)

дизъюнкция (V)

Знаки операции отрицания расставляем следующим образом:

если переменная равна 1, то запишем саму эту переменную, если же она равна 0, то запишем ее отрицание.

если переменная равна 0, то запишем саму эту переменную, если же она равна 1, то запишем ее отрицание.

Все полученные выражения связываем операцией

дизъюнкции

конъюнкции

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

инвертор

конъюнктор

дизъюнктор

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

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

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

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

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

Кратчайшая форма записи (при этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ);

Получение минимальной формы записи (получение минимального числа символов для записи всей функции сразу).

Но следует учесть, что ни один из способов минимизации не универсален.

Для минимизации функций алгебры логики был разработан ряд методов:

метод непосредственных преобразований логических функций;

метод минимизации логических функций при помощи карт Карно;

метод Квайна-Мак-Класки;

метод Блейка-Порецкого;

метод Петрика и другие.

Остановимся более подробно на первых двух методах.

Метод непосредственных преобразований логических функций

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

При применении данного метода:

Записываются СДНФ логических функций,

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

По отношению к соседним термам применяется закон склейки.

Термы, образованные при склеивании называются импликантами.

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

Полученная в результате минимизации функция называется тупиковой.

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

Минимизируем ее описанным выше методом. Для этого добавим еще одно слагаемое и воспользуемся законами склеивания .

Получили минимальную функцию

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

Метод минимизации логических функций при помощи карт Карно

Карта Карно или карта (диаграмма) Вейча – графический способ минимизации функций алгебры логики.

Карты Карно удобны при небольшом числе переменных.

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

На рис. 1 представлены карты Вейча для двух, трех и четырех переменных соответственно .

рис. 1

Расположение групп переменных x не имеет значения, необходимо лишь, чтобы каждая клетка отличалась от любой соседней лишь на одну переменную. Согласно принятой форме построения карт соседними также считаются клетки первой и последней строк, клетки первого и последнего столбцов. Число клеток карты равно числу возможных комбинаций значений переменных (термов) и в каждую клетку записывается значение логической функции, соответствующее данному набору переменных. Если какая-то из возможных комбинаций присутствует в совершенной дизъюнктивной нормальной форме (СДНФ) записи функции, то в соответствующей клетке карты Карно ставится «1». Если какого-то терма в полученной функции нет, то в соответствующей клетке карты Карно ставится «0» .

Например, рассмотренная в предыдущем примере функция

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

рис. 2

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

Так в первой строке карты Карно (см. рис. 2 б) переменная х , встречается в комбинации с х 1 и х 2 , которые дополняют друг друга:

Таким образом, группируя две соседние клетки в верхней строке (контур на рис. 2 б), можно исключить одну переменную – х 1 .

Аналогично, группируя две соседние клетки в левом столбце (контур на рис. 2 б) и исключая отличающиеся переменные, получим упрощенное выражение – х 2 .

Полученные упрощенные выражения объединяют с помощью операции ИЛИ.

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

Допускается также иметь несколько групп перекрывающихся клеток, как в только что рассмотренном примере.

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

Для исключения n переменных общее число группируемых клеток должно быть равно 2 n . Так, для исключения одной переменной требуется объединить две соседние клетки, а для исключения трех переменных уже требуется объединить восемь соседних клеток .

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

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

Так, карта Вейча для логической функции

приведена на рисунке 3.

рис. 3

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

Упрощенное выражение логической функции имеет вид

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

Рассмотрим пример минимизации логической функции

Карта Карно для этой функции представлена на рисунке 4:

рис. 4

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

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

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

рис. 5

Булево выражение этой функции имеет вид

Четыре угловые клетки можно объединить в одну группу. Это объединение позволяет исключить две переменные (х 1 и х 2 ) и получить член .

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

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

Таким образом, мы получим минимизированную логическую функцию

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

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

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

Упростить, используя карты Карно для функции 2 переменных:

Карта Карно (диаграмма Вейча) для этой функции будет иметь вид:

В первой строке можно исключить переменную х 2 и получить упрощенное выражение х 1 .

Во втором столбце можно исключить переменную х 1

Таким образом, упрощенное выражение логической функции будет иметь вид

В первом столбце можно исключить переменную х 1 и получить упрощенное выражение х 2 .

Во второй строке можно исключить переменную и получить упрощенное выражение .

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

Таким образом, упрощенное выражение логической функции будет иметь вид

Упростить, используя карты Карно для функции 3 переменных:

Диаграмма Вейча для этой функции будет иметь вид:

х 3 и получить упрощенное выражение .

В последнем столбце можно исключить переменную х 1 и получить упрощенное выражение .

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

Таким образом, упрощенное выражение логической функции будет иметь вид

Диаграмма Вейча для этой функции будет иметь вид:

В первой строке можно исключить переменную х 3 и получить упрощенное выражение и переменную х 2 и получить упрощенное выражение .

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

Таким образом, упрощенное выражение логической функции будет иметь вид

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

Тогда диаграмма Вейча для этой функции будет иметь вид:

В первой строке можно исключить переменную х 3 и получить упрощенное выражение .

В первой строке остается выражение .

Полученные выражения соединим операцией ИЛИ.

Таким образом, упрощенное выражение логической функции будет иметь вид

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

Это значит, что соседние клетки можно группировать разными способами, главное, не забывать основное правило: для исключения n переменных общее число группируемых клеток должно быть равно 2 n .

Диаграмма Вейча для этой функции будет иметь вид:

первой строке можно исключить переменную х 3 и получить упрощенное выражение .

0 1 0 0

О втором столбце можно исключить переменную х 1 .

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

Таким образом, упрощенное выражение логической функции будет иметь вид

Диаграмма Вейча для этой функции будет иметь вид:

В первой строке можно исключить переменную х 3 и получить упрощенное выражение .

Во второй строке можно исключить переменную х 3 и получить упрощенное выражение .

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

Таким образом, упрощенное выражение логической функции будет иметь вид

Диаграмма Вейча для этой функции будет иметь вид:

В первом и последнем столбце можно исключить переменные х 1 и х 2 и получить упрощенное выражение .

Во второй строке можно исключить переменную х 2 и получить упрощенное выражение . О .

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

Таким образом, упрощенное выражение логической функции будет иметь вид

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

Заключение

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

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

Мною было подробно рассмотрено 2 метода минимизации логических функций:

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

метод минимизации с помощью диаграмм Вейча (карт Карно).

Первый метод получил широкое распространение даже в школьных учебниках информатики (например, учебники 10-11 класса Н. Угриновича , Л. Щауцуковой ), поскольку является одним из простых методов упрощения функций алгебры логики. Задания, представленные в учебниках указанных авторов, достаточно разнообразны:

упростить логическую формулу с помощью законов алгебры логики;

по заданной функции построить логическую схему;

упростить переключательную схему;

доказать с помощью таблицы истинности логическое выражение;

построить для данной функции таблицу истинности.

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

Данная тема имеет практическое значение в микроэлектронике. Кроме того, ЕГЭ по информатике и ИКТ содержит некоторое количество заданий, связанных с алгеброй логики, которые мы разделили на 4 группы .

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

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

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

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

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

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

Список литературы

Гаврюкова Г. А. Логика в информатике [Электронный ресурс]. – Режим доступа: окт. 2010).

Ивин А. А. Логика: Учебное пособие. – 2-е изд. – М.: Знание, 1998. – 233 с.

Игошин В. И. Математическая логика и теория алгоритмов: Учебное пособие для студ. высш. учеб. заведений. – 2-е изд., стер. – М.: Академия, 2008. – 448 с.

Информатика и ИКТ. Подготовка к ЕГЭ-2009. Вступительные испытания. / Под ред. Ф. Ф. Лысенко. – Ростов н/Д: Легион-М, 2009. – 208 с.

Информатика: Учебник / Б. В. Соболь [и др.]. – 3-е изд., доп. и перераб. – Ростов н/Д: Феникс, 2007. – 446 с.

Информатика: Учебное пособие / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – 3-е изд. – М.: Академия, 2004. – 848 с.

Калабеков Б. А. Цифровые устройства и микропроцессорные системы: Учебник для техникумов связи. – М.: Горячая линия – Телеком, 2000. – 336 с.

Каймин В. А. Информатика: Учебник. – 2-е изд., перераб. и доп. – М.: ИНФРА-М, 2001. – 272 с.

Коваленко А. А, Петропавловский М. Д. Основы микроэлектроники: Учебное пособие. – М.: Академия, 2006. – 240 с.

Львовский М. Б. Методическое пособие по информатике для учащихся 9-11 классов, изучающих IBM PC [Электронный ресурс]. – Режим доступа: сент. 2010).

Математические основы информатики. Элективный курс: Учебное пособие / Е. В. Андреева, Л. Л. Босова, И. Н. Фалина. – М.: БИНОМ. Лаборатория знаний, 2005. – 328 с.

Минимизация логических функций [Электронный ресурс]. – Режим доступа: авг. 2010).

Основы микроэлектроники: Учебное пособие для вузов / Н. А. Аваев, Ю. Е. Наумов, В. Т. Фролкин. – М.: Радио и связь, 1991. – 288 с.: ил.

Практикум по информатике и информационным технологиям / Н. Д. Угринович, Л. Л. Босова, Н. И. Михайлова. – 2-е изд., испр. – М.: БИНОМ. Лаборатория знаний, 2004. – 394 с.

Прикладная математика: Пособие / И. Н. Ревчук, В. К. Пчельник. – Гродно: ГрГУ им. Я. Купалы, 2007. – 128 с.

Рабкин Е. Л., Фарфоровская Ю. Б. Дискретная математика: булевы функции и элементы теории графов: Методические указания и контрольные задания [Электронный ресурс]. – Режим доступа: 7 авг. 2010).

Савельев А. Я. Основы информатики: Учебник для вузов. – М.: МГТУ им. Н. Э. Баумана, 2001. – 328 с., ил.

Степаненко И. П. Основы микроэлектроники: Учебное пособие для вузов. – 2-е изд., перераб. и доп. – М.: Лаборатория Базовых Знаний, 2001. – 488 с.

Теория и методика обучения информатике: Учебник / [М. П. Лапчик, И. Г. Семакин, Е. К. Хеннер, М. И. Рагулина и др.]; под ред. М. П. Лапчика. – М.: Академия, 2008. – 592 с.

Угринович Н. В. Информатика и ИКТ. 10 класс. Профильный уровень. – 3-е изд., испр. – М.: Бином. Лаборатория знаний, 2008. – 387 с.

Угринович Н. В. Информатика и информационные технологии: Учебник для 10-11 классов. – М.: БИНОМ. Лаборатория знаний, 2003. – 512 с.

Шауцукова Л. З. Информатика 10 – 11. – М.: Просвещение, 2004. – 420 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

б)

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

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), наз. порядком метода. Осн. группа применяемых на практике методов имеет ту особенность, что информация, необходимая для вычисления очередного значения выражается через ограниченное к-во параметров, вычисляемых на данном шаге и предыдущих шагах процесса. Метод называют -ступенчатым, если схема алгоритма имеет, начиная с некоторого следующую структуру: на шаге вычисляем параметры где - некоторое натуральное число, и вектор по ф-лам следующего вида:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Статьи по теме