Метод, предложенный Петриком, использует логическую формулу покрытия.

Рассмотрим принцип работы данного метода на примере, рассмотренном выше.

Покрытие всех столбцов метками подразумевает покрытие 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. Недоопределенные БФ и способы их задания.