Расчётно-табличный метод минимизации

Расчётно-табличный метод минимизации. Минимизация этим способом отличается от расчётной минимизации только методикой выявления лишних членов в сокращённой Д К НФ. Данный метод предложен американским ученым У.Квайном.

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

Итак, пусть требуется минимизировать функцию 1.5 , заданную в СДНФ fсднф x1x2x3 x1x2x3 x1x2x3 x1x2x3 1-й этап - не отличается по содержанию от 1-го этапа при расчетном методе. Поэтому сразу же запишем исходную функцию в сДНФ fcднф x1x3 x2x3 x1x2 2-й этап - для выявления возможных лишних членов в сД К НФ функции построим таблицу, входными величинами в которой будут конституенты - члены СД К НФ и импликанты имплиценты - члены сокращенной Д К НФ. Поэтому чаще всего такую таблицу называют конституентно-импликантной имплицентной матрицей применяются также названия таблица Квайна и таблица покрытий.

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

Импли- Конституенты канты x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x3 x2x3 x1x2 Процесс минимизации начинается с последовательного составления каждой импликанты со всеми конституентами. Если какая-либо импликанта является собственной частью некоторой конституенты, то в табличной клетке, соответствующей обоим членам, проставляется любой условный значок так, в табл.1.3 клетка перечеркивается крест-накрест. Таким образом, значки в каждой строке заполненной таблицы показывают, какие члены совершенной формы функции появятся при развертывании данной импликанты в семейство конституент.

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

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

Возвращаясь к рассматриваемому примеру см.табл.1.3 , констатирует. что в ядро функции входят импликанты x1x2 и x2x3. Следовательно, остается только проверить возможность вычеркивания импликанты x1x3. Ее вычеркивание не нарушает условия о наличии хотя бы одного покрытия каждой конституенты любой импликантой. Следовательно, импликанта x1x3 является лишней. Тупиковая дизъюнктивная нормальная форма исходной функции fтднф x1x2 x2x3 1.8 Сравнение показывает идентичность соотношений 1.8 и 1.8 , что и должно было получиться. 3-й этап - по своему содержанию не отличается от соответствующего этапа при расчетном методе, поэтому сразу запишем минимальную форму исходной функции fмф x1x2 x2 x3 1.5. Табличный метод минимизации При относительно небольшом числе переменных R6 весьма удобным и наглядным является графическое представление логических функций в виде так называемых карт минтермов.

Наиболее распространенной их формой являются карты Карно. На рис.1.2 показаны карты Карно для функций R 2, 3, 4 и 5. Рис.1.2 Карты Карно и расположение в них минтермов для функций двух а, трёх б, четырёх в и пяти г переменных.

Карта Карно содержит q 2R клеток, причем каждой клетке соответствует один из q минтермов. Для иллюстрации этого на рис. 1.2 a-в в клетках карт Карно записаны соответствующие им минтермы. Если требуется представить на карте Карно логическую функцию, заданную в виде СДНФ, то в клетках карты, соответствующих минтермам, входящим в СДНФ, ставятся 1. Остальные клетки остаются незаполненными или заполняются 0. Примеры графического представления функций, заданных в виде СДНФ, показаны на рис.1.3 a-в. Рис.1.3 Примеры графического представления логических функций с помощью карт Карно а F AB AB б F ABC ABC ABC ABC в F ABCD ABCD ABCD ABCD. Каждой клетке карты поставлен также в соответствии один из наборов логических переменных, который определяется номером столбца и строки, на пересечении которых расположена клетка.

Например на рис.1.3 в на пересечении столбца с номером АВ 01 и строки с номером CD 10 расположена клетка, соответствующая набору переменных ABCD 0110 минтерм ABCD . Благодаря этому удобно представлять на карте Карно функции, заданные таблицами истинности.

Если при i-м наборе переменных значение функции в таблице истинности F fi 1, то в соответствующей клетке карты Карно ставится 1 т.е. соответствующий минтерм mi входит в СДНФ функции. Если же F fi 0, то клетка оставляется пустой либо ставится 0 т.е. соответствующий минтерм не входит в СДНФ функции. Таким образом, между представлением функции в табличной таблица истинности, алгебраической в виде сДНФ и графической на карте Карно формах имеется однозначное соответствие.

Логическая функция F на карте Карно представляется совокупностью клеток, заполненных 1, инверсия функции F представляется совокупностью пустых клеток или заполненных 0 . На рис.1.3 a дано представление в виде карты Карно функции Исключающее ИЛИ F6 в соответствии с её таблицей истинности.

Её инверсия F6 F9 AB AB представляется на этой карте совокупностью пустых клеток. Для логических функций с числом переменных R6 карты Карно становятся громоздкими число клеток q64 и не удобными для практического применения. Поэтому использование карты Карно можно рекомендовать при числе переменных R6. Рассмотренные выше логические функции были определены, т.е. имели определённое значение fi 0 или fi 1, при всех возможных наборах логических переменных.

Такие логические функции называются полностью определёнными. Кроме них имеется большой класс функций, значение которых определено только для части логических наборов переменных. Такие функции называются частично определенными. Наборы переменных, для которых функция определена, называются рабочими, а для которых не определена - безразличными. Значения функции, соответствующие безразличным наборам, будем обозначать в таблицах истинности и на картах Карно знаком Х . На практике безразличными являются такие наборы значений логических переменных, которые при работе данного конкретного цифрового устройства никогда не реализуются.

Частично определённую функцию можно сделать полностью определенной доопределить, приписав безразличным наборам какие-либо значения функции fi 0 или 1. Обычно доопределение функции проводится таким образом, чтобы упростить её алгебраическое выражение и практическую реализацию. Логическую функцию большого числа переменных можно представить в виде композиции функций меньшего числа переменных F A,B,C N AF0 O,B,C N AF1 1,B,C N где А - выделяемая переменная, функции F0 0,B,C N и F1 1,B,C N получаются из функции F подстановкой значений А 0 и А 1. В качестве выделяемой может использоваться любая переменная.

Например F AB ACD DE A B DE A CD DE AF1 AF0, F AB ACD DE D AB AC D AB E DF1 DF0 Процесс выделения более простых составляющих функции называется декомпозицией. Полученные функции F0, F1 могут подвергаться дальнейшей декомпозиции.

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