Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Основные определения. Минимизация функций алгебры логики




Минимизация функций алгебры логики

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

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

Пусть задана ДСНФ:

 

Преобразуем эту ДСНФ следующим образом. Добавим еще один конъюнктивный член х1х2х3. Это добавление не меняет данной функции, так как

 
 

Теперь преобразуем это выражение, используя сочетательное и распределительное свойства конъюнкции и дизъюнкции:

 

Используя свойство дизъюнкции = 1, получим:

 

Аналогично предыдущему делаем дальнейшие преобразования:

 

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

Определение 4. Конъюнкция называется элементарной, если в этой конъюнкции каждое переменное встречается не более одного раза.

Определение 5. Рангом элементарной конъюнкции называется число букв, образующих эту конъюнкцию.

Определение 6. Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

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

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

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

Определение 9. Дизъюнктивная нормальная форма, имеющая наименьшую длину по сравнению со всеми другими ДНФ, эквивалентными данной функции, называется кратчайшей ДНФ (КДНФ).

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

Определения, аналогичные определениям 4—10, можно дать и для случая конъюнктивных нормальных форм. В дальнейшем ограничимся рассмотрением класса дизъюнктивных нормальных форм. При необходимости читатель сам может повторить все нижеследующие утверждения для случая конъюнктивных нормальных форм.

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

(1.52)

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




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


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


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



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.