Минимизации функций методы. Табличные методы минимизации функций
Студент должен:
Знать:
· Методы минимизации логических функций.
Уметь:
· Выполнять минимизацию функций методом непосредственных преобразований; Выполнять минимизацию функций методом непосредственных преобразований;
· Выполнять минимизацию функций с помощью карт Карно.
Метод непосредственных преобразований
Логическая функция, задающая принцип построения схемы цифрового устройства, может быть, как было показано выше, представлена в виде таблицы истинности или в виде СДНФ или СКНФ и может быть использована для получения логической схемы устройства. Однако полученная логическая схема, как правило, не будет оптимальна. Поэтому важным этапом синтеза логических схем является минимизация логических функций.
Минимизация (упрощение формы записи) функции является важной операцией при синтезе логической схемы, так как благодаря предварительно проведенной минимизацией схема реализуется с наименьшим числом элементов.
Для минимизации разработан ряд методов. Одним из простых методов минимизации является метод непосредственных преобразований, который осуществляется с использованием основных теорем алгебры логики.
Например, логическую функцию
в виде СДНФ, можно минимизировать следующим образом:
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) 
Логические элементы
Студент должен
Знать:
· Таблицы логических состояний для основных функциональных логических схем;
· Основные базисы построения логических схем.
Уметь:
· Определять логические состояния на выходах цифровых схем по известным состояниям на входах;
· Выполнять логическое проектирование в базисах микросхем;
· Выбирать микросхему по справочнику, исходя из заданных параметров и условий использования.
Принцип логического устройства базируется в ИМС на работе биполярных транзисторов в режиме ключа (либо замкнут, либо разомкнут).
Логическое действие осуществляется как с одной (одновходовый логический элемент) так и с множеством (многовходовый логический элемент) входных переменных.
При работе логических устройств используются три основных действия согласно алгебры Буля – «И», «ИЛИ», «НЕ».
Логическая функция может быть выражена словесно, в алгебраической форме, таблицей истинности, называемой переключательной таблицей, с помощью временных диаграмм. Рассмотрим все варианты представления логических функций.
Алгебры логики
3.3.1. Минимизация ФАЛ с помощью матрицы Карно
Матрица Карно представляет собой своеобразную таблицу истинности ФАЛ, которая разбита на клетки. Количество клеток матрицы равно 2 n , где n – число аргументов ФАЛ. Столбцы и строки матрицы обозначаются наборами аргументов. Каждая клетка матрицы соответствует конституэнте единицы ФАЛ (двоичному числу). Двоичное число клетки состоит из набора аргументов строки и столбца. Матрица Карно для ФАЛ, зависящей от двух аргументов, представлена в виде таблицы 3.3., от трех аргументов таблицей 3.4. и от четырех аргументов таблицей 3.5.
Таблица 3.3.
Таблица 3.5.
| х 3 х 4 х 1 х 2 | ||||
| 0 0 0 0 | 0 0 0 1 | 0 0 1 1 | 0 0 1 0 | |
| 0 1 0 0 | 0 1 0 1 | 0 1 1 1 | 0 1 1 0 | |
| 1 1 0 0 | 1 1 0 1 | 1 1 1 1 | 1 1 1 0 | |
| 1 0 0 0 | 1 0 0 1 | 1 0 1 1 | 1 0 1 0 |
Клетки матриц (таблицы 3.3., 3.4. и 3.5.) пронумерованы десятичными эквивалентами двоичных чисел клеток. Рядом расположенные клетки матриц, как по горизонтали, так и по вертикали, содержат соседние двоичные числа. Кроме этого соседние двоичные числа находятся во всех столбцах верхней и нижней строк, так же как во всех строках крайних столбцов.
Процесс минимизации ФАЛ с помощью матрицы Карно основан на законе склеивания соседних двоичных чисел. Можно склеивать двоичные числа рядом расположенных клеток, но рекомендуется склеивать наборы аргументов, которыми обозначены строки и столбцы матриц. Рассмотрим склеивание двоичных чисел клеток первого столбца матрицы (табл. 3.5.).
Клетки 0 и 4, соответственно двоичные числа 0000 и 0100, результат склеивания 0-00.
Клетки 8 и 12, двоичные числа 1000 и 1100, результат 1-00. Полученные импликанты склеиваются между собой, т.к. тире стоит в одном и том же разряде и двоичные числа импликант являются соседними, окончательный результат - - 00.
Клетки 8 и 12
Таким образом, если склеиваются все двоичные числа одного столбца, то пропадают те разряды, которыми обозначены строки. Аналогично, если будут склеиваться все двоичные числа одной строки, например 4, 5, 7, 6, то пропадают все разряды, которыми обозначены столбцы, т.е. результат будет следующий 01- -.
Если будут склеиваться двоичные числа только двух любых клеток, то прочерк ставиться вместо того разряда двоичных чисел строки или столбца, который изменится при переходе клеток из одной строчки в другую (или из одного столбца в другой). Например, склеиваются числа клеток 5 и 13, получим результат -101, или клеток 7 и 6 результат 011-.
При склеивании двоичных чисел восьми рядом расположенных клеток пропадает три переменные, например для клеток 3, 7, 15, 11, 2, 6, 14, 10 пропадают переменные х 1 , х 2 , х 3 . Переменные х 1 , х 2 пропадают потому, что склеиваются все клетки столбцов, а х 3 потому, что последние два столбца склеиваются между собой.
Прежде, чем рассмотреть примеры минимизации ФАЛ с помощь матрицы Карно, необходимо дать классификацию наборов аргументов, с помощью которых определяются функции алгебры логики.
Известно, что для каждой ФАЛ имеет место количество наборов аргументов 2 n , где n – число аргументов от которых зависит функция или логическое выражение.
Наборы аргументов делятся на три вида
1. Наборы аргументов, на которых функция равна единице, называются рабочими.
2. Наборы аргументов, на которых функция равна нулю, называются запрещенными.
3. Наборы аргументов, на которых функция может быть равна или единице, или нулю, называются безразличными.
Если заданная ФАЛ не имеет безразличных наборов, то она может быть представлена в буквенном выражении в виде СДНФ. При наличии в заданной ФАЛ безразличных наборов, ее представление может иметь следующую форму.
где – десятичные эквиваленты рабочих наборов,
– десятичные эквиваленты запрещенных наборов.
Наборы аргументов, которых нет среди рабочих и запрещенных, будут безразличными.
Пример 3.3. Минимизировать заданную ФАЛ в виде СДНФ с помощью матрицы Карно .
Следовательно, функция задана только рабочими наборами. Остальные будут запрещенными. Функция зависит только от трех аргументов. Строим матрицу Карно и в ее клетках, которые соответствуют рабочим наборам ставим единицы, а в остальных клетках ставим нули.
Таблица 3.5.
| х 2 х 3 х 1 | ||||
| 0 | ||||
Для минимизации клетки матрицы, в которых стоят единицы, объединяются в контуры. В контур могут включаться две клетки, четыре или все восемь. В данном примере в контур включены четыре рядом расположенные клетки одной строки. Импликантой заданного контура будет 1 - -. Результат минимизации следующий , т.е. произошло сокращение заданной функции в СДНФ на 11 букв.
Пример 3.4. Минимизировать логическое выражение, заданное рабочими и запрещенными наборами с помощью матрицы Карно.
Строим матрицу Карно на четыре переменных и заполним клетки единицами и нулями соответственно для рабочих и запрещенных наборов.
Таблица 3.6.
| х 3 х 4 х 1 х 2 |
 00
