Метод Квайна.

Метод Квайна позволяет преобразовать СДНФ в минимальную ДНФ.

Наример минимизируем функцию:

Производится переход к сокращённой форме перебором возможных комбинаций склеивания и поглощения. Если функции отличаются только одной переменной, то они записываются в правый столбик. Отличающийся элемент заменяется ” * ”.

Члены сокращенной формы называют простыми импликантами функции.

Сокращенная форма может содержать лишние члены, исключение которых из выражения функции не повлияет на значение функции. Поэтому далее строят импликантную матрицу:

Простые импликанты	Члены СДНФ
	x	x
	x		x
			x	x
				x	x
					x	x

Простые импликанты, которые не могут быть лишними и не могут быть исключены – составляют ядро. Входящие в ядро импликанты легко определяют по матрице: для каждого ядра есть хотя бы 1 столбец, перекрываемый только одной импликантой.
Для получения минимальной формы достаточно выбрать из импликант, не входящих в ядро, такое минимальное их количество с минимальным вхождением букв в каждую, которые обеспечивают перекрытие всех столбцов импликантной матрицы не перекрытых членами ядра.

Недостаток метода Квайна – необходимость полного попарного сравнения всех термов на этапе нахождения первичных импликант.

Дата добавления: 2015-07-16