Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2017-12-12 | 568 |
5.00
из
|
Заказать работу |
|
|
Рассмотрим принцип работы данного метода на примере, рассмотренном выше.
Покрытие всех столбцов метками подразумевает покрытие 1 - ого столбца И покрытие 2 - ого столбца И покрытие 3 - ого … И покрытие 5 - ого столбца.
Первый столбец покрывается меткой импликанты А. Обозначим это высказывание как А.
Второй столбец покрывается меткой импликанты А или меткой импликанты В. Обозначим это высказывание как (), то - есть А или В.
Третий столбец покрывается меткой импликанты В или С. Обозначим это высказывание как ().
Четвертый столбец покрывается меткой импликанты D.
Пятый столбец покрывается меткой импликанты C или D. Обозначим это высказывание как ().
В итоге, так как должны быть покрыты все столбцы (1 - ый И 2 - ой И 3 - ий И 4 - ый И 5 - ый), получаем выражение А и (А или В) и (В или С) и (С или D) и D, то - есть .
Если раскрыть все скобки и выполнить поглощения, то получим выражение следующего вида:
Это означает, что таблица покрывается импликантами А и В и D либо А и С и D.
Иначе говоря, БФ имеет две ТДНФ:
Поиск всех ТДНФ может быть слишком трудоемким для таблиц большой размерности.
В связи с этим используются методы поиска одной ТДНФ, извлекаемой из таблицы покрытий.
(Можно считать, что это приближенное решение задачи поиска MДНФ.)
Рассмотрим на примере один из таких методов.
Совокупность строк, входящих в любое покрытие, назовем ядром таблицы.
Конъюнкции, определяющие столбцы с одной меткой являются ядром, так как если их исключить из ТДНФ, то в исходной функции будут потеряны наборы, определяемые этими столбцами.
В нашем примере ядро и .
* | * | A | ||||
* | * | B | ||||
* | * | C | ||||
* | * | D |
Выделяя ядро, мы получаем часть МДНФ. Конъюнкции ядра, записываются, как принадлежащие строящейся ТДНФ, а столбцы с метками ядра вычеркиваются, как не требующие более покрытия.
|
«Поглощаемой строкой» называется строка, чьи метки есть в тех же столбцах, что и метки какой либо одной другой строке.
Рассмотрим пример.
* | * | Поглощаемая строка | |||||
* | * | * | Непоглощаемая строка | ||||
* | * | * | * |
Удалив из таблицы «поглощаемую строку», мы не потеряем возможность найти одно из простейших покрытий.
Вернемся к нашему примеру.
После выделения ядра в таблице остается один столбец.
* | B | |
* | C |
Конъюнкцию можно удалить, как поглощаемую. При этом остается только одна строка . Но можно и удалить конъюнкцию . Тогда остается . Выбор в таком случае остается за человеком.
Упорядочив эти правила, можно получить алгоритм поиска ТДНФ.
1. Выделить ядро, если оно есть, и удалить столбцы с метками ядра.
2. Удалить поглощаемые строки.
3. Если в п.2 выполнялось удаление, идти к п.1.
4. Удалить строку с минимумом меток, оставляя для покрытия строки с большим числом меток и идти к п.1.
Другой вариант для п.4.
4. - Выделить строку с максимумом меток, как принадлежащую строящейся тднф, и удалить столбцы с ее метками, после чего идти к п.2. (Этот вариант не гарантирует нахождения тднф).
1.2.6. Недоопределенные БФ и способы их задания.
|
|
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!