Вычеркивание лишних столбцов.

В результате вычеркивания столбцов (1,2,3,4,7,8) получается новая модифицированная таблица:

		Первичн
		импл.-ты
			+
			+	+
				+

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

Вычеркивание лишних первичных импликант.

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

Выбор минимального покрытия.

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

Минимальная форма заданной функции складывается из суммы существенных импликант (см. п. 3) и первичных импликант, покрывающих оставшиеся минтермы (п. 6).

Метод Квайна - Мак - Класки

Метод Квайна имеет одно существенное неудобство - необходимость полного по парного сравнения на этапе нахождения простых импликант. С ростом числа минтермов увеличивается число этих сравнений и при достаточно большом числе минтермов применение метода Квайна является затруднительным. В 1956 году Мак - Класки предложил модернизацию первого этапа метода Квайна, дающую существенное уменьшение числа сравнений минтермов. Идея Мак - Класки заключается в следующем:

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

Пример. Минимизировать методом Квайна - Мак - Класки ФАЛ:

=

Записываем эти минтермы по группам в двоичном коде:

Сравнивая соседние группы получаем минтермы 3-го ранга:

Теперь находим минтермы 2-го ранга:

Составляется таблица меток:

Отсюда получаем:

.