Метод Квайна

Метод Квайна (1.3)

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

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

Определение: Непомеченные термы называются первичными импликантами.

Полученное логическое выражение  не всегда оказывается минимальным, поэтому исследуется возможность  дальнейшего упрощения.

Для этого:

1. Составляются таблицы, в строках которых пишутся найденные первичные импликанты, а в столбцах указываются термы первичной ФАЛ.

2. Клетки этой таблицы отмечаются  в том случае, если первичная  импликанта входит в состав  какого-нибудь первичного терма.

3. Задача упрощения сводится  к нахождению такого минимального  количества импликант, которые  покрывают все столбцы.

Алгоритм метода Квайна (шаги):

1. Нахождение первичных импликант.

 Исходные термы из ДНФ  записывают в столбик и склеиваю  сверху вниз. Непомеченные импликанты  переходят в функции на этом  шаге.

2. Расстановка меток избыточности.

 Составляем таблицу, в которой  строки – первичные импликанты, столбцы – исходные термы. Если некоторый min-терм содержит первичный импликант, то на пересечении строки и столбца ставим метку.

3. Нахождение существенных импликант.

  Если в каком-либо столбце  есть только одна метка, то  первичный импликант соответствующей строки является существенным.

4. Строка, содержащая существенный  импликант и соответствующие  столбцы вычеркиваются.

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

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

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

6. Далее результат  записывается в виде функции.

Пример:

Шаг 1.

Термы 4го ранга	Термы 3го ранга	Термы 2го ранга
* 1 * 3   * 4   * 1   * 2   * 2   * 3   * 4	* 1   * 2   * 2     * 1

 

Шаг 2.

	V			V
	V					V
			V	V
					V	V
					V			V
		V	V				V	V

 

Шаг 4 пропускаем.

Шаг 5.

Выбираем те min-термы, при записи которых, МДНФ функции минимальна.

Шаг 6.

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