Метод, предложенный Петриком, использует логическую формулу покрытия.
Рассмотрим принцип работы данного метода на примере, рассмотренном выше.
Покрытие всех столбцов метками подразумевает покрытие 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. Недоопределенные БФ и способы их задания.