| |||
| (1) | ||||
| (1) | (1) | |||
При объединении клеток с единицами в контуры желательно, чтобы в каждый контур включалось наибольшее число клеток из максимально возможного. Для этого клетки некоторых безразличных наборов используем как клетки рабочих наборов, подставив в них единицы в скобках. В результате получим три контура, содержащие по 4 клетки. В обобщенном коде контура, включающего в себя все клетки одной строки, пропадают переменные х 2 х 3 (10 - -). В обобщенном коде контура, включающего все клетки одного столбца пропадают переменные х 1 х 2 (- - 11) и для контура, содержащего по две клетки двух строк пропадают переменные х 2 (при переходе в контуре из одной строки в другую) и х 3 (при переходе из одного столбца в другой). В результате получим минимальную ДНФ в следующем виде
Возможные варианты объединения клеток матрицы Карно в контуры показаны на рисунке 3.4.
 х
3 х
4
х
1 х
2
| ||||||||||||||||
| А = 0 - 0 - | З = - 0 - 0 | |||||||||||||||
| Н | Б = 1 - 1 - | К = - - - 1 | ||||||||||||||
| В = - - 0 0 | Л = - 1 - - | |||||||||||||||
| Г = 1 0 - - | М = - - - 0 | |||||||||||||||
| Д = - 0 0 1 | Н = - 0 - - | |||||||||||||||
| Е = - 0 1 - | ||||||||||||||||
| Ж = - 1 - 1 |
Рис. 3.1. Возможные варианты объединения клеток матрицы Карно в контуры
3.3.2. Минимизация функций алгебры логики с помощью матрицы на пять переменных
Матрица минимизации на пять переменных строится аналогично матрице Карно, т.е. в этой матрице рядом расположенные столбцы и строки должны быть обозначены соседними двоичными числами наборов переменных
В матрице на пять переменных (таблица 3.7.) строкам соответствуют наборы переменных х 1 х 2 х 3 , а столбцам наборы переменных х 4 х 5 . Каждой клетке матрицы соответствует пятиразрядное двоичное число. В клетках матрицы (табл. 3.7.) проставлены десятичные эквиваленты соответствующих двоичных чисел.
Таблица 3.7.
| х 4 х 5 х 1 х 2 х 3 | ||||
Минимизация ФАЛ с помощью матрицы на пять переменных заключается в объединении клеток с рабочими наборами (включая при необходимости и клетки с безразличными наборами) в контуры и получении для этих контуров соответствующих им обобщенных кодов.
Особенность здесь заключается в том, что в столбцах матрицы на пять переменных объединять по четыре клетки в контуры можно только или четыре клетки сверху, или четыре клетки внизу, или четыре клетки посередине. Например, для последнего столбца матрицы контуры могут состоять из клеток 2, 6, 14, 10, или 26, 30, 22, 18 или 14, 10, 26, 30.
Пример 3.6. Минимизировать с помощью матрицы на пять переменных следующее логическое выражение
Строим матрицу на пять переменных и заполняем клетки рабочих наборов единицами, запрещенных – нулями.
Объединяем в контуры клетки с рабочими наборами, включая в них необходимые клетки безразличных наборов. Для каждого контура определяем обобщенных код.
Таблица 3.8.
х
4 х
5
 х
