A) элементтері болса 8 страница

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

Пример 2.5.4.

.

Первый вариант решения. Раздвоим 2-ой минтерм (аксиома 5), проведём компоновку полученного выражения и склеим выделенные скобками компоненты

Второй вариант решения. Раздвоим 4-ый минтерм. Проведём несколько иное выделение пар минтермов и склеим эти пары Имеют место две равносильные минимальные тупиковые формы и выбирать в качестве решения задачи минимизации можно любую.

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

Пример 2.5.5.

.

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

.

Далее, выбираются другие пары минтермов и производится их склеивание.

Раздваиваем 1-ый минтерм (аксиома 5). Производим компоновку минтермов с последующим склеиванием для получения окончательного результата

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

1. Функция, предназначенная для минимизации, преобразуется в двойственную ей функцию. Правило преобразования приведено в п.2.2.

2. Производится процедура минимизации функций.

3. Делается обратное преобразование двойственной формы результата, чтобы получить его искомый минимизированный оригинал.

Пример 2.5.6.

.

Находим двойственную функцию и минимизируем её.

По минимальной двойственной функции находим искомый оригинал.

Приведём ещё один пример минимизации функции, заданной в нормальной форме (НФ). На этом примере интересно проследить возможные пути минимизации и оценить их разнообразие.

Пример 2.5.7.

.

Первый вариант минимизации функции предполагает раскрытие скобок. С учётом аксиомы 8 и 9 получим

.

К подчёркнутым минтермам применим следствие закона поглощения (2.10).

.

К подчёркнутым минтермам применим закон без имени (2.26).

.

Затем, к подчёркнутым минтермам применим закон поглощения.

.

И, наконец, к подчёркнутым минтермам применим закон без имени

Результат первого варианта минимизации.

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

Согласно аксиомы 9, значение подчёркнутых минтермов равно «0». Аксиома 2 упрощает полученный результат.

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

Результат второго варианта минимизации.

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

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

2. Минимизация функции представленной в ДНФ иногда приводит не к минимальной тупиковой форме. Чтобы всё же получить минимальную тупиковую форму надо ДНФ преобразовать в СДНФ и вновь начать минимизацию, но уже минуя исходную ДНФ.

3. Минимизацию функций заданных в СКНФ (КНФ) рекомендуется преобразовывать в СДНФ (ДНФ). Пути преобразования могут быть разные. Это либо раскрытие скобок, либо преобразование в двойственную функцию (п. 2.2). Только надо не забывать, что результат минимизации, получающийся в двойственной форме, необходимо обратно обращать в оригинал.

4. С функциями, представленными к минимизации в НФ, следует поступать (смотри пример 2.4.7) в соответствии с рекомендациями пункта 3.

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

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

Дата добавления: 2014-11-09