История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Топ:
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2017-12-12 | 574 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!