Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




Множество существенных импликант соответствует максимальным кубам образующим ядро покрытия.

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

 

КДНФÞСДНФÞ{ТДНФ}Þ{МДНФ}

 

При получении множества максимальных кубов целесообразно разделить множество нуль-кубов (К°(f)) на ряд подмножеств, отличающихся количеством единиц. В операцию склеивания в этом случае могут вступать только кубы, относящиеся к соседним подмножествам, то есть отличающиеся на единицу.

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

Определение ядра покрытия реализуется с помощью таблицы покрытий. Kаждая строка таблицы - максимальный куб (простая импликанта). Каждый столбец - существенная вершина булевой функции (безразличные наборы не включаются). Элементы этой таблицы отражают отношение покрытия, то есть на пересечении i-ой строки и j-ого столбца ставится некоторая отметка в том случае, если i-ый максимальный куб покрывает j-ую вершину .

 

Рисунок 5.2. Импликантная таблица

 

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

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

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

 

 


Поделиться:

Дата добавления: 2015-08-05; просмотров: 227; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты