выш мат. Алексеев-В.В.-Алгебра-логики. Инистерство образования и науки российской федерации
 Скачать 6.59 Mb.
|
|
Глава 2 Минимизация ФАЛ Минимальная форма представления ФАЛ есть такая форма представления, которая содержит минимальное количество термов и переменных в термах. Минимальная форма представления ФАЛ не допускает никаких упрощений. Пусть задана СНДФ: ; Т.к. xx=x, то . Теперь преобразуем это выражение, используя распределительный и сочетательный законы для конъюнкции и дизъюнкции, и используя также аксиому . Получаем: = = == =. Как видно, результат преобразований позволил существенно упростить заданную ФАЛ. Определение. Конъюнкция называется элементарной, если в этой конъюнкции каждая переменная встречается не более одного раза. Определение. Дизъюнкция элементарных конъюнкций называется дизьюнктивной нормальной формой (ДНФ или НДФ). Определение. Длиной ДНФ называется число элементарных конъюнкций, образующих эту ДНФ. Определение. Дизъюнктивная нормальная форма, имеющая наименьшую длину по сравнению со всеми другими ДНФ, эквивалентными данной функции, называется кратчайшей ДНФ 2.1 Числовое и геометрическое представление ФАЛ. Для упрощения записи ФАЛ вместо полного перечисления термов используют номера наборов, для которых функция принимает единичное значение. Например, функция, заданная в таблице 1.5.1 может быть задана как . Это значит, что данная функция принимает значение логической единицы на наборах, номера которых равны 1, 2, 4, 6, 11, 13, 14. Такую форму записи называют числовой или числовой формой представления ФАЛ. Функцию двух переменных можно интерпретировать как некоторую плоскость, заданную в системе координат -. Отложив на осях единичные отрезки, получим квадрат, вершины которого соответствуют комбинациям логических переменных и . Это проиллюстрировано на рис.2.1. Рис. 2.1 Из такого геометрического представления функций двух переменных следует: две вершины, принадлежащие одному и тому же ребру и называемые соседними, “склеиваются” по переменной, меняющейся вдоль этого ребра. Геометрическое представление для функций трех переменных можно выполнить в виде куба (рис. 2.2) Вполне очевидно, что ребра куба поглощают вершины. Грани куба поглощают свои ребра и, следовательно, вершины. Рис. 2.2 Функция четырех переменных представляется уже в виде “четырехмерного” куба, как это приведено на рис. 2.3. В геометрическом смысле каждый набор может рассматриваться как n-мерный вектор, определяющий точку n-мерного пространства. Координаты вершин куба должны быть указаны в порядке, соответствующем порядку перечисления переменных в записи функции. Отметив точками (крестиками или другими символами) вершины, в которых функция принимает значение, равное единице, получим геометрическое представление ФАЛ Рис. 2.3 Терм максимального ранга принято называть 0-кубом (точкой) и обозначать . Например, для Если два 0-куба из комплекса различаются только по одной переменной (координате), то они образуют 1-куб (отрезок) - . ={ 0 x 0}, где x - независимая переменная. Если два 1-куба имеют общую независимую компоненту и различаются только по одной координате, то они образуют 2-куб. () Таким образом, для построения одномерного единичного куба берут два 0-куба (точки) и соединяют отрезком прямой. Двумерный куб (грань) получается, если вершины двух 1-кубов соединить параллельными отрезками Трехмерный куб получается при соединении соответствующих вершин двух двумерных кубов отрезком единичной длины. Геометрическое представление используется при разработке методов минимизации с использованием минимизирующих карт. 2.2 Метод неопределенных коэффициентов Описываемый здесь метод может быть применим для минимизации ФАЛ от любого числа аргументов, однако для простоты изложения и большой наглядности его рассмотрение произведем на примере минимизации функции, зависящей от трех переменных. Представим в ДНФ. = , т.е. здесь представлены все возможные конъюктивные члены, которые могут входить в ДФ. Коэффициенты K с различными индексами являются неопределенными и подбираются так, чтобы получающаяся после этого дизъюнктивная форма была минимальной. {K=0,1}. Критерий минимальности - минимальное количество символов в записи ДНФ. При записи ДНФ пользуются следующими свойствами: если ; если хотя бы один член равен 1. Если теперь задавать всевозможные наборы значений аргументов , и приравнять после этого выражение ( отбрасывая нулевые конъюнкции) значению функции на выбранных наборах, то получим систему уравнений: Если =0, то все коэффициенты, входящие в данное уравнение равны 0, тогда и в остальных уравнениях системы надо вычеркнуть члены, содержащие нулевые коэффициенты, а из оставшихся уравнений, равных единице, найти коэффициенты, определяющие конъюнкцию наименьшего ранга в каждом из уравнений. На основании изложенного можно сформулировать алгоритм нахождения неопределенных коэффициентов: Выбрать очередную строку, в которой =0. Все коэффициенты этой строки приравнять нулю; Если все нулевые строки просмотрены, то перейти к п.3, если нет, то к п.1; Просмотреть строки, в которых =1, и вычеркнуть из них все коэффициенты, встречающиеся в строках, где =0; Переписать все модифицированные уравнения; Выбрать очередную строку =1 и вычеркнуть максимально возможное количество коэффициентов так, чтобы ранг остающихся членов был минимальным. Следует заметить, что метод неопределенных коэффициентов применим для дизъюнктивной формы и практически непригоден для конъюктивной формы. Пример. Минимизировать функцию: . Запишем данную функцию в дизъюнктивной форме: . Составим систему уравнений: Отсюда вытекает, что После вычеркивания нулевых коэффициентов уравнения принимаю вид: И вполне очевидно, что из этих уравнений следует: И тогда получаем: . 2.3 Метод Квайна При минимизации по методу Квайна предполагается, что минимизируемая ФАЛ задана в СНДФ. Сам метод Квайна предполагает последовательное выполнение следующих этапов: 1.Нахождение первичных импликант. Импликанта функции - некоторая логическая функция, обращаемая в нуль при наборе переменных, на которых сама функция также равна нулю. Первичная импликанта функции - импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой. Все минтермы (минитермы) данной функции сравнивают между собой попарно. Если минтермы и таковы, что они имеют вид и , то выписывается конъюнкция f (), являющаяся минтермом (n-1)-го ранга. Минтермы n-го ранга, для которых произошло склеивание, отмечаются. После построения минтермов (n-1)-го ранга вновь сравнивают их попарно, выписывают минтермы (n-2)-го ранга и отмечают минтермы (n-1)-го ранга, подвергшиеся склеиванию, и т.д. Процесс заканчивается, когда минтермы полученного ранга уже не склеиваются между собой. Все отмеченные минтермы называются первичными или простыми импликантами. Пример. Минимизировать методом Квайна ФАЛ: . Запишем данную функцию в СНДФ: =
Итак, получаем импликанты наименьшего ранга . 2. Расстановка меток Составляется таблица, число меток которой равно числу полученных первичных импликант, а число столбцов совпадает с числом минтермов СНДФ. Если в некоторый минтерм СНДФ входит какая-либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка.
3. Нахождение существенных импликант Если в каком либо из столбцов имеется только одна метка, то первичная импликанта в соответствующей строке является существенной, т.к. без нее не будет получено все множество заданных минтермов. В данном примере это импликанты и . Столбцы, соответствующие существенным импликантам, из таблицы вычеркиваются. В данном примере это 1, 2, 3, 4, 7, и 8 столбцы. 4. Вычеркивание лишних столбцов. В результате вычеркивания столбцов ( 1,2,3,4,7,8) получается новая модифицированная таблица:
Если в таблице есть два столбца, в которых имеются метки в одинаковых строках, то один из них вычеркивается. Покрытие оставшегося столбца будет осуществлять оставшийся минтерм. 5. Вычеркивание лишних первичных импликант. Если после отбрасывания некоторых столбцов в п.4 появляются строки, в которых нет ни одной метки, то первичные импликанты, соответствующие этим строкам исключаются из дальнейшего рассмотрения, т.к. они не покрывают оставшиеся в рассмотрении минтермы. (-исключаются) 6. Выбор минимального покрытия. Выбирается такая совокупность первичных импликант (в последней таблице), которая включает метки во всех столбцах по крайней мере по одному разу. При нескольких возможных вариантах такого выбора предпочтение отдается варианту с минимальным суммарным числом символов в импликантах. В приведенном примере этому удовлетворяет один минтерм - . Минимальная форма заданной функции складывается из суммы существенных импликант (см. п. 3) и первичных импликант, покрывающих оставшиеся минтермы (п. 6). 2.4 Метод Квайна - Мак - Класки Метод Квайна имеет одно существенное неудобство - необходимость полного по парного сравнения на этапе нахождения простых импликант. С ростом числа минтермов увеличивается число этих сравнений и при достаточно большом числе минтермов применение метода Квайна является затруднительным. В 1956 году Мак - Класки предложил модернизацию первого этапа метода Квайна, дающую существенное уменьшение числа сравнений минтермов. Идея Мак - Класки заключается в следующем: Если записать минтермы в виде их двоичных номеров, то все номера можно разбить по числу единиц в этих номерах на пересекающиеся группы. При этом в i-ю группу войдут все номера, имеющие в своей двоичной записи ровно i единиц. По парное сравнение можно производить только между соседними по номеру группами, так как только эти группы отличаются для входящих в них минтермов в одном разряде. При образовании минтермов с рангом выше нулевого в разряды, соответствующие исключенным переменным пишется знак Х. Такая модификация на практике чрезвычайно удобна, так как позволяет избежать выписывания громоздких минтермов и импликант, заменяя эту процедуру выписыванием их двоичных номеров. Пример. Минимизировать методом Квайна - Мак - Класки ФАЛ: = Записываем эти минтермы по группам в двоичном коде:
Сравнивая соседние группы получаем минтермы 3-го ранга:
Теперь находим минтермы 2-го ранга:
Составляется таблица меток:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||