Студопедия

КАТЕГОРИИ:


Загрузка...

Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод минимизирующих карт




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

Пусть функция f(x1, x2, x3) задана в виде ДСНФ. Тогда составим следующую таблицу 1.11:

Таблица 1.11 -

Эта таблица представляет более компактную запись системы уравнений (1.54). Только вместо коэффициентов К в соответствующие клетки таблицы записаны сами конъюнкции.

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

Пусть, например, в ДСНФ функции не входит конъюнкция x2 x3. Покажем тогда, что в МДНФ не может входить член х3 (аналогично для других конъюнкций строки)

 

Таким образом, если бы в МДНФ входил член c х3 то в ДСНФ входил бы член х2 х3, что противоречит условию.

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

а) все строки таблицы, которые соответствуют конъюнкциям правого столбца, отсутствующим в ДСНФ рассматриваемой функции, вычеркиваются;

б) в каждом столбце в оставшихся после этого строках вычеркиваются все элементы, попавшие в вычеркнутые ранее строки;

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

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

Рисунок 1.8 – Минимизирующая карта

Пункт «в» этих правил показывает, что построение по ДСНФ соответствующей МДНФ есть процесс неоднозначный, так как выбор минимальных конъюнкций в строках не детерминирован. Однако все получаемые результаты будут «одинаково минимальны».

Рассмотрим пример минимизации функции, ДСНФ которой имеет вид:



 

Строим для этой функции минимизирующую карту (рисунок 1.8).

По вышеприведенным правилам получаем следующую минимальную дизъюнктивную нормальную форму:

 

Рассмотрим еще один пример минимизации функции:

 
 
 
 
 
 
 
 
 
                 

Рисунок 1.9 – Минимизирующая карта

Минимизирующая карта для этой функции имеет следующий вид (рисунок 1.9).

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

 
и  
 

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





Дата добавления: 2014-11-18; Просмотров: 386; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 107.22.109.65
Генерация страницы за: 0.106 сек.