Методы минимизации логических функций. Минимизация логических функций
Студент должен:
Знать:
· Методы минимизации логических функций.
Уметь:
· Выполнять минимизацию функций методом непосредственных преобразований; Выполнять минимизацию функций методом непосредственных преобразований;
· Выполнять минимизацию функций с помощью карт Карно.
Метод непосредственных преобразований
Логическая функция, задающая принцип построения схемы цифрового устройства, может быть, как было показано выше, представлена в виде таблицы истинности или в виде СДНФ или СКНФ и может быть использована для получения логической схемы устройства. Однако полученная логическая схема, как правило, не будет оптимальна. Поэтому важным этапом синтеза логических схем является минимизация логических функций.
Минимизация (упрощение формы записи) функции является важной операцией при синтезе логической схемы, так как благодаря предварительно проведенной минимизацией схема реализуется с наименьшим числом элементов.
Для минимизации разработан ряд методов. Одним из простых методов минимизации является метод непосредственных преобразований, который осуществляется с использованием основных теорем алгебры логики.
Например, логическую функцию
в виде СДНФ, можно минимизировать следующим образом:
1. Добавим к данной функции слагаемое , которое уже есть в данной функции, используя правило х+х=х
2. Применим метод склеивания одинаково подчеркнутых элементарных конъюнкций
3. Применим метод склеивания для двух последних элементарных конъюнкций
Полученная в результате минимизации логическая функция называется тупиковой. Логическая функция может иметь несколько тупиковых форм.
Выявление и устранить избыточности в записи функции путем её преобразований с использованием аксиом, законов, тождеств и теорем алгебры логики требуют громоздких выкладок и связаны с большой затратой времени.
Карты Карно
Метод непосредственных преобразований наиболее пригоден для простых формул, когда последовательность преобразований очевидна для исполнителя. Наиболее часто этот метод применяется для окончательной минимизации выражений, полученных после минимизации их другими методами.
Стремление к алгоритмизации поиска соседних элементарных произведений привело к разработке табличных методов минимизации логических функций. Одним из них является метод, основанный на использовании карт Карно.
Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.
Карта Карно - это графическое представление таблицы истинности логических функций. Она представляет собой таблицу, содержащую по 2 n прямоугольных ячеек, где n - число логических переменных.
Например, карта Карно для функции четырех переменных имеет 2 4 = 16 ячеек.
Структура карты Карно для функций двух переменных показана на рисунке 2.2. 2
Рисунок 2.2
На рисунке 2.3 представлена структура карты Карно для функции трёх переменных.
а) таблица истинности; б) структура карты Карно
Рисунок 2.3
Карта размечается системой координат, соответствующих значениям входных переменных. Например, верхняя строка карты для функции трех переменных (рисунок 2.3) соответствует нулевому значению переменной x1, а нижняя - ее единичному значению.
Каждый столбец этой карты характеризуется значениями двух переменных: х2 и х3. Комбинация цифр, которыми отмечается каждый столбец, показывает, для каких значений переменных х2 и х3 вычисляется функция, размещаемая в клетках этого столбца.
Если на указанном наборе переменных функция равна единице, то ее СДНФ обязательно содержит элементарное произведение, принимающее на этом наборе единичное значение. Таким образом, ячейки карты Карно, представляющие функцию, содержат столько единиц, сколько элементарных произведений содержится в ее СДНФ, причем каждой единице соответствует одно из элементарных произведений.
Обратим внимание на то, что координаты строк и столбцов в карте Карно следуют не в естественном порядке возрастания двоичных кодов, а в порядке 00, 01, 11, 10. Изменение порядка следования наборов сделано для того, чтобы соседние наборы были соседними, т.е. отличались значением только одной переменной.
Ячейки, в которых функция принимает значения, равные единице, заполняются единицами. В остальные ячейки записываются нули.
Процесс минимизации рассмотрим на примере, представленном на рисунке 2.4.
а) таблица истинности; б) карта Карно
Рисунок 2.4
Сначала формируем прямоугольники, содержащие по 2k ячеек, где k - целое число.
В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям.
Например, на рисунке 2.4,б объединены ячейки с координатами 001 и 101. При объединении этих ячеек образовался прямоугольник, в котором переменная x1 изменяет свое значение. Следовательно, она исчезнет при склеивании соответствующих элементарных произведений и останутся только х2 и х3, причем переменную х2 берем в инверсном виде, т.к. она равна 0.
Ячейки, расположенные в первой строке (рисунок 2.4 б), содержат единицы и являются соседними. Поэтому все они объединяются в прямоугольник, содержащий 2 2 = 4 ячейки.
Переменные х2 и х3 в пределах прямоугольника меняют свое значение; следовательно, они исчезнут из результирующего элементарного произведения. Переменная х1 остается неизменной и равной нулю. Таким образом, элементарное произведение, полученное в результате объединения ячеек первой строки рисунка 2.4 б, содержит лишь один х1, который берем в инверсном виде, т.к. он равен 0.
Это, в частности, следует из того, что четырем ячейкам первой строки соответствует сумма четырех элементарных произведений:
Двум ячейкам сторого столбца соответствует сумма двух произведений
Функция, соответствующая рисунку 2.4 имеет вид:
Совокупность прямоугольников, покрывающих все единицы, называют покрытием. Заметим, что одна и та же ячейка (например, ячейка с координатами 001) может покрываться два или несколько раз.
Итак, можно сделать следующие выводы:
1. Формула, получающаяся в результате минимизации логической функции с помощью карт Карно, содержит сумму стольких элементарных произведений, сколько прямоугольников имеется в покрытии.
2. Чем больше ячеек в прямоугольнике, тем меньше переменных содержится в соответствующем ему элементарном произведении.
Например, для карты Карно, изображенной на рисунке 2.5 а, прямоугольнику, содержащему четыре ячейки, соответствует элементарное произведение двух переменных, а квадрату, состоящему всего лишь из одной ячейки,- элементарное произведение 
включающее все четыре переменные.
а) б) в)
Рисунок 2.5
Функция, соответствующая покрытию, показанному на рисунке 2.5 а, имеет вид:
Несмотря на то, что карты Карно изображаются на плоскости, соседство квадратов устанавливается на поверхности тора. Верхняя и нижняя границы карты Карно как бы «склеиваются», образуя поверхность цилиндра. При склеивании боковых границ получается тороидальная поверхность. Следуя изложенным рассуждениям, устанавливаем, что ячейки с координатами 1011 и 0011, изображенные на рисунке 2.5 б, являются соседними и объединяются в прямоугольник. Действительно, указанным ячейкам соответствует сумма элементарных произведений
Аналогично объединяются и остальные четыре единичные ячейки. В результате их объединения получаем элементарное произведение .
Окончательно функция, соответствующая покрытию, изображенному на рисунке 2.5 б, имеет вид
Карта Карно, показанная на рисунке 2.5 в, содержит единичные ячейки, расположенные по углам. Все четыре ячейки являются соседними, и после объединения дадут элементарное произведение
Рассмотренные выше примеры позволяют сформулировать последовательность проведения минимизации логических функций с помощью карт Карно:
1. Изображается таблица для n переменных и производится разметка ее сторон.
2. Ячейки таблицы, соответствующие наборам переменных, обращающих функцию в единицу, заполняются единицами, остальные ячейки - нулями.
3. Выбирается наилучшее покрытие таблицы правильными прямоугольниками, которые обводим контурами. В каждом прямоугольнике должно быть 2 n ячеек.
4. Одни и те же ячейки с единицами могут входить в разные контуры.
5. Количество прямоугольников должно быть минимальным, а площадь прямоугольников максимальная.
6. Для каждого прямоугольника записываем произведение только тех переменных, которые не изменяют своего значения. Если эта переменная равна нулю, то ее записывают в инверсном виде.
7. Полученные произведения соединяем знаком логического сложения.
1. Что называют минтермами и минтермами?
2.Записать функции, заданные таблицами 2.9 и 2.10 в СДНФ и СКНФ.
Таблица 2.9
3. Упростите логические функции, используя аксиомы тождества и законы алгебры логики:
a) 
c) 
Логические элементы
Студент должен
Знать:
· Таблицы логических состояний для основных функциональных логических схем;
· Основные базисы построения логических схем.
Уметь:
· Определять логические состояния на выходах цифровых схем по известным состояниям на входах;
· Выполнять логическое проектирование в базисах микросхем;
· Выбирать микросхему по справочнику, исходя из заданных параметров и условий использования.
Принцип логического устройства базируется в ИМС на работе биполярных транзисторов в режиме ключа (либо замкнут, либо разомкнут).
Логическое действие осуществляется как с одной (одновходовый логический элемент) так и с множеством (многовходовый логический элемент) входных переменных.
При работе логических устройств используются три основных действия согласно алгебры Буля – «И», «ИЛИ», «НЕ».
Логическая функция может быть выражена словесно, в алгебраической форме, таблицей истинности, называемой переключательной таблицей, с помощью временных диаграмм. Рассмотрим все варианты представления логических функций.
Процедура минимизации
Чтобы моделировать деформацию при нулевой температуре используется процедура минимизации, которая позволяет поддерживать систему вблизи локального минимума энергии все время. Деформация и минимизация выполняются одновременно. Алгоритм минимизации представляет собой модифицированный алгоритм МД. После каждого шага по времени МД для каждого атома вычисляется скалярное произведение между импульсом и силой. Для атомов, скалярное произведение для которых отрицательно, импульс зануляется, так как эти атомы движутся в направлении, в котором потенциальная энергия возрастает. Таким образом, кинетическая энергия атомов удаляется, тогда как потенциальная энергия приближается к локальному минимуму энергии вдоль направления движения атома. Такая процедура минимизации быстро сдвигает систему в окрестность локального минимума энергии, но полной сходимости не получается, так как полная сходимость требует числа шагов по времени порядка числа степеней свободы системы. Однако, обычно увеличении числа шагов процедуры минимизации приводит лишь к малым изменениям в эволюции системы.
Вычисление сил
Наибольших вычислительных усилий требует вычисление сил, действующих между атомами. Поэтому оптимизации алгоритма вычисления сил необходимо уделить особое внимание. Один из шагов в этом направлении состоит в замене сложных для вычисления выражений для сил (например, содержащих экспоненту) на легко вычисляемые выражения (например, сплайны третьего порядка). Второй шаг состоит в использовании потенциалов с ограниченным радиусом действия, или, как указывалось выше, в обрезании несущественной области потенциала, если радиус действия потенциала бесконечен. При этом необходимо вычислить только силы, действующие со стороны ближайших атомов, т.е. находящихся внутри сферы (окружности в двумерном случае) с радиусом равным радиусу обрезания.
Третий шаг состоит в оптимизации алгоритма поиска атомов, ближайших к данному атому. Дело в том, что прямолинейный перебор всех атомов, вычисление расстояний до них и отбрасывание тех атомов, расстояние до которых превышает радиус обрезания, требует количества операций пропорционального, где - число атомов в системе. Следовательно, с ростом число требуемых операций быстро возрастает, и поэтому выполнение вычислений сильно замедляется, а, для больших, делается практически невыполнимым. Таким образом, чтобы избежать этого замедления нужен алгоритм, для которого число требуемых операций росло бы с линейно, а не квадратично. В принципе такой алгоритм прост - нужно перебирать не все атомы, а только достаточно близкорасположенные. Такое утверждение представляет собой тавтологию, пока не конкретизировано понятие близкорасположенных атомов. Чтобы сделать это, разобьем ячейку моделирования на более мелкие субячейки. Тогда близкорасположенные к данному атому будут атомы, которые расположены в субячейках, соседних с субячейкой, содержащей данный атом или в субячейках соседних с соседними.
Удобно разбить ячейку моделирования на субячейки - параллелепипеды (прямоугольники в двумерном случае). Вследствие сильного отталкивания на малых расстояниях, атомы не могут подходить близко друг к другу. Поэтому можно выбрать такие размеры субячеек, что в каждой из них будет находится не более одного атома.
Таким образом, алгоритм поиска атомов, удаленных от данного атома на расстояние не больше радиуса обрезания, выглядит следующим образом. По номеру атома находим координаты атома и по ним субячейку, в которой находится атом. Затем находим субячейки, удаленные от нее на расстояние не более чем. Атомы, расположенные в этих субячейках, и будут искомыми (см. рис.1). Чтобы найти номер атома, хранящегося в заданной субячейке, удобно ввести массив, каждый элемент которого соответствует определенной субячейке. В этом элементе массива будет хранится номер атома, расположенного в этой субячейке, или нуль, если субячейка пуста. Элементы этого массива обновляются на каждом шаге по времени МД. Ясно, что изложенный алгоритм обеспечивает линейный рост числа операций с ростом числа атомов в системе. Вариации этого алгоритма используются в программах МД “Gromex”, “MOLDY”, “DL_POLY” и др.
Возможна и другая организация вычислений, которая будет удобна для организации параллельных вычислений. Именно для вычисления сил, действующих на данный атом, можно перейти от суммирования по близлежащим атомам, к суммированию по близлежащим субячейкам (см рис.1). Будем двигаться последовательно по субячейкам первого ряда. Дойдя до конца первого ряда, перейдем в начало второго ряда и т.д.
Рис.1 Схема поиска ближайших атомов.
Если в субячейке находится атом, то вычисляем силу, действующую на него, со стороны ближайших атомов, расположенных в близлежащих субячейках. Если же субячейка пуста, то переходим к следующей. Отметим при этом, что, например, для атома находящегося в субячейке 6 (см. рис.1) необходимо вычислить силу, действующую со стороны атомов расположенных в субячейках 1, 2, 3, 7. Силы, действующие со стороны атомов, расположенных в субячейках 5, 9, 10, 11 в силу третьего закона Ньютона, с точностью до знака уже известны. Они были вычислены, когда вычислялись силы, действующие на атомы, расположенные в этих субячейках. Таким образом, в данной организации вычислений, необходимо рассматривать лишь половину близлежайших субячеек. Далее, при переходе к смежной субячейке 7 нет необходимости исследовать все близлежащие субячейки для поиска находящихся в них близко расположенных атомов. Необходимо лишь исследовать ячейки 4 и 8. И к найденным в них атомам, добавить атомы, найденные для ячейки 6, за исключением атомов находящихся в субячейках 1 и 6. Таким образом, информация о ближайших атомах для данной субячейки не теряется, а используется при поиске ближайших атомов для смежной субячейки. Это естественно приводит к ускорению вычислений.
8.3. Аналитические методы минимизации переключательных функций
Метод Квайна .
Метод основан на попарном сравнении и склеивании при возможности всех конституент (членов СДНФ). Для этого каждая конституента сравнивается с последующими, что приводит к получению импликант. Полученные импликанты вновь подвергаются сравнению и при возможности склеиваются – и т.д. до тех пор, пока оставшиеся импликанты уже не будут поддаваться склеиванию. Это и есть простые импликанты, их дизъюнкция представляет собой сокращенную ДНФ.
Для упорядочения целесообразно разбивать конституенты на группы по числу неинверсированных переменных. В этом случае каждая очередная конституента, начиная сверху, сравнивается только с конституентами группы, соседней снизу, с числом неинверсированных переменных на единицу больше.
Пусть имеется переключательная функция, заданная СДНФ:
Разобьем конституенты на группы по числу неинверсированных переменных.
Римская цифра номера группы соответствует числу неинверсных переменных. Проведем линии, указывающие склеиваемые конституенты. Результатом склеивания является всегда элементарная конъюнкция, представляющая собой общую часть исходных конъюнкций (в частности, конституент).
Полученные
импликанты также допускают склеивание,
причем в результате получается одна и
та же импликанта
.
Дальнейшие склеивания невозможны, поэтому полученные импликанты – простые, а сокращенная ДНФ имеет вид:
Первый этап выполнен. На втором этапе необходимо исключить лишние простые импликанты. Это делается с помощью специальной импликантной таблицы Квайна (таблицы покрытий). Строки таблицы отмечаются простыми импликантами переключательной функции, т.е. членами сокращенной ДНФ, а столбцы – конституентами единицы, т.е. членами СДНФ переключательной функции.
Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной таблицы на пересечении строки данной простой импликанты и столбцов с конституентами единицы отмечается, например, знаком «+». Минимальные ДНФ строятся по импликантной таблице следующим образом:
1) ищутся столбцы импликантной таблицы, имеющие только один крестик, соответствующие этим крестикам простые импликанты называются базисными и составляют так называемое ядро переключательной функции. Ядро обязательно входит в минимальную ДНФ;
2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв.
Ядром
нашей функции (табл. 35) являются импликанты
и х 1 х 2 х 3 ,
т.е. функция имеет единственную тупиковую
и минимальную ДНФ:
Таблица 35
Импликантная таблица Квайна
|
Конституенты 1 (члены СДНФ) |
|||||||
|
импли-канты |
|
|
|
|
|
|
|
|
| |||||||
Видно,
что импликанта х 2 х 3 х 4
является лишней, так как она покрывает
конституенты, уже покрытые импликантами
,
х 1 х 2 х 3 .
Число крестиков в строке является степенью числа 2; более того, можно убедиться, что оно равно N=2 n - k , где k – число букв в простой импликанте, n – число переменных, от которых зависит функция.
Если вначале не задана СДНФ, то ее надо получить, используя, например, уже известные нам методы.
Ясно, что для больших импликантных таблиц трудно визуально выявить варианты с минимальным числом букв. Поэтому используется метод Петрика, позволяющий получать все тупиковые ДНФ по импликантной таблице путем построения так называемого конъюнктивного ее представления. Для этого все простые импликанты обозначаются разными буквами (А, В, С в табл. 35), а затем для каждого столбца строится дизъюнкция всех букв, обозначающих строки таблицы, пересечение которых с данным столбцом отмечено крестиком. Конъюнктивное представление импликантной матрицы образуется как конъюнкция построенных дизъюнкций для всех столбцов. К конъюнктивному представлению импликантной таблицы могут быть применены все соотношения булевой алгебры переключательных функций с целью его упрощения. После раскрытия скобок и выполнения всех возможных поглощений получается дизъюнкция конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ.
Это
означает, что тупиковая ДНФ содержит
две простые импликанты (
и одновременно С=х 1 х 2 х 3)
и имеет вид:
Метод Квайна-Мак-Класки.
Метод представляет собой формализацию метода Квайна, ориентированную на использование ЭВМ. Формализация заключается в записи конституент единицы (членов СДНФ) их двоичными номерами. Все номера разбиваются на непересекающиеся группы по числу единиц в двоичном номере. Склеивания производятся только между соседними группами. Ликвидируемый разряд обозначается знаком «–» («тире»). Дальнейшие группы из полученных импликант образуются с учетом однинакового расположения тире. Такое обозначение импликант называется обобщенными кодами. Пусть задана логическая функция
111101001000110.
Сгруппируем эти конституенты единицы по числу единиц:
Дальнейшие склеивания невозможны. Нахождение минимальных ДНФ далее производится по импликантной таблице (табл. 36):
Это означает, что тупиковые ДНФ содержат по три простые импликанты и имеют вид:
(две
инверсии);
(три
инверсии).
Таблица 36
Импликантная таблица Квайна-Мак-Класки
|
импликанты |
Конституенты единиц |
|||||||
Заметим, что склеивание двух импликант с тире возможно только при соответствующем их расположении, например:
|
|
|
|
|
Можно выбрать любую из полученных ТДНФ, а с учетом меньшего числа инверсий – первую.
Метод Блейка-Порецкого .
Метод позволяет получать сокращенную ДНФ булевой функции по ее произвольной ДНФ, а не по СДНФ, как в методах Квайна и Квайна-Мак-Класки, используя закон обобщенного склеивания . В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции провести всевозможные операции, обратные обобщенному склеиванию, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции.
Пусть задана ДНФ функции:
Видно, что к первой и второй конъюнкциям можно применить закон обобщенного склеивания по переменной х 1 ; получим:
Аналогично для первой и третьей конъюнкций:
т.е. все остается, как есть!
Вторая и третья конъюнкции допускают обобщенное склеивание по х 2:
Переходим к ДНФ:
После применения закона идемпотентности (повторения) и поглощения получаем:
Попытки дальнейшего применения обобщенного склеивания и поглощения не дают результата. Следовательно, получена сокращенная ДНФ функции.
Таблица 37
Импликантная таблица для иллюстрации метода Блейка-Порецкого
|
импликанты |
Наборы функции и ее значения |
|||||||||
Таким
образом, рабочие (единичные) наборы
можно покрыть тремя простыми импликантами,
например,
,
,
.
В ядро входят импликанты
,
.
Тогда тупиковые ДНФ имеют вид:
(лучше по числу инверсий).
Существует два направления минимизации:
- Ш Кратчайшая форма записи (цель - минимизировать ранг каждого терма);
- Ш Получение минимальной формы записи (цель - получение минимального числа символов для записи всей функции сразу).
- 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, также вычеркиваются).
Запишем теперь конъюнкции, соответствующие коэффициентам, равным единицам. Мы получим минимальную ДНФ.
Методы поиска минимумов функций. Поиск максимумов сводится к поиску минимумов путем изменения знака ф-ции. М. ф. м.- раздел вычислительной математики, играющий большую роль в таких приложениях, как выбор оптим. вариантов в задачах планирования, проектирования и операций исследования, управления технологическими процессами, управления движением сложных объектов и т. п. М. ф. м. применяются также для решения систем ур-ний и неравенств при отыскании спектра операторов, при решении краевых задач и т. п.
Наиболее изучены М. ф. м- применительно к ф-циям, определенным во всем -мерном евклидовом простр. Рассмотрим их, не касаясь дискретных и дискретно-непрерывных задач минимизации, а также задач минимизации при наличии ограничений. Последние во многих случаях можно свести к задаче безусловной минимизации (напр., с использованием штрафных ф-ций). Не будем рассматривать методы нахождения минимума, основанные на непосредственном использовании необходимых условий экстремума, т. к. решение получаемых при этом систем нелинейных ур-ний можно рассматривать как задачу минимизации суммы квадратов невязок (или максимума модуля невязок). Возможность применения и сравнительная эффективность различных М. ф. м. во многом определяется классом ф-ций, к которому они применяются. Большинство М. ф. м. дают возможность находить локальный минимум, и лишь априорная информация о свойствах ф-ции (выпуклость, унимодальность) позволяет считать этот минимум глобальным. Методы, гарантирующие поиск глобального минимума с заданной точностью для достаточно общих классов ф-ций, являются весьма трудоемкими. На
практике для нахождения глобального минимума в основном используется сочетание Монте-Карло метода и одного из методов локальной минимизации.
Широкий класс М. ф. м. описывают следующей вычислительной схемой. Пусть минимизируемая ф-ция, определенная в произвольно выбранная начальная точка. Допустим, что имеет непрерывные частные производные до порядка включительно будем рассматривать как производную нулевого порядка). Для получения последовательных приближений к локальному минимуму строится последовательность точек по ф-лам следующего вида:
где обозначает вектор частных производных порядка вычислимые ф-ции своих аргументов. Порядок высших частных производных, вычисляемых для реализации ф-лы (1), наз. порядком метода. Осн. группа применяемых на практике методов имеет ту особенность, что информация, необходимая для вычисления очередного значения выражается через ограниченное к-во параметров, вычисляемых на данном шаге и предыдущих шагах процесса. Метод называют -ступенчатым, если схема алгоритма имеет, начиная с некоторого следующую структуру: на шаге вычисляем параметры где - некоторое натуральное число, и вектор по ф-лам следующего вида:
(начальные параметры вычисляются с помощью спец. процедур). В широко распространенных методах спуска оператор конкретизируется в следующей форме:
где вещественное число, которое наз. шаговым множителем, вектор определяет направление спуска. Среди методов спуска выделяются методы монотонного спуска или релаксационные методы. Метод релаксационным, если при к Бели непрерывно дифференцируема, то релаксационность метода (3) обеспечивается, когда направление спуска образует острый угол с направлением градиента и достаточно мал. Обшая теория релаксационных процессов развита наиболее полно для случая выпуклых ф-ций. В качестве осн. параметров, характеризующих процесс, рассматриваются углы релаксации между и направлением градиента), а также множители релаксации определяемые равенством
где градиент ф-ции (для квадратичного функционала при наискорейшем спуске). Обозначим через приведенный коэфф. релаксации. Необходимое и достаточное условие сходимости релаксационного процесса для сильно выпуклой ф-ции :
Среди релаксационных методов наиболее известны градиентные методы. Рассмотрим более подробно одноступенчатые методы градиентного типа. Общая схема их следующая:
В рамках этой схемы можно выделить такие модификации:
а) градиентный спуск с постоянным шагом: единичная матрица;
б) наискорейший градиентный спуск: , где определяется из условия минимума
в) метод Ньютона-Рафсона: , где - гессиан в точке
г) промежуточные схемы: . К числу наиболее распространенных двухступенчатых градиентных методов можно отнести методы сопряженных градиентов; примером двухступенчатой схемы является метод сопряженных градиентов Флетчера - Ривза:
Методы a) и б) при достаточно общих условиях (первый - при достаточно малом а) сходятся к локальному минимуму со скоростью геом. прогрессии. Метод в) при достаточно общих условиях сходится из достаточно малой окрестности минимума с квадратичной скоростью. Промежуточная схема г) более гибкая и позволяет при определенной регулировке последовательностей также получить квадратическую скорость сходимости при более слабых требованиях на начальное приближение.
Недостатком методов в), г) является необходимость вычисления гессиана. От этого недостатка избавлены методы сопряженных градиентов и так называемые алгоритмы с изменяемой метрикой, обладающие свойствами ускоренной сходимости для достаточно гладких ф-ций в окрестности минимума. Схемы алгоритмов с изменяемой метрикой по своему характеру являются комбинацией схемы сопряженных градиентов и метода Ньютона - Рафсона. Одновременно с движением по схеме типа сопряженных градиентов происходит итеративная аппроксимация матрицы, обратной гессиану в точке минимума. После каждых п шагов процесса происходит шаг по методу Ньютона-Рафсона, где вместо выступает ее аппроксимация.
Если градиент разрывен, перечисленные выше методы не применимы. Поэтому большое значение имеют методы минимизации выпуклых (не обязательно дифференцируемых) ф-ций; эти методы можно условно разбить на 2 группы: 1) методы градиентного типа и 2) методы «секущих плоскостей». К 1-й группе относятся различные модификации обобщенных градиентов метода, а также схемы с ускоренной сходимостью, основанные на растяжении простр. в направлении градиента или разности двух последовательных градиентов. К методам 2-й группы относится, напр., метод Келли. Пусть ЗП - выпуклое (ограниченное) мн-во, на котором определена последовательность точек, в которых вычисляется обобщенный градиент . Тогда находится как решение задачи: найти
Метод Келли сходится по функционалу при любом начальном . Из распространенных методов минимизации следует отметить, в частности, метод оврагов для минимизации ф-ций с сильно вытянутыми гиперповерхностями уровня; методы покоординатного поискас изменяемой системой координат; методы случайного поиска; комбинированные методы быстрого спуска и случайного поиска, когда направление убывания ф-ции находится методом Монте-Карло; методы дифференциального спуска, стохастической аппроксимации методы и др. В задачах оптим. регулирования большое значение имеют методы поиска нулевого порядка. В основе алгоритмов минимизации для этого случая обычно лежит идея линейной или квадратичной аппроксимации минимизируемой ф-ции или разностной аппроксимации соответствующих частных производных. Для поиска экстремума глобального предложен ряд методов. Осн. из них: метод Монте-Карло, комбинация метода Монте-Карло определения начальной точки с одним из алгоритмов локального поиска, методы, основанные на построении нижней огибающей данной ф-ции, методы последовательного отсечения подмн-в, методы построения траекторий, всюду плотно покрывающих область определения ф-ции, и минимизации вдоль этих траекторий.
Для решения спец. классов многоэкстремальных задач используются методы программирования динамического.
В наст, время создаются оптим. алгоритмы минимизации ф-ций разных классов. Пусть класс ф-ций, определенных в кубе , и имеющих в частные производные до s-го порядка, удовлетворяющие условию Липшица с константой L. Любой алгоритм минимизации из , использующий информацию о значениях f и ее производных до порядка включительно не более чем в N точках эквивалентен (в смысле результата) некоторому алгоритму А получения последовательности итераций (1) для и аппроксимации искомого значения при помощи итоговой операции
где - некоторая вычислимая ф-ция. Введем следующие обозначения:
Алгоритм, для которого достигается оптимальным. Условия означают соответственно асимптотическую оптимальность и оптимальность по порядку алгоритма Можно показать, что
причем выбор , влияет лишь на константу в указанной оценке. В частном случае и имеем:
где миним. сеть в .
Другой подход к построению оптим. алгоритмов минимизации связан с обобщением идей последовательных статистических решений. Алгоритм минимизации рассматривается как управляемая последовательность опытов, каждый из которых дает тот или иной исход. На совокупности исходов определяется априорная вероятностная мера. После получения конкретного исхода очередного опыта происходит перераспределение вероятностей по ф-ле Байеса и выбирается следующий опыт или принимается окончательное решение. Алгоритмы отличаются друг от друга правилом, по которому выбирается следующий опыт, правилами остановки и выбора окончательного решения. Качество решения определяется ф-цией потерь, которая усредняется в соответствии с полученным на данном этапе вероятностным распределением. В этих терминах ставится задача выбора оптим. алгоритма как построения последовательного байесовского правила поиска решений. Такая постановка интересна тем, что в ее рамках можно учитывать статистические свойства класса решаемых задач, сопоставлять «средние» потери, связанныз с погрешностью решения, с затратами, связанными с уточнением решения. Лит.: Любич Ю. И., Майстровский Г. Д. Общая теория релаксационных процессов для выпуклых функционалов. «Успехи математических наук», 1970, т. 25, в. 1; Михалевич В. С. Последовательные алгоритмы оптимизации и их применение. «Кибернетика», 1965, N5 1-2; Иванов В. В. Об оптимальных алгоритмах минимизации функций некоторых классов. «Кибернетика», 1972, № 4; Уайлд Д. Дк. Методы поиска экстремума. Пер. с англ. М., 1967.
В. В. Иванов, В. С. Михалевич, Н. 3. Шор.
