1.2.4. Построение сднф по произвольной днф.

БФ часто задают не в виде ДСНФ, а в виде произвольной ДНФ. От произвольной ДНФ можно перейти к ДСНФ, а по ней строить СДНФ. Но это нерационально.

Метод Блека-Порецкого построения СДНФ по произвольной ДНФ.

Данный метод основывается на использовании операции обобщеного склеивания

В справедливости этого равенства легко убедиться, построив таблицы функций для левого и правого выражения.

Рассмотрим алгоритм работы данного метода.

1. В ДНФ производятся все возможные преобразования вида:

Полученная днф обозначается D₁.

2. К днф D₁ применяются те же действия для получения D₂.

3. Далее аналогично получаются D₃ ,D₄,…, до тех пор, пока новые ДНФ отличаются от предыдущих.

В результате, после осуществления всех поглощений вида = А, будет получена СДНФ.

Рассмотрим пример.

D₃ не получаем, так как D₂ равно D₁.

В ДНФ D₂ конъюнкция XYW поглощается конъюнкцией XW и, таким образом получается СДНФ следующего вида: .

1.2.5. Получение тднф с помощью таблиц покрытий.

После того, как построена СДНФ (набор всех простых импликант БФ), можно получить любую ТДНФ БФ. Строить ТДНФ удобно по таблице покрытий (импликантной матрице).

Рассмотрим механизм построения таблицы.

- Столбцы отмечаются всеми наборами из М₁.

- Строки отмечаются всеми простыми импликантами К₁, К₂…К_i…

- На пересечении i-ой строки и j-ого столбца ставится метка, если К_i принимает значение 1 на наборе значений переменных Мj.

Рассмотрим пример формирования таблицы покрытий.

Пусть функция от трех переменных F(XYZ) с М₁ = (000,001,011,110,111) меет СДНФ .

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

	000	001	011	110	111
	*	*				A
		*	*			B
			*		*	C
				*	*	D

ТДНФ БФ будет соответствовать набор конъюнкций, имеющий метки во всех столбцах и не допускающая удаления ни одной конъюнкции.

Из таблицы видно, что ТДНФ образуют конъюнкции (строки А, В, С) или (строки А, С, D).

Для поиска всех ТДНФ необходимо применять регулярные методы.

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

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

Покрытие всех столбцов метками подразумевает покрытие 1-ого столбца И покрытие 2-ого столбца И покрытие 3-ого … И покрытие 5-ого столбца.

Первый столбец покрывается меткой импликанты А. Обозначим это высказывание как А.

Второй столбец покрывается меткой импликанты А или меткой импликанты В. Обозначим это высказывание как ( ), то-есть А или В.

Третий столбец покрывается меткой импликанты В или С. Обозначим это высказывание как ( ).

Четвертый столбец покрывается меткой импликанты D.

Пятый столбец покрывается меткой импликанты C или D. Обозначим это высказывание как ( ).

В итоге, так как должны быть покрыты все столбцы (1-ый И 2-ой И 3-ий И 4-ый И 5-ый), получаем выражение Аи(А или В) и (В или С) и (С или D) и D, то-есть .

Если раскрыть все скобки и выполнить поглощения, то получим выражение следующего вида:

Это означает, что таблица покрывается импликантами А и В и D либо А и С и D.

Иначе говоря, БФ имеет две ТДНФ:

Поиск всех ТДНФ может быть слишком трудоемким для таблиц большой размерности.

В связи с этим используются методы поиска одной ТДНФ, извлекаемой из таблицы покрытий.

(Можно считать, что это приближенное решение задачи поиска MДНФ.)

Рассмотрим на примере один из таких методов.

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

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

В нашем примере ядро и .

	000	001	011	110	111
	*	*				A
		*	*			B
			*		*	C
				*	*	D

Выделяя ядро, мы получаем часть МДНФ. Конъюнкции ядра, записываются, как принадлежащие строящейся ТДНФ, а столбцы с метками ядра вычеркиваются, как не требующие более покрытия.

«Поглощаемой строкой» называется строка, чьи метки есть в тех же столбцах, что и метки какой либо одной другой строке.

Рассмотрим пример.

*		*					Поглощаемая строка
*		*	*				Непоглощаемая строка
*		*		*	*

Удалив из таблицы «поглощаемую строку», мы не потеряем возможность найти одно из простейших покрытий.

Вернемся к нашему примеру.

После выделения ядра в таблице остается один столбец.

	011
	*	B
	*	C

Конъюнкцию можно удалить, как поглощаемую. При этом остается только одна строка . Но можно и удалить конъюнкцию . Тогда остается . Выбор в таком случае остается за человеком.

Упорядочив эти правила, можно получить алгоритм поиска ТДНФ.

1. Выделить ядро, если оно есть, и удалить столбцы с метками ядра.

2. Удалить поглощаемые строки.

3. Если в п.2 выполнялось удаление, идти к п.1.

4. Удалить строку с минимумом меток, оставляя для покрытия строки с большим числом меток и идти к п.1.

Другой вариант для п.4.

4. - Выделить строку с максимумом меток, как принадлежащую строящейся тднф, и удалить столбцы с ее метками, после чего идти к п.2. (Этот вариант не гарантирует нахождения тднф).