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

Минимизация на основе использования законов алгебры логики

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

Для получения минимальной ФАЛ пользуются аксиомами и законами АЛ, которые позволяют упростить исходное выражение (приложение В).

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

Для упрощения второй функциииспользуют закон двойственности (правило де Моргана), распределительный закон, законы дополнительности и поглощения.

Минимизация при помощи карт Карно

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

Минимальные выражения могут быть получены как на основе ДНФ, так и на основе КНФ. Если требуется получить выражение на базе ДНФ, то в карте учитываются клетки с единицами, а если на основе КНФ, то – с нулями.

Правила объединения в контуры при минимизации для ДНФ:

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

2) во всех клетках контура должны быть только единицы;

3) число клеток в контуре должно быть кратным степени числа два (1, 2, 4, 8, 16, 32);

4) контуры могут накладываться друг на друга;

5) контуры, все клетки которых уже вошли в другие контуры, являются лишними;

6) для получения наиболее простой формулы надо выбирать контуры с максимально возможным числом клеток;

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

При составлении конъюнкций контуров для каждого контура рассматривается вхождение всех аргументов.

Если контур пересекает (захватывает) как прямое, так и инверсное значение аргумента, то этот аргумент в конъюнкцию не входит.

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

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

Рассмотрим некоторые примеры.

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

На карте Карно, представленной на рисунке 4.2, получено три контура.

Клетки карты, которые при ее условном «сворачивании» могут образовывать прямоугольные контуры с числом клеток кратным степени числа два, также могут объединяться в контуры. Примером такого объединения является контур под номером 3.

Упрощенная функция будет иметь три конъюнкции, соответственно числу контуров. При этом в конъюнкции для 1-го контура будет отсутствовать переменная х₃, в конъюнкции для 2-го контура – переменная х₂, а в конъюнкции для 3-го контура – переменная х₁. Получим упрощенную функцию
.

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

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

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

Правила объединения в контуры при минимизации для КНФ:

1) все нули должны быть заключены в прямоугольные контуры;

2) во всех клетках контура должны быть нули;

3) число клеток в контуре должно быть кратным степени числа два (1, 2, 4, 8 , 16, 32);

4) контуры могут накладываться друг на друга;

5) контуры, все клетки которых уже вошли в другие контуры, являются лишними;

6) для получения наиболее простой формулы надо выбирать контуры с максимально возможным числом клеток;

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

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

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

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

Рассмотрим пример на карте Карно для четырех переменных для той же функции, которая была представлена на рисунке 4.3. Выделение контуров с нулями представлено на рисунке 4.6. Для рассматриваемого рисунка получаем три контура с нулями, которым соответствуют три скобочные дизъюнкции , и . Объединив полученные скобки знаками конъюнкции, получаем формулу упрощенной ФАЛ на основе КНФ .

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

Наиболее часто карты Карно используются для упрощения ФАЛ от двух, трех и четырех переменных. Однако существует возможность использовать каты Карно для минимизации ФАЛ от пяти и шести аргументов.

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

В результате упрощения методом карт Карно может быть получена ТДНФ (трудно поддающаяся дальнейшему упрощению) либо окончательно минимальная форма ФАЛ.

Минимизация методом Квайна

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

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

Суть метода в следующем.

1 Осуществляется переход от канонической формы записи ФАЛ (СДНФ) к сокращенной на основе формулы склеивания

, (4.1)

где W – одинаковая часть выражения в обеих конъюнкциях формулы,

Х – переменная, которая в разных конъюнкциях имеет противоположные значения.

2 Выполняется переход от сокращенной формы ФАЛ к минимальной с применением формулы поглощения

, (4.2)

где Y – часть конъюнкции, которая в одной конъюнкции присутствует, а в другой отсутствует.

Рассмотрим упрощение ФАЛ методом Квайна на примере. Пусть ФАЛ задана табличным способом (таблица 4.1).

Запишем СДНФ функции, заданной ТИ. В формуле каждую конъюнкцию пронумеруем соответственно ее порядковому номеру в ТИ. Нумерация нужна для отслеживания попарного перебора всех конъюнкций на предмет применения правила склеивания.

На первом этапе, в полученной формуле, сравниваем попарно все конъюнкции (минтермы четвертого ранга) и применяем там, где это возможно, правило склеивания. Склеиванию могут подвергаться только те конъюнкции, которые различаются инверсией лишь одной переменной. Для рассматриваемой функции склеиваются соответственно 0 и 1, 0 и 4, 0 и 8, 1 и 9, 4 и 6, 6 и 7, 6 и 14, 7 и 15, 8 и 9, 14 и 15 конъюнкции. Склеенные минтермы четвертого ранга отмечаются номерами под каждым минтермом третьего ранга с целью отследить, все ли исходные конъюнкции подверглись склеиванию. После первой итерации склеивания получена сокращенная функция из минтермов третьего ранга.

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

Далее, если это возможно, к минтермам функции, имеющим одинаковый ранг, снова применяется правило склеивания. В полученной функции склеиванию подвергаются соответственно минтермы третьего ранга 0–1 и 8–9, 0–8 и 1–9, 6–7 и 14–15, 6–14 и 7–15. В результате образуются минтермы второго ранга. При этом минтермы 0–4 и 4–6 не подвергаются склеиванию с другими минтермами. Поэтому они присутствуют в сокращенной форме функции.

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

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

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

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

Ядро функции – это та сокращенная импликанта, которая единолично перекрывает какие-либо столбцы таблицы (т.е. в этих столбцах стоит только одна отметка).

Упрощенная функция может иметь несколько ядер или не иметь их вообще. Если функция имеет ядро(а), то оно(и) должно(ы) обязательно присутствовать в минимальной формуле. Если функция не имеет ядра, то условно за ядро принимается та сокращенная импликанта, которая является наиболее простой и одновременно перекрывает как можно больше столбцов исходных импликант функции.

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

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

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

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

Т а б л и ц а 4.2 – Таблица перекрытий

№ п/п	Упрощенные импликанты	Исходные импликанты
№ п/п	Упрощенные импликанты
1		V	V				V	V
2		V		V
3				V	V
4					V	V			V	V
Строка перекрытий		V	V	V	V	V	V	V	V	V
Примечания: 1 Овалом выделены те упрощенные импликанты, которые составляют ядро функции. 2 Сплошными линиями показаны направления переноса отметок поглощения в строку перекрытий от ядер функции. 3 Штриховой и штрихпунктирной линиями соответственно показаны направления переноса отметок перекрытия от первого и второго вариантов дополнений функции. 4 Отметки первого ядра показаны в таблице жирным и наклонным шрифтом, отметки второго ядра показаны жирным шрифтом, а отметки дополнений – обычным шрифтом.

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

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

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

Дата добавления: 2019-02-12; просмотров: 372; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 234 5 6 7 Следующая ⇒

Мы поможем в написании ваших работ!