1 х
2 х
3
| ||||
| (1) | (1) | (1) | ||
| (1) | ||||
| (1) | (1) | |||
| (1) | (1) | |||
| (1) | (1) | |||
| (1) | ||||
| (1) | (1) | |||
Получаем минимальную ДНФ
Контрольные вопросы
1. Дать определение сокращенной ДНФ.
2. Что представляет собой тупиковая ДНФ?
3. Как выбирается минимальная ДНФ из тупиковых ДНФ?
4. Для чего используется импликантная таблица и как она строится?
5. Пояснить аналитический способ минимизации ФАЛ Квайна-Мак-Класски.
6. Как строится матрица Карно на три и четыре переменных?
7. Минимизировать аналитическим способом следующие логические выражения, заданные только рабочими наборами
8. Минимизировать с помощью матрицы Карно логические выражения, заданные рабочими и запрещенными наборами
Похожая информация.
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
Импликантная таблица для иллюстрации метода Блейка-Порецкого
|
импликанты |
Наборы функции и ее значения |
|||||||||
Таким
образом, рабочие (единичные) наборы
можно покрыть тремя простыми импликантами,
например,
,
,
.
В ядро входят импликанты
,
.
Тогда тупиковые ДНФ имеют вид:
(лучше по числу инверсий).
Все логические функции задаются либо в виде формулы, либо в виде таблицы значений. Иногда бывает нужно определить простейшую форму записи этой функции с минимальным количеством элементарных логических функций И, ИЛИ, НЕ для удобства работы. Для этого используются все рассмотренные операции начиная с №4 и методы Квайна и Вейча.
Метод Квайна позволяет найти простейшую нормальную дизъюнктивную форму логического выражения, т.е. записать логическое выражение в виде дизъюнкции или конъюнкции, при этом знак инверсии может стоять только над одним аргументом или не стоять вообще. Алгоритм дается в специальной литературе.
Метод Вейча (карты Карно)
В этом методе для изображения функции n переменных рисуется специальная таблица, которая содержит 2 n клеток. В каждой клетке ставится соответствие одному из наборов n переменных. В клетке записывается значение, принимаемое функцией при этом наборе аргументов. Все клетки, соответствующие наборам содержащие некоторую переменную без знака инверсии образуют область из 2 n -1 клеток. Эта область называется областью данной переменной (например, область переменной х). Остальные клетки образуют область этой инверсной переменной. Возможные наборы аргументов распределены по клеткам таким образом, чтобы границы областей всех переменных и их инверсии были четки, а принадлежность любой клетки к той или иной область зрительно легко выявлялась.
1) Функция одной переменной:
2) Функция двух переменных:
3) Диаграмма для дизъюнкции:
4) Диаграмма для конъюнкции:
5) Для трех аргументов:
6) Для четырех аргументов:
Можно минимизировать заданное логическое выражение, объединив в группы стоящие рядом единицы и при этом исключать ту переменную, которая переходит из прямого в инверсное состояние. Объединять можно не только по вертикали и горизонтали, но и по краям, так как в общем случае карта Карно образует тор. Пример:
б) 
Методы поиска минимумов функций. Поиск максимумов сводится к поиску минимумов путем изменения знака ф-ции. М. ф. м.- раздел вычислительной математики, играющий большую роль в таких приложениях, как выбор оптим. вариантов в задачах планирования, проектирования и операций исследования, управления технологическими процессами, управления движением сложных объектов и т. п. М. ф. м. применяются также для решения систем ур-ний и неравенств при отыскании спектра операторов, при решении краевых задач и т. п.
Наиболее изучены М. ф. м- применительно к ф-циям, определенным во всем -мерном евклидовом простр. Рассмотрим их, не касаясь дискретных и дискретно-непрерывных задач минимизации, а также задач минимизации при наличии ограничений. Последние во многих случаях можно свести к задаче безусловной минимизации (напр., с использованием штрафных ф-ций). Не будем рассматривать методы нахождения минимума, основанные на непосредственном использовании необходимых условий экстремума, т. к. решение получаемых при этом систем нелинейных ур-ний можно рассматривать как задачу минимизации суммы квадратов невязок (или максимума модуля невязок). Возможность применения и сравнительная эффективность различных М. ф. м. во многом определяется классом ф-ций, к которому они применяются. Большинство М. ф. м. дают возможность находить локальный минимум, и лишь априорная информация о свойствах ф-ции (выпуклость, унимодальность) позволяет считать этот минимум глобальным. Методы, гарантирующие поиск глобального минимума с заданной точностью для достаточно общих классов ф-ций, являются весьма трудоемкими. На
практике для нахождения глобального минимума в основном используется сочетание Монте-Карло метода и одного из методов локальной минимизации.
Широкий класс М. ф. м. описывают следующей вычислительной схемой. Пусть минимизируемая ф-ция, определенная в произвольно выбранная начальная точка. Допустим, что имеет непрерывные частные производные до порядка включительно будем рассматривать как производную нулевого порядка). Для получения последовательных приближений к локальному минимуму строится последовательность точек по ф-лам следующего вида:
где обозначает вектор частных производных порядка вычислимые ф-ции своих аргументов. Порядок высших частных производных, вычисляемых для реализации ф-лы (1), наз. порядком метода. Осн. группа применяемых на практике методов имеет ту особенность, что информация, необходимая для вычисления очередного значения выражается через ограниченное к-во параметров, вычисляемых на данном шаге и предыдущих шагах процесса. Метод называют -ступенчатым, если схема алгоритма имеет, начиная с некоторого следующую структуру: на шаге вычисляем параметры где - некоторое натуральное число, и вектор по ф-лам следующего вида:
(начальные параметры вычисляются с помощью спец. процедур). В широко распространенных методах спуска оператор конкретизируется в следующей форме:
где вещественное число, которое наз. шаговым множителем, вектор определяет направление спуска. Среди методов спуска выделяются методы монотонного спуска или релаксационные методы. Метод релаксационным, если при к Бели непрерывно дифференцируема, то релаксационность метода (3) обеспечивается, когда направление спуска образует острый угол с направлением градиента и достаточно мал. Обшая теория релаксационных процессов развита наиболее полно для случая выпуклых ф-ций. В качестве осн. параметров, характеризующих процесс, рассматриваются углы релаксации между и направлением градиента), а также множители релаксации определяемые равенством
где градиент ф-ции (для квадратичного функционала при наискорейшем спуске). Обозначим через приведенный коэфф. релаксации. Необходимое и достаточное условие сходимости релаксационного процесса для сильно выпуклой ф-ции :
Среди релаксационных методов наиболее известны градиентные методы. Рассмотрим более подробно одноступенчатые методы градиентного типа. Общая схема их следующая:
В рамках этой схемы можно выделить такие модификации:
а) градиентный спуск с постоянным шагом: единичная матрица;
б) наискорейший градиентный спуск: , где определяется из условия минимума
в) метод Ньютона-Рафсона: , где - гессиан в точке
г) промежуточные схемы: . К числу наиболее распространенных двухступенчатых градиентных методов можно отнести методы сопряженных градиентов; примером двухступенчатой схемы является метод сопряженных градиентов Флетчера - Ривза:
Методы a) и б) при достаточно общих условиях (первый - при достаточно малом а) сходятся к локальному минимуму со скоростью геом. прогрессии. Метод в) при достаточно общих условиях сходится из достаточно малой окрестности минимума с квадратичной скоростью. Промежуточная схема г) более гибкая и позволяет при определенной регулировке последовательностей также получить квадратическую скорость сходимости при более слабых требованиях на начальное приближение.
Недостатком методов в), г) является необходимость вычисления гессиана. От этого недостатка избавлены методы сопряженных градиентов и так называемые алгоритмы с изменяемой метрикой, обладающие свойствами ускоренной сходимости для достаточно гладких ф-ций в окрестности минимума. Схемы алгоритмов с изменяемой метрикой по своему характеру являются комбинацией схемы сопряженных градиентов и метода Ньютона - Рафсона. Одновременно с движением по схеме типа сопряженных градиентов происходит итеративная аппроксимация матрицы, обратной гессиану в точке минимума. После каждых п шагов процесса происходит шаг по методу Ньютона-Рафсона, где вместо выступает ее аппроксимация.
Если градиент разрывен, перечисленные выше методы не применимы. Поэтому большое значение имеют методы минимизации выпуклых (не обязательно дифференцируемых) ф-ций; эти методы можно условно разбить на 2 группы: 1) методы градиентного типа и 2) методы «секущих плоскостей». К 1-й группе относятся различные модификации обобщенных градиентов метода, а также схемы с ускоренной сходимостью, основанные на растяжении простр. в направлении градиента или разности двух последовательных градиентов. К методам 2-й группы относится, напр., метод Келли. Пусть ЗП - выпуклое (ограниченное) мн-во, на котором определена последовательность точек, в которых вычисляется обобщенный градиент . Тогда находится как решение задачи: найти
Метод Келли сходится по функционалу при любом начальном . Из распространенных методов минимизации следует отметить, в частности, метод оврагов для минимизации ф-ций с сильно вытянутыми гиперповерхностями уровня; методы покоординатного поискас изменяемой системой координат; методы случайного поиска; комбинированные методы быстрого спуска и случайного поиска, когда направление убывания ф-ции находится методом Монте-Карло; методы дифференциального спуска, стохастической аппроксимации методы и др. В задачах оптим. регулирования большое значение имеют методы поиска нулевого порядка. В основе алгоритмов минимизации для этого случая обычно лежит идея линейной или квадратичной аппроксимации минимизируемой ф-ции или разностной аппроксимации соответствующих частных производных. Для поиска экстремума глобального предложен ряд методов. Осн. из них: метод Монте-Карло, комбинация метода Монте-Карло определения начальной точки с одним из алгоритмов локального поиска, методы, основанные на построении нижней огибающей данной ф-ции, методы последовательного отсечения подмн-в, методы построения траекторий, всюду плотно покрывающих область определения ф-ции, и минимизации вдоль этих траекторий.
Для решения спец. классов многоэкстремальных задач используются методы программирования динамического.
В наст, время создаются оптим. алгоритмы минимизации ф-ций разных классов. Пусть класс ф-ций, определенных в кубе , и имеющих в частные производные до s-го порядка, удовлетворяющие условию Липшица с константой L. Любой алгоритм минимизации из , использующий информацию о значениях f и ее производных до порядка включительно не более чем в N точках эквивалентен (в смысле результата) некоторому алгоритму А получения последовательности итераций (1) для и аппроксимации искомого значения при помощи итоговой операции
где - некоторая вычислимая ф-ция. Введем следующие обозначения:
Алгоритм, для которого достигается оптимальным. Условия означают соответственно асимптотическую оптимальность и оптимальность по порядку алгоритма Можно показать, что
причем выбор , влияет лишь на константу в указанной оценке. В частном случае и имеем:
где миним. сеть в .
Другой подход к построению оптим. алгоритмов минимизации связан с обобщением идей последовательных статистических решений. Алгоритм минимизации рассматривается как управляемая последовательность опытов, каждый из которых дает тот или иной исход. На совокупности исходов определяется априорная вероятностная мера. После получения конкретного исхода очередного опыта происходит перераспределение вероятностей по ф-ле Байеса и выбирается следующий опыт или принимается окончательное решение. Алгоритмы отличаются друг от друга правилом, по которому выбирается следующий опыт, правилами остановки и выбора окончательного решения. Качество решения определяется ф-цией потерь, которая усредняется в соответствии с полученным на данном этапе вероятностным распределением. В этих терминах ставится задача выбора оптим. алгоритма как построения последовательного байесовского правила поиска решений. Такая постановка интересна тем, что в ее рамках можно учитывать статистические свойства класса решаемых задач, сопоставлять «средние» потери, связанныз с погрешностью решения, с затратами, связанными с уточнением решения. Лит.: Любич Ю. И., Майстровский Г. Д. Общая теория релаксационных процессов для выпуклых функционалов. «Успехи математических наук», 1970, т. 25, в. 1; Михалевич В. С. Последовательные алгоритмы оптимизации и их применение. «Кибернетика», 1965, N5 1-2; Иванов В. В. Об оптимальных алгоритмах минимизации функций некоторых классов. «Кибернетика», 1972, № 4; Уайлд Д. Дк. Методы поиска экстремума. Пер. с англ. М., 1967.
В. В. Иванов, В. С. Михалевич, Н. 3. Шор.