A) Метод Квайна (оптимален для функций с большим количеством переменных)

Целиком и полностью основан на операции «Склейка». Заключается в последовательном полном переборе всех термов и их потомков на предмет возможности данной операции.

Пример:

Составим таблицу. В первую колонку перепишем все термы. Перебираем их все попарно, проверяем возможность операции «Склейка». Во вторую колонку выписываем результаты операции «Склейка», помечаем символами * те термы, которые образовали "потомков":

Больше нет

Повторяем эту операцию для последующих столбцов, пока не получим набор, не подлежащий дальнейшей «Склейке». Термы, не помеченные символом * (не имеющие "потомков") - претенденты для конечного решения. Из них надо выбрать такой набор, чтобы он покрывал все "родительские" термы (те, что были заданы в условии). Для этого построим таблицу наследования:

					*
							*
		*						*
			*	*
	*	*	*			*

Далее, выбираем незаменимые термы (столбцы с единственной меткой). Эти элементы обязательно должны присутствовать в ответе: 5,7,12,13,15. Т.е. в первой части ответа уже обязательно будет фрагмент конечного решения

					(*)
							(*)
		*						(*)
			*	(*)
	(*)	*	*			(*)

Вычеркиваем для каждого столбец и строку, на пересечении которых находится эта единственная метка. Не забываем и про те столбцы, которые ”уходят” вместе с ”незаменимыми” (т.е. в исключаемых строках учитываем все метки, не только единственные в столбце – они-то и уносят дополнительные столбцы). Размерность таблицы уменьшается.

В нашем случае таблица уничтожилась полностью! Но если этого не произошло, необходимо выполнить следующие действия:

Если после преобразований могут появиться пустые строки - также удаляем их. Если есть одинаковые столбцы - удаляем лишние копии, оставляя только один экземпляр. Т.е. всеми способами сокращаем таблицу. Пример несократившейся таблицы:

	VII	VIII	IX	X
I
II	*		*
III	*	*		*
IV		*	*	*

	VII	VIII	IX	X
I
II	*		*
III	*	*		*
IV		*	*	*

Опять ищем незаменимые термы (если находим - повторяем те же действия). Если незамени-мых термов нет, а таблица еще не вся сократилась - получена неоднозначная ситуация.

	VII	VIII	IX
II	*		*
III	*	*
IV		*	*

Выписываем ВСЕ возможные варианты из оставшихся элементов (так, чтобы были закрыты все столбцы). Среди этих вариантов и следует выбрать наиболее приемлемое. Эта вариабельность и является второй частью ответа:

Ответ для нашего примера:

Примечание: для успешной минимизации ДНФ должна быть совершенного вида. В противном случае необходимо провести операцию, обратную СКЛЕЙКе – ”расклеить” все термы до высшего порядка.