Минимизация методом Квайна

Минимизация логических выражений

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

- минимизация методом Квайна;

- минимизация методом с использованием диаграмм Вейча (или карт Карно).

Метод минимизации Квайна предполагает следующее.

В качестве исходной формы представления логического выражения используется СДНФ.

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

В результате таких действий будет получена дизъюнкция простых конъюнкций (т.е. конъюнкций, логическими сомножителями которой являются переменные или их отрицания). Далее для получения СДНФ, у которой используемые простые конъюнкции включают все переменные или их отрицания, в конъюнкции, где представлены не все переменные, вводят недостающие переменные x_i за счет умножения расширяемой конъюнкции на

и раскрытия скобок.

Метод Квайна выполняется два этапа.

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

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

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

Пример

Найти методом Квайна минимальное выражение для функции y:

Решение

1-й этап.

у =	_ _ 1 x1 x2 x3 x4 +	2 _ _ x1 x2 x3 x4 +	_ 3 _ x1 x2 x3 x4 +	_ 4 _ x1 x2 x3 x4 +	_ 5 _ _ x1 x2 x3 x4 +
+	6 _ x1 x2 x3 x4 +	_ 7 _ x1 x2 x3 x4 +	8 _ x1 x2 x3 x4 +	9 _ x1 x2 x3 x4 +	_ _ 10 _ x1 x2 x3 x4 =

(проставлены номера конъюнкций; подчеркнуты те конъюнкции, которые склеивались на первом шаге)

=	_ 1 x2 x3 x4 + 1 -9	_ _ 2 x1 x2 x3 + 1 -10	3 _ _ x2 x3 x4 + 2 -5	4 _ x1 x2 x4 + 2 -8	_ 5 _ x1 x2 x3 + 3 -5	_6 x2x3x4 + 3-6
+	_ 7 _ x1x2x4 + 4 -5	8 _ x2x3x4 + 4 -8	_ 9 _ x1 x3 x4 + 4 -10	10 _ x1 x3 x4 + 7 -8	_ 11 x1 x2 x3 + 7 -9	_12 _ x2 x3 x4 = 7 -10

(выражение представлено только результатами склеивания; если бы в исходном выражении были бы не подчеркнутые конъюнкции, то они должны были бы через знак «+» дописаны к сумме результатов склеивания; в скобка под конъюнкцией (i-j) указывают, что данная конъюнкция является результатом склеивания i-й и j-й конъюнкций исходного выражения)

=

_1 x2 x3+ 1-12

_2 x2 x3+ 2-11

3 _ x2 x3+ 3-6

4 _ x2 x4+ 3-8

5 _ x2 x4+ 4-7

6 _ x3 x4+ 8-12

7 _ x3 x4 + 9-10

_ 8 _ x1 x2 x3 =

(к результатам склеивания логически добавлена ни с чем не склеенный пятый член исходного выражения; несколько одинаковых конъюнкций представляются одной конъюнкцией)

=

_1 x2 x3+

2 _ x2 x3+

3 _ x2 x4+

4 _ _ 5 _ x3 x4 + x1 x2 x3 = yT - тупиковая форма

Выражение получено из предыдущего посредством удаления повторяющихся членов

Второй этап.

На основании исходного выражения и полученной тупиковой формы составляется и заполняется импликантная табл.2.2-3.

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

Строки таблицы помечены простыми импликантами полученной тупиковой формы.

. Таблица 2.2‑3

	_ _ x1x2x3x4	_ _ x1x2x3x4	_ _ x1x2x3x4	_ _ x1x2x3x4	_ _ _ x1x2x3x4	_ x1x2x3x4	_ ­_ x1x2x3x4	_ x1x2x3x4	_ x1x2x3x4	_ _ _ x1x2x3x4
_ x2x3	*						*		*	*
_ x2x3		*	*		*	*
_ x2x4		*		*	*			*
_ x3x4				*			*	*		*
_ _ x1x2x3			*		*

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

Анализируя покрытия простыми импликантами конституент единицы заданной функции, составляем её минимальное выражение:

ymin =

_1 x2 x3+

2 _ x2 x3+

3 _ x2x4.

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

- простая импликанта является единственной, покрывающей одну из колонок;

- если импликант вышеуказанного типа нет, то выбирается импликанта, покрывающая большее количество еще не покрытых колонок.

Последовательность включения простых импликант в приведенное минимальное выражение:

- единственная импликанта, покрывающая колонку 1, при этом из дальнейшего рассмотрения исключаются все колонки, покрываемые этой импликантой, т.е. колонки 1,7,9 10;

- покрывает максимальное число колонок, оставшихся для рассмотрения (колонки 2,3,5,6) - эти колонки из дальнейшего рассмотрения исключаются;

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

Дата добавления: 2014-01-07