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

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

• Ш Кратчайшая форма записи (цель - минимизировать ранг каждого терма);
• Ш Получение минимальной формы записи (цель - получение минимального числа символов для записи всей функции сразу).
• 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, также вычеркиваются).

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

Алгебры логики

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

Похожая информация.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис . 45.

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

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

Пример 4.1

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

Решение

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

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

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

Решение

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

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

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

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

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

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

Таблица 4.2

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

		X + Z + X-Z

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

Рис. 4.6.

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

Рис. 4.7.

на рис. 4.6

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

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

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

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

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

Рис. 4.8.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где А - элементарная конъюнкция.

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

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

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

Минимизация сложных логических выражений с помощью матрицы Карно

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

Матрицы Карно целесообразно использовать для минимизации ФАЛ на наборах из 2,3,4,5 и 6 переменных. Номера столбцов в матрицах Карно образуют младшие разряды, а номера строк - старшие разряды наборов. Номера клеток составляются из номеров строк и столбцов и соответствуют наборам переменных.

Рассмотрим матрицу Карно для функции алгебры логики на наборах из 4-х переменных (табл. 1).

Таблица 1. Матрица Карно

Столбцы и строки в этой матрице обозначены двоичными соседними числами: 00-0I-II-I0. Поэтому номера смежных по горизонтали и вертикали клеток, а также крайних в строках и столбцах клеток являются соседними числами, например:

клетки с номерами и;

клетки с номерами;

клетки с номерами;

клетки с номерами.

Для минимизации функции алгебры логики, заданной в совершенной дизъюнктивной нормальной форме, с помощью матрицы Карно необходимо: подготовить матрицу Карно, вписав в клетки, соответствующие обязательным конституентам, единицы, объединить клетки с единицами в «подкубы», записать минимизированную функции алгебры логики в дизъюнктивной нормальной форме.

В «подкубы» объединяются:

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

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

Пусть необходимо минимизировать следующую функцию алгебры логики:

Матрица Карно, заполненная в соответствии с этой формулой, может быть представлена в виде таблицы 2:

Таблица 2. Матрица Карно

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

Метод Квайна

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

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

по всем недостающим переменным x ik , ..., xim исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.

В результате выполнения склеивания получается конъюнкция n-1 ранга, а конъюнкции остаются в исходном выражении и участвуют в сравнении с другими членами СДНФ. Таким образом, удается снизить ранг термов.

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

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

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

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

f СДНФ = V (1,2,5,6,7)=x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3

1 2 3 4 5

Выполним операцию склеивания:

• 1 - 3 (x1 ) x2 x3 1
• 2 - 4 (x1 ) x2 x3 2
• 3 - 5 (x2 ) x1 x3 3
• 4 - 5 (x3 ) x1 x2 4

В результате выполнения первого шага склеивания получаем четыре новые конъюнкции, простых импликант не выявлено. Полученные конъюнкции более не склеиваются и образуют сокращенную ДНФ.

f сокр СДНФ =x2 x3 + x2 x3 + x1 x3 + x1 x2

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

Таблица 3. Импликантная таблица

	x 1 x2 x3	X 1 x2 x3	x 1 x2 x3	x 1 x2 x3	x 1 x2 x3

Простые импликанты являются обязательными так как только они покрывают конституэнтыи включаются в минимальное покрытие. Остается одна непокрытая конституэнта x1 x2 x3 которая может быть покрыта одной из двух оставшихся простых импликант. Это приводит к получению двух тупиковых форм.

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

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

справедливость которой легко доказать. Действительно,

Следовательно,

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

Рассмотрим пример. Пусть булева функция f задана произвольной ДНФ.

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

Первый и третий элемент исходной ДНФ допускают обобщенное склеивание как по переменной х 1 , так и по х2 . После склеивания по x1 имеем:

После склеивания по x 2 имеем:

Второй и третий элемент ДНФ допускают обобщенное склеивание по переменной х 2 . После склеивания получаем:

Выполнив последнее обобщенное склеивание, приходим к ДНФ:

После выполнения поглощений получаем:

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

Минимизация не полностью определенных ФАЛ

Если при синтезе логической схемы, реализующей некоторую ФАЛ n переменных, окажется, что некоторые наборы из общего числа 2n никогда не смогут появиться на входах схемы, то данная логическая функция не определена на этих наборах. Тогда 2n наборов переменных можно подразделить на три группы: наборы, на которых функция принимает единичное значение L, нулевое значение D и группа наборов, на которых функция не определена N (неопределенные наборы). ФАЛ, содержащая неопределенные наборы, называется неполностью или частично определенной. Неопределенные наборы могут быть использованы для улучшения качества минимизации. При этом неопределенные наборы (при минимизации, например, картами Вейча, Карно) могут участвовать в образовании контуров как с единичными, так и с нулевыми наборами. Это приводит к формированию более простой минимизированной логической функции.

Универсальным методом минимизации является использование законов и соотношений алгебры логики, которые позволяют проводить минимизацию ФАЛ при любом числе переменных.

Предыдущая статья: Чему равна скорость света Следующая статья: Углерод — характеристика элемента и химические свойства